《约瑟夫环》实验报告
专业：网络工程班级
学号姓名
一、问题描述：
约瑟夫问题的一种描述是：编号为1，2，……，n点的n个人按顺时针方向围坐一个圈，每人持有一个密码。

一开始选一个正整数作为报数上限值m，从第一个人开始从顺时针方向自1开始报数，报到m时停止。

报到m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始从新从1报数，如此下去，直达所有人出列。

基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。

测试数据：m的初始值为20；n=7，7个人的密码依次是3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序为6，1，4，7，2，3，5）
二、程序设计的基本思想，原理和算法描述：
采用结构体定义单链表，格式为：struct Lnode
{int number;
int password;
struct Lnode*next;
}Lnode,*p,*q,*head;
其中number是人的排列序号，password是各人所持有的密码值，next是节点指针。

Lnode是节点变量，p、q是节点，head是头指针。

程序的代码：定义变量n，i,m,j
输入人的数量n
If n<=0或n>30
重新输入n值
当0<i<n时
建立单链表并且输入各人的密码值p->password
尾指针指向头指针，形成循环链表
输入初始报数上限值m
当1<=j<=n时
循环找出报m的节点p
输出报m节点的编号p->number
将p->password赋给m值
删除此节点
结束
三、源程序及注释：
#include<stdio.h>
#include<stdlib.h>
struct Lnode/*定义链表*/
{int number;
int password;
struct Lnode*next;
}Lnode,*p,*q,*head;
int main(void)
{int n;/*n个人*/
int i;
int m;/*初始报数上限值*/
int j;
printf("please enter the number of people n:");/*输入测试人的数量*/ scanf("%d",&n);
loop:if(n<=0||n>30)/*检验n是否满足要求，如不满足重新输入n值*/ {printf("\n n is erorr!\n\n");
printf("please enter the number of people again n:");
scanf("%d",&n);
goto loop;
}
for(i=1;i<=n;i++)/*建立单链表*/
{if(i==1)
{head=p=(struct Lnode*)malloc(sizeof(struct Lnode));
}
else
{q=(struct Lnode*)malloc(sizeof(struct Lnode));
p->next=q;
p=q;
}
printf("please enter the%d people's password:",i);/*输入每个人所持有的密码值*/ scanf("%d",&(p->password));
p->number=i;
}
p->next=head;/*形成循环链表*/
p=head;
printf("please enter the number m:");
scanf("%d",&m);
printf("The password is:\n");
for(j=1;j<=n;j++)/*输出各人的编号*/
{for(i=1;i<m;i++,p=p->next);
m=p->password;
printf("%d",p->number);
p->number=p->next->number;/*删除报m的节点*/
p->password=p->next->password;
q=p->next;
p->next=p->next->next;
free(q);
}
printf("\n\n");
system("pause");/*等待按任意键退出*/
}
四、运行输出结果：
测试的数据：n为7，m的初值为20，密码：3、1、7、2、4、8、4，正确的结果应为：6、1、4、7、2、3、5。

五、调试分析
本次实习作业难度较低，没有太大的困难。

主要是练习使用单项循环链表。

六、实验小结
1、通过本次上机实践,对链表存储结构有了更深的理解和把握,以及应用链表的知识解
决和分析问题的能力有了新的提高.
2、通过上机实践,掌握了用高级语言实现算法的基本步骤和方法。

3、通过本次实验，提高了理论和实际相结合的能力。