约瑟夫生死游戏课程设计(含源代码可以运行)

1、 目录目录 第一章 需求分析.1 1.1 课程设计目的 .1 1.2 课程设计要求 .1 1.3 课程设计目标与总体方案 .1 1.4 程序执行的命令 .1 第二章 系统的功能.2 2.1 系统功能说明 .2 2.2 系统功能解析 .2 第三章 系统的设计.3 3.1JOSPHU链表的实现.3 3.2 循环链表 .3 3.3 对程序的各个部分的详细介绍 .3 3.3.1 利用类定义构造成员函数以及成员.3 3.3.2 定义成员函数 .4 3.3.3 创建含有 n 个结点的单循环链表.5 3.3.4 Josephu 操作.5 3.3.5 主函数.6 3.4 程序的流程 .7 第四章 程序的运行结

2、果图.8 4.1 开始运行程序 .8 4.2 先键入参加游戏的人数及报数间隔 .8 4.3 按空格键运行程序 .9 第五章 总结.10 致谢.11 附录一 参考文献.12 附录二 程序源代码.13 约瑟夫生死游戏约瑟夫生死游戏 第一章 需求分析 1.1 课程设计目的 课程设计目的是为学生提供了一个既动手又动脑，独立实践的机会，将课 本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。 提高学生适应实际，实践编程的能力。通过实践让学生理论和实际操作相结合， 更好的理解书面知识，并在巩固的基础上融会所学认识。 1.2 课程设计要求 约瑟夫生死游戏：30 个人围成一个圈由第一个人数

3、起，依次报数，数到第 九个人，便把他剔除，然后再从他的下一个人数起，数到第九个人，再将他剔 除剩下 15 个乘客为止，问那些位置将是被扔下大海的位置。课程设计要求是将 30 个人改为 n,报数（原为 9） ，也改为任意正整数。根据得到的初始数据得到 生者和死者的位置编号并输出。 1.3 课程设计目标与总体方案 本实验设计的目标是运用循环链表来解决 Josephu 环问题，其中运用了许 多链表中的基本操作使改程序能不只解决一个 Josephu 的简单链表，其中的 Josephu 函数则是用于，运用 C+程序编写程序，实现队列的建立、插入和删除 基本功能，在程序设计成功的基础上，进一步深化理解队列

4、的作用和实现原理。 1.4 程序执行的命令 构造链表、输入数据、执行报数输出出列人的序号结束。 第二章 系统的功能 2.1 系统功能说明 约瑟夫生死游戏 确定 n值 更新 链表 输入输出 构建 链表 图 1 系统功能程序图 2.2 系统功能解析 如上图所示，本系统分为五个功能模块分别为：构建链表，确定 n 值，更 新链表，输入，输出。下面就每个功能进行详细说明： （1）构建约瑟夫链表：使整个游戏在链表中运行，使得结点在删除时不需 要移动大量的结点； （2）确定 n 的值：进而使链具化体，从而可以构建一个具体的链表； （3）更新链表：对剔除结点后的链表进行重新连接又，有构成了一个新的 链表，使得

5、循环继续进行； （4）输入：输入 n 的值进行链表具体化，输入间隔值 m，使得间隔被确定， 程序得以有效正确的进行； （5）输出：输出要剔除的结点的数值。 第三章 系统的设计 3.1Josphu 链表的实现 Josphu 链表链式表示和实现约瑟夫（Josephu）问题：已知 N 个人围 坐在一张圆桌周围（不妨以 1，2，N 对每一个人依次编号） ，现在先从序 号为 K 的人开始报数，数到 m 的那个人出列，他的下一个人又从 1 开始数，报 数到 m 的人出列直到所有人都出出列为止。给出出列的顺序。 3.2 循环链表 队列的顺序表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用 一组地址连续

6、的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两 个指针 front 和 rear 分别指示队列头元素及队列尾元素的位置。为了 C 语言中 描述方便起见，在此我们约定，初始化建空队列时，令 front=rear=0,每当插 入新的队列尾元素时， “尾指针增 1” ；每当删除队列头元素时， “头指针增 1” 。 因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾 元素的下一个位置从上述分析可见，在 C+中不能用动态分配的一维数组来实 现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大 队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。 3.3

