数据结构约瑟夫环课程设计报告书

上传人:飞*** 文档编号:42719783 上传时间:2018-06-03 格式:DOC 页数:11 大小:199.50KB
返回 下载 相关 举报
数据结构约瑟夫环课程设计报告书_第1页
第1页 / 共11页
数据结构约瑟夫环课程设计报告书_第2页
第2页 / 共11页
数据结构约瑟夫环课程设计报告书_第3页
第3页 / 共11页
数据结构约瑟夫环课程设计报告书_第4页
第4页 / 共11页
数据结构约瑟夫环课程设计报告书_第5页
第5页 / 共11页
点击查看更多>>
资源描述

《数据结构约瑟夫环课程设计报告书》由会员分享,可在线阅读,更多相关《数据结构约瑟夫环课程设计报告书(11页珍藏版)》请在金锄头文库上搜索。

1、 数 据 结 构 课课程程设计报设计报告告书书设计题目: 约瑟夫环 专 业: 班 级: 姓 名: 指导教师: 完成日期: 目目 录录一、 问题描述1二、 基本要求1三、 测试数据1四、 算法思想2五、 模块划分3六、 数据结构4七、 源程序4八、 界面设计6九、 运行与测试6十、 总结8十一、思考与感悟9数据结构课程设计报告书1课程设计设计报告书课程设计设计报告书一、问题描述一、问题描述约瑟夫问题是由古罗马著名的史学家 Josephus 提出的问题演变而来,所以通常称为 Josephus 问题。改进约瑟夫问题的描述是:编号为 1,2,n 的 n个人按顺时针方向围坐一圈, 每人有一个密码(整数)

2、 ,留作其出圈后应报到后出圈。报数方法采用顺时针报数和逆时针报数交替进行,初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景,后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构,就是将一个链表的尾元素指针指向队首元素。 p-link=head 解决问题的核心步骤:先建立一个具有 n 个链结点,无头结点的循环链表,然后确定第一个报数人的位置,并不断地从链表中删除链结点,直到链表为空。二、基本要求二、基本要求(1)输入的形式和输入值的范围:输入的形式是以数字的形式输入,输入范围

3、为-21474836482147483648(2)输出的形式:字符串形式输出(3)程序所能达到的功能:达到符合约瑟夫环要求的响应功能。三、测试数据三、测试数据进入程序,显示“1.开始游戏 0.退出游戏”输入非 0 数进入游戏,输入0 退出游戏。进入游戏后显示“输入总人数” ,输入大于 0 的整数;若输入错误,则光标处清空,重新输入。后提示“输入开始人的序号” ;范围是大于零,小于总人数的整数,若输入错误,则光标处清空,重新输入。后提示“输入间隔数字” ,范围是任意正整数;若输入错误,则光标处清空,重新输入。按回车键,显示结果,并重新询问“1.开始游戏 0.退出游戏” 。数据结构课程设计报告书2

4、四、算法思想四、算法思想首先,设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质,考虑采用循环链表,为了统一对表中任意节点的操作,循环链表不带头结点。循环链表的结点定义为如下结构类型:typedef struct node int data;struct node *next; LNode;其次,建立一个不带头结点的循环链表并由头指针 p 指示。最后,设计约瑟夫环问题的算法。1、工作指针 first,r,s,p,q 初始化2、输入人数(n)和报数(m)3、循环 n 次,用尾插法创建链表int start=k-1; LNode *s,*p,*L=0,*t; if (start=0) s

