約瑟夫生死游戲課程設(shè)計(jì)(含源代碼可以運(yùn)行)

1、約瑟夫生死游戲課程設(shè)計(jì)(含源代碼可以運(yùn)行)目錄目錄第一章 需求分析.11.1 課程設(shè)計(jì)目的 .11.2 課程設(shè)計(jì)要求 .11.3 課程設(shè)計(jì)目標(biāo)與總體方案 .11.4 程序執(zhí)行的命令 .1第二章 系統(tǒng)的功能.22.1 系統(tǒng)功能說明 .22.2 系統(tǒng)功能解析 .2第三章 系統(tǒng)的設(shè)計(jì).33.1JOSPHU鏈表的實(shí)現(xiàn).33.2 循環(huán)鏈表 .33.3 對(duì)程序的各個(gè)部分的詳細(xì)介紹 .33.3.1 利用類定義構(gòu)造成員函數(shù)以及成員.33.3.2 定義成員函數(shù) .43.3.3 創(chuàng)建含有 n 個(gè)結(jié)點(diǎn)的單循環(huán)鏈表.53.3.4 Josephu 操作.53.3.5 主函數(shù).63.4 程序的流程 .7第四章 程序的運(yùn)行

2、結(jié)果圖.84.1 開始運(yùn)行程序 .84.2 先鍵入?yún)⒓佑螒虻娜藬?shù)及報(bào)數(shù)間隔 .84.3 按空格鍵運(yùn)行程序 .9第五章 總結(jié).10致謝.11附錄一 參考文獻(xiàn).12附錄二 程序源代碼.13約瑟夫生死游戲約瑟夫生死游戲第一章 需求分析1.1 課程設(shè)計(jì)目的 課程設(shè)計(jì)目的是為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)，將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來，鍛煉學(xué)生的分析解決實(shí)際問題的能力。提高學(xué)生適應(yīng)實(shí)際，實(shí)踐編程的能力。通過實(shí)踐讓學(xué)生理論和實(shí)際操作相結(jié)合，更好的理解書面知識(shí)，并在鞏固的基礎(chǔ)上融會(huì)所學(xué)認(rèn)識(shí)。1.2 課程設(shè)計(jì)要求 約瑟夫生死游戲：30 個(gè)人圍成一個(gè)圈由第一個(gè)人數(shù)起，依次報(bào)數(shù)，數(shù)到第九個(gè)人

3、，便把他剔除，然后再?gòu)乃南乱粋€(gè)人數(shù)起，數(shù)到第九個(gè)人，再將他剔除剩下 15 個(gè)乘客為止，問那些位置將是被扔下大海的位置。課程設(shè)計(jì)要求是將30 個(gè)人改為 n,報(bào)數(shù)（原為 9） ，也改為任意正整數(shù)。根據(jù)得到的初始數(shù)據(jù)得到生者和死者的位置編號(hào)并輸出。1.3 課程設(shè)計(jì)目標(biāo)與總體方案 本實(shí)驗(yàn)設(shè)計(jì)的目標(biāo)是運(yùn)用循環(huán)鏈表來解決 Josephu 環(huán)問題，其中運(yùn)用了許多鏈表中的基本操作使改程序能不只解決一個(gè) Josephu 的簡(jiǎn)單鏈表，其中的Josephu 函數(shù)則是用于，運(yùn)用 C+程序編寫程序，實(shí)現(xiàn)隊(duì)列的建立、插入和刪除基本功能，在程序設(shè)計(jì)成功的基礎(chǔ)上，進(jìn)一步深化理解隊(duì)列的作用和實(shí)現(xiàn)原理。1.4 程序執(zhí)行的命令構(gòu)

4、造鏈表、輸入數(shù)據(jù)、執(zhí)行報(bào)數(shù)輸出出列人的序號(hào)結(jié)束。第二章 系統(tǒng)的功能2.1 系統(tǒng)功能說明 圖 1 系統(tǒng)功能程序圖2.2 系統(tǒng)功能解析 如上圖所示，本系統(tǒng)分為五個(gè)功能模塊分別為：構(gòu)建鏈表，確定 n 值，更【精品文檔】如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流.精品文檔.新鏈表，輸入，輸出。下面就每個(gè)功能進(jìn)行詳細(xì)說明：（1）構(gòu)建約瑟夫鏈表：使整個(gè)游戲在鏈表中運(yùn)行，使得結(jié)點(diǎn)在刪除時(shí)不需要移動(dòng)大量的結(jié)點(diǎn)；（2）確定 n 的值：進(jìn)而使鏈具化體，從而可以構(gòu)建一個(gè)具體的鏈表；（3）更新鏈表：對(duì)剔除結(jié)點(diǎn)后的鏈表進(jìn)行重新連接又，有構(gòu)成了一個(gè)新的鏈表，使得循環(huán)繼續(xù)進(jìn)行；（4）輸入：輸入 n 的值進(jìn)行鏈表具體化，輸入間

5、隔值 m，使得間隔被確定，程序得以有效正確的進(jìn)行；（5）輸出：輸出要剔除的結(jié)點(diǎn)的數(shù)值。第三章 系統(tǒng)的設(shè)計(jì)3.1Josphu 鏈表的實(shí)現(xiàn)Josphu 鏈表鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)約瑟夫（Josephu）問題：已知 N 個(gè)人圍坐在一張圓桌周圍（不妨以 1，2，N 對(duì)每一個(gè)人依次編號(hào)） ，現(xiàn)在先從序號(hào)為 K 的人開始報(bào)數(shù)，數(shù)到 m 的那個(gè)人出列，他的下一個(gè)人又從 1 開始數(shù)，報(bào)數(shù)到 m 的人出列直到所有人都出出列為止。給出出列的順序。3.2 循環(huán)鏈表隊(duì)列的順序表示和實(shí)現(xiàn)和順序棧相似，在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外，尚需附設(shè)兩個(gè)指針 front 和 rea

