实习报告
题 目 : 实现一个约瑟夫环程序
班级： 05计（1） 姓名： 学号：
完成日期：2007.10.12
一、需求分析
1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的
编号和密码）。
2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示"提示信
息"之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其
后。
3． 程序执行的命令包括：
1)构造单向循环链表；2）进行数值的输入，并作判断分析；3）约瑟夫算法的实
现与结果输出；4）结束。
4． 测试数据
m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，（正确的出
列顺序为6，1，4，7，2，1，3，5）。
二、概要设计
1．单向循环链表的抽象数据类型定义为：
ADT List｛
数据对象：D=｛ai | ai↔正整数，I=1，2，......，n,n≥0｝
数据关系：R1=｛< ai-1，ai > |，ai-1，ai↔D,I=1，2，......，n｝
基本操作：
Init List(&L)
操作结果：构造一个空的线性表L。
List Insert(&L,i,e)
初始条件：线性表L已存在，1≤i≤List Length(L)+1.
操作结果：在L中第i个位置之前插入新的数据元素e，L长度加1。
List Delete(&L,i,&e)
初始条件：线性表L存在非空，1≤i≤List Length(L).
操作结果：删除L的第i个元素，并用e返回其值，L长度减1。
2． 程序包含四个模块：
1）主程序模块：
void main( )
{
初始化；
for（; ;）
{}
while（命令=开始）
{
接受命令；
处理命令；
}
for（; ;）
{ }
}
2）有序表单元模块——实现有序表的抽象数据类型；
3）节点结构单元模块——定义有序表的节点结构；
4）数据输入分析模块——判断输入数据正确有效；
各模块之间的调用关系如下：
主程序模块
↓
有序表结构模块
↓
节点结构单元模块
↓
数据输入分析模块
三、详细设计
1、结点类型，指针类型
Typedef struct LNode{
int code,date; //code 为人所在位置 date为人持有的密码
struct LNode *next;
}; // 结点类型，指针类型
2、构造单向循环链表
struct LNode *p,*head,*q; //定义头节点，和指针
for(i=2;i<=n;i++)
{
struct LNode *s=(struct LNode *)malloc (sizeof(struct LNode)); //分配
新结点空间
s->code=i;
input(s->date);
p->next=s;
p=p->next;
}
p->next=head; //根据输入的人数，进行单项循环链表的创建，p指向最后一个
结点，并与头节点链接，形成单项循环链表
3、约瑟夫环的程序实现部分
while(n!=1) //判断输入人数，如为1则直接输出结果，不循环
{
for(i=1，m=m%n;i
{
p=p->next;
}
q=p->next; //找到要删除节点
p->next=q->next; //找到要删除节点的后继，并连接新环
m=q->date; //找到下一个密码
printf("%d",q->code);
free(q); //释放已删除节点空间
n--; //链表长度减一
}
printf("%d",p->code); //约瑟夫环的结果输出
4、其他函数代码
数值的输入限制
int input()
{
int y,k,z=0;
char c; //元素类型
char a[4]; //数组初始化
if(!z) //输入判断，确定位数字或控制字符且位置和密码不为零
{
for(y=0;y<4;y++)
{
c=getch();
if(c>=48&&c<=57) //确定为输入数字
{a[y]=c;
putch(c);
}
else
{
y--;
if(c=='\r') //确定输入为控制字符 即回车或者删除
break;
else
if(c==8)
{a[y]='\n';
y--;}
continue;
}
}
k=atoi(a); //确定最终输入数字的值
printf("\n");
z=k;
if(z==0)
printf("ERROR! The number couldn't be 0! \n"); // 输入为零，重新输入
}
return(k); //数值的返回
5、函数的调用关系图反映程序层次结构
Main→input
四、调试分析
1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时
候会经常出错。比如是输入字母，或者输入0，大于32767溢出；
2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间；
3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判
断，浪费了资源；
4、算法的时空分析
为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，
但是做的是do……while循环，复杂度为o（1）;
当n大于1时：
在数据输入中，链表的创建是for循环，时间复杂度为o（n-1）
在约瑟夫环实现程序中，为for循环。时间复杂度为o（m%n -1）
当n=1时，复杂度为o（1）。
五、用户手册
用户根据提示，先输入起始密码m，然后输入人数n，再根据人数，分别输
入每个人的密码date，数值均不能为0，否则会提示重新输入，输入为字母则自
动丢弃，输入错误可用删除键进行修改，输入完成后按回车键确定本次输入完毕
（若输入数字大于9999，则第五位自动转换为下一个数字的起始位，依此类推）。
当n个数字全部输入完毕，则自动显示结果，按任意键则退出本程序。
六、测试结果
第一组：m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，出
列顺序为6，1，4，7，2，1，3，5。
第二组： m 的初值为30；n=8，7个人的密码依次为：5，1，6，9，4，7，2，3，
出列顺序为6，5，2，3，7，1，4，8。
第三组 : m 的初值为15；n=6，7个人的密码依次为：5，3，4，7，6，9，出列
顺序为3，1，2，6，4，5。
七、附录
源程序头文件名清单：
#include "malloc.h" //内存空间分配头文件
#include "stdio.h" //输入输出函数头文件
#include "stdlib.h" //input函数中字符串转短整形函数的头文件
#include "conio.h" //最后显示结果、清屏函数头文件