约瑟夫环实验报告.doc

一需求分析1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。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前面一组为常规数据，后面两组为边缘数据二、概要设计为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为：ADT LinkList数据对象：D= ai | ai termset,i=1,2,n,n=0，termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1= | ai-1, ai D , i=2,n基本操作：LinkList EvaluList(int n);/对单向循环链表进行尾插入赋值int size(LinkList L);/求链表的节点个数Status ScanList(LinkList L);/遍历单向循环链表Status Joseph(LinkList &L,int m);/约瑟夫环的实现此抽象数据类型中的一些常量如下：#define TRUE 1#define FALSE 0#define OK 1typedef int Status;typedef double ElemType;单向循环链表中节点的定义如下所示：typedef struct LNodeint number;int data;struct LNode *next;LNode, *LinkList;三、详细设计#includeusing namespace std;#define TRUE 1#define FALSE 0#define OK 1typedef int Status;typedef double ElemType;/-/定义单向循环链表typedef struct LNodeint number;int data;struct LNode *next;LNode, *LinkList;/-LinkList EvaluList(int n);/对单向循环链表进行尾插入赋值int size(LinkList L);/求链表的节点个数Status ScanList(LinkList L);/遍历单向循环链表Status Joseph(LinkList &L,int m);/约瑟夫环的实现 /-void main()int m,n;cout请输入初始密码(正整数)和人数mn;coutendl请输入n个人的密码endlendl;LinkList L=EvaluList(n);coutn个人的密码为endl;ScanList(L);coutn个人的出列顺序为endl;Joseph(L,m);/-对单向循环链表进行尾插入赋值-LinkList EvaluList(int n)if(n=0)return NULL;int key;coutkey;LinkList L=new LNode;L-data=key;L-number=1;L-next=L;for(int i=2;i=n;i+)LinkList p=new LNode;int key;cout输入第ikey;p-data=key;p-number=i;p-next=L-next;L-next=p;L=L-next;coutnext;return L;/-求链表的节点个数-int size(LinkList L)if(L=NULL)return 0;int i=1;LinkList p=L-next;while(p!=L)i+;p=p-next;return i;/-遍历单向循环链表-Status ScanList(LinkList L)LinkList p=L;if(p=NULL)cout人数为空endl;return FALSE;cout第1个人的密码 ;coutdatanext;while(p!=L)cout第number个人的密码 ;coutdatanext;coutendl;return TRUE;/-约瑟夫环的实现-Status Joseph(LinkList &L,int m)if(L=NULL)cout人数为空，出列结束next!=L)p=p-next;for(int n=size(L); n0 ; n-)cout密码为m,出列编号为;for(int i=1; inext;coutnext-numbernext-data;LinkList q=p-next;p-next=q-next;free(q);return OK;四、调试分析1.当执行输入人数时，输入0程序出现了意想不到的错误，所以再重新设计时加入了对空节点的处理2.在链表节点的设计上，最初是仅包含密码和指针，但是后来考虑到链表节点删除时会带来一系列的编号变化，编号难以确定，所以节点设计上又加了一个编号3.在单向链表的赋值操作时，原本是以一个不变的L作为头结点，但是这种赋值方法带来了诸多变量设计的问题，所以将L为节点，赋值完成后，再让L指向头结点4.程序原本是没有求节点个数的函数，但是在约瑟夫环的实现函数中，节点的个数时时影响着结果的判断，所以加入了该函