数据结构Ⅰ课程设计约瑟夫环.doc

，目录数据结构课程设计 约瑟夫环问题 2014年01月04日 第3章 概要设计目 录目 录2第1章 问题描述3第2章 基本要求4第3章 概要设计53.1 数据结构的设计53.2 算法的设计63.3抽象数据类型的设计8第4章 详细设计104.1设计抽象数据类型对应的C+类的定义104.2 设计每个成员函数114.3设计主函数12第5章 运行与测试135.1程序运行环境135.2测试数据及测试结果135.3程序运行结果截图16第6章 总结与心得17参考文献18附录 程序源代码1918 第2章 基本要求第1章 问题描述 编号是1,2,3n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。第2章 基本要求1) 建立数据模型，确定存储结构；2) 对任意n个人，密码为m，实现约瑟夫环问题；3) 出圈的顺序可以依次输出。 第3章 概要设计第3章 概要设计3.1 数据结构的设计 解决此问题需要用到单链表的数据结构。约瑟夫环问题，从确定的初报数开始进行，顺着这一方向向前如此循环，若能找到新的密码m所对应的数值则直接输出，若不能找到，继续向下依次寻找，直到找到密码m所对应的数值，再输出，如此循环。约瑟夫环问题中的数据是人所在的位置，而这种数据存在“第一元素、最后元素”，并且存在唯一的前驱和后继，完全符合单链表的特点。 很显然，这需要应用单循环链表的知识。单链表的基本思想就是用指针表示结点之间的逻辑关系，要确定指针变量p，结点p，指针p和L。3.2 算法的设计按照模块进行划分： （1）链表节点设计 struct Lnode int pwd;/密码 int bianhao;/编号 struct Lnode* next; ; （2）采用头插法构造链表，由此必须倒着输入个人的密码 和编号，由此可计一个线性表作为缓存暂时保存个人密码和编号。an=pwd。n为编号，pwd为n的人的密码。 （3）将上述2中缓存的数据从an到a1一次赋给链表L： Lnode *L,*p; L=new Lnode; L-next=NULL; for(i=num;i0;i-) p=new Lnode; p-pwd=ai-1; p-bianhao=i; p-next=L-next; L-next=p; （4）用循环模拟报数的过程 p=L； while(num0) for(i=1;inext; if(p-next=NULL) p-next=L-next; Lnode *temp; temp=p-next; coutbianhaonext=temp-next; m=temp-pwd; free(temp); num-; num是用来控制循环次数的变量，值为总人数n，每完成一次删除操。 即每有一个人出列，num减1。 循环中设置了中间变量temp用来存储要删除的结点的指针，以保证删除操 作不会导致链表指针无法找到下一结点。结束后free掉temp。（5）删除结点，即找到出列对象的同时输出这个结点的数据域：编号 和密码！3.3抽象数据类型的设计采用类C语言定义相关的数据类型 struct Lnode int pwd; /每个人持有的密码 int bianhao; /人员编号 struct Lnode* next; /指向下一个结点 ; 第5章 运行与测试第4章 详细设计4.1设计抽象数据类型对应的C+类的定义 （1）链表节点设计 struct Lnode int pwd;/密码 int bianhao;/编号 struct Lnode* next; ; （2）将数据从an到a1（运用结点、链表指针）一次赋给链表L： Lnode *L,*p; L=new Lnode; L-next=NULL; for(i=num;i0;i-) p=new Lnode; p-pwd=ai-1; p-bianhao=i; p-next=L-next; L-next=p; （3）运用循环模拟报数过程 p=L； while(num0) for(i=1;inext; if(p-next=NULL) p-next=L-next; Lnode *temp; temp=p-next; coutbianhaonext=temp-next; m=temp-pwd; free(temp); num-; 4.2 设计每个成员函数 int pwd; int bianhao; struct Lnode* next; 将密码和编号存入程序中，通过结点指针对所需的数据进行调用。 Lnode *temp 找到出列对象的同时，输出这个结点的数据域，存储要删除结点，直到程序运行完毕。4.3设计主函数主函数 定义输入人数和密码 输入相应的初始报数 输入操作完成后，输出相应数据第5章 运行与测试5.1程序运行环境Windows 7系统下 在VC+6.0 开发平台进行程序的运行与测试。5.2测试数据及测试结果数据1：输入人数5，初次报数3，密码依次为： 2 6 8 4 7，测试结果：3 2 1 5 4 数据2：输入人数8，初次报数6，密码依次为： 3 4 8 7 1 6 4 5 ，测试结果：6 4 5 7 3 1 2 8 数据3：输入人数13，初次报数9，密码依次为： 4 6 3 7 9 8 2 3 1 5 7 5 8，测试结果：9 10 2 8 13 12 6 11 3 7 4 5 1 5.3程序运行结果截图 数据1：程序清单 运行结果： 3 2 1 5 4 数据2：程序清单 运行结果： 6 4 5 7 3 1 2 8数据3：程序清单 运行结果： 9 10 2 8 13 12 6 11 3 7 4 5 1 参考文献第6章 总结与心得我的这次数据结构课程设计的题目是约瑟夫环问题，通过对该题目的设计，使我加深了对数据结构的理解 。做什么事情，都要对认真，既然是该你做的事，肯定是你应该有这个能力，即使能力不够，也是应该借这个机会来培养。所以放心大胆地做，对自己有信心，就有动力。有人说，世上的事就怕认真二字。确实，做什么，只是认真地去做，踏踏实实，戒躁戒躁，静静地思考，慢慢地进步，真的是天下无难事。这就是我这次课程设计中得到的最大的体会，受益匪浅。 通过课程设计我的收获如下：1、 巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、 培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、 通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、 通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。 根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。 3、认真的学习课本知识，并在此基础上学会灵活运用。附录参考文献1 胡明，王涛 等著. 数据结构（C+版）M. 北京：清华大学出版社，2011.2 谭浩强 著. C程序设计（第四版）M. 北京：清华大学出版社，2005.3 谭浩强 著. C+程序设计 M. 北京：清华大学出版社，2004.附录附录 程序源代码#include using namespace std; struct Lnode int pwd; int bianhao; struct Lnode* next; ; int main() int i=0; int num,m; cout输入人数：num; cout输入初始报数:m; cout输入密码:n; int a100; for(i=0;iai; Lnode *L,*p; L=new Lnode; L-next=NULL; for(i=num;i0;i-) p=new Lnode; p-pwd=ai-1; p-bianhao=i; p-next=L-next; L-n