C++範例程式 : 約瑟夫問題

這個題目是用來測試程式設計師對環狀單向鍊結串列操作是否熟悉. 建立環狀鍊結串列是本程式中簡單的任務, 重點放在如何將環狀鍊結串列成員正確的刪除並保持串列完整性.
程式碼如下 :


/* * Author : 2012 Cheng-Yi Chen * * Josephus Problem (Josephus Ring) * * */ #include using namespace std; #define CARDNUM 13 #define MAXSTEP 52 // Define card structure typedef struct _card * cardptr; typedef struct _card{ int cardId; cardptr next; }card; bool isLastCard(cardptr); cardptr insertCard(cardptr); cardptr deleteCard(cardptr,int); cardptr genCardList(cardptr); int getLastCard(cardptr,int); void showAllCard(cardptr); void printCard(int); // Purpose : Main program // Params : void // Return : 0 : normal execution int main() { // Define head pointer cardptr head = NULL; // Define how many step to delete card int skipNum = 1; int lastCardID; // User choice to continue/exit program char choice; do{ // Null card ring head = NULL; // Get how many step to delete card cout << "Delete card per ? card : "; cin >> skipNum; // Handle the max skipNum if(skipNum > MAXSTEP) { cout << "Can not handle step number more than " << MAXSTEP << endl; continue; } else if(skipNum <= 0) { cout << "Can not handle step number less than or equal 0" << endl; continue; } cout << endl; // Generate the card ring head = genCardList(head); cout << endl; // Show all cards of the ring one by one showAllCard(head); cout << endl; // Get the card ID of last card lastCardID = getLastCard(head,skipNum); // Output the last card ID cout << "The last card is "; printCard(lastCardID); cout << endl << endl; // Run again or exit cout << "Want to try again? (N/n to exit program) "; cin >> choice; }while(choice != 'N' && choice != 'n'); cout << "Bye! Program will exist now." << endl; return 0; } // Purpose : To see if the ring has only one card // Params : Head pointer // Return : True : has only one card; False : has two or more cards bool isLastCard(cardptr head) { if(head->next == head) return true; else return false; } // Purpose : Insert one card to the head end of card ring, Assign the card ID // Params : Old head pointer, Card ID // Return : New head pointer cardptr insertCard(cardptr head, int cid) { // Temp pointer to last card cardptr cur; // Generate new card and assign cardId cardptr newCard = new card; newCard->cardId = cid; // Generate circular linked list // Condition : see if head points to empty if(head) { // Card list is not empty, then insert newCard to the head end newCard->next = head; // Search the last card(the next pointer of card that points to card in head end) cur = head; while(cur->next != head) { cur = cur->next; } // Let the next pointer of last card points to newCard cur->next = newCard; } else { // Card list is empty, then let next pointer points to himself newCard->next = newCard; } // Move head pointer to newCard head = newCard; return head; } // Purpose : Remove the head card and return the next head pointer // Params : Old head pointer, How many step to remove a card // Return : Next head pointer cardptr deleteCard(cardptr head, int step) { cardptr lastCard, delCard = head; // Handle empty ring for safety if(!head) return NULL; // Hanld zero step for safety if(step <= 0) return head; // If not single card ring then remove one card if(!isLastCard(head)) { // Find lastCard lastCard = head; while(1) { lastCard = lastCard->next; if(lastCard->next == head) break; } // Remove delCard (1) : Move head pointer to next one and // Link lastCard to new head head = head->next; lastCard->next = head; // For Debug //cout << "Delete"; //printCard(delCard->cardId); //cout << endl; // Remove delCard (2) : Remove delCard and finish the first step to next head delete delCard; step--; // Determin next head (next delete point) while(step) { head = head->next; step--; } } return head; } // Purpose : Generate the card ring // Params : Head pointer // Return : New head pointer cardptr genCardList(cardptr head) { int i; cout << "====== Generate Card List ==========" << endl; for(i = CARDNUM; i > 0; i--) { cout << "Card "; printCard(i); cout << " added" << endl; head = insertCard(head, i); } cout << "====================================" << endl; return head; } // Purpose : Get the last card of the ring // Params : Head pointer, How many step to remove a card // Return : The card ID of last card int getLastCard(cardptr head, int step) { while(!isLastCard(head)) { head = deleteCard(head,step); } return head->cardId; } // Purpose : Show all cards in the ring // Params : Head pointer // Return : Void void showAllCard(cardptr head) { cardptr cur = head; cout << "====== Show Card List ==============" << endl; while(1) { printCard(cur->cardId); cout << " "; cur = cur->next; if(cur == head) break; } cout << endl << "====================================" << endl; } // Purpose : Translate card ID to the face of playing cards // Params : Card ID // Return : Void void printCard(int cid) { switch(cid) { case 1: cout << "Ace"; break; case 11: cout << "Jack"; break; case 12: cout << "Queen"; break; case 13: cout << "King"; break; default: cout << cid; break; } }