约瑟夫环实验报告.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.08M 资料格式：doc 举报版权申诉

baidu_35145586-9880209-4744300845365776884.doc.pdf-第1页.png

第1页 / 共8页

baidu_35145586-9880209-4744300845365776884.doc.pdf-第2页.png

第2页 / 共8页

baidu_35145586-9880209-4744300845365776884.doc.pdf-第3页.png

第3页 / 共8页

baidu_35145586-9880209-4744300845365776884.doc.pdf-第4页.png

第4页 / 共8页

baidu_35145586-9880209-4744300845365776884.doc.pdf-第5页.png

第5页 / 共8页

baidu_35145586-9880209-4744300845365776884.doc.pdf-第6页.png

第6页 / 共8页

baidu_35145586-9880209-4744300845365776884.doc.pdf-第7页.png

第7页 / 共8页

baidu_35145586-9880209-4744300845365776884.doc.pdf-第8页.png

第8页 / 共8页

文本预览

一．需求分析 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 1

typedef int Status; typedef double ElemType; 单向循环链表中节点的定义如下所示： typedef struct LNode { int number; int data; struct LNode *next; }LNode, *LinkList; 三、详细设计 #include using namespace std; #define TRUE 1 #define FALSE 0 #define OK 1 typedef int Status; typedef double ElemType; //----------------------------------- //定义单向循环链表 typedef struct LNode { int 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<<"请输入初始密码(正整数)和人数"<>m>>n; cout<>key; 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<<"输入第"<>key; p->data=key; p->number=i; p->next=L->next; L->next=p; L=L->next; cout<next; 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<<"人数为空"<data<next; while(p!=L) { } cout<<"第"<number<<"个人的密码 "; cout<data<next; cout<next!=L)

p=p->next; for(int n=size(L); n>0 ; n--) { } cout<<"密码为"<next; cout<next->number<next->data; LinkList q=p->next; p->next=q->next; free(q); return OK; } 四、调试分析 1.当执行输入人数时，输入 0 程序出现了意想不到的错误，所以再重新设计时加入了对空节点的处理 2.在链表节点的设计上，最初是仅包含密码和指针，但是后来考虑到链表节点删除时会带来一系列的编号变化，编号难以确定，所以节点设计上又加了一个编号 3.在单向链表的赋值操作时，原本是以一个不变的 L 作为头结点，但是这种赋值方法带来了诸多变量设计的问题，所以将 L 为节点，赋值完成后，再让 L 指向头结点 4.程序原本是没有求节点个数的函数，但是在约瑟夫环的实现函数中，节点的个数时时影响着结果的判断，所以加入了该函数 5.考虑到时间问题，密码采用对剩余节点取余来减少遍历次数 6.当程序大体完成时，却又在调试过程中发现出列次序总是错误的，才想到第一次指向时应该让变化的指针指向尾节点，这样可以减少当密码为 1 时程序的设计量五、测试结果（第一组为常规数据，二、三两组为边缘数据）

分享到：

赞收藏

资料库

约瑟夫环实验报告.doc

相关推荐

课程资源

热门标签

最新资料