约瑟夫环问题（C语言、数据结构版）
一、问题描述
N个人围城一桌（首位相连），约定从1报数，报到数为k的人出局，然后下一位又从1开始报，以此类推。最后留下的人获胜。（有很多类似问题，如猴子选代王等等，解法都一样）
二、思路分析
　　　　（1）可将人的顺序简单编号，从1到N；
　　　　（2）构造一个循环链表，可以解决首位相连的问题，同时如果将人的编号改为人名或者其他比较方便
&&&&&& & （3）将人的编号插入到结构体的Data域；
&&&&&& & （4）遍历人的编号，输出参与的人的编号；
&&&&&& & （5）开始报数，从头报数，报到k的人出局（删除次结点），（输出出局的人更人性化）避免浪费，可释放次结点。直到人数只有一个人时，退出循环。输出获胜的人。
　　　（6）注意：在写删除删除结点的函数时都是针对K&=2的情况处理，所以要考虑k=1的情况，要是出局的密码为1时则最后一个获胜。
三、算法实现
&&&&& （1）构造结构体
&&&&&&&&&&&&&&&&& typedef struct Node{
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& int N//Data域
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& struct Node *
　　　　　　}JoseNode, *PNode, *HN//PNode为指针变量，HNode为头结点
&&&&&& （2）得到头结点
&&&&&&&&&&& &&& HNode h = ((HNode)malloc(sizeof(JoseNode)));
　　（3）初始化循环单链表
&&&&&&&&&&&& int JoseInit(HNode *h)
&&&&&&&&&&&&&&&&&&&&&&&&&&& if (!h)
&&&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&& &&&&&&&&&&&&& printf("初始化链表错误！\n");
&&&&&&&&&&&&&&&&&&&&&&&&&&& return 0;
&&&&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&& &&&&&&&&&&&&&&&&&&&& (*h)-&next = (*h);//循环单链表
&&&&&&&&&&&&&&&&&&&&&&&&&&& return 1;
（4）插入算法
&&&&&&&&&&& int JoseInsert(JoseNode *h, int pos, int x)
&&&&&&&&&&&&&&&&&&&&&&&&& PNode p=h,q;
&&&&&&&&&&&&&&&&&&&&&&&&& int i=1;
&&&&&&&& &&&&&&&&&&&&&&&&& if (pos == 1)/*尾插法*/
&&&&&&&&&&&&&&&&& &&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&& p-&Num =
&&&&&&&&&&&&&&&&&&&&&&&&& p-&next =
&&&&&&&&&&&&&&&&&&&&&&&&& return 1;
&&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&&&&&&&&&&& while(i&pos-1)
&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&& p=p-&
&&&&&&&&&&&&&&&&&&&&&&&&& i++;
&&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&&&&&&&&&&& q=(PNode)malloc(sizeof(JoseNode));
&&&&&&&&&&&&&&&&&&&&&&&&& q-&Num=x;
&&&&&&&&&&&&&&&&&&&&&&&&& q-&next=p-&
&&&&&&&&&&&&&&&&&&&&&&&&& p-&next=q;
&&&&&&&&&&&&&&&&&&&&&&&&& return 1;
for (i = 1; i &=N; i++)
&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&& JoseInsert(h, i, i);
&&&&&&&&&&&&&&&&& }
（4）遍历算法
void TraverseList(HNode h, int M)
&&&&&&&&&&&&&&&&&&&&&&&&& int i = 0;
&&&&&&&&&&&&&&&&&&&&&&&&& PNode p =
&&&&&&&& &&&&&&&&&&&&&&&&& printf("参与的人的编号为：\n");
&&&&&&&&&&&&&&&&&&&&&&&&& while (i&M)
&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&& printf("%d\t", p-&Num);
&&&&&&&&&&&&&&&&&&&&&&&&& p = p-&
&&&&&&&&&&&&&&&&&&&&&&&&& i++;
&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&&& printf("\n");
（5）找到出局的人，并删除（删除算法）
　　if(k & 1)//考虑出局密码为1时的情况
&&&&&& &&&&&& JoseDelete(h, N, k);
&&&&&& else
&&&&&&&&&&&&& for(i = 1; i & N; i++)
&&&&&&&&&&&&&&&&&&&& printf("出局的人为：%d号\n",i);
&&&&&&&&&&&&& printf("***************获胜者为：%d号***************",N);
&&&&& int JoseDelete(HNode h, int M, int k)
&&&&&&&&&&&&&&&&& PNode p=h,q;
&&&&&&&&&&&&&&&&& while(M&1)//循环终止条件，只剩一个人时
&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&& for(i=1;i&k-1;i++)//此处为i&k-1,因为要找到的是出局的人的前一个结点①
&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& p=p-&
&&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&& q=p-&
&&&&&&&&&&&&&&&&&&&&&&&&& p-&next=q-&
&&&&&&&&&&&&&&&&& &&&&&&&& printf("出局的人为：%d号\n",q-&Num);
&&&&&&&&&&&&&&&&&&&&&&&&& free(q);//释放次结点
&&&&&&&&&&&&&&&&&&&&&&&&& p=p-&//与①处的相对应，①处找到的只是出局的人的前一个结点
&&&&&&&&&&&&&&&&&&&&&&&&& M--;
&&&&&&&&&&&&&&&&& }
&&&&&&&& printf("***************获胜者为：%d号***************",p-&Num);
&&&&&&&& return 1;
四、完整代码
1 #include &stdio.h&
2 #include &malloc.h&
4 /*构建结构体*/
5 typedef struct Node{
struct Node *
8 }JoseNode, *PNode, *HN
10 /**********初始化循环单链表*********/
11 int JoseInit(HNode *h)
printf("初始化链表错误！\n");
(*h)-&next = (*h);//循环单链表
23 /*************单链表插入操作**********/
24 int JoseInsert(JoseNode *h, int pos, int x)
PNode p=h,q;
if (pos == 1)/*尾插法*/
while(i&pos-1)
q=(PNode)malloc(sizeof(JoseNode));
q-&next=p-&
p-&next=q;
46 /*遍历*/
47 void TraverseList(HNode h, int M)
int i = 0;
printf("参与的人的编号为：\n");
while (i&M)
printf("%d\t", p-&Num);
printf("\n");
60 /**************出局函数****************/
62 int JoseDelete(HNode h, int M, int k)
PNode p=h,q;
while(M&1)
for(i=1;i&k-1;i++)
p-&next=q-&
printf("出局的人为：%d号\n",q-&Num);
printf("***************获胜者为：%d号***************",p-&Num);
85 /***************************************/
86 int main()
int//计数器
int N;//参与的人数
int//报数密码
printf("请输入参与人数：");
scanf("%d",&N);
printf("请输入出局密码：");
scanf("%d",&k);
96 /**************得到头结点****************/
HNode h = ((HNode)malloc(sizeof(JoseNode)));
99 /***************初始化单链表************/
JoseInit(&h);
102 /******将编号插入到循环单链表中******/
for (i = 1; i &=N; i++)
JoseInsert(h, i, i);
107 /**************遍历单链表***************/
TraverseList(h,N);
110 /***************出局函数************/
JoseDelete(h, N, k);
for(i = 1; i & N; i++)
printf("出局的人为：%d号\n",i);
printf("***************获胜者为：%d号***************",N);
printf("\n");
printf("\n");
五、实验验证
经过验证，实验成功！如果有不足的地方，请大家指出来，一起探讨！写得不清楚的可以与我联系。
阅读(...) 评论()C语言中约瑟夫环的问题(跪求大神解读程序)_百度知道
C语言中约瑟夫环的问题(跪求大神解读程序)
hile(p-&next，包含data和下一个地址{
for(i=1;%5d&data);;
p=p-&gt，我看不懂后面的……
q=p;/m就是约瑟夫环里数到第m的那个人;m;i++)
/i&lt，提前已经定义了LinkList*结构体;
p=p-&/
free(temp);
printf(&next=p-&gt!=p)
/p是一个循环链表的头指针的地址,p-&next
提问者采纳
& //由于不清楚你的其他程序段;&nbsp。& free(temp);&&&&&nbsp，那么在数到m之前（其实是m-1）执行循环{& q=p;&&&i++) &i& &&&&& p=p-&&&&&m;&&nbsp，本程度段中temp被赋值然后被释放;//等循环到m时的那个人输出退出的那个值（人）;&&nbsp，不知道该语句究竟干什么&& &&&& q-&& printf(& &&&&&&&&&& &&&&&&&&&&&&&&&&nbsp，其实就是在链表中把当前人的下一值（人）属性更改为下一个值（人）的下一个值（人），那么q的下一个值（人）要从链表中拿掉;&&&&//将下一个值（人）p的下一个值付给当前人的下一个值（人）;& }&nbsp，然后开始下一个循环&nbsp；就本程序段而言;&&&&&&&nbsp，因为q是循环m-1次的那个值（人）你这个程序不完整;& //把下一个值（人）p赋值给当前值（人）q&&temp=p：本质上就是如果最后只剩一个人的时候退出for(i=1;&//&&&&&&%5d&//下一个值（人）p指向更下一个值（人）p&&//在本程序段中同上面&nbsp，在“while(p-&&& &&&nbsp，不知道有什么作用;&&&data);&&nbsp，应该是递归程序的一个程序段，也就是q的下一个值（人）;next=p-&&&&&&&& &&&nbsp。&& &&&& &&&&//这个时候将p设为p的下一个值（人）;&&//如果m是退出的那个编号;& &nbsp，也就是把第m个人从链表中去掉的过程;&&&& temp=p;&&&& p=p-&&的赋值一样;&nbsp,p-&&&& &&&&&&&&& &&&&&&，这是时候其实是p;&&//&& //约瑟夫环的退出条件;&&&& & &&&&nbsp!=p){ &&nbsp：while(p-&&&& &&nbsp!=p)”的后面应该有执行递归程序的语句;&nbsp，没做什么事情}这个程序段后面应该是执行本子程序
提问者评价
其他类似问题
为您推荐：
其他2条回答
&&&&{&&&nbsp，提前已经定义了LinkList*结构体;&data);i&&//p是一个循环链表的头指针的地址;&nbsp!=p)&&&&&p赋值为p节点的下一个节点;&&&&nbsp，使得q是p的前一个节点&//&//&&&&&%5d&&&&free(temp);&&&p=p-&&&&&&&&&}&printf(&&&&&&temp=p;&//&&&&q的next指针指向p节点的下一个节点&&q=p;p=p-&i++)&&nbsp，也就是q的下一个节点&&&&nbsp,p-&&nbsp，包含data和下一个地址{&&nbspwhile(p-&&&&&&m;&&q-&//m就是约瑟夫环里数到第m的那个人;for(i=1;&next=p-&//&;先把p节点赋值给temp&nbsp
就是说指针跳过了m那个节点？那temp有什么作用
m就是下一个开始算m个了temp就是要来保存需要删除的节点
p=p-&是指针
哦哦，下面的是什么意思……
上面大神都回答了
约瑟夫环的相关知识
下载知道APP
随时随地咨询
出门在外也不愁详解约瑟夫环问题及其相关的C语言算法实现-C 语言_软件编程-脚本宝典
页面导航： >
> 详解约瑟夫环问题及其相关的C语言算法实现
详解约瑟夫环问题及其相关的C语言算法实现
这篇文章主要介绍了详解约瑟夫环问题及其相关的C语言算法实现,也是ACM当中经常会引用到的基础题目,文中共介绍了三种C语言解答,需要的朋友可以参考下
约瑟夫环问题
N个人围成一圈顺序编号，从1号开始按1、2、3......顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。&&
请按退出顺序输出每个退出人的原序号&
用数学归纳法递推。
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，若nm非常大，无法在短时间内计算出结果。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
现在我们把他们的编号做一下转换：
k&&&& --& 0
k+1&& --& 1
k+2&& --& 2
k-2&& --& n-2
k-1&& --& n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况——这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
f[i]=(f[i-1]+m)%i; (i&1)
一、循环链表
建立一个有N个元素的循环链表，然后从链表头开始遍历并计数，如果基数i == m，则踢出该元素，继续循环，直到当前元素与下一个元素相同时退出循环
#include &stdio.h&
#include &stdlib.h&
#include &string.h&
typedef struct lnode
struct lnode *
* 构建循环链表&&循环遍历
void create_ring(lnode **root, int loc, int n)
lnode *pre, *current, *
current = *
pre = NULL;
while (current != NULL) {
current = current-&
new = (lnode *)malloc(sizeof(lnode));
new-&pos =
new-&next =
if (pre == NULL) {
pre-&next =
// 循环链表
if (loc == n) {
new-&next = *
* 约瑟夫环
void kickoff_ring(lnode *head, int p)
lnode *pre, *
pre = pcur =
while (pcur-&next != pcur) {
for (i = 1; i & i ++) {
pcur = pcur-&
printf("%d ", pcur-&pos);
pre-&next = pcur-&
free(pcur);
pcur = pre-&
printf("%d\n", pcur-&pos);
free(pcur);
void print_ring(lnode *head)
while (cur-&next != head) {
printf("%d ", cur-&pos);
cur = cur-&
printf("%d\n", cur-&pos);
int main()
while (scanf("%d %d", &n, &p) != EOF) {
// 构建循环链表
for (i = 1, head = NULL; i &= i ++)
create_ring(&head, i, n);
// 约瑟夫环
if (p != 1)
kickoff_ring(head, p);
print_ring(head);
本文链接：
最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具The page is temporarily unavailable
nginx error!
The page you are looking for is temporarily unavailable.
Please try again later.
Website Administrator
Something has triggered an error on your
This is the default error page for
nginx that is distributed with
It is located
/usr/share/nginx/html/50x.html
You should customize this error page for your own
site or edit the error_page directive in
the nginx configuration file
/etc/nginx/nginx.conf.