数据结构约瑟夫生者死者游戏课程设计.doc

数据机构课程设计 选题名称: 约瑟夫生者死者游戏 系（院）: 信息工程系 专 业: 信息管理与信息系统 班 级: 1430602 姓 名: 程宜兴 学 号: 201430060209 指导教师: 童怀水 2016年4月9日 目录 1、需求分析 3 2、系统功能 4 3、系统设计 5 4、程序具体运行结果 10 5、总结 12 1、需求分析 1.1课程设计目的 课程设计目的是为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。通过实践让学生理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。 1.2课程设计要求 约瑟夫生死游戏：30个人围成一个圈由第一个人数起，依次报数，数到第九个人，便把他剔除，然后再从他的下一个人数起，数到第九个人，再将他剔除剩下15个乘客为止，问那些位置是被扔下大海的位置。我们的设计目标是可以输入任意的位置和剩下的乘客。 1.3课程设计目标与总体方案 实验设计的目标是运用循环链表来解决Josephu环问题，其中运用了许多链表中的基本操作使改程序能不只解决一个Josephu的简单链表，其中的Josephu函数则是用于，运用C++程序编写程序，实现队列的建立、插入和删除基本功能，在程序设计成功的基础上，进一步深化理解队列的作用和实现原理。 2、系统的功能 2.1系统功能说明 2. 2系统功能解析 （1）构建约瑟夫链表：使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点; （2）确定n的值：进而使链具化体，从而可以构建一个具体的链表; （3）更新链表：对剔除结点后的链表进行重新连接，有构成了一个新的链表，使得循环继续进行; （4）输入：输入n的值进行链表具体化，输入间隔值m，使得间隔被确定，程序得以有效正确的进行； （5）输出：输出要剔除的结点的数值; 3、系统的设计 3.1 josphu链表的实现 Josphu链表——链式表示和实现约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1,2，??，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的那个人出列,他的下一个人又从1开始数，报数到m的人出列??直到所有人都出出列为止。给出出列的顺序。 3.2循环链表 表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了C语言中描述方便起 在此我们约定，初始化建空队列时front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置从上述分析可见，在C++中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。 3.3程序的代码 #includestdio.h #includestdlib.h typedef struct node{ int data; struct node*next; }ListNode,*LinkList; void main() { LinkList R=NULL; int n,k; LinkList InitRing(int n ,LinkList R); LinkList DeleteDeath(int n,int k,LinkList R); void OutRing(int n ,LinkList R); printf(输入总人数n和报数上限 k：); scanf(%d%d,n,k); R=InitRing(n,R); R=DeleteDeath(n,k,R); OutRing(n,R); } LinkList InitRing(int n ,LinkList R) { ListNode *p,*q; int i ; R=q=(ListNode *)malloc(sizeof(ListNode)); for(i=1;in;i++){ p=(ListNode *)malloc(sizeof(ListNode)); q-data=i; q-next=p; q=p