什么是约瑟夫环
约瑟夫环是循环链表的一个典型应用，其描述如下：m个人围成一圈，从任意一个人开始，按顺时针顺序使所有人依次从1开始报数，报到n的人出列，然后使n之后的人接着从1开始报数，再次使报到n的人出列，不断重复此操作，并输出出局的先后顺序，直到最后只剩下一个人，如下示意图所示
假设8个人围成一圈，依次编号1到8，按从小到大顺序报数，报到3的人出局，流程如下
第一轮：从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号
约瑟夫环的实现方式
一：数组链接方式实现；
二：数组标志位实现
三：循环链表实现（重点）；
因为我是学习循环链表的时候接触的约瑟夫环，所以本文只用第三种方式实现——循环链表实现，当然，循环链表实现约瑟夫环也有很多种写法，下面仅仅是我个人的观点，有不完善的地方还请见谅，下面让我们进入正文。
循环链表的构建
因为本文主要讲述的是用循环链表实现约瑟夫环，所以循环链表的创建就一带而过了，对循环链表不太熟悉的小伙伴也可以参考一下我的上一篇博客，里面对循环链表有比较清楚的讲解，点此链接可以直接进入：C语言数据结构篇——单循环链表的创建，插入，节点删除，打印等操作_Grande joie的博客-CSDN博客下面直接附上为大家封装好的函数
头结点和数据节点结构体的定义如下
typedef struct header//头结点 { int length; struct node* next; }head; typedef struct node//数据节点 { int val; struct node* next; }node;
1， head* listcreat(）//循环链表的创建
head* listcreat() { head* p; p=(head*)malloc(sizeof(head)); p->next=NULL; p->length=0; return p; }
2， void listinsert(head* p,int pos,int x)//循环链表数据节点的插入
void listinsert(head* p,int pos,int x) { if(p==NULL||pos<0||pos>p->length) { printf("listinsert():error\n"); return; } node* temp=(node*)malloc(sizeof(node)); temp->val=x; node* pcur=p->next;//指向第一个数据节点 node* plast=p->next;//指向最后一个数据节点 while(pcur!=NULL&&plast->next!=pcur)//使plast指向最后一个节点 { plast=plast->next; } if(p->length==0)//判断循环链表为空的情况 { p->next=temp; temp->next=temp; } else if(pos==0)//头插 { plast->next=temp; temp->next=pcur; p->next=temp; } else if(pos==p->length)//尾插 { plast->next=temp; temp->next=pcur; } else { node* pval=p->next;//pval用来指向要插入位置的数据节点 for(int i=1;i<pos;i++) { pval=pval->next; } temp->next=pval->next; pval->next=temp; } p->length++; return; }
void listdelete(head* p,int x)//循环链表数据节点的删除
void listdelete(head* p,int x) { node* temp;//temp指向要删除的节点 temp=p->next; for(int i=0;i<p->length;i++) { if(temp->val==x) { break; } temp=temp->next; } if(temp->val!=x) { printf("listdelete():error\n"); return; } node* pcur=p->next;//pcur指向第一个节点 node* plast=p->next;//plast用来指向最后一个节点 while(plast->next!=pcur) { plast=plast->next; } if(p->length==1)//只有一个元素时 { p->next=NULL; } else if(temp==pcur)//删除的是第一个节点 { p->next=pcur->next; plast->next=pcur->next; } else if(temp==plast)//删除的是最后一个节点 { node* pre=p->next;//指向倒数第二个节点 while(pre->next!=plast) { pre=pre->next; } pre->next=pcur; } else { node* pre=p->next; while(pre->next!=temp)//使pre指向temp的前一个元素 { pre=pre->next; } pre->next=temp->next; } p->length--; }
void listprint(head* p)//循环链表的遍历打印（输出）
void listprint(head* p) { if(p==NULL||p->length==0) { printf("listprint():error"); return; } node* temp=p->next; for(int i=0;i<p->length;i++) { printf("%d ",temp->val); temp=temp->next; } printf("\n"); return; }
有了这些封装函数，一个基础的循环链表就可以构建啦
循环链表在约瑟夫问题上的应用
int main() { head* p;定义循环链表头结点 p=listcreat(); printf("题意：m个人围成一圈，报到n的人退出，直到只留下一个\n"); printf("请输入约瑟夫环的总人数m\n"); int m,n; scanf("%d",&m); printf("请输入被踢出的报数n\n"); scanf("%d",&n); for(int i=m;i>0;i--)//围圈操作（即按要求构建循环链表） { listinsert(p,0,i); } printf("输出初始循环链表\n"); listprint(p); node* temp=p->next;//定义指向循环链表第一个数据节点的指针，方便报数 int count=1;//因为此时temp已经指向第一个人了，所以报数从1开始，多看几遍也许好理解一点 printf("被踢顺序\n"); while(temp->next!=temp)//剩下一个数时结束循环 { if(count==n)//如果报数等于需要出局的数 { node* pre=p->next;//用于保留位置使temp不至于丢失 while(pre->next!=temp)//遍历到指向temp的前一个节点 { pre=pre->next; } printf("%d ",temp->val); listdelete(p,temp->val);//出局操作（即删除该数据节点） //此时如果没有前面定义的pre，那么temp就没有任何指向了，而有了pre，出局后就可以用 temp代表pre的指向，temp就不会丢失指向 temp=pre; count=0;//因为temp指向了出局的前一个人，下一个人报数从一开始，所以报数先归0 continue;//出局时就不执行遍历和报数操作 } count++; temp=temp->next; } printf("\n"); printf("链表中最后被剩下的是：\n"); listprint(p); }
完整代码
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct header { int length; struct node* next; }head; typedef struct node { int val; struct node* next; }node; head* listcreat() { head* p; p=(head*)malloc(sizeof(head)); p->next=NULL; p->length=0; return p; } void listinsert(head* p,int pos,int x) { if(p==NULL||pos<0||pos>p->length) { printf("listinsert():error\n"); return; } node* temp=(node*)malloc(sizeof(node)); temp->val=x; node* pcur=p->next;//指向第一个数据节点 node* plast=p->next;//指向最后一个数据节点 while(pcur!=NULL&&plast->next!=pcur)//使plast指向最后一个节点 { plast=plast->next; } if(p->length==0)//判断循环链表为空的情况 { p->next=temp; temp->next=temp; } else if(pos==0)//头插 { plast->next=temp; temp->next=pcur; p->next=temp; } else if(pos==p->length)//尾插 { plast->next=temp; temp->next=pcur; } else { node* pval=p->next;//pval用来指向要插入位置的数据节点 for(int i=1;i<pos;i++) { pval=pval->next; } temp->next=pval->next; pval->next=temp; } p->length++; return; } void listdelete(head* p,int x) { node* temp;//temp指向要删除的节点 temp=p->next; for(int i=0;i<p->length;i++) { if(temp->val==x) { break; } temp=temp->next; } node* pcur=p->next;//pcur指向第一个节点 node* plast=p->next;//plast用来指向最后一个节点 while(plast->next!=pcur) { plast=plast->next; } if(temp->val!=x) { printf("listprintf():error\n"); return; } if(p->length==1)//只有一个元素时 { p->next=NULL; } else if(temp==pcur)//删除的是第一个节点 { p->next=pcur->next; plast->next=pcur->next; } else if(temp==plast)//删除的是最后一个节点 { node* pre=p->next;//指向倒数第二个节点 while(pre->next!=plast) { pre=pre->next; } pre->next=pcur; } else { node* pre=p->next; while(pre->next!=temp)//使pre指向temp的前一个元素 { pre=pre->next; } pre->next=temp->next; } p->length--; } void listprint(head* p) { if(p==NULL||p->length==0) { printf("listprint():error"); return; } node* temp=p->next; for(int i=0;i<p->length;i++) { printf("%d ",temp->val); temp=temp->next; } printf("\n"); return; } int main() { head* p; p=listcreat(); printf("题意：m个人围成一圈，报到n的人退出，直到只留下一个\n"); printf("请输入约瑟夫环的总人数m\n"); int m,n; scanf("%d",&m); printf("请输入被踢出的报数n\n"); scanf("%d",&n); for(int i=m;i>0;i--) { listinsert(p,0,i); } printf("输出初始循环链表\n"); listprint(p); node* temp=p->next; int count=1; printf("被踢顺序\n"); while(temp->next!=temp)//剩下一个数时结束循环 { if(count==n) { node* pre=p->next; while(pre->next!=temp)//指向temp的前一个节点 { pre=pre->next; } printf("%d ",temp->val); listdelete(p,temp->val); temp=pre; count=0; continue; } count++; temp=temp->next; } printf("\n"); printf("链表中最后被剩下的是：\n"); listprint(p); }
循环链表在约瑟夫环上的应用就完整的写出来了，随便写点数据运行一下就是下面这个效果啦
题意：m个人围成一圈，报到n的人退出，直到只留下一个
请输入约瑟夫环的总人数m
8
请输入被踢出的报数n
3
输出初始循环链表
1 2 3 4 5 6 7 8
被踢顺序
3 6 1 5 2 8 4
链表中最后被剩下的是：
7
大家如果有疑问可以随时私信，都会回复大家。
