《数据结构Ⅰ课程设计约瑟夫环.doc》由会员分享，可在线阅读，更多相关《数据结构Ⅰ课程设计约瑟夫环.doc（18页珍藏版）》请在三一文库上搜索。
1、数据结构课程设计约瑟夫环问题2014年01月04日目录2第1章问题描述3第2章基本要求3第3章概要设计53.1数据结构的设计53.2算法的设计53.3抽象数据类型的设计7第4章详细设计84.1设计抽象数据类型对应的C卄类的定义84.2设计每个成员函数94.3设计主函数10第5章 运行与测试115.1程序运行环境115.2测试数据及测试结果115.3程序运行结果截图11第6章 总结与心得15参考文献16附录 程序源代码17第1章问题描述编号是1,2,3n的n个人按照顺时针方向围坐一圈，每个 人持有一个密码（正整数）。一开始任选一个正整数作为报数上 限值m,从第一个人开始顺时针方向自1开始顺序报数
2、，报到m 时停止报数。报m的人出列，将他的密码作为新的m值，从他 在顺吋针方向的下一个人开始重新从1报数，如此下去，直到所 有人全部出列为止。设计一个程序来求出出列顺序。第2章基本要求1）建立数据模型，确定存储结构；2）对任意n个人，密码为m,实现约瑟夫环问题;3）出圈的顺序可以依次输出。第3章概要设计3.1数据结构的设计解决此问题需要用到单链表的数据结构。约瑟夫环问题，从 确定的初报数开始进行，顺着这一方向向前如此循环，若能找到 新的密码m所对应的数值则直接输出，若不能找到，继续向下依 次寻找，直到找到密码m所对应的数值，再输岀，如此循环。约 瑟夫环问题中的数据是人所在的位置，而这种数据存在
3、“第一元 素、最后元素”，并且存在唯一的前驱和后继，完全符合单链表 的特点。很显然，这需要应用单循环链表的知识。单链表的基本思想就是用指针衣示结点之间的逻辑关系，要 确定指针变量P，结点p，指针p和L。3.2算法的设计按照模块进行划分：（1）链表节点设计stiuct Lnodeint pwd;/ 密码int biaiiliao;/编号stmct Lnode* next;（2）采用头插法构造链表，由此必须倒着输入个人的密码 和编号，由此可计一个线性表作为缓存暂时保存个人密码和 编号。an=pwdo 11为编号，pwd为n的人的密码。（3）将上述2中缓存的数据从an到al次赋给链表L：Lnode
4、*L,*p;L=new Lnode;L->next=NULL; for(i=num;i>0;i) p=new Lnode;p->pwd=ai-l; p->biaiiliao=i; p ->next=L ->next; T.->next=p;(4) 用循环模拟报数的过程p=L；while(num>0) fbr(i=l;i<m;i+) p=p->next;if(p->next=NULL) p->next=L->next;Lnode *temp;temp=p > next;cout«tenip->bi
5、aiiliao«n n”；p->next=temp->iiext;m=temp->pwd;free(temp);num-;num是用來控制循环次数的变量，值为总人数m每完 成一次删除操。即每有一个人出列，num减1。循环屮设置了中间变量temp用来存储要删除的结点的指 针，以保证删除操作不会导致链表指针无法找到下一结点。 结束后fie掉temp。（5）删除结点，即找到出列对象的同时输出这个结点的 数据域：编号 和密码！3.3抽象数据类型的设计采用类c语言定义相关的数据类型stnict Lnodeint pwd; 每个人持有的密码 int biaiiliao; 人员编
6、号 struct Lnode* next; /指向下一个结点；第4章详细设计4.1设计抽象数据类型对应的C+类的定义（1）链表节点设计stnict Lnodeint pwd;/ 密码int biaiiliao;/编号stnict Lnode* next;（2）将数据从an到al（运用结点、链表指针）一次赋给链 表L：Lnode *L,*p;L=new Lnode;L->next=NULL; fbr（i=num;i>O;i） p=new Lnode;p->pwd=ai-l; p->biaiiliao=i; p > next=L ->next; L->ne
7、xt=p;（3）运用循环模拟报数过程p=L；wliile(iium>0)fbr(i=l;i<m;i+)p=p->next;if(p->next=NULL) p> next=L >next;Lnode *temp;temp=p > next;cout«temp->biaiiliao«n nu;p> next=temp->next;m=temp->pwd;free(temp);num;4.2设计每个成员函数iiit pwd;int biaiiliao;stmct Lnode* next;将密码和编号存入程序中，通
8、过结点指针对所需的数据进行 调用。Lnode *temp找到出列对象的同吋，输出这个结点的数据域，存储要删除 结点，直到程序运行完毕。4.3设计主函数主函数定义输入人数和密码输入相应的初始报数输入操作完成后，输出相应数据第5章运行与测试5.1程序运行环境Windows 7系统下 在VC+6.0开发平台进行程序的运行与测 试。5.2测试数据及测试结果数据1：输入人数5,初次报数3,密码依次为：2 6 84 7,测试 结果：32 154数据2：输入人数8,初次报数6,密码依次为：3 4 8 7 1 64 5 , 测试结果：64 5 7 3 1 2 8数据3：输入人数13,初次报数9,密码依次为：4
9、 6 3 7 9 8 2 3 1 5 7 5 8,测试结果：9 102 8 13 12 6 11 3 74 5 15.3程序运行结果截图数据1:程序清单运行结果：32154数据2：程序清单常入初始报数：P 齣入密码： 348716456428A按任意键继续Press any key to continue运行结果：64 5 7 3 1 28数据3：程序清单當入初始报数：9输入密码：463798231575891081312按任意键继续运行结果：9 102 8 13 12 6 11 3 74 5 1总结与心得我的这次数据结构课程设计的题日是约瑟夫环问题，通 过对该题日的设计，使我加深了对数据结构
10、的理解。做什么事 情，都要对认真，既然是该你做的事，肯定是你应该有这个能力, 即使能力不够，也是应该借这个机会来培养。所以放心大胆地做, 对自己有信心，就有动力。有人说，世上的事就怕认真二字。确 实，做什么，只是认真地去做，踏踏实实，戒躁戒躁，静静地思 考，慢慢地进步，真的是天下无难事。这就是我这次课稈设计中 得到的最大的体会，受益匪浅。通过课程设计我的收获如下：1、巩固和加深了对数据结构的理解，提高综合运用本课程所 学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养 独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设讣、编程调试，掌握应用软件 的分析
11、方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立 正确的生产观念、经济观念和全局观念。根据我在课程设计中遇到得问题，我将在以后的学习过程中 注意以下儿点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、认真的学习课本知识，并在此基础上学会灵活运用。参考文献1 胡明，王涛等著.数据结构（C+版）M.北京：清华大学 出版社，2011.2 谭浩强著.C程序设计（第四版）M.北京：清华大学出版 社，2005.3 谭浩强著.C卄程序设计M.北京:清华大学出版社，2004.附录程序源代码# include<iostream>usin
12、g namespace std; stmct Lnode int pwd; int biaiiliao;stnict Lnode* next;iiit main()int i=0;int numjn;cout«n输入人数cin»num;coutvv”输入初始报数:” vv”n”； cin»m;coutvv”输入密码:y v”n” ；int a100;fbr(i=0; i<num; i+) cin»ai;Lnode *L/p;L=nev Lnode;L->next=NULL;for(i=num;i>0;i) p=new Lnode; p->pwd=ai-l; p->bianhao=i;p> next=L >next;L->next=p;p=L;while(num>0)for(i= 1p=p->next; if(p->next=NULL) p->next=L->next; Lnode *temp;temp=p->next;cout«temp->biaiiliao«n iiH;p >next=temp >next;m=temp->pwd;fiee(temp);num-;system(” pause”)；return 0;