dsa hw0 1
unknown
c_cpp
a year ago
5.5 kB
10
Indexable
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> #define ADD 1 #define REMOVE 2 #define MOVE 3 #define MERGE 4 #define MAX_NUM_DECKS 100000 // hello typedef struct card { int value; struct card* next; struct card* prev; } Card; typedef struct { int numCards; Card* btm; Card* top; } Deck; Card* newCard(int card, Card* prev, Card* next); void printDeck(Deck decks[], int deckIdx); void initDecks(int numDecks, Deck decks[]); void add(Deck decks[], int targetDeck, int card); void removeCard(Deck decks[], int targetDeck); void move(Deck decks[], int srcDeck, int destDeck); void merge(Deck decks[], int deck1, int deck2); int main() { int numDecks, numOperations; scanf("%d%d", &numDecks, &numOperations); Deck decks[MAX_NUM_DECKS]; initDecks(numDecks, decks); for (int i = 0; i < numOperations; i++) { int opType; scanf("%d", &opType); if (opType == ADD) { int targetDeck, card; scanf("%d%d", &targetDeck, &card); add(decks, targetDeck - 1, card); } else if (opType == REMOVE) { int targetDeck; scanf("%d", &targetDeck); removeCard(decks, targetDeck - 1); } else if (opType == MOVE) { int srcDeck, destDeck; scanf("%d%d", &srcDeck, &destDeck); move(decks, srcDeck - 1, destDeck - 1); } else // opType == MERGE { int srcDeck, destDeck; scanf("%d%d", &srcDeck, &destDeck); merge(decks, srcDeck - 1, destDeck - 1); } } for (int i = 0; i < numDecks; i++) { printf("%d ", decks[i].numCards); printDeck(decks, i); } } Card* newCard(int card, Card* prev, Card* next) { Card* newCard = (Card*)malloc(sizeof(Card)); newCard->value = card; newCard->prev = prev; newCard->next = next; return newCard; } void printDeck(Deck decks[], int deckIdx) { Card* ptr = decks[deckIdx].top; for (int i = 0; i < decks[deckIdx].numCards; i++) { /*de printf("\n"); printf("%d %d %d \n", decks[0].numCards, decks[1].numCards, decks[2].numCards); printf("failed, deck: %d, card: %d\n", deckIdx + 1, i); */ assert(ptr != NULL); printf("%d ", ptr->value); ptr = ptr->prev; } printf("\n"); } void initDecks(int numDecks, Deck decks[]) { for (int i = 0; i < numDecks; i++) decks[i].numCards = 0; } void add(Deck decks[], int targetDeck, int card) { decks[targetDeck].numCards++; if (decks[targetDeck].numCards == 1) { decks[targetDeck].top = newCard(card, NULL, NULL); decks[targetDeck].btm = decks[targetDeck].top; return; } // the deck is not empty decks[targetDeck].top->next = newCard(card, decks[targetDeck].top, NULL); decks[targetDeck].top = decks[targetDeck].top->next; } void removeCard(Deck decks[], int targetDeck) { if (decks[targetDeck].numCards == 0) return; decks[targetDeck].top = decks[targetDeck].top->prev; if (decks[targetDeck].top != NULL) decks[targetDeck].top->next = NULL; decks[targetDeck].numCards--; // assert(decks[targetDeck].numCards >= 0); return; } void move(Deck decks[], int srcDeck, int destDeck) { if (decks[srcDeck].numCards == 0) return; if (decks[destDeck].numCards == 0) { decks[destDeck] = decks[srcDeck]; decks[srcDeck].numCards = 0; return; } decks[destDeck].numCards += decks[srcDeck].numCards; decks[srcDeck].numCards = 0; // both destDeck and srcDeck aren not empty decks[destDeck].top->next = decks[srcDeck].btm; decks[srcDeck].btm->prev = decks[destDeck].top; decks[destDeck].top = decks[srcDeck].top; return; } void merge(Deck decks[], int deck1, int deck2) { if (decks[deck1].numCards == 0) return; if (decks[deck2].numCards == 0) { decks[deck2] = decks[deck1]; decks[deck1].numCards = 0; return; } Deck merged; Card* ptr1 = decks[deck1].top; Card* ptr2 = decks[deck2].top; merged.top = ptr1; merged.btm = ptr1; ptr1 = ptr1->prev; while (ptr1 != NULL && ptr2 != NULL) { Card* tempPrev1 = ptr1->prev; Card* tempPrev2 = ptr2->prev; merged.btm->prev = ptr2; ptr2->next = merged.btm; merged.btm = merged.btm->prev; merged.btm->prev = ptr1; ptr1->next = merged.btm; merged.btm = merged.btm->prev; ptr1 = tempPrev1; ptr2 = tempPrev2; } if (ptr1 == NULL && ptr2 != NULL) { merged.btm->prev = ptr2; ptr2->next = merged.btm; merged.btm = decks[deck2].btm; } else if (ptr1 != NULL && ptr2 == NULL) { merged.btm->prev = ptr1; ptr1->next = merged.btm; merged.btm = decks[deck1].btm; } merged.numCards = decks[deck1].numCards + decks[deck2].numCards; decks[deck1].numCards = 0; decks[deck2] = merged; return; }
Editor is loading...
Leave a Comment