約瑟夫生死游戲C++數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

1、約瑟夫生者死者游戲（鏈表存儲(chǔ)）一：【內(nèi)容與要求】約瑟夫游戲的大意是：每30個(gè)旅客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)高浪大，危險(xiǎn)萬(wàn)分；因此船長(zhǎng)告訴乘客，只有將全船一半的旅客投入還中，其余人才能幸免遇難。無(wú)奈，大家只得同意這種辦法，并議定30個(gè)人圍成一圈，由第一個(gè)人數(shù)起，依次報(bào)數(shù)，數(shù)到第9人，便把他投入大海中，然后再?gòu)乃南乱粋€(gè)人數(shù)起，數(shù)到第9人,再將他扔進(jìn)大海中，如此循環(huán)地進(jìn)行，直到剩下15個(gè)乘客為止。問(wèn)哪些位置是將被扔下大海的位置。二：概要設(shè)計(jì)利用鏈表循環(huán)來(lái)解決。首先，就必須先定義一個(gè)鏈表，按照所需要的長(zhǎng)度進(jìn)行定義，然后令其為指針指向頭指針，即完成了一個(gè)循環(huán)鏈表的創(chuàng)建。接下來(lái)先打印鏈表輸出。其次

2、，就是算法實(shí)現(xiàn)，需要利用指針來(lái)進(jìn)行，數(shù)據(jù)域標(biāo)記人員編號(hào)，先用一個(gè)指針循環(huán)查找，找到第一個(gè)需要?jiǎng)h除的人，標(biāo)記為1,先輸出節(jié)點(diǎn)數(shù)，再進(jìn)行刪除。依次循環(huán)查找，直到被刪除的節(jié)點(diǎn)數(shù)量為總?cè)藬?shù)的一半的時(shí)候則結(jié)束。:程序執(zhí)行流程圖三：詳細(xì)代碼結(jié)構(gòu)1 .鏈表的創(chuàng)建(1) 創(chuàng)建頭節(jié)點(diǎn)Josephring()(head=newNode;為頭結(jié)點(diǎn)申請(qǐng)空間head->no=1;/為數(shù)據(jù)域賦值head->next=head;/形成循環(huán)鏈表(2)循環(huán)插入鏈表voidJosephring二CreateJosephus(intn)(Node*s=head;/標(biāo)記頭結(jié)點(diǎn)totalnum=n;for(inti=2;i

3、<=n;i+)Node*w=newNode;/新建一個(gè)節(jié)點(diǎn)w->no=i;w->next=head;s->next=w;s=w;/S作為尾指針首先申請(qǐng)一個(gè)節(jié)點(diǎn)，并且W指針指向它，然后從2開(kāi)始賦值，此時(shí)先令新節(jié)點(diǎn)的W指針指向頭結(jié)點(diǎn)，再令S指針指向它，依次循環(huán)插入創(chuàng)建。2 .打印輸出鏈表voidJosephring:show()cout<<head->no<<"t"先輸出頭節(jié)點(diǎn)Node*q=head->next;while(q!=head)cout<<q->no<<"t"

4、;q=q->next;先打印輸出頭結(jié)點(diǎn)，然后循環(huán)判定，將不等于頭結(jié)點(diǎn)的全部輸出。3 .程序主算法voidJosephring:Joseph(intk,intm)/從第k個(gè)人開(kāi)始數(shù)數(shù)，數(shù)到m的人出列Node*p=head;/工作指針intj=1;/計(jì)數(shù)器while(j!=k)j+;p=p->next;/指針后移找到第k個(gè)人開(kāi)始數(shù)1的那個(gè)人for(inti=1;i<=totalnum/2;i+)Node*w=p;/指針w指向開(kāi)始數(shù)1的第k個(gè)人j=1;/計(jì)數(shù)器，為了找到數(shù)m的那個(gè)人while(j!=m)j+;p=w;w=w->next;找到了數(shù)m的那個(gè)人cout<<

5、;w->no<<"t"/輸出此人的編號(hào)p->next=w->next;/此人出列并刪除節(jié)點(diǎn)p=p->next;首先，先要找到第一個(gè)報(bào)數(shù)人的位置，用一個(gè)計(jì)數(shù)器進(jìn)行循環(huán)對(duì)比查找，從第一個(gè)位置起依次后移一個(gè)位置，直到輸入的數(shù)值等于鏈表上的某個(gè)位置數(shù)據(jù)域上的數(shù)值時(shí)，停止查找并且標(biāo)記為P指針。其次，從P位置開(kāi)始，再用一個(gè)W指針標(biāo)記，兩個(gè)指針一次后移循環(huán)查找，當(dāng)W指針指向的數(shù)據(jù)域等于所輸入的報(bào)數(shù)間隔M時(shí)，則打印輸出該節(jié)點(diǎn)上的數(shù)據(jù)，并且刪除該節(jié)點(diǎn)，P指針后移，作為下一次開(kāi)始數(shù)的起始位置。最后，依次循環(huán)打印輸出，知道人數(shù)為總?cè)藬?shù)的一半時(shí)候，程序停止。四：

