《数据结构约瑟夫环课程设计报告书》由会员分享,可在线阅读,更多相关《数据结构约瑟夫环课程设计报告书(11页珍藏版)》请在金锄头文库上搜索。
1、数 据 结 构课程设计报告书设计题目:约瑟夫环专 业:班 级:姓 名:指导教师:完成日期:一、问题描述1二、基本要求1三、测试数据1四、算法思想2五、模块划分3六、数据结构4七、源程序4八、界面设计6九、运行与测试6十、总结8十一、思考与感悟9课程设计设计报告书一、问题描述约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来,所以通 常称为Josephus问题。改进约瑟夫问题的描述是:编号为1, 2,,n的n个人 按顺时针方向围坐一圈, 每人有一个密码(整数),留作其出圈后应报到后出圈。 报数方法采用顺时针报数和逆时针报数交替进行,初始密码可任意确定。求最后 剩下的人的编号。这个
2、就是约瑟夫环问题的实际场景,后来老师要求我们对要求 中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环 问题如果采用双向循环链表则能很好的解决。循环链表的数据结构,就是将一个 链表的尾元素指针指向队首元素。 p-link=head 解决问题的核心步骤:先建立 一个具有n个链结点,无头结点的循环链表,然后确定第一个报数人的位置,并 不断地从链表中删除链结点,直到链表为空。二、基本要求(1) 输入的形式和输入值的范围:输入的形式是以数字的形式输入,输入范 围为-2147483648 2147483648(2) 输出的形式:字符串形式输出(3) 程序所能达到的功能:达到符合约瑟夫
3、环要求的响应功能。三、测试数据进入程序,显示“1.开始游戏 0.退出游戏”输入非0 数进入游戏,输入0 退出游戏。进入游戏后显示“输入总人数” ,输入大于 0 的整数;若输入错误,则光 标处清空,重新输入。后提示“输入开始人的序号” ;范围是大于零,小于总人数的整数,若输 入错误,则光标处清空,重新输入。后提示“输入间隔数字” ,范围是任意正整数;若输入错误,则光标处清 空,重新输入。按回车键,显示结果,并重新询问“1.开始游戏 0.退出游戏”。四、算法思想 首先,设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质, 考虑采用循环链表,为了统一对表中任意节点的操作,循环链表不带头结点
4、。循 环链表的结点定义为如下结构类型:typedef struct nodeint 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) start=n;while (n!=0)s=(LNode *)malloc(sizeof(LNode);if (L=0) p=s;if (n=start) t=s
5、;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;5、循环n次删除结点并报出位置(其中第一个人后移k个) 当 inext=L; 删除 p 结点的后一结点 qq=p;q-next!=p;q=q-next q-next=p-next;报出位置后 free q; 计数器 i+;五、模块划分图 5-1 流程关系图六、数据结构通过对
6、问题的分析,给出该课程设计需要使用的数据结构的类型定义,并阐 述定义理由。存储结构:循环链表first图 6-1 循环链表七、源程序#include #include typedef struct nodeint 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(l.开始游戏0.退出游戏n);scanf(%d,&flag);if(!flag) br
7、eak;doprintf (输入总人数); scanf (%d,&n);while (n=0);doprintf (输入开始人的序号(ld)”,n);scanf (%d,&k);while (kn);doprintf (输入间隔数字); scanf (%d,&m); while(mdata=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);Print(LNode
8、*p,int m)/* 输出函数*/int i;printf (出队编号:n);while (p-next!=p)for (i=1;inext;printf (%d ,p-data); p=GetNode(p);printf(%dn,p-data);return 0;八、界面设计1.开始游戏0.退出游戏1输入总人数:7输入开始人的序号(17):1 输入间隔数字:3 出对编号: 36275141.开始游戏0.退出游戏0Press any key to continue九、运行与测试图 9-1 开始界面图 9-2 输入总人数图9-3输入开始人的序号口开始游戏昜-退岀游戏 爲入总人数7输入开站X的序
9、钦m 輸人间隔数字.图 9-6 退出界面十、总结调试时出现的问题及解决办法:利用带头结点的尾插法建立链表求解的时候,头节点的作用无法确定,导致 编译通过,但是运行之后的结果都不是正确的运行结果。苦苦思索,包括和同学 讨论,一直没能解决,最后决定改用另一种存储方法,将头节点直接改成 NULL, 最终测试的结果是正确的。(但是还未能完全理解原因是什么)用函数返回存储节点的地址的时候,函数中的一句没有问题的语句出现访问 错误,更改函数从而解决了问题。十一、思考与感悟通过这次数据结构课程设计,我感受最深的就是对于循环链表的使用,可以 说对循环链表有了比以前更进一步的认识,以前只是一知半解的,如果只给个
10、题 目自己根本不能把程序完整地编写出来,所以这次课程设计最大的收获就在于对 循环链表有了一定的理解,包括其中的一系列操作,如建立一个循环链表,删除 链表中的一个结点,增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索,这这个过程当中我发现 自己在数据结构方面知识掌握不够深入,对一些基本概念不能很好的理解,对一 些数据结构不能够熟练的进行上机实现,这是自己比较薄弱的。学好基础知识是 理论付诸实践的前提,这样理论和实践才能充分地结合起来。在以后的学习中, 我还要努力改正,充分利用上机实验的机会提高自己。在程序的输入的时候,因 为自己对键盘的不熟练,代码又很多很繁琐,常常会产生放弃的念头,从中我也 感受到只有坚持到底,胜利才会出现。在调试程序的时候我也有所体会,虽然约瑟夫环问题不是很难,但调试的时 候还是会出现很多错误,因此我们不能认为容易就不认真对待。在以后的学习中, 要能不断发现问题,提出问题,解决问题,从不足之处出发,在不断学习中提高 自己。