[C/C++] 環狀鏈結：尋找特別數

#include <stdlib.h>
#include <iostream> 
#include <algorithm>
#include <string> 
using namespace std;

/*-------------------- 定義環狀串列結構 --------------------*/
// 定義節點結構
class Node{
    public:
        char sex;
        Node *next;
        // Constructor
        Node(char c){ sex = c; next = NULL; }
};

// 定義串列結構
class CircularList{
    public:
        Node *rear;
        
        CircularList(){ rear = NULL; }
        
        // 清空節點方法
        void clearNode(){
            if(rear != NULL){
                Node *ptr, *lnk;                //ptr是存取的指針，從頭（rear->next）開始存取
                for(ptr = rear->next; ptr != rear; ptr = lnk){
                    lnk = ptr->next;            //lnk暫存下個節點的指針
                    delete ptr;                 //刪除目前節點
                }
                delete ptr;                     //刪除最後一個節點
                rear = NULL;                    //重新初始化串列
            }
        }
        // 加入新節點
        void addNode(char c){
            Node *newp = new Node(c);
            if(rear == NULL)            //若環狀串列為空，則自己連到自己
                rear = newp->next = newp;
            else {                      //否則
                newp->next = rear->next;    //新節點的下個節點連到頭節點
                rear = rear->next = newp;   //原本的尾的下一個連到新節點，再把尾改成新節點
            }
        }
        // 移除節點
        void deleteNode(Node *target){
            Node *prev = rear;
            while(prev->next != target)     //從頭節點（rear->next）開始找
                prev = prev->next;

            prev->next = target->next;      //若在A->B->C中找到B，目前prev是A，target是B，將A的next重新指向C
            if(target == rear)              //若B是尾，
                rear = prev;                    //則將尾指定給A
            
            delete target;
        }
};

CircularList circularList;  //宣告並初始化環狀鏈結

/*-------------------- 特別數驗證 --------------------*/
bool isTrue(int num, int ALL_MALE){
    int count = 0;                          //已登船的人數
    Node *ptr = circularList.rear, *tbk;    //ptr == 第一次被計算的人之前的人 == 被允許登船的人之前的人
    while(count != ALL_MALE) {              //【若 NUMBERS_OF_ON_BOARD != ALL_MALE】
        /*--- Counting ---*/
        for(int i = 1; i < num; i++)                //只找N-1次，因為只有N個人可以登船，所以PTR是N-1位.
            ptr = ptr->next;                                //算人數移動PTR.
        
        /*--- Checking ---*/
        tbk = ptr->next;                            //tbk = 第N個人 (ptr->next)
        if(tbk->sex == 'O'){                        //【若第N個人 (tbk) 是男性】
            circularList.deleteNode(tbk);                   //刪除節點（該人被允許登船）
            count++;                                        //已登船的人數+1
        }else return false;                         //【否則，這不是個特別數】
    }
    return true;
}

/*-------------------- Data input --------------------*/
// 建立新的環狀鏈結
void createCircular(string members){
    for(int i = 0; i < members.size(); i++)
        circularList.addNode(members[i]);
}
// 輸入
void input(string prompt, string *members){
    cout << prompt;
    cin >> *members;
}

/*-------------------- Main Function --------------------*/
int main(void) {
    string MemberList;              //名單的清單
    int maleCount, specialNum = 0;  //男性數量及特別數

    input("請輸入男女生名單（O為男X為女）：", &MemberList);
    maleCount = count(MemberList.begin(), MemberList.end(), 'O');

    if(maleCount>0)
        do{
            specialNum++;                   //從1開始找特別數
            circularList.clearNode();       //清除環狀鏈結
            createCircular(MemberList);     //重建環狀鏈結
        }while(!isTrue(specialNum, maleCount));

    cout << "Number: " << specialNum << endl;
    system("pause");
    return 0; 
}

測試資料：

請輸入男女生名單（O為男X為女）：OXOOXOOOOXOO
Number: 54