6、運(yùn)行結(jié)果圖如下1.輸出船上的總?cè)藬?shù)輸入報(bào)數(shù)的起始位置"C:Userdmin-stratorDe5IrtopDebugsadaw,自2.強(qiáng)上的總?cè)藬?shù)為30w數(shù)起始的位置日?qǐng)?bào)數(shù)人間隔J輸入報(bào)數(shù)人的間隔之后便是最終界面3.五：設(shè)計(jì)過(guò)程主要問(wèn)題在設(shè)計(jì)過(guò)程中，開(kāi)始需要掌握是就是思想，主要就是鏈表的創(chuàng)建跟刪除，在設(shè)計(jì)過(guò)程中，我不知道如何去循環(huán)查找，以及如何循環(huán)輸出，因此剛剛開(kāi)始無(wú)從下手。之后我就開(kāi)始查找資料，網(wǎng)上參考別人的算法實(shí)現(xiàn)，在去咨詢同學(xué)跟老師，最主要是這個(gè)程序不是很難，只要思想掌握好，了解指針鏈表的創(chuàng)建刪除就可以編寫(xiě)。因此在掌握好循環(huán)算法之后就可以完成編寫(xiě)。六：心得體會(huì)經(jīng)過(guò)本次的實(shí)訓(xùn)，使

7、我得到了不少的收獲。使我的動(dòng)手能力有了一定的提升，并且學(xué)會(huì)了如何真正去設(shè)計(jì)一個(gè)簡(jiǎn)單的程序，在實(shí)訓(xùn)之前，我對(duì)程序整體的結(jié)構(gòu)基本上沒(méi)什么底子，自己從來(lái)沒(méi)完整的編寫(xiě)過(guò)一個(gè)程序，而這次無(wú)疑對(duì)我來(lái)說(shuō)我一個(gè)最好的練習(xí)。雖然每次去詢問(wèn)都是很簡(jiǎn)單的問(wèn)題，很遭反感，但是每次我都有收獲。本次實(shí)訓(xùn)的主要運(yùn)用就是鏈表，從而也加強(qiáng)了我對(duì)鏈表這反面的了解，最主要的收獲就是對(duì)程序整體的結(jié)構(gòu)以及其構(gòu)造，對(duì)我今后的學(xué)習(xí)有很大的幫助，今后我會(huì)多編寫(xiě)程序來(lái)提高自己的綜合水平。附錄：源程序完整代碼#include"iostream.h"#include"stdlib.h"#definemaxs

8、ize100/最大人數(shù)structNodeintno;/第幾個(gè)人Node*next;classJosephringprivate:Node*head;inttotalnum;public:Josephring()head=newNode;head->no=1;head->next=head;voidCreateJosephus(intn);voidshow();voidJoseph(intk,intm);)；voidJosephring:CreateJosephus(intn)/創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表(Node*s=head;totalnum=n;for(inti=2;i<=n;

9、i+)(Node*w=newNode;w->no=i;w->next=head;s->next=w;s=w;)voidJosephring:show()/輸出鏈表(cout<<head->no<<"t"Node*q=head->next;while(q!=head)(cout<<q->no<<"t"q=q->next;)voidJosephring:Joseph(intk,intm)/從第k個(gè)人開(kāi)始數(shù)數(shù)，數(shù)到m的人出列(Node*p=head;/工作指針intj=1

10、;/計(jì)數(shù)器while(j!=k)(j+;p=p->next;/指針后移找到第k個(gè)人開(kāi)始數(shù)1的那個(gè)人for(inti=1;i<=totalnum/2;i+)(Node*w=p;/指針w指向開(kāi)始數(shù)1的第k個(gè)人Node*q;j=1;計(jì)數(shù)器，為了找到數(shù)m的那個(gè)人while(j!=m)(j+;q=w;w=w->next;/找到了數(shù)m的那個(gè)人cout<<w->no<<"t"/輸出此人的編號(hào)q->next=w->next;/此人出列并刪除節(jié)點(diǎn)p=q->next;intmain()(intk,m;/船上的總數(shù)，k為從第幾個(gè)人

11、開(kāi)始數(shù)，m為數(shù)到m的那個(gè)人出列Josephringjosephus;cout<<"船上的總?cè)藬?shù)為："cin>>k;while(k>maxsize|k<0)(cout<<"超出范圍，請(qǐng)重新輸入："cin>>k;cout<<endl;cout<<endl<<endl;josephus.CreateJosephus(k);cout<<"報(bào)數(shù)起始的位置："cin>>k;cout<<endl<<endl<<"報(bào)數(shù)人間隔："；cin>>m;cout<<endl<<endl;cout&l