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