学习循环链表，约瑟夫问题

pyzyd

循环链表——约瑟夫问题

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. typedef int ElemType;
   
5. 
   
6. typedef struct Node {
   
7.     ElemType data;
   
8.     struct Node *next;
   
9. } LinkNode, *LinkList;
   
10. 
    
11. // 初始化循环链表
    
12. bool InitList(LinkList &L) {
    
13.     L = new LinkNode;
    
14.     if (!L) {
    
15.         return false;
    
16.     }
    
17.     L->next = L;
    
18.     L->data = -1;
    
19.     return true;
    
20. }
    
21. 
    
22. // 尾插法
    
23. bool insert_tail(LinkList &L, ElemType e) {
    
24.     if (!L) {
    
25.         return false;
    
26.     }
    
27.     LinkNode *p = L;
    
28.     while (p->next != L) {
    
29.         p = p->next;
    
30.     }
    
31.     LinkNode *s = new LinkNode;
    
32.     if (!s) {
    
33.         return false;
    
34.     }
    
35.     s->data = e;
    
36.     s->next = p->next;
    
37.     p->next = s;
    
38.     return true;
    
39. }
    
40. 
    
41. void printList(const LinkList &L) {
    
42.     if (!L) {
    
43.         return;
    
44.     }
    
45.     LinkNode *p = L->next;
    
46.     while (p != L) {
    
47.         cout << p->data << " ";
    
48.         p = p->next;
    
49.     }
    
50.     cout << endl;
    
51. }
    
52. 
    
53. bool Joseph(LinkList &L, int interval) {
    
54.     if (!L || L->next == L) {
    
55.         cout << "循环链表为空" << endl;
    
56.         return false;
    
57.     }
    
58.     if (interval <= 0) {
    
59.         cout << "间隔数必须大于0" << endl;
    
60.         return false;
    
61.     }
    
62.     LinkNode *p = L->next, *pre=L; // p指向要删除的结点，pre指向要删除结点的前一个结点
    
63.     int times = 0;
    
64.     while (L->next != L) {
    
65.         // 找到要删除的结点的前一个结点和要删除的结点
    
66.         // 从1 开始计数，删除计数到interval 的结点，不包括头结点
    
67.         for (int i = 1; i < interval; i++) {
    
68.             pre = p;
    
69.             p = p->next;
    
70.             if (p == L) { // 跳过头结点计数
    
71.                 pre = p;
    
72.                 p = L->next;
    
73.             }
    
74.         }
    
75.         pre->next = p->next;
    
76.         LinkNode *temp = p;  // 用temp 保存要删除的结点，删除
    
77.         p = p->next;
    
78.         times++;
    
79.         cout << "第" << times << "次删除的元素为" << temp->data << endl;
    
80.         delete temp;
    
81.         if (p == L){  //防止计数错误，当p指向头结点时，重新指向头结点的下一个结点
    
82.             pre = p;
    
83.             p = L->next;
    
84.         }
    
85.         printList(L);
    
86.     }
    
87.     return true;
    
88. }
    
89. 
    
90. int main() {
    
91.     LinkList L;
    
92.     // 1.初始化一个空的循环链表
    
93.     if (!InitList(L)) {
    
94.         exit(-1);
    
95.     } else {
    
96.         cout << "初始化成功" << endl;
    
97.     }
    
98.     // // 2.尾插法插入元素
    
99.     // cout << "请输入要插入的元素,ctrl d结束" << endl;
    
100.     // ElemType e;
     
101.     // while (cin >> e) {
     
102.     //     insert_tail(L, e);
     
103.     // }
     
104.     // cin.clear();
     
105.     for (int i = 1; i <= 10; i++) {
     
106.         insert_tail(L, i);
     
107.     }
     
108.     cout << endl;
     
109. 
     
110.     // // 3.打印循环链表
     
111.     // printList(L);
     
112. 
     
113.     // 约瑟夫环
     
114.     Joseph(L, 9);
     
115. 
     
116.     return 0;
     
117. }
     

复制代码

FishC

循环链表是一种特殊的链表，其中最后一个节点的指针指向头节点，从而形成一个环状结构。约瑟夫问题是一个经典的数学应用问题：有 n 个人围成一圈，从第 k 个人开始报数，数到 m 的人出列，然后从下一个人继续报数，直到所有人出列。循环链表非常适合模拟这个过程。

