作者名：Demo不是emo
主页面链接：主页传送门创作初心：对于计算机的学习者来说，初期的学习无疑是最迷茫和难以坚持的，中后期主要是经验和能力的提高，我也刚接触计算机1年，也在不断的探索，在CSDN写博客主要是为了分享自己的学习历程，学习方法，总结的经验等等，希望能帮助到大家座右铭：不要让时代的悲哀成为你的悲哀专研方向：网络安全，数据结构
每日emo：唯一有效的安慰方式，就是你在我身边 ————————————————
大一新生自学中，有不完善的地方希望大家见谅，有什么好的改进想法欢迎提出来一起交流，感谢大家的阅读。
目录
什么是约瑟夫环
约瑟夫环的实现方式
循环链表的构建
循环链表在约瑟夫问题上的应用
完整代码
什么是约瑟夫环
约瑟夫环是循环链表的一个典型应用，其描述如下：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 { 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 { 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 { 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 #include #include 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 { 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 { 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 { 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 大家如果有疑问可以随时私信，都会回复大家。
发表评论