6、r 分別指示隊(duì)列頭元素及隊(duì)列尾元素的位置。為了 C 語言中描述方便起見，在此我們約定，初始化建空隊(duì)列時(shí)，令 front=rear=0,每當(dāng)插入新的隊(duì)列尾元素時(shí)， “尾指針增 1” ；每當(dāng)刪除隊(duì)列頭元素時(shí)， “頭指針增 1” 。因此，在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置從上述分析可見，在 C+中不能用動(dòng)態(tài)分配的一維數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個(gè)最大隊(duì)列長(zhǎng)度；若用戶無法預(yù)估所用隊(duì)列的最大長(zhǎng)度，則宜采用鏈隊(duì)列。3.3 對(duì)程序的各個(gè)部分的詳細(xì)介紹 編寫本實(shí)驗(yàn)設(shè)計(jì)程序采用 C+進(jìn)行，在 Visual c+ 6.0 環(huán)境下

7、運(yùn)行。3.3.1 利用類定義構(gòu)造成員函數(shù)以及成員templateclass Listpublic:List()first=new LinkNode;first-link=first;List(T x)first=new LinkNode(x);first-link=first;List(List&L);List()void Insert(int i,T x);T getHead()return first-data; LinkNode* getfirst()return first;【精品文檔】如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流.精品文檔.void xiuf(LinkNode*

8、a)first=a;LinkNode*Locate(int i);protected:LinkNode*first;3.3.2 定義成員函數(shù)templateList:List(List&L)T value;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;s

9、rcptr=srcptr-link;last=srcptr;templateLinkNode* 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 創(chuàng)建含有 n 個(gè)結(jié)點(diǎn)的單循環(huán)鏈表templatevoid List:Insert(int i,T x)LinkNode* current=Locate(i);if(current=NULL)return;LinkNode*newNode=

10、new LinkNode(x);if(newNode=NULL)cout存儲(chǔ)分配錯(cuò)誤!link=current-link;current-link=newNode;3.3.4 Josephu 操作 Josephu 操作為本程序的重點(diǎn)，在本程序中我是利用了一個(gè) Josephu 函數(shù)來解決該問題的，該函數(shù)是通過不斷的循環(huán)、輸出、再循環(huán)、再輸出直到將【精品文檔】如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流.精品文檔.Josephu 鏈表中的一半元素被輸出。函數(shù)如下：templatevoid Josephus(List& Js,int n,int m)LinkNode *p=Js.Locate(1

11、),*pre;int i,j;for(i=1;i=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 主函數(shù)void main() List clist(1); int i,n,m; cout輸入游戲者的人數(shù)和報(bào)數(shù)間隔：nm; for

12、(i=1;in;i+) clist.Insert(i,i+1); Josephus(clist,n,m); 3.4 程序的流程3.4.1 流程圖圖 2 程序流程圖3.4.2 流程圖的說明開始進(jìn)入程序，先確定 n 的值，然后，根據(jù) n 得知建立鏈表，然后數(shù)數(shù)，確定輸出的位置，輸出數(shù)，更新鏈表，如果剩下的數(shù)小于等于 n/2,則停止程序，否則繼續(xù)計(jì)數(shù)進(jìn)行循環(huán)直至結(jié)束程序。 第四章 程序的運(yùn)行結(jié)果圖4.1 開始運(yùn)行程序 程序的初始化圖 3 程序初始化4.2 先鍵入?yún)⒓佑螒虻娜藬?shù)及報(bào)數(shù)間隔輸入人數(shù)和報(bào)數(shù)間隔 30 9圖 4 確定 n 值及間隔值 m4.3 按空格鍵運(yùn)行程序運(yùn)行結(jié)果圖 4.3 運(yùn)行結(jié)果第五

13、章 總結(jié)致謝附錄一 參考文獻(xiàn)1譚浩強(qiáng).C+程序設(shè)計(jì).北京:清華大學(xué)出版社 .2003年2嚴(yán)蔚敏,吳偉民 .數(shù)據(jù)結(jié)構(gòu).北京:清華大學(xué)出版社.2006年3嚴(yán)蔚敏,吳偉民,米寧.數(shù)據(jù)結(jié)構(gòu)教程上機(jī)實(shí)驗(yàn)指導(dǎo).北京:清華大學(xué)出版社.2006年附錄二 程序源代碼#includeusing namespace std;templatestruct LinkNodeT data; LinkNode*link;LinkNode( T item) data=item;link=NULL;templateclass Listpublic:List()first=new LinkNode;first-link=firs

14、t;List(T x)first=new LinkNode(x);first-link=first;List(List&L);List()【精品文檔】如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流.精品文檔.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*first;templateList:List(List&L)T

15、value;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;templateLinkNode* List:Locate(int i)if(i0)return NULL;LinkNode* current=

16、first;int k=1;while(klink;k+;if(current=first)return NULL;return current;template【精品文檔】如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流.精品文檔.void List:Insert(int i,T x)LinkNode* current=Locate(i);if(current=NULL)return;LinkNode*newNode=new LinkNode(x);if(newNode=NULL)cout存儲(chǔ)分配錯(cuò)誤!link=current-link;current-link=newNode;templatevoid Josephus(List& Js,int n,int m)LinkNode *p=Js.Locate(1),*pre;int i,j;for(i=1;i=n/2;i+) if(m=1)cout出列的人是:datalink; Js.xiuf(p-link);delete p;p=pre;else for(j=1;jlink; cout出