约瑟夫环的实现.docVIP

实验一：约瑟夫环问题 题目：编制一个求解约瑟夫环的程序 班级： 姓名： 学号： 完成日期： 一.需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.程序的演示，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入数据，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和总人数 2）依次输入所有人的密码 3）显示输入的所有人的编号及相应的密码 4）输出出列人的密码及编号 5）程序结束 4.测试数据 (1)m=6, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1，此人的密码是20 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二.概要设计 1.为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针 数据关系：R1={ai-1,ai | ai-1, ai ∈D , i=2,……n} 基本操作： LinkList AddList(int n);//对单向循环链表进行尾插入赋值 初始条件：存在一个空链表，并以此向其中插入元素 操作结果：向单循环链表中进行尾插入赋值 int ListLength(LinkList L);//求链表的节点个数 初始条件：链表L已存在 操作结果：返回链表L的长度 Status yuesefu(LinkList L,int m);//约瑟夫环的实现 初始条件：实现约瑟夫环的链表L已存在 操作结果：依次输出出列人的密码和出列顺序 } 2.此抽象数据类型中的一些常量如下： #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 typedef int Status; typedef double ElemType; 3.单向循环链表中节点的定义如下所示： typedef struct LNode { int number; ElemType data; struct LNode *next; }LNode,*LinkList; 4.本程序包含三个模块 1).主程序模块 void main( ) { 初始化； 接受命令； 函数实现； } 2).链表模块——实现链表的抽象数据类型 3).约瑟夫环模块——实现约瑟环 各模块之间的调用关系如下： 主程序模块 链表模块 约瑟夫环的实现 5.约瑟夫环中出列一个人的伪码算法： 约瑟夫环的实现(开始) { 判断链表中的数据元素是否为空； 利用P指针依次沿链表中的元素向后跳跃； 循环 {利用P指针依次沿链表移动，共移动(密码-1)次； 直到指向满足上一密码的人的结点； 依次输出出列人的密码和编号； 再把该出列结点的下一结点的编号赋给一个新的变量； 删除该结点，链表长度减一； 依次循环，直到所有人出列为止；} }//结束 三.详细设计 #include stdafx.h #includeiostream using namespace std; #define MAXSIZE 100 //链表的最大长度 #define TRUE 1 #define FALSE 0 typedef int Status; typedef double ElemType; //函数定义 LinkList AddList(int n); int ListLength(LinkList L); Status yuesefu(LinkList L,int m); /********************************************************** 先创建一个单向循环链表； ***********************************************************/ typedef struct LNode { int number; ElemType data; struct LNode *next; }LNode,*LinkList; /****