约瑟夫环
约瑟夫问题是循环链表的一个典型应用，其描述如下：m个人围成了一圈，从其中任一个人开始，按顺时针顺序使所有人依次从1开始报数，报到n的人出列；然后使n之后的人接着从1开始报数，再次使报到n的人出列……如此下去，求算出列的顺序，及最后留下来的人的编号。
为了更清晰的描述问题，可以将m与n设定为具体数字，如m = 8，n = 3，即8个人围坐成一圈。为这8个人编号，使编号为1的人从1开始报数，报到3的人出局；编号为4的人再从1开始报数，报到3的出局……如此重复，直到这8个人全部出局。出局过程如图1所示。
图1 约瑟夫环
第一轮：从1到3，第3个人出局。
第二轮：第4个人从1开始报数，第6个人报到3，则第6个人出局。
第三轮：第7个人从1开始报数，第1个人报到3，则第1个人出局。
第四轮：第2个人从1开始报数，第5个人报到3，则第5个人出局。
第五轮：第7个人从1开始报数，第2个人报到3，则第2个人出局。
第六轮：第4个人从1开始报数，第8个人报到3，则第8个人出局。
第七轮：第4个人从1开始报数，此时只剩下他和7，他自己报到3，则第4个人出局。
最后这一圈人只剩下7。
当数据量较小时，通过作图我们很轻易地就能找出出列顺序，但当数据量较大时，人工计算几乎是不可能的。要解决这样的问题，需要借助一定的编程算法，而我们刚刚学习过的循环链表就正好可以用来解决此问题。首先用这些数据创建一个循环链表；然后设置限制条件并循环遍历链表，当遍历到要出局的元素时，就将其删除，这样循环操作直到链表中只剩下一个结点。具体代码实现如例1所示。
例1
clist.h //头文件
1 #ifndef _CLIST_H_
2 #define _CLIST_H_
3
4 struct Node;
5 typedef struct Head* pHead; //头结点类型
6 typedef struct Node* pNode; //数据结点类型
7 //定义头结点
8 struct Head
9 {
10 int length;
11 pNode next; //指向下一个结点的指针
12 };
13 //定义数据结点
14 struct Node
15 {
16 int data;
17 pNode next; //指向后继结点的指针
18 };
19 pHead ClistCreate(); //创建循环链表
20 int getLength(pHead ph); //获取循环链表的长度
21 int IsEmpty(pHead ph); //判断链表是否为空
22 int ClistInsert(pHead ph, int pos, int val); //在链表的pos位置插入元素val
23 void print(pHead ph); //打印循环链表中的元素
24
25 #endifclist.c //文件
26 #include "clist.h"
27 #include <stdio.h>
28 #include <stdlib.h>
29
30 pHead ClistCreate() //创建循环链表
31 {
32 pHead ph = (pHead)malloc(sizeof(struct Head)); //为头结点分配空间
33 if (ph == NULL)
34 printf("分配头结点失败！"); //为了方便运行结果查看，不设置return返回
35 //创建好头结点后，初始化头结点中数据
36 ph->length = 0;
37 ph->next = NULL;
38 return ph; //将头结点返回
39 }
40
41 int IsEmpty(pHead ph) //判断链表是否为空
42 {
43 if (ph == NULL)
44 printf("传入的循环链表有误！");
45 if (ph->length == 0) //如果长度为0，则链表为空
46 return 1;
47 else
48 return 0;
49 }
50
51 int ClistInsert(pHead ph, int pos, int val) //在链表的pos位置插入元素val
52 {
53
54 if (ph == NULL || pos < 0 || pos > ph->length)
55 {
56 printf("插入元素时，参数传入有误！\n");
57 }
58
59 pNode pval = NULL;
60 //参数传入无误，则为新元素val分配结点
61 pval = (pNode)malloc(sizeof(struct Node));
62 pval->data = val; //将值val保存到此结点中
63
64 //接下来要判断在哪个位置插入元素，先判断链表是否为空
65 if (IsEmpty(ph)) //如果链表为空
66 {
67 ph->next = pval; //直接将结点插入到头结点后
68 pval->next = pval; //将第一个结点指向它自己
69 }
70 else //循环链表不为空，则分为在头部插入（即头结点后）和普通位置插入
71 {
72 pNode pRear = ph->next;
73 if (pos == 0) //在第一个位置（头结点后）插入
74 {
75 //在0号位置插入，需要先找到尾结点
76 while (pRear->next != ph->next) //循环结束的条件
77 {
78 pRear = pRear->next; //pCur指针向后移动
79 }
80 //while循环结束后，pRear指向尾结点
81 //然后插入元素
82 pval->next = ph->next;
83 ph->next = pval;
84 pRear->next = pval; //这三个步骤顺序不能更改
85 }
86 else //如果不是0号位置插入，则和单链表无区别
87 {
88 pNode pCur = ph->next;
89 for (int i = 1; i < pos; i++) //就要遍历链表找到要插入的位置
90 {
91 pCur = pCur->next; //pCur指针向后移
92 }
93 //循环结束后，此时pCur指向的是要插入的位置
94 pval->next = pCur->next; //指针断开再连接的过程
95 pCur->next = pval;
96 }
97 }
98 ph->length++;
99 return 1;
100 }
101
102 void print(pHead ph) //打印循环链表中的元素
103 {
104 if (ph == NULL || ph->length == 0)
105 {
106 printf("参数传入有误！");
107 }
108
109 pNode pTmp = ph->next;
110
111 for (int i = 0; i < ph->length ; i++)
112 {
113 printf("%d ", pTmp->data);
114 pTmp = pTmp->next;
115 }
116 printf("\n");
117 }Joseph.c //测试文件
118 #define _CRT_SECURE_NO_WARNINGS
119 #include "clist.h"
120 #include <stdio.h>
121 #include <stdlib.h>
122
123 int main()
124 {
125 int m, n;
126 printf("请输入约瑟夫环的总人数：\n");
127 scanf("%d", &m);
128 if (m <= 0)
129 {
130 printf("请输入正确的数字！\n");
131 return 0;
132 }
133 printf("请输入出局者的报数：\n");
134 scanf("%d", &n);
135 if (n <= 0)
136 {
137 printf("请输入正确的数字！\n");
138 return 0;
139 }
140
141 //根据输入的m创建链表
142 pHead ph = NULL;
143 ph = ClistCreate();
144 if (ph == NULL)
145 {
146 printf("创建循环链表失败！\n");
147 return 0;
148 }
149
150 //插入元素
151 for (int i = m; i > 0; i--)
152 {
153 ClistInsert(ph, 0, i); //使用头插法从m到1倒序插入
154 }
155
156 print(ph);
157 printf("出局顺序：\n");
158 //插入元素后，就循环遍历链表
159 pNode node = ph->next; //node指针指向第一个结点
160 while (node->next != node) //循环结束条件，结点指向其自身，此时剩最后一个结点
161 {
162 for (int i = 1; i < n - 1; i++) //i < n - 1，报到n就重新开始
163 {
164 node = node->next;
165 }
166 //for循环结束后，node指针指向待出局的结点的前驱结点
167 pNode pTmp = node->next; //pTmp指向要被踢出的结点
168
169 //接下来先要判断这个结点是0号位置的结点还是其他位置的结点
170 if (pTmp == ph->next) //如果此结点在0号位置
171 {
172 ph->next = pTmp->next; //头结点也要作处理
173 node->next = pTmp->next;
174 printf("%d ", pTmp->data);
175 free(pTmp);
176 ph->length--;
177 }
178 else //如果此结点在其他位置
179 {
180 node->next = pTmp->next;
181 printf("%d ", pTmp->data);
182 free(pTmp);
183 ph->length--;
184 }
185 node = node->next;
186 }
187 node->next = node; //循环结束，只剩下node一个结点，让其指向自身
188 printf("\n");
189
190 printf("链表中最后留下的是 ");
191 print(ph);
192
193 system("pause");
194 return 0;
195 }运行结果如图2所示。
图2 例1运行结果
在例1中，创建一个循环链表，以循环链表为基础来计算这一圈人的出局序列，并求出最后留下来的人。解决约瑟夫问题并没有用到循环链表的全部算法，因此在本例中只实现了此问题涉及的操作。首先创建一个循环链表，使用每位参与者信息初始化该链表；然后开始遍历，第159~187行代码是将报数为n的结点删除，第160行代码的循环条件是node->next != node，即当链表中只剩一个结点时终止循环；while循环里用一个for循环（第162-165行代码）来控制报数情况，报到n就将此结点删除。
点击此处
隐藏目录
隐藏目录
