约瑟夫环问题课程毕业设计（论文）说明书.doc

目录： 摘 要 2 前言 3 课程设计报告正文 4 一．需求分析 4 二．概要设计 5 三．详细设计 7 1．各模块关键代码及算法的解释： 7 2．函数的调用关系图 10 四．调试分析 13 五．用户使用说明 15 六．测试结果 16 七．源程序（带注释） 22 总结 26 参考文献 26 致谢 28 附录，带注释的源程序 29 摘 要 当约瑟夫环中某人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。 为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：int quit[n];n为一个根据实际问题定义的一个足够大的整数。 解决问题的核心步骤： 1.建立一个具有n个链结点，无头结点的循环链表 2.确定第1个报数人的位置 3.不断地从链表中删除链结点，直到链表为空约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。 约瑟夫环问题的具体描述是：设有编号为1，2，……，n的n(n0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。1．输入的形式和输入值的范围 本程序中，输入，，均限定为正整数输入的形式为一个以“回车符”为结束标志的正整数。2．输出的形式3．程序功能 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并从屏幕显示出列顺序。 #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() { 初始化； 输入数据； 执行功能； 显示结果； } Void main（）{ 初始化； do { 接受命令； 处理命令； }while（“命令”=“退出”）； } （2）创建链表模块 Static void creatlist（行参）{ 初始化； For{ 接受命令； 处理命令 } } （3）输出链表信息模块 static void PrntList(参数){ 定义变量并初始化； 输出命令； } （4）删除结点也就是出队模块 static void StatGame(参数){ 定义变量并初始化； While{ 开始报数； 输出结果；}} 4．各程序模块之间的层次(调用)关系。 本程序包含以下模块： （1）主程序模块： （2）各功能模块——实现顺序表的各项功能。 各模块的调用关系： 主程序 ↓ 各功能模块circularlist pHead=NULL; int main(void) { int n, m， iflag=1 while(iflag=1){ printf(请输入总人数n=); scanf(%d,n); printf(\n再请输入初始报数上限m=); scanf(%d,m)； CreatList(pHead,n); printf(\n输出所有人的信息如下:\n); PrntList(pHead); printf(\n按照出列顺序输出每个人的编号:\n); StatGame(pHead, m); printf(\n约瑟夫环的游戏完成!\n); printf(输入1开始建环做游戏，输入0退出该游戏，请选择!);scanf(%d,i); } return 0; } 程序解释：该