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

1、实用文案数据结构课程设计约瑟夫环问题标准文档实用文案2014 年01 月04 日标准文档实用文案目 录目 录3第 1章问题描述 .5第 2章基本要求 .5第 3章概要设计 .73.1数据结构的设计 .73.2算法的设计 .73.3抽象数据类型的设计 .9第 4章详细设计 .104.1设计抽象数据类型对应的C+ 类的定义.104.2设计每个成员函数 .114.3设计主函数 .12第 5章运行与测试 .135.1程序运行环境 .135.2测试数据及测试结果 .135.3程序运行结果截图 .13第 6章总结与心得 .17标准文档实用文案参考文献19附录程序源代码20标准文档实用文案第1章问题描述编号

2、是 1,2,3 n 的 n 个人按照顺时针方向围坐一圈， 每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m ，从第一个人开始顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向的下一个人开始重新从 1 报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。标准文档实用文案第2章 基本要求1) 建立数据模型，确定存储结构；2) 对任意 n 个人，密码为 m ，实现约瑟夫环问题；3) 出圈的顺序可以依次输出。标准文档实用文案第3章概要设计3.1 数据结构的设计解决此问题需要用到单链表的数据结构。约瑟夫

3、环问题，从确定的初报数开始进行，顺着这一方向向前如此循环，若能找到新的密码 m 所对应的数值则直接输出， 若不能找到，继续向下依次寻找，直到找到密码m 所对应的数值，再输出，如此循环。约瑟夫环问题中的数据是人所在的位置，而这种数据存在“第一元素、最后元素”，并且存在唯一的前驱和后继，完全符合单链表的特点。很显然，这需要应用单循环链表的知识。单链表的基本思想就是用指针表示结点之间的逻辑关系，要确定指针变量 p ，结点 p ，指针 p 和 L。3.2 算法的设计按照模块进行划分：（1）链表节点设计struct Lnodeint pwd;/密码int bianhao;/编号struct Lnode*

4、 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

5、-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 Lnodeint

6、 pwd;/ 每个人持有的密码int bianhao;/ 人员编号struct Lnode* next;/ 指向下一个结点;标准文档实用文案第4章详细设计4.1 设计抽象数据类型对应的C+ 类的定义（1）链表节点设计struct Lnodeint 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-ne

7、xt;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 设计每个成员函数intpwd;intbianhao;struct Lnode* next;将密码和编号存入程序中，通过结点指针对所需的数据进行调用。Lnode *temp找到出列对象的同时，输出这个结点的数据域，存储要删除结点，直到程序运行完毕。标准文档

8、实用文案4.3 设计主函数主函数定义输入人数和密码输入相应的初始报数输入操作完成后，输出相应数据标准文档实用文案第 5 章运行与测试5.1 程序运行环境Windows 7 系统下 在 VC+6.0 开发平台进行程序的运行与测试。5.2 测试数据及测试结果数据 1 ：输入人数 5 ，初次报数 3，密码依次为：2 6 8 4 7 ，测试结果：32154数据 2：输入人数 8，初次报数 6，密码依次为： 3 4 8 7 1 6 4 5，测试结果：64573128数据 3 ：输入人数 13 ，初次报数 9 ，密码依次为：4 6 3 7 9 8 2315758 ，测试结果：5.3 程序运行结果截图数据

9、1 ：程序清单标准文档实用文案运行结果：32154数据 2 ：程序清单标准文档实用文案运行结果：64573128数据 3 ：程序清单标准文档实用文案运行结果：标准文档实用文案第 6 章总结与心得我的这次数据结构课程设计的题目是约瑟夫环问题，通过对该题目的设计，使我加深了对数据结构的理解。做什么事情，都要对认真，既然是该你做的事， 肯定是你应该有这个能力，即使能力不够，也是应该借这个机会来培养。 所以放心大胆地做，对自己有信心，就有动力。有人说，世上的事就怕认真二字。确实，做什么，只是认真地去做，踏踏实实，戒躁戒躁，静静地思考，慢慢地进步，真的是天下无难事。这就是我这次课程设计中得到的最大的体会

10、，受益匪浅。通过课程设计我的收获如下：1 、巩固和加深了对数据结构的理解， 提高综合运用本课程所学知识的能力。2 、培养了我选用参考书， 查阅手册及文献资料的能力。 培养独立思考，深入研究，分析问题、解决问题的能力。3 、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。标准文档实用文案4 、通过课程设计， 培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点：1 、认真上好专业实验课，多在实践中锻炼自己。2 、写程序的过程中要考虑周到，严密。3、认真的学习课本知识，并在此基础上学会灵

11、活运用。标准文档实用文案参考文献1 胡明，王涛 等著 . 数据结构（ C+ 版） M. 北京：清华大学出版社， 2011.2 谭浩强 著. C 程序设计（第四版） M. 北京：清华大学出版社， 2005.3 谭浩强 著. C+ 程序设计 M. 北京：清华大学出版社，2004.标准文档实用文案附录程序源代码#includeusing namespace std;struct Lnodeint 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