数据结构 课程设计报告
题 目：约瑟夫环实验 班 级： 成 员： 指导教师： 完成日期： 第 1 页 共 24 页 1
目录： 实习报告要求................................................................ 2 约瑟夫环实验描述 ........................................................ 3 课程设计报告正文 ................................. 4 一．需求分析................................................................ 4 二．概要设计................................................................ 4 三．详细设计................................................................ 6 1．各模块关键代码及算法的解释： ............. 6 2．函数的调用关系图 ......................... 8 四．调试分析.............................................................. 11 五．用户使用说明 ...................................................... 12 六．测试结果.............................................................. 13 七．小结 ....................................................................... 3 八．附录，带注释的源程序 .......................................... 4 第 2 页 共 24 页 2
实习报告要求 实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容： 1. 需求分析 以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定: (1) 输入的形式和输入值的范围； (2) 输出的形式； (3) 程序所能达到的功能； (4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 2. 概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 3. 详细设计 实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数的调用关系图。 4. 调试分析 内容包括： (1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析； (2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想； (3)经验和体会等。 5. 用户使用说明 说明如何使用你编写的程序，详细列出每一步的操作步骤。 6. 测试结果 列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。 7. 附录 带注释的源程序。可以只列出程序文件名的清单。
实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然也可以应该最后用实验报告纸誉清或打印)。 第 3 页 共 24 页 3
约瑟夫环实验描述 【问题描述】 约瑟夫 (Joseph) 问题的一种描述是：编号为 1，2，… ，n 的n个人按顺时针方向围坐一 圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】 m 的初值为 20；n=7，7 个人的密码依次为：3，1，7，2，4，8，4， 首先 m 值为 6( 正确的出列顺序应为 6，1，4，7，2，3，5) 。 【实现提示】 程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n≤30。 此题所用的循环链表中不需要 “头结点”，请注意空表和非空表的界限。 【选作内容】 向上述程序中添加在顺序结构上实现的部分。 第 4 页 共 24 页 4
课程设计报告正文 一．需求分析 1．输入的形式和输入值的范围 本程序中，输入人数n(n小于等于30)和初始密码m（m大于等于1），然后给每个人输入所持有的密码key，均限定为正整数。用单循环链表模拟约瑟夫环，从队头开始从1报数，报到m的人出列，再把此人的密码赋给m，继续下一轮的报数，直到所有的人出列。结果出来后再选择输入一数字，输入1继续新一轮的游戏，输入0结束，退出此游戏。演示程序以用户和计算机对话方式进行，根据提示信息由用户从键盘输入数据，输入的形式为一个以“回车符”为结束标志的正整数。 2．输出的形式 在计算机终端上显示提示信息之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。运行后输出的结果是约瑟夫环的相关信息和经过报数后出队的人的序列号及相关信息。 程序执行的命令包括：（1）输入人数和初始密码 （2）输入所有人的密码 （3）显示输入的所有人的编号及相应的密码（4）输出出列密码及编号 （5）结束 即：（1）构造单循环链表；（2）输出循环链表的信息；（3）按照出列的顺序输出各人的编号 3．程序功能 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并从屏幕显示出列顺序。 4．测试数据 （1）n=7 ,m=20（常规数据）, 7个人的密码依次为3，1，7，2，4，8，4，正确的输出序列为6，1，4，7，2，3，5. （2）n=5，m=6（常规数据），5个人的密码依次为2，5，4，6，7，正确的输出序列为1,3,4,2,5。 （3）n=31, m=3（错误数据），“这个人数太大了，请重新输入”。 （4）n=0, m=3（错误数据），“这个约瑟夫环里没有人！”。 （5）n=1, m=4,（边缘数据），正确的输出序列为1。 （6）n=3, m=1,（边缘数据），正确的输出序列为1，3，2。 第一组为常规数据，中间两组为错误数据，后面两组为边缘数据。 5．设计思路及方案 用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出队的函数、主函数等函数。
二．概要设计 1．抽象数据类型的定义 第 5 页 共 24 页 5
为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： 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; 2．主程序的流程 void main() { 初始化； 输入数据； 执行功能； 显示结果； } 3．模块的设计及介绍 （1）主程序模块 Void main（）{ 初始化； do { 接受命令； 处理命令； }while（“命令”=“退出”）； } （2）创建链表模块 Static void creatlist（行参）{