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

1、 数据机构课程设计选题名称: 约瑟夫生者死者游戏 系（院）: 信息工程系专 业: 信息管理与信息系统班 级: 1430602 姓 名: 程宜兴 学 号: 201430060209指导教师: 童怀水 2016年4月9日目录1、需求分析32、系统功能43、系统设计54、程序具体运行结果105、总结121、需求分析1.1课程设计目的课程设计目的是为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。通过实践让学生理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。1.2课程设计要求

2、约瑟夫生死游戏：30个人围成一个圈由第一个人数起，依次报数，数到第九个人，便把他剔除，然后再从他的下一个人数起，数到第九个人，再将他剔除剩下15个乘客为止，问那些位置是被扔下大海的位置。我们的设计目标是可以输入任意的位置和剩下的乘客。1.3课程设计目标与总体方案 实验设计的目标是运用循环链表来解决Josephu环问题，其中运用了许多链表中的基本操作使改程序能不只解决一个Josephu的简单链表，其中的Josephu函数则是用于，运用C+程序编写程序，实现队列的建立、插入和删除基本功能，在程序设计成功的基础上，进一步深化理解队列的作用和实现原理。2、系统的功能2.1系统功能说明约瑟夫生死游戏输出

3、输入更新链表确定n值构建链表2. 2系统功能解析（1）构建约瑟夫链表：使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点;（2）确定n的值：进而使链具化体，从而可以构建一个具体的链表;（3）更新链表：对剔除结点后的链表进行重新连接，有构成了一个新的链表，使得循环继续进行;（4）输入：输入n的值进行链表具体化，输入间隔值m，使得间隔被确定，程序得以有效正确的进行；（5）输出：输出要剔除的结点的数值;3、系统的设计3.1 josphu链表的实现 Josphu链表链式表示和实现约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1,2，N对每一个人依次编号），现在先从序号为K

4、的人开始报数，数到m的那个人出列,他的下一个人又从1开始数，报数到m的人出列直到所有人都出出列为止。给出出列的顺序。3.2循环链表 表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了C语言中描述方便起 在此我们约定，初始化建空队列时front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置从上述分析可见，在C+中不能用动态分配

5、的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。3.3程序的代码#include<stdio.h>#include<stdlib.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,Lin

6、kList 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;i<n;i+)p=(ListNode *)malloc

7、(sizeof(ListNode);q->data=i;q->next=p;q=p;p->data=n;p->next=R;R=p;return R; LinkList DeleteDeath(int n ,int k ,LinkList R) int i ,j ; ListNode *p,*q; p=R; printf("抛入大海者的编号如下：n"); for(i=1;i<=n/2;i+) for(j=1;j<=k-1;j+) p=p->next; q=p->next; p->next=q->next; prin

8、tf("%4d",q->data); if(i%10=0)printf("n"); free(q); printf("n");R=p;return R; void OutRing(int n ,LinkList R) int i ; ListNode *p; p=R; printf("幸存者编号如下:n"); for(i=1;i<=(n+1)/2;i+,p=p->next) printf("%4d",p->data); if(i % 10=0)printf("n

9、"); printf("n"); 开始3.4程序的流程图输入n,m值创建列表计数删除结点连接链表结束I<=n/23.5流程图说明 开始进入程序，先确定n的值，然后，根据n得知建立链表，然后数数，确定输出的位置，输出数，更新链表，如果剩下的数小于等于n/2,则停止程序，否则继续计数进行循环直至结束程序。4、程序具体运行结果4.1先编译，编译无错后运行4.2输入总人数和报数上限5、总结经过这次集中上机的实验，从开始选题到自己上手还是编写程序的过程中，我学会了很多的东西，一个软件系统框架应建立在数据之上，而不是建立在操作之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。本实验设计就是建立在“定义、表示、实现”的基础上完成的。同时，做好课程设计更能体现出同学的学习态度，对于新知识的渴望与追求，能够反映出同学对自己负责任的决心，这点让我感受颇深。另外，据结构的知识和算法总是模棱两可的经过这次练习