在您提供的代码中，定义了一个循环链表结构，并实现了初始化、尾插法和打印功能。但约瑟夫问题的函数不完整。下面我将解释关键部分，并提供一个完整的约瑟夫问题实现。

首先，循环链表的基本操作：
- InitList：初始化链表，创建一个头节点并使其指向自身。
- insert_tail：使用尾插法在链表末尾添加新节点。
- printList：遍历并打印链表中的数据（跳过头节点）。

约瑟夫问题函数需要模拟报数出列的过程。以下是完整的实现：

1. 
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. typedef int ElemType;
   
6. 
   
7. typedef struct Node {
   
8.     ElemType data;
   
9.     struct Node *next;
   
10. } LinkNode, *LinkList;
    
11. 
    
12. // 初始化循环链表
    
13. bool InitList(LinkList &L) {
    
14.     L = new LinkNode;
    
15.     if (!L) {
    
16.         return false;
    
17.     }
    
18.     L->next = L;
    
19.     L->data = -1;
    
20.     return true;
    
21. }
    
22. 
    
23. // 尾插法
    
24. bool insert_tail(LinkList &L, ElemType e) {
    
25.     if (!L) {
    
26.         return false;
    
27.     }
    
28.     LinkNode *p = L;
    
29.     while (p->next != L) {
    
30.         p = p->next;
    
31.     }
    
32.     LinkNode *s = new LinkNode;
    
33.     if (!s) {
    
34.         return false;
    
35.     }
    
36.     s->data = e;
    
37.     s->next = p->next;
    
38.     p->next = s;
    
39.     return true;
    
40. }
    
41. 
    
42. void printList(const LinkList &L) {
    
43.     if (!L) {
    
44.         return;
    
45.     }
    
46.     LinkNode *p = L->next;
    
47.     while (p != L) {
    
48.         cout << p->data << " ";
    
49.         p = p->next;
    
50.     }
    
51.     cout << endl;
    
52. }
    
53. 
    
54. // 约瑟夫问题函数
    
55. void josephus(LinkList &L, int m) {
    
56.     if (!L || L->next == L) {
    
57.         cout << "链表为空或只有头节点！" << endl;
    
58.         return;
    
59.     }
    
60.     LinkNode *p = L->next; // 从第一个数据节点开始
    
61.     LinkNode *prev = L;    // 记录p的前驱节点
    
62.     while (L->next != L) { // 当还有数据节点时循环
    
63.         for (int i = 1; i < m; i++) { // 数m-1次
    
64.             prev = p;
    
65.             p = p->next;
    
66.             if (p == L) { // 如果遇到头节点，跳过
    
67.                 prev = p;
    
68.                 p = p->next;
    
69.             }
    
70.         }
    
71.         // 删除当前节点p
    
72.         prev->next = p->next;
    
73.         cout << p->data << " ";
    
74.         delete p;
    
75.         p = prev->next;
    
76.         if (p == L) { // 如果删除后指向头节点，调整到下一个数据节点
    
77.             p = p->next;
    
78.             prev = L;
    
79.         }
    
80.     }
    
81.     cout << endl;
    
82. }
    
83. 
    
84. int main() {
    
85.     LinkList L;
    
86.     InitList(L);
    
87.     int n, m;
    
88.     cout << "请输入人数n：";
    
89.     cin >> n;
    
90.     cout << "请输入报数m：";
    
91.     cin >> m;
    
92.     for (int i = 1; i <= n; i++) {
    
93.         insert_tail(L, i);
    
94.     }
    
95.     cout << "初始链表：";
    
96.     printList(L);
    
97.     cout << "出列顺序：";
    
98.     josephus(L, m);
    
99.     return 0;
    
100. }
     

复制代码

使用说明：
1. 代码首先初始化循环链表，然后使用尾插法插入数据（例如人的编号）。
2. josephus 函数模拟报数过程，每次数到 m 时删除节点并输出数据。
3. 在循环中，如果指针遇到头节点，会自动跳过以确保只处理数据节点。

这个实现确保了约瑟夫问题的正确模拟，代码简洁易读。如果您有更多问题，欢迎继续提问！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。