7、 对程序的各个部分的详细介绍 编写本实验设计程序采用 C+进行，在 Visual c+ 6.0 环境下运行。 3.3.1 利用类定义构造成员函数以及成员 template class List public: List() first=new LinkNode; first-link=first; List(T x) first=new LinkNode(x); first-link=first; List(List List() void Insert(int i,T x); T getHead()return first-data; LinkNode* getfirst()return f

8、irst; void xiuf(LinkNode* a)first=a; LinkNode*Locate(int i); protected: LinkNode*first; ; 3.3.2 定义成员函数 template List:List(List LinkNode*srcptr=L.getHead(); LinkNode*destptr=first=new LinkNode; destptr-data=srcptr-data; while(srcptr-link!=first) value=srcptr-link-data; destptr-link=new LinkNode(value

9、); destptr=destptr-link; srcptr=srcptr-link; last=srcptr; ; template LinkNode* List:Locate(int i) if(i0)return NULL; LinkNode* current=first; int k=1; while(klink; k+; if(current=first)return NULL; return current; ; 3.3.3 创建含有 n 个结点的单循环链表 template void List:Insert(int i,T x) LinkNode* current=Locate

10、(i); if(current=NULL)return; LinkNode*newNode=new LinkNode(x); if(newNode=NULL) cout存储分配错误!link=current-link; current-link=newNode; ; 3.3.4 Josephu 操作 Josephu 操作为本程序的重点，在本程序中我是利用了一个 Josephu 函数 来解决该问题的，该函数是通过不断的循环、输出、再循环、再输出直到将 Josephu 链表中的一半元素被输出。函数如下： template void Josephus(List int i,j; for(i=1;i=

11、n/2;i+) if(m=1) cout出列的人是:datalink; Js.xiuf(p-link); delete p; p=pre; else for(j=1;jlink; cout出列的人是datalink=p-link; if(p=Js.getfirst()Js.xiuf(p-link); /if(p=Js.getlast()Js.movelast(pre); delete p; p=pre-link; 3.3.5 主函数 void main() List clist(1); int i,n,m; cout输入游戏者的人数和报数间隔：nm; for(i=1;in;i+) clist.

12、Insert(i,i+1); Josephus(clist,n,m); 3.4 程序的流程 3.4.1 流程图 开始 输入n、m 的值 创建链表 计数 删除结点 连接链表 i=n/2 结束 否 是 图 2 程序流程图 3.4.2 流程图的说明 开始进入程序，先确定 n 的值，然后，根据 n 得知建立链表，然后数数， 确定输出的位置，输出数，更新链表，如果剩下的数小于等于 n/2,则停止程序， 否则继续计数进行循环直至结束程序。 第四章 程序的运行结果图 4.1 开始运行程序 程序的初始化 图 3 程序初始化 4.2 先键入参加游戏的人数及报数间隔 输入人数和报数间隔 30 9 图 4 确定 n

13、 值及间隔值 m 4.3 按空格键运行程序 运行结果 图 4.3 运行结果 第五章 总结 致谢 附录一 参考文献 1谭浩强.C+程序设计.北京:清华大学出版社 .2003年 2严蔚敏,吴伟民 .数据结构.北京:清华大学出版社.2006年 3严蔚敏,吴伟民,米宁.数据结构教程上机实验指导.北京:清华大学 出版社.2006年 附录二 程序源代码 #include using namespace std; template struct LinkNode T data; LinkNode*link; LinkNode( T item) data=item; link=NULL; ; template

14、 class List public: List() first=new LinkNode; first-link=first; List(T x) first=new LinkNode(x); first-link=first; List(List List() void Insert(int i,T x); T getHead()return first-data; LinkNode* getfirst()return first; void xiuf(LinkNode* a)first=a; LinkNode*Locate(int i); protected: LinkNode*firs

15、t; ; template List:List(List LinkNode*srcptr=L.getHead(); LinkNode*destptr=first=new LinkNode; destptr-data=srcptr-data; while(srcptr-link!=first) value=srcptr-link-data; destptr-link=new LinkNode(value); destptr=destptr-link; srcptr=srcptr-link; last=srcptr; ; template LinkNode* List:Locate(int i)

16、if(i0)return NULL; LinkNode* current=first; int k=1; while(klink; k+; if(current=first)return NULL; return current; ; template void List:Insert(int i,T x) LinkNode* current=Locate(i); if(current=NULL)return; LinkNode*newNode=new LinkNode(x); if(newNode=NULL) cout存储分配错误!link=current-link; current-link=newNode; ; template void Josephus(List int i,j; for(i=1;i=n/2;i+) if(m=1) cout出列的人是:datalink; Js.xiuf(p-link); delete p; p=p