5、tart=n; while (n!=0) s=(LNode *)malloc(sizeof(LNode); if (L=0) p=s; if (n=start) t=s; s-data=n; s-next=L; L=s; n-; p-next=L; return t; LNode* GetNode(LNode *p)/*出队函数*/ LNode *q; for (q=p;q-next!=p;q=q-next); q-next=p-next; free (p); return (q); 4、输入报数的起始人号数 k;数据结构课程设计报告书35、循环 n 次删除结点并报出位置(其中第一个人后移 k

6、 个)当 inext=L;删除 p 结点的后一结点 qq=p;q-next!=p;q=q-next q-next=p-next;报出位置后 free q;计数器 i+;五、模块划分五、模块划分创建并初始化 n 个结点输入第一个报 的数 kn=0图 5-1 流程关系图输入总人数 n报数过程输出出列者 的编号及密 码n-结束数据结构课程设计报告书4六、数据结构六、数据结构通过对问题的分析,给出该课程设计需要使用的数据结构的类型定义,并阐述定义理由。存储结构:循环链表123n first图 6-1 循环链表七、源程序七、源程序#include #include typedef struct node

7、 int data; struct node *next; LNode; main() LNode* Create(int,int); LNode* GetNode(LNode *); int Print(LNode *,int); LNode *p; int n,k,m; int flag; while(1) printf(“1.开始游戏 0.退出游戏n“); scanf(“%d“, if(!flag) break;do printf (“输入总人数“); scanf (“%d“, while (nn); do printf (“输入间隔数字“); scanf (“%d“, while(md

8、ata=n; s-next=L; L=s; n-; p-next=L; return t; LNode* GetNode(LNode *p)/*出队函数*/ LNode *q; for (q=p;q-next!=p;q=q-next); q-next=p-next; free (p); return (q); 数据结构课程设计报告书6Print(LNode *p,int m)/*输出函数*/ int i; printf (“出队编号:n“); while (p-next!=p) for (i=1;inext; printf (“%d “,p-data); p=GetNode(p); print

9、f(“%dn“,p-data); return 0; 八、界面设计八、界面设计1.开始游戏 0.退出游戏 1 输入总人数:7 输入开始人的序号(17):1 输入间隔数字:3 出对编号: 3 6 2 7 5 1 41.开始游戏 0.退出游戏 0 Press any key to continue九、运行与测试九、运行与测试图 9-1 开始界面数据结构课程设计报告书7图 9-2 输入总人数图 9-3 输入开始人的序号图 9-4 输入间隔数字数据结构课程设计报告书8图 9-5 结果输出图 9-6 退出界面十、总结十、总结调试时出现的问题及解决办法:利用带头结点的尾插法建立链表求解的时候,头节点的作用

10、无法确定,导致编译通过,但是运行之后的结果都不是正确的运行结果。苦苦思索,包括和同学讨论,一直没能解决,最后决定改用另一种存储方法,将头节点直接改成NULL,最终测试的结果是正确的。 (但是还未能完全理解原因是什么)用函数返回存储节点的地址的时候,函数中的一句没有问题的语句出现访问错误,更改函数从而解决了问题。数据结构课程设计报告书9十一、思考与感悟十一、思考与感悟通过这次数据结构课程设计,我感受最深的就是对于循环链表的使用,可以说对循环链表有了比以前更进一步的认识,以前只是一知半解的,如果只给个题目自己根本不能把程序完整地编写出来,所以这次课程设计最大的收获就在于对循环链表有了一定的理解,包

11、括其中的一系列操作,如建立一个循环链表,删除链表中的一个结点,增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索,这这个过程当中我发现自己在数据结构方面知识掌握不够深入,对一些基本概念不能很好的理解,对一些数据结构不能够熟练的进行上机实现,这是自己比较薄弱的。学好基础知识是理论付诸实践的前提,这样理论和实践才能充分地结合起来。在以后的学习中,我还要努力改正,充分利用上机实验的机会提高自己。在程序的输入的时候,因为自己对键盘的不熟练,代码又很多很繁琐,常常会产生放弃的念头,从中我也感受到只有坚持到底,胜利才会出现。在调试程序的时候我也有所体会,虽然约瑟夫环问题不是很难,但调试的时候还是会出现很多错误,因此我们不能认为容易就不认真对待。在以后的学习中,要能不断发现问题,提出问题,解决问题,从不足之处出发,在不断学习中提高自己。

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 行业资料 > 其它行业文档

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号