C++_学习随笔_通过链表实现约瑟夫环

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int m, n,s;
 6 
 7 //共有n个人，数到第m个出局
 8 typedef struct Node
 9 {
10     int data;
11     struct Node* next;
12 }node, * linklist;
13 
14 void creatLinklist(linklist& L)
15 {
16     linklist p, q;
17 
18     L = new node();
19     L->next = NULL;
20     L->data = 1;
21     p = L;
22     for (int i = 0; i < n-1; i++) {
23         q = new node();
24         q->data = i + 2;
25         q->next = NULL;
26 
27         p->next = q;
28         p = q;
29     }
30     p->next = L;
31 }
32 
33 void outgame(linklist& L) {
34     linklist p, q;
35     p = L;
36     q = L->next;
37     for (int i = 0; i < s-1; i++) {
38         q = q->next;
39         p = p->next;
40     }
41     int cnt = 2;
42     while (p->data!=0) {
43         if (cnt==m&&q->data!=0) {
44             p->next = q->next;
45             cout << "出局，" << q->data<<endl;
46             q->data = 0;
47             q = q->next;
48             cnt = 1;//因为第一次报数算上自己，之后的报数从自己的下一个开始
49         }
50         else {
51             cnt++;
52             p = p->next;
53             q = q->next;
54         }
55     }
56 }
57 void show(linklist& L) {
58     for (int i = 0; i < n; i++) {
59         cout << "Address: " << &L[i] << "; Data:" << L[i].data << "; Next:" << L[i].next << endl;;
60     }
61 }
62 
63 int main() {
64     cout << "number of participant:" << endl;
65     cin >> n;
66     cout << "death number:" << endl;
67     cin >> m;
68     if (m == 0) {
69         cout << "m=0无意义，将不会调用程序" << endl;
70     }
71     else {
72         cout << "begin number:" << endl;
73         cin >> s;
74         linklist L;
75         creatLinklist(L);
76         cout << "-------------------" << endl;
77         show(L);
78         cout << "-------------------" << endl;
79         outgame(L);
80     }
81 }