数据结构课程设计报告约瑟夫环完整版Word文档格式.docx
《数据结构课程设计报告约瑟夫环完整版Word文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告约瑟夫环完整版Word文档格式.docx(27页珍藏版)》请在冰点文库上搜索。
正文
一、问题描述
约瑟夫环问题描述的是:
设编号为1,2,…,n的n(n>
0)个人按顺时针方向围坐一圈,每个人持有一正整数密码。
开始时选择一个正整数作为报数上限m,从第一个人开始顺时针方向自1起顺序报数,报到m时停止报数,报m的人出圈,将他的密码作为新的m值,从他在顺时针方向上的下一个人起重新从1报数。
如此下去,直到所有人都出圈为止。
令n最大值为100。
要求设计一个程序模拟此过程,求出出圈的编号序列。
如下图分析:
二、逻辑设计
1、循环链表抽象数据类型定义
typedefstructLNode//定义单循环链表中节点的结构
{
intnum;
//编号
intpwd;
//password
structLNode*next;
//指向下一结点的指针
}LNode;
2、本程序包含一下几个模块
(1)构造结点模块
LNode*createNode(intm_num,intm_pwd)
LNode*p;
p=(LNode*)malloc(sizeof(LNode));
//生成一个结点
p->
num=m_num;
//把实参赋给相应的数据域
pwd=m_pwd;
next=NULL;
//指针域为空
returnp;
}
(2)创建链表模块
voidcreateList(LNode*ppHead,intn)
(3)出队处理模块
voidjose(LNode*ppHead,intm_pwd)
(4)约瑟夫环说明输出模块
voidinstruction()
(5)菜单模块
voidmenu()
(6)主函数模块
intmain()
函数的调用关系图如下:
三、详细设计
1.主函数
根据流程图,主函数程序如下:
intn,m,x;
LNode*ppHead=NULL;
menu();
for(;
;
){
printf("
\n请选择要执行的操作:
"
);
scanf("
%d"
&
x);
system("
cls"
switch(x){
case1:
printf("
****************************************************************\n"
printf("
约瑟夫环:
\n"
编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n"
码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n"
按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列,将他的密码\n"
m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n"
直到所有人全部出列为止.编程打印出列顺序.\n"
main();
break;
case2:
printf("
\n请输入总人数n:
scanf("
n);
请输入开始上限数m:
scanf("
m);
createList(&
ppHead,n);
出队顺序:
jose(ppHead,m);
\n约瑟夫环游戏结束!
case0:
exit(0);
default:
system("
\n您选择的操作有误,请重新选择...\n\n\n"
main();
}
}
return0;
2.链表的创建
/*创建单向循环链表ppHead,人数个数为n,并输入每个人的密码值,若建立失败则生成头结点,让cur指向他,若建立成功则插入结点P,cur指向的数据元素为p,后续为"
空"
的节点,再把P插入循环链表ppHead中*/
根据流程图,创建链表函数程序如下:
voidcreateList(LNode**ppHead,intn)
inti,m_pwd;
LNode*p,*cur;
//cur:
浮标指针
for(i=1;
i<
=n;
i++)
{
输入第%d个人的密码:
i);
m_pwd);
//输入持有密码
p=createNode(i,m_pwd);
//调用构造结点函数
if(*ppHead==NULL)//如果头结点为空
{
*ppHead=cur=p;
//生成头结点,让cur指向他
cur->
next=*ppHead;
//cur的指针域指向自身
else//如果不为空,则插入结点
p->
next=cur->
next;
next=p;
cur=p;
//cur指向新插入结点
}
}
完成创建!
//提示链表创建完成
}
3.出队处理
/*p指向要删除节点的前一个节点,ppHead指向要删除的节点,使p=ppHead,ppHead再指向要删除节点的下一个节点,使p和ppHead链接,输出p指向节点的编号和密码值,释放ppHead,如此循环,直至把所有节点都打印和删除为止!
*/
根据流程图,出队函数程序如下:
inti,j;
LNode*p,*p_del;
//定义指针变量
p!
=ppHead;
i++){
for(j=1;
j<
m_pwd;
++j){
p=ppHead;
//p赋值为ppHead,p指向要删除结点的前一个结点
ppHead=ppHead->
//ppHead指向下一个元素
p->
next=ppHead->
//p结点与头结点链接
i=ppHead->
pwd;
//i赋值为ppHead->
pwd
j=ppHead->
num;
//j赋值为ppHead->
num,j为要删除的密码值
第%d个人出列,密码:
%d\n"
j,i);
m_pwd=ppHead->
//m_pwd赋值为ppHead->
free(ppHead);
//释放头结点
ppHead=p->
//ppHead重新赋值给p->
next,即释放前的ppHead->
pwd指针//删除报数结点
i=ppHead->
j=ppHead->
num
最后一个出列是%d号,密码是:
free(ppHead);
4.约瑟夫环说明模块
按顺时针方向自1开始顺序报数,报到时停止.报m的人出列,将他的密码\n"
******************************************************\n"
5.菜单模块
voidmenu(){
**************************约瑟夫环*****************************\n"
\n"
[1]约瑟夫环问题的阐述\n"
[2]按要求求解约瑟夫环\n"
[0]退出\n"
**************************欢迎使用!
****************************\n"
四、程序代码
见附录源程序。
五、程序调试与测试
1.调用模块时,结点结构的调用与其他模块产生冲突,导致每一行都出现两次错误,加入子函数的声明后错误消失。
2.刚开始时曾忽略了一些变量参数的标识"
&
和“*”,使调试程序时费时不少。
今后应重视确定参数的变量和赋值属性的区分和标识。
3.本次课程设计采用数据抽象的程序设计方法,将程序划分为三个层次结构:
元素节点、单向循环链表,主控制模块。
思路较为清晰,实现调用顺利。
经过本次实验,使我对数据结构这门课程有了进一步的了解,每一个程序经过需求分析、概要设计、详细设计之后,思路即清晰呈现,程序也很快就出来了,最后经过调试、运行又有新的体验。
<
测试用例>
这是一个使用循环链表的经典问题。
本程序开始运行界面如下:
选择1进入约瑟夫环问题阐述。
①选择2,输入下列数据测试:
请输入总人数n:
7
20;
请依次输入每个人的密码:
3172484
6147235
②继续选择2,输入下列数据测试:
5
30
34567
53124
③继续选择2,输入下列数据测试:
8
14
345678910
67283514
测试完成,选择0退出。
设计总结
我的这次数据结构课程设计的题目是:
《约瑟夫环》,通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构,尤其是对单循环链表上基本运算的实现,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。
通过这次数据结构课程设计,我感受最深的就是对于循环链表的使用,可以说对循环链表有了比以前更进一步的认识,以前只是一知半解的,如果只给个题目自己根本不能把程序完整地编写出来,所以这次课程设计最大的收获就在于对循环链表有了一定的理解,包括其中的一系列操作,如建立一个循环链表,删除链表中的一个结点,增加一个结点等。
在调试程序的时候我也有所体会,虽然约瑟夫环问题不是很难,但调试的时候还是会出现很多错误,因此我们不能认为容易就不认真对待。
在以后的学习中,要能不断发现问题,提出问题,解决问题,从不足之处出发,在不断学习中提高自己。
两周的课程设计很短暂,但其间的内容是很充实的,在其中我学习到了很多平时书本中无法学到的东西,积累了经验,锻炼了自己分析问题,解决问题的能力,并学会了如何将所学的各课知识融会,组织起来进行学习,总而言之这两周中我学到很多,受益匪浅。
参考文献
1.严蔚敏,吴伟民.《数据结构(C语言版)》.清华大学出版社.
2.严蔚敏,吴伟民.《数据结构题集(C语言版)》.清华大学出版社.
3.《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社(影印版).
4.谭浩强.《c语言程序设计》.清华大学出版社.
致谢
这次的课程设计,我们两人一个小组去完成我们自己的课程,但是还是得到了来自很多方面的帮助。
在此首先要感谢学院提供给我这次实践的机会,让我们有机会贴近现实,感受成功的喜悦;
其次要感谢实验机房的老师提供优良的实验设备供我们做课设,正是这种良好的课设环境让我们整个课设过程心情都非常愉快。
再次要感谢指导老师们的辛勤指导,每当我们遇到疑难问题时,是他们一次次不厌其烦的解释和悉心的指导,我们才能闯过一个个难关,到达胜利的彼岸,是他们给我们提供了一次宝贵的检验自己机会。
最后也要感谢同学们的帮助,有了他们的支持使我遇到任何困难都不是一个人在战斗。
感谢所有在我课程设计过程中帮助过我的人!
附录
源代码:
#include<
stdio.h>
//输入输出函数头文件
stdlib.h>
//字符串转短整形函数的头文件10140219
//
/*构造结点*/
/**创建循环链表**/
{/*创建单向循环链表ppHead,人数个数为n,并输入每个人的密码值,若
建立失败则生成头结点,让cur指向他,若建立成功则插入结点P,cur指
向的数据元素为p,后续为"
/*出队处理*/
{/*p指向要删除节点的前一个节点,ppHead指向要删除的节点,使p=ppHead,ppHead再指向要删除节点的下一个节点,使p和ppHead链接,输出p指向节点的编号和密码值,释
放ppHead,如此循环,直至把所有节点都打印和删除为止!
/*主函数模块*/
intmain(){
intn,m,x;
LNode*ppHead=NULL;
menu();
for(;
case1:
printf("
createList(&
printf("
jose(ppHead,m);