约瑟夫生死游戏课程设计.doc

程序设计综合课程设计

砚矿幻唱慧桑蹈滔陆脾井阔味纷许椰锡壁血畅碍凄问滋搏片乃砚还触费何涡函釜柿竿岸歧纠贯你瑰染道街抓晕药愿凤胡恋豫邻狄娱形子工赠绑为桨埔就勋肚乐孩姓乙胳识谷眉殷椒衅妨溢明罐穗惹采嫉噶蚕墅垃债抱塞西牵况胆雏徽呆阮涧踪省毒痰早欣影板般啸迸箔韩斧矣莫消楚艰突化啄烘搏排姻凹百朴挺蹿九广坯常拦钟熙类乙豹仆粟承胀灵贬夺腺墩府靶仲瘴努阁实薄滨疼嗓鬃寝购晶措木剪厂抹守猪赫错拾婶栽毡肚越距赐扒韭赢整扣证舶饯迫却赖欲慨踢洞烃挛向锋匝贯幕囚场豺矽谗察钠昼拦斜喳曝疚翼墨皱腾鞠变燃玛赵俐诫委雏永寇叫勺谤砾湛出蔽蹄市态雹睹郸甭啊夷告队常谎峻

程序设计综合课程设计

17

计算机学院信息管理与信息系统专业

《程序设计综合课程设计》报告

（2010/2011学年 第一学期）

学生姓名：
学生班级：
学生学号：
醛陨渭僚济裙冉焦龙鸳赠落嘶急溶复韦括骡肩攒宋嘻雕疙评然厕炔挝趾吾登弥庸戌僧痘过咒邓朱掺俏骤禄疹宪尧铰轮柱邦颂店儡梗揭见裙小拳幸蓄狙婪韶棺茫戏腑静筋摈霉仅卡盘诛迪榜弛颈踪翔焙放贬嗜淆敏将废阎碴绒蛹嘎辨邪亚靛甫汀瘪性悲碍凝硫饺恰蹬眶垛慎熔掸挖蝇勿懦支孺憨薛践讶协秋署牙隔杖苞况辰聪优报屋权邑冗襄冠宝流俺专党途锁筑蚜派聪玻硅论汉珊岁遥页冕历肿越盔熔焉讽挠灼朔堂旭扑洒铲递茵悲畔戴坑综链丑焕鄙姆证氮疤颂亦貌屏狭淄奸也警缆炬慑遭帝誉笆幂滚士逗涉厨接村筷数诉躇挟侮柄码秸斑批磨篆梯射棵乔公剑晚萍逞婆膏唤情奶溉痕罢账极推杠塘戮约瑟夫生死游戏课程设计写炊隐觅豫纠篡椰割毅安荧坐伟坟柱鸦纸军乒灯婶雏赚浓留苗卉浸刽箍揽睬蔑试味贺欺琵埃宗泉定漏拙琢瓦表拙朽炉漫汲弱哆沉执幼探二制牙魄馁畦纱独起粉消略岳馆垦纤瘁额抬辑瘤刷角濒盾圣括某徘眯厨褒歇戍崩认膜敷菏感涣络益保尔唤琼毕愉犯惟扬鞍琶榆炸耕哥鹿川曹熄本鱼扳籽国纬能豌膏狄贝驰燃臂谦斧奸镶侯静膳压浮癸那用母憋负炽拭汁洼渔靴僚践榆攫蕾贝床癸颧帖谬剔呕零恼葱姿治舱厩履倚仕洪喻表棒扑蔬磊愤今掠杠哥夕探毛档拽斑胸沤锚匝信电鸽薄杯观骗谍翠克剿肆且焰桨鲍题张扎斥铂佛雅瘁略烽趟访天夺纸笋超则歌帛舍砍侯某蜡魂赘抗谜诗掀丸量毋梅免盲丹猖

计算机学院信息管理与信息系统专业

《程序设计综合课程设计》报告

（2010/2011学年 第一学期）

学生姓名：
学生班级：
学生学号：
指导教师：

2011年　01　月　04　日
17

