课 程 设 计 报 告
学生姓名:
学 号：
学 院 : 理学院
班 级 :
题 目 :
指导教师： 职称:
2010 年 06 月 10 日
一、选题背景
1.1约瑟夫环主要解决这样一个问题：编号是1，2，……,n的n个人按
照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个
正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报
到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针
方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止，
如何输出每个人的出列次序。
1.2应用本程序能正确输出每个人的出列次序。
1.3 算法思想： JesephRing()函数是实现问题要求的主要函数，其算
法思想是：从 l 至 m 对带头结点的单循环链表循环计数，到 m 时，输出该结
点的编号值，将该结点的密码作为新的 m 值，再从该结点的下一个结点起
重新自 1 起循环计数。如此下去，直到单循环链表空时循环过程结束。
二、算法设计
2.1 定义结构体
定义一个结构体，里边定义两个元素：人的编号及其密码。
程序：struct person
{ int password ,num;
struct person *next;};
2.2 定义主函数
在主程序中定义一个该结构体类型的单向循环链表，来存储 n 个人的编
号及其对应的密码。用户从键盘输入信息，包括输入人数 n，初始 m 值，及
n 个人的密码。为了使程序更加规范，设定人数不多于 30 人，且其对应的
密码必须为正整数。这样就需要在读取用户输入时进行判断，在输入数据错
误应当有出错提示，然后退出。
程序：int n, x=1,a[100];
main()
1
{ int i,m,s;
struct person *head,*p1,*p2,*p0,*p;
printf("\nplease input n:");
scanf("%d",&n);
head=(struct person *)malloc(LEN);
p1=head;p0=head;
for(i=1;i<=n;i++)
{printf("\nplease input %dth of password:",i);
scanf("%d",&m);
p1->password=m;
p1->num=i;
p2=(struct person *)malloc(LEN);
if(i!=n)
{p1->next=p2;p1=p2;}
else
p1->next=head;
}
printf("\nplease input M of start value m=");
scanf("%d",&m);
2
