约瑟夫环.docx
- 文档编号:12946621
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:10
- 大小:18.29KB
约瑟夫环.docx
《约瑟夫环.docx》由会员分享,可在线阅读,更多相关《约瑟夫环.docx(10页珍藏版)》请在冰点文库上搜索。
约瑟夫环
数据结构设计——约瑟夫环问题
(2008-03-3015:
47:
24)
转载▼
标签:
校园
第一份
目录
1.设计任务书
2.本组课题及本人任务
3.程序功能简介
4.主体内容
5.程序说明
6.操作方法(流程)
7.设计体会
8.附录
9.测试数据
10.附参考书目
1.设计任务书
1)小组五人根据自己的想法独立编写解决约瑟夫环问题的算法.
2)小组每个人说出自己的算法思想,选择最优算法,编写人负责向其他小组成员解释算法
3)分配各自任务,进行开发
2.本组课题及本人任务
1)课题名:
约瑟夫环问题
2)任务:
⑴编写算法
⑵记录开发日志
⑶文档编写
⑷程序代码编写
⑸调试运行
3)小组成员:
指导教师:
3.程序功能简介
1)界面友好
2)能完操作方法(流程)
3)执行报数,储存出列人的序号,删除出列人的信息以及把出列人的密码赋给m;
4)输出正确的排列顺序
4.主体内容
设计分析:
基本思想
通过我们对约瑟夫问题的分析,我们认为利用单向循环链表就能解决这个问题。
因为约瑟夫环的大小有输入决定,所以要进行动态内存分配。
为了实现上述操作,应以单向循环链表为存储结构。
基本操作:
new_code()
操作结果:
构造空链表,若成功就初始化每个人的相关信息
delete_code()
初始条件:
线性链表存在
操作结果:
释放指向出列的人的结点,并重新报数
本程序包含三个模块:
⑴主程序模块;
⑵构造链表并输入每个人信息模块;
⑶释放结点模块;
5.程序说明
本程序完成的是:
编号为1,2,....,N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数上限值M,从第一个人开始按顺时针方向自1开始顺序报数,报到M时停止报数.报M的人出列,将他的密码作为新的M值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止.程序输出出列顺序.
6.操作方法(流程)
1)打开VC++6.0中文版。
2)输入自己编写好的源程序代码。
3)运行程序,并找出程序中的错误,加以改正,直到能成功运行
4)输入测试数据,分析实验结果
7.设计体会
通过约瑟夫环算法的课题设计让我理解了循环队列,不单单只是书本上文字的循环队列的概念,更多是自己能够通过实际的操作对循环队列有了更深的了解。
上机的编程的过程是对数据结构的基础的进一步的巩固。
学习过程体验到了学习的乐趣,实验课题使我认识到平时学习的漏洞和知识的缺乏,为以后的学习敲了一下警钟,数据结构是门基础,要学习扎实才行
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。
它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。
数据结构有逻辑上的数据结构和物理上的数据结构之分。
逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。
数据结构是数据存在的形式。
数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。
数据结构课程的主要目的是介绍一些常用的数据结构,阐明数据结构内在的逻辑关系,讨论它们在计算机中的存储表示,并结合各种数据结构,讨论对它们实行的各种运算的实现算法。
很多算法实际上是对某种数据结构施行的一种变换,研究算法也就是研究在实施变换过程中数据结构的动态性质。
学习的过程需要合作,而且在合作中提到自己的编程水平,借鉴他人好的地方,改掉原先自己不足,书本知识的与实际的联系,使自己的编程不在局限于原来的纸上谈兵,更多的是积累了经验,培养了能力
8.附录
1)程序中主要变量、函数(指自定义函数及程序中用到的部分不常用系统函数)列表(含简要说明);实现主要功能的(本人任务部分)核心源程序
#include
#include
typedefstructList
{
boolIsOn;
intnum;
intpsw;
List*pnext;
}*PList;
enum
Status{ERROR_OK=0,ERROR_MEMORY_FALIED,ERROR_INPUT_NUM,ERROR_NOPERSON,ERROR_NUM};
voidGetErrorMsg(constStatus&errorCode)
{
charmsg[256];
switch(errorCode)
{
caseERROR_OK:
strcpy(msg,"执行成功!
");
break;
caseERROR_MEMORY_FALIED:
strcpy(msg,"内存错误:
没有足够大的内存!
");
break;
caseERROR_INPUT_NUM:
strcpy(msg,"输入数据错误!
");
break;
caseERROR_NUM:
strcpy(msg,"数据错误!
");
break;
caseERROR_NOPERSON:
strcpy(msg,"错误:
此编号的人不存在!
");
break;
default:
strcpy(msg,"未知错误!
");
}
cout< } StatusCreateList(PList&pls,constintnum) { if(num>30||num<=0) returnERROR_NUM; PListpTemp=newList; pls=pTemp; pls->num=1; pls->IsOn=true; for(inti=1;i { pTemp->pnext=newList; if(pTemp==NULL) returnERROR_MEMORY_FALIED; pTemp=pTemp->pnext; pTemp->num=i+1; pTemp->IsOn=true; pTemp->pnext=NULL; } pTemp->pnext=pls; returnERROR_OK; } StatusInputPassWord(PList&pls,constintnum) { if(num<=0) returnERROR_INPUT_NUM; PListpTemp=pls; for(inti=1;i! =num;i++) { pTemp=pTemp->pnext; } if(num==i) { cin>>pTemp->psw; if(pTemp->psw<=0) returnERROR_INPUT_NUM; else returnERROR_OK; } else returnERROR_INPUT_NUM; } StatusShowResult(constPList&pls,constint&m) { if(m<=0) returnERROR_INPUT_NUM; if(pls==NULL) returnERROR_NUM; intnum=0; PListpTemp=pls; do{ num++; pTemp=pTemp->pnext; }while(pTemp! =pls); inti=0,j,ps=m; while(i! =num) { if(i==0) ps--; for(j=0;j { do{ pTemp=pTemp->pnext; }while(! pTemp->IsOn); } pTemp->IsOn=false; cout<<"第"< "< ps=pTemp->psw; i++; } returnERROR_OK;//返回成功 } voidmain() { cout<<"*************************************"< <<"*******欢迎使用约瑟夫环模拟程序******"< <<"*************************************"< < cout<<"****************数据输入*************"< <<"*************************************"< PListpls=NULL; intiTemp; StatuserrorCode; cout<<"**********Step1: 环中人数输入*********"< do{ cout<<"请输入模拟环中的人数: "; cin>>iTemp; errorCode=CreateList(pls,iTemp); GetErrorMsg(errorCode); }while(! (ERROR_OK==errorCode)); cout<<"************Step2: 密码输入***********"< for(inti=1;i<=iTemp;i++) { cout<<"请输入第"< "; errorCode=InputPassWord(pls,i); while(errorCode! =ERROR_OK) { GetErrorMsg(errorCode); cout<<"请输入第"< "; errorCode=InputPassWord(pls,i); } } cout<<"**********Step3: 初始密码输入*********"< do{ cout<<"请输入初始密码: "; cin>>iTemp; cout<<"**********程序执行结果***********"< <<"**********************************"< errorCode=ShowResult(pls,iTemp); GetErrorMsg(errorCode); }while(ERROR_OK! =errorCode); } 9.测试数据: 当n=7,7个人的密码依次为: 3,1,7,2,4,8,4,首先m值为6,则这正确的出列顺序为6,1,4,7,2,3,5 10.附参考书目 清华大学出版社《数据结构(C语言版)》 数据结构——习题与解析,李春葆,清华大学出版社
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 约瑟夫