实习报告（一）
题目：编制一个求解约瑟夫环的程序
班级：计算机09052712班 姓名：史丹丹学号：09052204 完成日期：2011.1.3
一、需求分析
1. 演示程序需利用单向循环链表存储结构模拟该过程，按照出列顺序打印出个人的编码 2. 输出的形式
从屏幕显示出列顺序。 3. 程序功能
提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。 4. 测试数据
n=7 初识code=1
num=1，code=1； num=2，code=2； num=3，code=3； num=4，code=4； num=5，code=5； num=6，code=6； num=7，code=7；
二、概要设计
以单向循环链表实现该结构。 1. 抽象数据类型的定义为： ADT LNode
{
数据对象：D={ai | ai∈CharSet，i= 1，2，…，n，n≥0} 数据关系：R1={< ai-1 ，ai > | ai ∈D， I=2，…，n} 基本操作：
InitList(&L)
操作结果：构造一个最大长度ms内容为空的有序表L。 ClearList(&L)
初始条件：线性表L已经存在。 操作结果：将L重置为空表。 EmptyList(L)
初始条件：线性表L已经存在。
操作结果：若L为空表返回TRUE，否则返回FALSE。 ListLength(L)
初始条件：线性表L已经存在。 操作结果：返回L中数据元素个数。 GetElem(L, pos, &e)
初始条件：线性表L已经存在，1≤i≤ListLength(L)。 操作结果：用e返回L中第i个数据元素的值。 LocateElem(L, e)
初始条件：线性表L已经存在。
操作结果：返回L中第1个与e相同的元素的位序。若不存在返回0。 ListInsert (L, i, e)
初始条件：线性表L已经存在。
操作结果：在L中的第i个元素的位置之前插入新元素 e,L的长度加1。ListDelete(L, pos, e)
初始条件：线性表L已经存在，1≤i≤ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L)
初始条件：线性表L已经存在。
操作结果：依次对L的每个数据元素进行访问。 }ADT SqList
本程序包含以下模块： （1）主程序模块： void main() {
初始化； 输入数据； 执行功能； 显示结果；
}
（2）各功能模块——实现顺序表的各项功能。 各模块的调用关系： 主程序 ↓
各功能模块
三、详细设计
#include #include #define LEN sizeof(node) typedef struct typedata {int num; int code;
}typedata; typedef struct node {
typedata data;
struct node *next;
}node; //结点类型，指针类型
node *creat(node *head, node *tail,int num); //创建循环链表并构成环 node *del(node *tail,int code,int *psw);
//删除本轮密码指向的结点，并将删除结点的密码作为下一个循环的密码 int main() {
node *head, *tail;
int num,i,code,psw; printf(\"请输入人数: \");
scanf(\"%d\ //输入数据 printf(\"初始的code :\"); scanf(\"%d\
tail=creat(head,tail,num); //创建循环链表 for(i=1;i<=num;i++)
{
tail=del(tail,code,&psw); code=psw;
} //调用del函数，输出出列顺序 return 0; }
node *creat(node *head,node *tail,int num) {
node *p,*q; int i;
for(i=1;i<=num;i++) {
p=(node*)malloc(LEN); printf(\"第%d个人的code:\
}
p->data.num=i;
scanf(\"%d\
if(i==1) //由于第一个结点比较特殊，既可能是头结点，也可能是尾结点
head=q=p;
q->next=p; q=p;
} //通过指针p，q建立循环链表
p->next=head; //将表头和表尾链接，构成环 tail=p;
return tail; //返回尾指针，做del函数之用
node *del(node *tail,int code,int *psw) //用尾指针有利于找到头指针的前驱 {
node *p,*q; int i; q=tail;
for(i=1;itail=tail->next;q=tail->next;
tail->next=q->next; printf(\" %d \ }
*psw=q->data.code; // 用psw记录所删数据的密码 free(q); //删除q指向结点 return tail;
四、调试分析
1．开始时，没有考虑初始code=1的情况，返回的头指针，很麻烦，后来修改成返回尾指针，更利于找前驱。
2．creat函数中，没有考虑到第一个数据的特殊性，出现了乱码，废了不少时间才找出原因。
3．对于creat（），依次读入n个code，需时间为O（n）；对del（），读入一个code值，需在循环链表中查找位置，时间复杂度为O（n2）
五、用户手册
用户进入界面后根据提示信息进行操作 1．输入游戏总人数。提示信息：请输入人数： 2．输入初始密码。提示信息：初始的code：
3．依次输入每个人的密码。提示信息为：第i个人的code： 4．输出执行结果
六、测试结果
请输入人数：7 初始的code： 第1个人的code：1 第2个人的code：2 第3个人的code：3 第4个人的code：4 第5个人的code：5 第6个人的code：6 第7个人的code：7 1 2 4 3 7 5 6
