约瑟夫环实验报告

题目：约瑟夫环（Josephus）问题班级：自动化05姓名：刘丽丽学号：10054107完成日期：2011.12.20一、需求分析1、问题描述：设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此反复直到所有的人全部出列为止。2、本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号，从第s个人开始的标号s以及一个使游戏循环至结束的密码m），模拟约瑟夫环的显示过程，按照出列的顺序印出各人的编号。3、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中需要输入的数据，以“回车符”为结束标志。相应的输入数据和运算结果显示在其后。4、程序执行的命令包括：1）建立长度为n的链表；2)将开始报数的人的序列号置为1,并从1开始数到m;2）连续删除第m个元素，同时打印m并重新计数直至结束；课内实验报告5、测试数据假设总人数n=8，从第s=1个人开始，m的初值为4；则正确的输出顺序为：48521376。二、概要设计1、线性表的抽象数据类型的定义:ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit())线性表遍历初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(＆L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：将e的值赋值给L中第i个元素。ListInsert(&L,i,e)初始条件：L已存在，1≤i≤LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：L已存在，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList2、程序包含两个模块：1）主程序模块：voidmain（）{初始化；do{接受命令；处理命令；}while（命令！=“退出“）；}2）循环链表单元模块——实现循环链表的抽象数据类型。各模块之间的调用关系如下：主程序模块循环链表单元模块三、详细设计：1、元素类型，结点类型和指针类型。typedefstruct_Node{intinfo;struct_Node*next;}Node;//结构体info为节点编号，next为指向下一个节点的指针2//删除node之后的第一个节点Node*delNode(Node*node){Node*temp=NULL;if(node!=NULL&&node-next!=node){temp=node-next;node-next=node-next-next;}returntemp;}//在node之后添加一个节点intaddNode(Node*node,intinfo){Node*temp;if(node!=NULL){temp=(Node*)malloc(sizeof(Node));temp-info=info;temp-next=node-next;node-next=temp;return1;}return0;}//构建一个长度为n的约瑟夫环Node*buildLink(intn){Node*head=(Node*)malloc(sizeof(Node));inti;head-info=1;head-next=head;for(i=n-1;i0;i--){addNode(head,i+1);}returnhead;}intmain(){intguyNum;intcountNum;intbeginnum;inti;Node*guys;printf(Pleaseinputthenumberoftheguywhotakepartinthisgame\n);scanf(%d,&guyNum);printf(Andinputthenumberyouwillcount\n);scanf(%d,&countNum);printf(pleaseinputthebeginningnumber\n);scanf(%d,&beginnum);guys=buildLink(guyNum);for(i=1;ibeginnum;i++){guys=guys-next;}printf(Thesequencyis);while(countNum!=1&&guys!=guys-next){//数countNum下，i=1因为当前节点被数作1//icountNum-1因为单向链表只能删后一个节点，所以在数到最后一个之前删除for(i=1;icountNum-1;i++){guys=guys-next;}printf(%d,delNode(guys)-info);//将在for循环中省去的1次补上guys=guys-next;}printf(%d,guys-info);if(countNum==1){for(i=1;i=guyNum-1;i++){guys=guys-next;printf(%4d,guys-info);}}return0;}四、调试分析：1、本实习作业采用数据抽象的程序设计方法，将程序分为四个层次：主函数、单向循环链表函数、插入结点并编号的函数、链表输出函数，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性。2、由于对循环链表的算法设计不熟，在早期调试的过程中出现了很多问题，尤其发现自己对指针的用法掌握得不到位。3、经常会将链表中的指针所指位置混淆，以致在头结点的问题上徘徊多时，今后应注意这方面的问题。4、此单项循环链表采用了带头结点的链表，并增设尾指针和表的长度两个标识，各种操作的算法时间复杂度比较合理5、算法的时空分析1）本算法的时间复杂度为：o(mn)2）本算法的空间复杂度为：o(2n+5)五、用户手册1、本程序的运行环境为Win7操作系统，MicrosoftVisualc++6.0，执行文件为：JosephusHuan.exe；2、进入演示程序后的用户界面为：3、进入“Pleaseinputthenumberoftheguywhotakepartinthisgame”的命令后，即提示键入报数的总人数，接受输入之后即显示报数的总人数；4、进入“Andinputthenumberyouwillcount”的命令后，即提示键入出列的人所报的数字，接受输入之后即显示密码；5、进入“pleaseinputthebeginningnumber”的命令后，即提示键入开始报数人的序列号，接受输入之后即显示开始报数人的序列号；6、进入“Thesequencyis”的命令后，即提示键入出队的序列，接受之后即显示出队的序列号；7、接受其他命令后即执行相应运算和显示相应的结果。3、接受其他命令后即执行相应运算和显示相应的结果六、测试结果1、依次输入总人数n、从第s个人开始报数以及密码m后的运行结果为：2、最后的运行结果：七、附录源程序的文件清单名：Voidmain//主程序LNode.H//循环链表类型node.H//元素结点实现单元