约瑟夫环实习报告.docVIP

课程设计报告 需求分析 本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表和非空表的界限。 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。 程序执行的命令包括： 构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码； 3）结束。 4、测试数据 1）m的初始值为20； 2）n=7，7个人的密码依次为：3、1、7、2、4、8、4。 3）首先m值为6，正确的出列顺序应为6、1、4、7、2、3、5。 二、概要设计 为实现上述程序功能，应以单向循环链表表示约瑟夫环。为此，需要两个抽象数据类型：单向循环链表和约瑟夫环。 1）、单向循环链表的抽象数据类型定义为： ADT List{ 数据对象：D={ai｜ai∈Elemset,i=1,2,…,n,n≥0} 数据关系：R1={＜a(i-1),ai＞｜a(i-1),ai∈D,i=2,…n} 基本操作： InitList(L) 操作结果：构造一个空的链表L。 DestroyList(L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ListLength(L) 初始条件：线性表L已存在。 操作结果：返回L中数据元素个数。 GetElem(L,i,e) 初始条件：线性表L已存在，1≤i≤ListLength(L)。 操作结果：用e返回L中第i个数据元素的值。 ListInsert(L,I,e) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 ListDelete(L,i,e) 初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L,visit()) 初始条件：线性表L已存在。 操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。 }ADT List 2)约瑟夫环的抽象数据类型定义为： ADT Set{ 数据对象：D={ai｜ai为用户输入的数字密码，i=1,2,…,n,1≤n≤7} 数据关系：{} 基本操作： CreatSet(L，s) 初始条件：L为单向循环链表。 操作结果：对链表中的数据域进行赋值。 DeleteSet(L,i,e) 初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 PrintSet(L) 初始条件：链表L已存在。 操作结果：按输出次序显示每个人的密码。 }ADT Set 3)本程序包含四个模块： 1、主程序模块： Void main(){ 初始化； Do{ 接受命令； 处理命令； } while (“命令”=”退出”)； } 2、约瑟夫环单元模块——实现约瑟夫环的抽象数据类型； 3、单向循环链表单元模块——实现单向循环链表的抽象数据类型； 4、结点结构单元模块——定义单向循环链表的结点结构。 各模块之间的调用关系如下： 结点结构单元模块 ↓ 单向循环链表单元模块 ↓ 约瑟夫环单元模块 ↓ 主程序模块 详细设计 元素类型、结点类型和指针类型 Typedef char ElemType; //元素类型 Typedef struct NodeType{ ElemType data; ElemType *next; } ElemTyp