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

1
#include
2
#include
3
#include
4
#include
5
using namespace std;
6

7
/*-------------------- 定義環狀串列結構 --------------------*/
8
// 定義節點結構
9
class Node{
10
    public:
11
        char sex;
12
        Node *next;
13
        // Constructor
14
        Node(char c){ sex = c; next = NULL; }
15
};
16

17
// 定義串列結構
18
class CircularList{
19
    public:
20
        Node *rear;
21

22
        CircularList(){ rear = NULL; }
23

24
        // 清空節點方法
25
        void clearNode(){
26
            if(rear != NULL){
27
                Node *ptr, *lnk;                //ptr是存取的指針，從頭（rear->next）開始存取
28
                for(ptr = rear->next; ptr != rear; ptr = lnk){
29
                    lnk = ptr->next;            //lnk暫存下個節點的指針
30
                    delete ptr;                 //刪除目前節點
31
                }
32
                delete ptr;                     //刪除最後一個節點
33
                rear = NULL;                    //重新初始化串列
34
            }
35
        }
36
        // 加入新節點
37
        void addNode(char c){
38
            Node *newp = new Node(c);
39
            if(rear == NULL)            //若環狀串列為空，則自己連到自己
40
                rear = newp->next = newp;
41
            else {                      //否則
42
                newp->next = rear->next;    //新節點的下個節點連到頭節點
43
                rear = rear->next = newp;   //原本的尾的下一個連到新節點，再把尾改成新節點
44
            }
45
        }
46
        // 移除節點
47
        void deleteNode(Node *target){
48
            Node *prev = rear;
49
            while(prev->next != target)     //從頭節點（rear->next）開始找
50
                prev = prev->next;
51

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

56
            delete target;
57
        }
58
};
59

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

62
/*-------------------- 特別數驗證 --------------------*/
63
bool isTrue(int num, int ALL_MALE){
64
    int count = 0;                          //已登船的人數
65
    Node *ptr = circularList.rear, *tbk;    //ptr == 第一次被計算的人之前的人 == 被允許登船的人之前的人
66
    while(count != ALL_MALE) {              //【若 NUMBERS_OF_ON_BOARD != ALL_MALE】
67
        /*--- Counting ---*/
68
        for(int i = 1; i next;                                //算人數移動PTR.
69

70
        /*--- Checking ---*/
71
        tbk = ptr->next;                            //tbk = 第N個人 (ptr->next)
72
        if(tbk->sex == 'O'){                        //【若第N個人 (tbk) 是男性】
73
            circularList.deleteNode(tbk);                   //刪除節點（該人被允許登船）
74
            count++;                                        //已登船的人數+1
75
        }else return false;                         //【否則，這不是個特別數】
76
    }
77
    return true;
78
}
79

80
/*-------------------- Data input --------------------*/
81
// 建立新的環狀鏈結
82
void createCircular(string members){
83
    for(int i = 0; i > *members;
84
}
85

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

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

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

101
    cout << "Number: " << specialNum << endl;
102
    system("pause");
103
    return 0;
104
}