约瑟夫环实习报告.doc

课程实验报告实验课程：数据结构实验项目：编制一个演示约瑟夫环问题的程序指导教师：李洪波学生姓名:学生学号：班 级：实习报告一、 需求分析1、 本演示程序中，编号为1,2,3,n的n个人按顺时针方向 围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。2、 本程序利用单向循环链表存储结构实现，按照出列的顺序印出各人的编号。程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n30。3、 程序执行后，要求用户在计算机终端上显示“提示信息”后，用键盘输入“提示信息”中规定的命令，以“回车符”为结束标志。相应的输入数据和运算结果显示在其后。4、 程序的“提示信息”如下：please enter m and n:please enter the password:the output quene is:5、 测试数据m的初值为20；n7，7个人的密码依次为：3,1,7,2,4,8,4,首先m的值为6（正确的出列顺序为6,1,4,7,2,3,5）。二、 概要设计1、为实现上述程序的功能，应以有序链表表示集合。有序表的抽象数据类型定义为：ADT OrderedList数据对象：D=ai|aiElemType，i=1，2， n，n0数据关系：R1=| ai-1，aiD, ai-1ai ，i=2， n 基本操作：InitList(&L) 操作结果：构造一个空的有序表L。DestroyList(&L) 初始条件：有序表L已存在。 操作结果：销毁有序表L。ListEmpty(L)初始条件：有序表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。ListLength(L)初始条件：有序表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i)初始条件：有序表L已存在，并且1iListLength(L)。操作结果：返回L中第i个数据元素。LocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类型的值。操作结果：若L中存在和e相同的元素，则返回位置；否则返回0。InsertElem(&L,e)初始条件：有序表L已存在操作结果：在L中，按有序关系插入值和e相同的数据元素。DeleteElem(&L,i)初始条件：有序表L已存在。操作结果：删除L中第i个数据元素。ListTraverse(L,visit()初始条件：有序表L已存在。操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。 ADT OrderedList2、本程序包含两个模块： 主程序模块： void main() 初始化； 调用函数（接受命令，处理命令）； 有序表单元模块实现有序表的抽象数据类型。 输出函数模块有序表的输出。各模块之间的调用关系如下：主程序模块有序表单元模块输出函数模块三、 详细设计1、 元素类型，结点类型和指针类型。 typedef struct LNode /定义结构体 int num,pwd; /num用来存储人的序号，pwd用来存储人的密码 struct LNode *next;struct LNode *head,*p,*pt; /定义结点2、 创建循环链表函数。int creatLinkList(int n) /参数n传递人数 int i; head=(struct LNode*)malloc(sizeof(struct LNode);/创建一个带头结点的链表 if(!head) return 0; /创建不成功，返回0 p=head; for(i=1;inext=pt; p=pt; p-next=head;/构成循环链表 pt=head; 3、 创建输入密码函数 int enterPwd(int n) /参数n传递人数 int i,j; printf(nplease enter the password:(example:12 13 14)n); for( i=1;inum=i; /num存储人的序号 pt-pwd=j; /pwd存储人的密码 pt=pt-next; pt=p; 4、 创建输出函数 int outList(int m,int n) /参数m、n传递报数上限值和人数 int i,a; for(i=1;i=n;i+) /用一个for循环搜索循环链表 for(a=1;anext; p=pt-next; m=p-pwd; printf(%d ,p-num); /输出人的序号 pt-next=p-next; free(p); /释放动态申请的结点空间 5、 main主函数void main() int m,n; /m为报数上限值，n为人数 printf(nplease enter m and n:(example:12 13 14)n); scanf(%d %d,&m,&n); creatLinkList( n); /调用创建链表函数 enterPwd( n); /调用输入密码函数 printf(nthe output quene is:n); outList( m,n); /调用输出链表函数四、 调试分析1、 由于对循环链表的理解不够，导致编程开始的时候比较困难，查阅有关资料才得以解决。2、 刚开始的时候忽略了一些标识符，使调试程序时费时不少，今后一定要重视这方面的问题。还有一些小问题，比如字母大小写，丢失字母等。3、 链表中的指针运用不够熟练，常常出现一些莫名其妙的问题，调试费时太多。今后一定会多编程，多思索。4、 本实习作业采用数据抽象的程序设计方法，将程序分为四个层次：主函数，创建循环链表函数，输入密码函数，输出链表函数，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确定得到了一次良好的程序设计训练。五、 用户手册1、 本程序运行环境为WindowsXP Professional。2、 进入演示程序后即