《数据结构》第十二篇、线性表中的链式存储结构——约瑟夫环

黑镜3：急转直下

约瑟夫问题是循环链表的一个典型利用，其描写如下：m个人围成为了一圈，从其中任意一个人开始，按顺时针顺序使所有人一次从1开始报数，报导n的人出列；然后使n以后的人接着从1开始报数，再次使报到n的人出列。。。。。。如斯下去，求出列的顺序及最后留下来的人的编码。文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

举个栗子文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

为了更清晰的描写问题，可以将m与n设定为具体数字，如m=8，n=3，即8个人围着坐成一圈。文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

给这8个人编号，使编号为1的人开始从1开始报数，报到3的人出列；文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

编号为4的人接着从1开始报数，报到3出列。。。文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

如斯重复，知道最后只剩下一个人。额，有点不太好想，那咱们来画图看看吧。文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

01.png文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

02.png文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

03.png文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

04.png文章源自微观生活（93wg.com）微观生活-https://93wg.com/17586.html

05.png

06.png

07.png

08.png

09.png

来，咱们来把步骤总结一下

第一轮：从1到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开始报数，这个时候只剩下4以及7，第4个人又报到3，则第4个人出列。 最后，只剩下第7个人，此时，报数终止。

看图发现

当数据量较小时，通过作图很容易就能找到出局顺序；

然而当数据量较大时，人工计算几近是不可能的。

要解决这样的问题，需要借助一定的编程算法，而循环链表就正好可以用来解决此问题。

首先用这些数据创立一个循环链表；

然后设置限定前提；

并循环遍历链表；

当遍历到要出局的元素时，就将其删除了；

这样循环操作指点链表中只剩下一个结点。

代码实现

clist.h （头文件）

Joseph.c(测试文件)

解决约瑟夫问题并无用到循环链表的全体算法，因而，在本例子中只触及到了此问题的相关办法实现。即：

首先创立一个循环链表

两个变量去设置这个循环链表的长度即报数单位

然后开始遍历

以上就是微观生活（93wg.com）关于“《数据结构》第十二篇、线性表中的链式存储结构——约瑟夫环”的详细内容，希望对大家有所帮助！