完整word版约瑟夫生死游戏课程设计含源代码可以运行word文档良心出品文档格式.docx
《完整word版约瑟夫生死游戏课程设计含源代码可以运行word文档良心出品文档格式.docx》由会员分享，可在线阅读，更多相关《完整word版约瑟夫生死游戏课程设计含源代码可以运行word文档良心出品文档格式.docx（15页珍藏版）》请在冰点文库上搜索。
2.2系统功能解析
如上图所示，本系统分为五个功能模块分别为：
构建链表，确定n值，更新链表，输入，输出。
下面就每个功能进行详细说明：
（1）构建约瑟夫链表：
使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点；
（2）确定n的值：
进而使链具化体，从而可以构建一个具体的链表；
（3）更新链表：
对剔除结点后的链表进行重新连接又，有构成了一个新的链表，使得循环继续进行；
（4）输入：
输入n的值进行链表具体化，输入间隔值m，使得间隔被确定，程序得以有效正确的进行；
（5）输出：
输出要剔除的结点的数值。
第三章系统的设计
3.1Josphu链表的实现
Josphu链表——链式表示和实现约瑟夫（Josephu）问题：
已知N个人围坐在一张圆桌周围（不妨以1，2，……，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的那个人出列，他的下一个人又从1开始数，报数到m的人出列……直到所有人都出出列为止。
给出出列的顺序。
3.2循环链表
队列的顺序表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。
为了C语言中描述方便起见，在此我们约定，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；
每当删除队列头元素时，“头指针增1”。
因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置从上述分析可见，在C++中不能用动态分配的一维数组来实现循环队列。
如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；
若用户无法预估所用队列的最大长度，则宜采用链队列。
3.3对程序的各个部分的详细介绍
编写本实验设计程序采用C++进行，在Visualc++6.0环境下运行。
3.3.1利用类定义构造成员函数以及成员
template<
classT>
classList
{
public:
List（）
{
first=newLinkNode<
T>
;
first->
link=first;
}
List（Tx）
（x）;
List（List<
&
L）;
~List（）{}
voidInsert（inti,Tx）;
TgetHead（）{returnfirst->
data;
}
LinkNode<
*getfirst（）{returnfirst;
voidxiuf（LinkNode<
*a）{first=a;
LinkNode<
*Locate（inti）;
protected:
*first;
};
3.3.2定义成员函数
List<
:
List（List<
L）
Tvalue;
LinkNode<
*srcptr=L.getHead（）;
*destptr=first=newLinkNode<
destptr->
data=srcptr->
while（srcptr->
link!
=first）
{
value=srcptr->
link->
destptr->
link=newLinkNode<
（value）;
destptr=destptr->
link;
srcptr=srcptr->
last=srcptr;
}
*List<
Locate（inti）
if（i<
0）returnNULL;
*current=first;
intk=1;
while（k<
i）
{
current=current->
k++;
if（current==first）returnNULL;
returncurrent;
3.3.3创建含有n个结点的单循环链表
voidList<
Insert（inti,Tx）
*current=Locate（i）;
if（current==NULL）return;
*newNode=newLinkNode<
if（newNode==NULL）
cout<
<
"
存储分配错误!
endl;
exit
（1）;
newNode->
link=current->
current->
link=newNode;
3.3.4Josephu操作
Josephu操作为本程序的重点，在本程序中我是利用了一个Josephu函数来解决该问题的，该函数是通过不断的循环、输出、再循环、再输出直到将Josephu链表中的一半元素被输出。
函数如下：
voidJosephus（List<
Js,intn,intm）
*p=Js.Locate
（1）,*pre;
inti,j;
for（i=1;
i<
=n/2;
i++）
if（m==1）
cout<
出列的人是:
p->
data<
pre=p->
Js.xiuf（p->
link）;
deletep;
p=pre;
else
for（j=1;
j<
m;
j++）
pre=p;
p=p->
出列的人是"
pre->
link=p->
if（p==Js.getfirst（））Js.xiuf（p->
//if（p=Js.getlast（））Js.movelast（pre）;
deletep;
p=pre->
3.3.5主函数
voidmain（）
{List<
int>
clist
（1）;
inti,n,m;
cout<
输入游戏者的人数和报数间隔：
cin>
>
n>
n;
clist.Insert（i,i+1）;
Josephus（clist,n,m）;
3.4程序的流程
3.4.1流程图
图2程序流程图
3.4.2流程图的说明
开始进入程序，先确定n的值，然后，根据n得知建立链表，然后数数，确定输出的位置，输出数，更新链表，如果剩下的数小于等于n/2,则停止程序，否则继续计数进行循环直至结束程序。
第四章程序的运行结果图
4.1开始运行程序
程序的初始化
图3程序初始化
4.2先键入参加游戏的人数及报数间隔
输入人数和报数间隔309
图4确定n值及间隔值m
4.3按空格键运行程序
运行结果
图4.3运行结果
第五章总结
致谢
附录一参考文献
[1]谭浩强.《C++程序设计》.北京:
清华大学出版社.2003年
[2]严蔚敏,吴伟民.《数据结构》.北京:
清华大学出版社.2006年
[3]严蔚敏,吴伟民,米宁.《数据结构教程上机实验指导》.北京:
附录二程序源代码
#include<
iostream>
usingnamespacestd;
structLinkNode
Tdata;
*link;
LinkNode（Titem）
data=item;
link=NULL;
}
Tvalue;
value=srcptr->
};
if（m==1）
{
List<
{clist.Insert（i,i+1）;
升级会员 