版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
年4月19日数据结构Ⅰ课程设计约瑟夫环文档仅供参考数据结构Ⅰ课程设计约瑟夫环问题01月04日目录TOC\o"1-3"\h\u8534目录 212599第1章问题描述 37780第2章基本要求 424538第3章概要设计 587543.1数据结构的设计 586853.2算法的设计 6321673.3抽象数据类型的设计 83115第4章详细设计 1092714.1设计抽象数据类型对应的C++类的定义 10223294.2设计每个成员函数 11150914.3设计主函数 123833第5章运行与测试 13299465.1程序运行环境 13157885.2测试数据及测试结果 13206465.3程序运行结果截图 1630970第6章总结与心得 178934参考文献 1810324附录程序源代码 19第1章问题描述编号是1,2,3……n的n个人按照顺时针方向围坐一圈,每个人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将她的密码作为新的m值,从她在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。设计一个程序来求出出列顺序。
第2章基本要求1)建立数据模型,确定存储结构;2)对任意n个人,密码为m,实现约瑟夫环问题;3)出圈的顺序能够依次输出。
第3章概要设计3.1数据结构的设计解决此问题需要用到单链表的数据结构。约瑟夫环问题,从确定的初报数开始进行,顺着这一方向向前如此循环,若能找到新的密码m所对应的数值则直接输出,若不能找到,继续向下依次寻找,直到找到密码m所对应的数值,再输出,如此循环。约瑟夫环问题中的数据是人所在的位置,而这种数据存在“第一元素、最后元素”,而且存在唯一的前驱和后继,完全符合单链表的特点。很显然,这需要应用单循环链表的知识。单链表的基本思想就是用指针表示结点之间的逻辑关系,要确定指针变量p,结点p,指针p和L。3.2算法的设计按照模块进行划分:(1)链表节点设计structLnode{intpwd;//密码intbianhao;//编号structLnode*next;};(2)采用头插法构造链表,由此必须倒着输入个人的密码和编号,由此可计一个线性表作为缓存暂时保存个人密码和编号。。n为编号,pwd为n的人的密码。(3)将上述2中缓存的数据从a[n]到一次赋给链表L:Lnode*L,*p;L=newLnode;L->next=NULL;for(i=num;i>0;i--){p=newLnode;p->pwd=a[i-1];p->bianhao=i;p->next=L->next;L->next=p;}(4)用循环模拟报数的过程p=L;while(num>0){for(i=1;i<m;i++){p=p->next;if(p->next==NULL){p->next=L->next;}}Lnode*temp;temp=p->next;cout<<temp->bianhao<<"\n";p->next=temp->next;m=temp->pwd;num--;}num是用来控制循环次数的变量,值为总人数n,每完成一次删除操。即每有一个人出列,num减1。循环中设置了中间变量temp用来存储要删除的结点的指针,以保证删除操作不会导致链表指针无法找到下一结点。结束后掉temp。(5)删除结点,即找到出列对象的同时输出这个结点的数据域:编号和密码!3.3抽象数据类型的设计采用类C语言定义相关的数据类型structLnode{intpwd;//每个人持有的密码intbianhao;//人员编号structLnode*next;//指向下一个结点};第4章详细设计4.1设计抽象数据类型对应的C++类的定义(1)链表节点设计structLnode{intpwd;//密码intbianhao;//编号structLnode*next;};(2)将数据从a[n]到一次赋给链表L:Lnode*L,*p;L=newLnode;L->next=NULL;for(i=num;i>0;i--){p=newLnode;p->pwd=a[i-1];p->bianhao=i;p->next=L->next;L->next=p;}(3)运用循环模拟报数过程p=L;while(num>0){for(i=1;i<m;i++){p=p->next;if(p->next==NULL){p->next=L->next;}}Lnode*temp;temp=p->next;cout<<temp->bianhao<<"\n";p->next=temp->next;m=temp->pwd;num--;}4.2设计每个成员函数intpwd;intbianhao;structLnode*next;将密码和编号存入程序中,经过结点指针对所需的数据进行调用。Lnode*temp找到出列对象的同时,输出这个结点的数据域,存储要删除结点,直到程序运行完毕。4.3设计主函数主函数{定义输入人数和密码输入相应的初始报数输入操作完成后,输出相应数据}
第5章运行与测试5.1程序运行环境Windows7系统下在VC++6.0开发平台进行程序的运行与测试。5.2测试数据及测试结果数据1:输入人数5,初次报数3,密码依次为:26847,测试结果:32154数据2:输入人数8,初次报数6,密码依次为:34871645,测试结果:64573128数据3:输入人数13,初次报数9,密码依次为:4637982315758,测试结果:910281312611374515.3程序运行结果截图数据1:程序清单运行结果:32154数据2:程序清单运行结果:64573128数据3:程序清单运行结果:91028131261137451第6章总结与心得我的这次数据结构课程设计的题目是《约瑟夫环问题》,经过对该题目的设计,使我加深了对数据结构的理解。做什么事情,都要对认真,既然是该你做的事,肯定是你应该有这个能力,即使能力不够,也是应该借这个机会来培养。因此放心大胆地做,对自己有信心,就有动力。有人说,世上的事就怕认真二字。确实,做什么,只是认真地去做,踏踏实实,戒躁戒躁,静静地思考,慢慢地进步,真的是天下无难事。这就是我这次课程设计中得到的最大的体会,受益匪浅。经过课程设计我的收获如下:巩固和加深了对数据结构的理解,提高综合运用本课程所学知识的能力。培养了我选用参考书,查阅手册及文献资料的能力。培养独立思考,深入研究,分析问题、解决问题的能力。经过实际编译系统的分析设计、编程调试,掌握应用软件的分析方法和工程设计方法。经过课程设计,培养了我严肃认真的工作作风,逐步建立正确的生产观念、经济观念和全局观念。根据我在课程设计中遇到得问题,我将在以后的学习过程中注意以下几点:1、认真上好专业实验课,多在实践中锻炼自己。2、写程序的过程中要考虑周到,严密。3、认真的学习课本知识,并在此基础上学会灵活运用。参考文献[1]胡明,王涛等著.数据结构(C++版)[M].北京:清华大学出版社,.[2]谭浩强著.C程序设计(第四版)[M].北京:清华大学出版社,.[3]谭浩强著.C++程序设计[M].北京:清华大学出版社,.
附录程序源代码#include<iostream>usingnamespacestd;structLnode{ intpwd; intbianhao; structLnode*next;};intmain(){ inti=0; intnum,m; cout<<"输入人数:"<<"\n"; cin>>num; cout<<"输入初始报数:"<<"\n"; cin>>m; cout<<"输入密码:"<<"\n"; inta[100]; for(i=0;i<num;i++) cin>>a[i]; Lnode*L,*p; L=newLnode; L->next=NULL; for(i=num;i>0;i--){ p=newLnode; p->pwd=a[i-1]; p->bianhao=i; p->next=L->next; L->next=p; } p=L
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年度物联网传感器研发与供应合同
- 2024年喷泉建设项目维护施工协议一
- 保本理财投资合同三篇
- 2024年建筑外墙保温施工安全责任协议版B版
- 山西省房产过户合同参考模板
- 苗圃场地2024年度销售代理合同2篇
- 2024年新能源汽车充换电设施建设合同
- 2024年度大众化妆品电商渠道合作协议版
- 2024实验室装修改造及实验设备采购合同
- 2024年借款中介服务合同详细规定
- (高清版)JTST 273-2024 水运工程测量定额
- 2024春期国开电大《应用写作(汉语)》形考任务1-6参考答案
- 基于项目化设计的习作教学评价策略研究
- GB/T 9442-2024铸造用硅砂
- MOOC 英文技术写作-东南大学 中国大学慕课答案
- 戏剧之美(山东联盟)智慧树知到期末考试答案2024年
- 第22课《陈涉世家》课件(共71张)
- 国开2024年《机械设计基础》形考任务1-4答案
- 国开2024年《兽医基础》形考任务1-4答案
- 《药理学》试题库1 药理学总论(附答案)
- 2024全国职业院校技能大赛ZZ060母婴照护赛项规程+赛题
评论
0/150
提交评论