资源描述：
《实验一---约瑟夫环》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、实验报告一题目：约瑟夫环路班级：信息管理与信息系统姓名：王志钢学号：20081121614指导教师：孟繁军完成日期：2010.6.25一．需求分析1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中
2、规定的运算命令，相应的输入数据和运算结果显示在其后。3.程序执行的命令包括：1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束4.测试数据(1)m=20,n=7,7个人的密码依次为3，1，7，2，4，8，4(2)m=20,n=1(3)m=20,n=0前面一组为常规数据，后面两组为边缘数据二、概要设计为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为：ADTLinkList{数据对象：D={ai
3、ai∈termset,i=1,2,……n,n>=0}，termset中每个元素包含编号
4、，密码，和一个指向下一节点的指针数据关系：R1={
5、ai-1,ai∈D,i=2,……n}基本操作：LinkListEvaluList(intn);//对单向循环链表进行尾插入赋值intsize(LinkListL);//求链表的节点个数StatusScanList(LinkListL);//遍历单向循环链表StatusJoseph(LinkList&L,intm);//约瑟夫环的实现}此抽象数据类型中的一些常量如下：#defineTRUE1#defineFALSE0#defineOK1typedefintStatus;typedefdoubleElemType;单向循环链
6、表中节点的定义如下所示：typedefstructLNode{intnumber;intdata;structLNode*next;}LNode,*LinkList;三、详细设计编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。四．运行环境Dev-C++五．调试分析1.当执行输入人数时，输入0程序出现了意想不到的错误，所
7、以再重新设计时加入了对空节点的处理2.在链表节点的设计上，最初是仅包含密码和指针，但是后来考虑到链表节点删除时会带来一系列的编号变化，编号难以确定，所以节点设计上又加了一个编号3.在单向链表的赋值操作时，原本是以一个不变的L作为头结点，但是这种赋值方法带来了诸多变量设计的问题，所以将L为节点，赋值完成后，再让L指向头结点六、用户使用说明：题目：约瑟夫环路本程序将利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。[测试数据]输入m的初值为20，n的初值7；依次输入密码：3，1，7，2，4，8，4输出：当前密码为，出列编号为七、源代码#includeusin
8、gnamespacestd;#defineTRUE1#defineFALSE0#defineOK1typedefintStatus;typedefdoubleElemType;//-----------------------------------//定义单向循环链表typedefstructLNode{intnumber;intdata;structLNode*next;}LNode,*LinkList;//-----------------------------------LinkListEvaluList(intn);//对单向循环链表进行尾插入赋值intsize(LinkLis
9、tL);//求链表的节点个数StatusScanList(LinkListL);//遍历单向循环链表StatusJoseph(LinkList&L,intm);//约瑟夫环的实现//-------------------------------------------------voidmain(){intm,n;cout<<"请输入初始密码(正整数)和人数"<>m>>n;cout<