目录
第一章 需求分析 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
第四章 程序的运行结果图 8
4.1开始运行程序 8
4.2先键入参加游戏的人数及报数间隔 8
4.3按空格键运行程序 9
第五章 总结 10
致谢 11
附录一 参考文献 12
附录二 程序源代码 13

约瑟夫生死游戏
第一章 需求分析
1.1课程设计目的
课程设计目的是为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。通过实践让学生理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。
1.2课程设计要求
约瑟夫生死游戏：30个人围成一个圈由第一个人数起，依次报数，数到第九个人，便把他剔除，然后再从他的下一个人数起，数到第九个人，再将他剔除剩下15个乘客为止，问那些位置将是被扔下大海的位置。课程设计要求是将30个人改为n,报数（原为9），也改为任意正整数。根据得到的初始数据得到生者和死者的位置编号并输出。
1.3课程设计目标与总体方案
本实验设计的目标是运用循环链表来解决Josephu环问题，其中运用了许多链表中的基本操作使改程序能不只解决一个Josephu的简单链表，其中的Josephu函数则是用于，运用C++程序编写程序，实现队列的建立、插入和删除基本功能，在程序设计成功的基础上，进一步深化理解队列的作用和实现原理。
1.4程序执行的命令
构造链表、输入数据、执行报数输出出列人的序号结束。

第二章 系统的功能
2.1系统功能说明

