约瑟夫环(约瑟夫环问题)

引言

黑镜3：急转直下

约瑟夫问题是循环链表的一个典型应用，其描述如下：m个人围成了一圈，从其中任意一个人开始，按顺时针顺序使所有人一次从1开始报数，报道n的人出列；然后使n之后的人接着从1开始报数，再次使报到n的人出列。。。。。。如此下去，求出列的顺序及最后留下来的人的编码。

举个栗子

为了更清晰的描述问题，可以将m与n设定为具体数字，如m=8，n=3，即8个人围着坐成一圈。

给这8个人编号，使编号为1的人开始从1开始报数，报到3的人出列；

编号为4的人接着从1开始报数，报到3出列。。。

如此重复，知道最后只剩下一个人。额，有点不太好想，那我们来画图看看吧。

01.png

02.png

03.png

04.png

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 （头文件）

#ifndef _CLIST_H_#define _CLIST_H_struct Node;typedef struct Head *pHead;//定义头结点类型为pHeadtypedef struct Node * pNode;//数据结点类型//定义头结点 struct Head{ int length; pNode next;//指向下一个结点的指针 }; //定义数据结点 struct Node { int data; pNode next; //指向后继结点的指针 }; pHead ClistCreate(); //声明创建循环链表的方法 int getLength(pHead ph); //获取循环链表的长度 int IsEmpty(pHead ph); //判断链表是否为空 int ClistInrt(pHead ph,int pos,int val); //在链表的pos位置插入元素 val void print(pHead ph); //打印循环链表中的元素 #endif

clist.c（文件）

#include "clist.h" #include <stdio.h> #include <stdlib.h> pHead ClistCreate(){ //创建循环链表 pHead ph=(pHead)malloc(sizeof(struct Head));//为头结点分配空间 if(ph==NULL){ printf("分配头结点失败");//为了方便运行结果查看，不设置return返回值 } //创建好头结点后，初始化头结点中的数据 ph->length=0; ph->next=NULL; return ph;//带头结点返回 } int IsEmpty(pHead ph)//判断链表是否为空 { if(ph=NULL) printf(“传入的循环链表有误”); if(ph->length==0){ return 1; //说明为空 } el{ return 0;//说明不为空 } } //在链表的pos位置插入元素val int ClistInrt(pHead ph,int pos,int val){ if(ph==NULL||pos<0||pos>ph->length){ printf(“插入元素时，参数传入有误! ”); } pNode pval=val;//将值val保存到此结点中 //判断在哪个位置插入元素，先判断链表是否为空 if(IsEmpty(ph)){ //如果链表为空 ph->next=pval;//直接将结点插入到头结点后 pval->next=pval;//将第一个结点指向他自己 } el{ //循环链表不为空，则分为在头部插入（即在头结点后）和普通位置插入 pNode pRear=ph->next; if(pos==0)//在第一个位置（头结点后）插入 { //在0号位置插入，需要先找到尾节点 while(pRear->next!=ph->next) //循环结束的条件 { pRear=pRear->next;//pCur指针向后移动 } //while循环结束后，pRear指向尾节点 //然后插入元素 pval->next=ph->next; ph->next=pval; pRear->next=pval;//这3个步骤顺序不能更改 } el{ //如果不是0号位置插入，这和单链表无区别 pNode pCur=ph->next; for(int i=1;i<pos;i++){ //遍历链表找到要插入的位置 pCur=pCur->next;//pCur指针往后移 } //循环结束，此时pCur指向的是要插入的位置 pval->next=pCur->next;//指针断开再连接的过程 pCur->prev=pval; } } ph->length++; return 1; } //打印循环链表中的元素 void print(pHead ph){ if(ph==NULL||ph->length==0){ printf("参数传入有误！"); } pNode pTmp=ph->next; for(int i=0;i<ph->length;i++){ printf("%d",pTmp->data); pTmp=pTmp->next; } printf(" "); }

ok,以上就讲循环链表的一些方法都已经第一好了，接下来我们来测试一下

Joph.c(测试文件)

#define _CRT_SECURE_NO_WARNINGS #include "clist.h" #include <stdio.h> #include <stdlib.h> int main(){ int m,n; printf("请输入约瑟夫环的总人数： "); scanf("%d",&m); if(m<=0){ printf(“请输入正确的数字！ ”); return 0; } printf("请输入被提出的报数： "); scanf("%d",&n); if(n<=0){ printf("请输入正确的数字! "); return 0; } //根据输入的m创建链表 m即链表的长度 pHead ph=NULL; ph=ClistCreate(); if(ph==NULL){ printf("创建循环链表失败！ "); return 0; } //插入元素 for(int i=m;i>0;i--){ ClistInrt(ph,0,i);//使用头插法从m到1倒序插入 } print(ph); printf("被踢顺序： "); //插入元素后，就循环遍历链表 pNode node=ph->next; //node指针指向第一个结点 while(node->next!=node){ //循环结束条件，结点指向其自身，此时剩下最后一个结点 for(int i=1;i<n-1;i++){ //i<n-1,即报数报到n就重新开始 node=node->next; } //for 循环条件结束后，node指针指向待出局的结点的前驱结点 pNode pTmp=node->next;//pTmp指向要出局的结点 //接下来要先判断这个结点是0号位置的结点还是其他位置的结点 if(pTmp==ph->next){ //如果此结点在0号位置 ph->next=pTmp->next;//对头结点进行处理 node->next=pTmp->next; printf("%d",tTmp->data); free(pTmp); ph->length--; } el{ //如果此结点在其他位置 node->next=pTmp->next; printf("%d",pTmp->data); free(pTmp); ph->length--; } node=node->next; } node->next=node;//循环结束，只剩下node一个结点，让其指向自身 printf(" "); printf("链表中最后留下的是"); printf(ph); system("pau"); return 0; }

上方的测试代码中，创建了一个循环链表，以循环链表为基础来计算这一圈人的出局序列，并求出最后留下来的人。

解决约瑟夫问题并没有用到循环链表的全部算法，因此，在本例子中只涉及到了此问题的相关方法实现。即：

首先创建一个循环链表

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

然后开始遍历

如果报到指定的报数单位，就将这个报数的位置的结点移除，并free

直到链表中只剩下一个结点时，终止循环

完事~~~

总结一下啦

我们从第六篇文章到本篇文章讲解了最简单的数据结构——线性表，具体包括常用的顺序表、单链表、双链表、循环链表。

我们通过使用线性表来解决一些简单的问题，从而为以后的数据结构的学习打下结实的基础。

下一篇，我们来看一下android中的 LinkedList 的源码，看看这个LinkedList内部是怎样一个构成~~，敬请期待