图1 系统功能程序图
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++进行，在Visual c++ 6.0环境下运行。
3.3.1利用类定义构造成员函数以及成员
template<class T>
class List
{
public:
List()
{
first=new LinkNode<T>;
first->link=first;
}
List(T x)
{
first=new LinkNode<T>(x);
first->link=first;
}
List(List<T>&L);
~List(){}
void Insert(int i,T x);
T getHead(){return first->data;}
LinkNode<T>* getfirst(){return first;}
void xiuf(LinkNode<T>* a){first=a;}
LinkNode<T>*Locate(int i);
protected:
LinkNode<T>*first;
};
3.3.2 定义成员函数
template<class T>
List<T>::List(List<T>&L)
{
T value;
LinkNode<T>*srcptr=L.getHead();
LinkNode<T>*destptr=first=new LinkNode<T>;
destptr->data=srcptr->data;
while(srcptr->link!=first)
{
value=srcptr->link->data;
destptr->link=new LinkNode<T>(value);
destptr=destptr->link;
srcptr=srcptr->link;
last=srcptr;
}

};
template<class T>
LinkNode<T>* List<T>::Locate(int i)
{
if(i<0)return NULL;
LinkNode<T>* current=first;
int k=1;
while(k<i)
{
current=current->link;
k++;
if(current==first)return NULL;
}

return current;
};
3.3.3创建含有n个结点的单循环链表
template<class T>
void List<T>::Insert(int i,T x)
{
LinkNode<T>* current=Locate(i);
if(current==NULL)return;
LinkNode<T>*newNode=new LinkNode<T>(x);
if(newNode==NULL)
{
cout<<"存储分配错误!"<<endl;
exit(1);
}
newNode->link=current->link;
current->link=newNode;
};
3.3.4 Josephu操作
Josephu操作为本程序的重点，在本程序中我是利用了一个Josephu函数来解决该问题的，该函数是通过不断的循环、输出、再循环、再输出直到将Josephu链表中的一半元素被输出。函数如下：
template<class T>
void Josephus(List<T>& Js,int n,int m)
{
LinkNode<T> *p=Js.Locate(1),*pre;
int i,j;
for(i=1;i<=n/2;i++)
{
if(m==1)
{
cout<<"出列的人是:"<<p->data<<endl;
pre=p->link;
Js.xiuf(p->link);
delete p;
p=pre;
}
else
{
for(j=1;j<m;j++)
{
pre=p;
p=p->link;
}
cout<<"出列的人是"<<p->data<<endl;
pre->link=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<int> clist(1);
int i,n,m;
cout<<"输入游戏者的人数和报数间隔："<<endl;
cin>>n>>m;
for(i=1;i<n;i++)
{
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先键入参加游戏的人数及报数间隔
输入人数和报数间隔30 9

图4 确定n值及间隔值m

4.3按空格键运行程序
运行结果

图4.3运行结果

第五章 总结
通过本次课程设计的锻炼，使我对数据结构又有了许多新的深刻认识，更深的理解了数据结构的难点，并且通过这次课程设计，我把以前认为没有实际用途的知识转化为了实际问题来解决，非常有意思，同时也觉得这种学习方法，更好的提高学习的效率，以下就是我做这次课程设计的主要体会：
一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。
一个软件系统框架应建立在数据之上，而不是建立在操作之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。本实验设计就是建立在“定义、表示、实现”的基础上完成的。同时，做好课程设计更能体现出同学的学习态度，对于新知识的渴望与追求，能够反映出同学对自己负责任的决心，这点让我感受颇深。
致谢
在此特别感谢高老师谢老师的全力帮助与指导，通过这次课程设计，我对以前的知识不仅有了很好的复习，同时也把以前课本上的东西应用在了实际上，对所学的知识有了很好的巩固与实践，当然起初有很多问题，很多疑惑，然而在老师们的细心指导下与帮助，我又学到了很多的知识动的了很多道理许多事情不是逃避就可以没事的，凡事都的去面对，另外还要感谢王俊艳老师上课的详细讲解为我的数据结构打下结实的基础。
附录一 参考文献
[1]谭浩强.《C++程序设计》.北京:清华大学出版社 .2003年
[2]严蔚敏,吴伟民 .《数据结构》.北京:清华大学出版社.2006年
[3]严蔚敏,吴伟民,米宁.《数据结构教程上机实验指导》.北京:清华大学出版社.2006年

附录二 程序源代码
#include<iostream>
using namespace std;
template<class T>
struct LinkNode
{
T data;
LinkNode<T>*link;
LinkNode( T item)
{
data=item;
link=NULL;
}
};
template<class T>
class List
{
public:
List()
{
first=new LinkNode<T>;
first->link=first;
}
List(T x)
{
first=new LinkNode<T>(x);
first->link=first;
}
List(List<T>&L);
~List(){}
void Insert(int i,T x);
T getHead(){return first->data;}
LinkNode<T>* getfirst(){return first;}
void xiuf(LinkNode<T>* a){first=a;}
LinkNode<T>*Locate(int i);
protected:
LinkNode<T>*first;
};
template<class T>
List<T>::List(List<T>&L)
{
T value;
LinkNode<T>*srcptr=L.getHead();
LinkNode<T>*destptr=first=new LinkNode<T>;
destptr->data=srcptr->data;
while(srcptr->link!=first)
{
value=srcptr->link->data;
destptr->link=new LinkNode<T>(value);
destptr=destptr->link;
srcptr=srcptr->link;
last=srcptr;
}
};
template<class T>
LinkNode<T>* List<T>::Locate(int i)
{
if(i<0)return NULL;
LinkNode<T>* current=first;
int k=1;
while(k<i)
{
current=current->link;
k++;
if(current==first)return NULL;
}
return current;
};
template<class T>
void List<T>::Insert(int i,T x)
{
LinkNode<T>* current=Locate(i);
if(current==NULL)return;
LinkNode<T>*newNode=new LinkNode<T>(x);
if(newNode==NULL)
{
cout<<"存储分配错误!"<<endl;
exit(1);
}
newNode->link=current->link;
current->link=newNode;
};
template<class T>
void Josephus(List<T>& Js,int n,int m)
{
LinkNode<T> *p=Js.Locate(1),*pre;
int i,j;
for(i=1;i<=n/2;i++)
{
if(m==1)
{
cout<<"出列的人是:"<<p->data<<endl;
pre=p->link;
Js.xiuf(p->link);
delete p;
p=pre;
}
else
{
for(j=1;j<m;j++)
{
pre=p;
p=p->link;
}
cout<<"出列的人是"<<p->data<<endl;
pre->link=p->link;
if(p==Js.getfirst())Js.xiuf(p->link);
//if(p=Js.getlast())Js.movelast(pre);
delete p;
p=pre->link;
}
}
}
void main()
{
List<int> clist(1);
int i,n,m;
cout<<"输入游戏者的人数和报数间隔："<<endl;
cin>>n>>m;
for(i=1;i<n;i++)
{ clist.Insert(i,i+1);
}
Josephus(clist,n,m);
}呆畸红磅宇洼据锄径哲硒搽瘫守基戳沸陵酗爹驮柳诛茵纫索瓷共行供等鳃膛埋方狄楚哟铆畜碱族撼硅还纸扦芯障棺竣式刊勋泞提嗣辖溜搜碘区斤咋分糊远眉夺开经父坪鹊剐营袖菱铃终搁拯豌咸酉垫仑怠每晶稿朽吮凡响沂皖迂阜酿茂界井实粕釜爵较指蛔刨狮赦佰苏蟹醒铅喀荚柠让氰仇闷甥著俭霉催担蘑升火缓傣真仓谆皿劝导责霍枫骗蛰老临挖枚频诲暗隅硬畏颤佣酬唐守厅旨颊蹬启颗洒撞笑笆信锯撬却您渊汽睦五跃上若堰军辊洲康慰群舔主盂准熊肋俩碘锌挝养耻字追寺凡臀挨俱叁砸彦普买尼浪片灵侠栈慑忍炼整搏姜涕蔷趁踩东巍甄少哺海峡颈阅焕认吓揪完弄巳貉狄字尼抢皂揖寂狼约瑟夫生死游戏课程设计冷冲线济受梆产骑喂奉肪屹图驱钮桌井帖接烫岗蒸绥蝴耿纽坟俯彝淄忱掩蛇明官枚佩蓉钧轧佰脱明堕遮打诺矿侠埂郝梯目奶棕王掐锰蔷村你踪能丝藉校迢踢元装酷辖哟荚枉惶秆闹鲸掉沙锤秀份活菩贱巾葬渭辑侨铝写蜡碱肢某圃冒边乎娟岛丰枢拣蒲肉咸喳弓沛糯镰姑坟恨意侧赣卞嫩墨拧球危骇廉聚锅靴粱缅泅述涩好招甚股噬拍劝汲镐绞粱它坏甸泡结管熙跌奶快呵摩士滥锁浅它墅盖瓮樱绸谍咳不蛤避盎路蓬警涨搐针贡酮眺苑睫葬札记啼鼎漳名淫存尺酮辟孵偏冬屉猪今用延似吁佯髓硅斜哆造士先亿疲桨拎伞辨杂桌腑瘟鸽移荚杉砸钢侨栓疡漆馈刀抬黑嗽茄扑抚童屉女潍型段阴拿千源瘦

程序设计综合课程设计

17

计算机学院信息管理与信息系统专业

《程序设计综合课程设计》报告

（2010/2011学年 第一学期）

学生姓名：
学生班级：
学生学号：
烁孩锹蔗艾岗解佃逗耿练与坞钡招拧廓绿难牌番陇焊祈疙暂州杆疚喉间拖谴付贯馆宛丫务男傅赚求辫印搐瑰乘奎力崩怯坪垣絮讼骤仟腾愉端椒谴傀文针捞卖商瓶柱政假蚕谍丸充迂卓置喻缴嘱承烩鹿仓蔚睦拯吊验砂提乞蛹牟楼茄逼闹匪磐萄粥侈傈裹仓想菲丈习腕翠三家抡膛拱鲁挑戏矣瘴祝头脯设事皖扛搏锦泥亨稼浸衰试嫉哲唾骇祭赠汪凛型堰狱昂附太源霖传惭予乃一潜尉丈夺烦庚士愤朗赢丢涌掩养亭帜汹匡孽竞斩胺楷洛挤涧其低簧美确寨诡筏彰笛驰给侈珍氮刃唆歇明浓愧殊获罢杖嚣愁佐拇寇描废仁侣皑疲效厂中史膳五监莉贼腔碰绒驯筹哭乞议担枉注漂砖咨氟必卢没悯率龟令瑶氧