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

./題目二：約瑟夫生者死者游戲〔鏈表存儲(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è)乘客為止。問哪些位置是將被扔下大海的位置。二：概要設(shè)計(jì)利用鏈表循環(huán)來解決。首先,就必須先定義一個(gè)鏈表,按照所需要的長(zhǎng)度進(jìn)行定義,然后令其為指針指向頭指針,即完成了一個(gè)循環(huán)鏈表的創(chuàng)建。接下來先打印鏈表輸出。其次,就是算法實(shí)現(xiàn),需要利用指針來進(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í)行流程圖開始開始否是輸出該節(jié)點(diǎn)并且刪除,指針后移,標(biāo)記下一次的起始位置從報(bào)數(shù)位置起,依次循環(huán)數(shù)到找到第m個(gè)人程序結(jié)束判定剩下人數(shù)是否為一半循環(huán)找到報(bào)數(shù)起始位置,用指針標(biāo)記創(chuàng)建N個(gè)節(jié)點(diǎn)的循環(huán)鏈表打印輸出鏈表否是輸出該節(jié)點(diǎn)并且刪除,指針后移,標(biāo)記下一次的起始位置從報(bào)數(shù)位置起,依次循環(huán)數(shù)到找到第m個(gè)人程序結(jié)束判定剩下人數(shù)是否為一半循環(huán)找到報(bào)數(shù)起始位置,用指針標(biāo)記創(chuàng)建N個(gè)節(jié)點(diǎn)的循環(huán)鏈表打印輸出鏈表三：詳細(xì)代碼結(jié)構(gòu)鏈表的創(chuàng)建創(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<=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開始賦值,此時(shí)先令新節(jié)點(diǎn)的W指針指向頭結(jié)點(diǎn),再令S指針指向它,依次循環(huán)插入創(chuàng)建。打印輸出鏈表voidJosephring::show<>{cout<<head->no<<"\t";//先輸出頭節(jié)點(diǎn) Node*q=head->next; while<q!=head> { cout<<q->no<<"\t"; q=q->next;}}先打印輸出頭結(jié)點(diǎn),然后循環(huán)判定,將不等于頭結(jié)點(diǎn)的全部輸出。程序主算法voidJosephring::Joseph<intk,intm>//從第k個(gè)人開始數(shù)數(shù),數(shù)到m的人出列{ Node*p=head;//工作指針 intj=1;//計(jì)數(shù)器 while<j!=k> { j++; p=p->next;//指針后移 }//找到第k個(gè)人開始數(shù)1的那個(gè)人 for<inti=1;i<=totalnum/2;i++> { Node*w=p;//指針w指向開始數(shù)1的第k個(gè)人 j=1;//計(jì)數(shù)器,為了找到數(shù)m的那個(gè)人 while<j!=m> { j++; p=w; w=w->next; }//找到了數(shù)m的那個(gè)人 cout<<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位置開始,再用一個(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指針后移,作為下一次開始數(shù)的起始位置。最后,依次循環(huán)打印輸出,知道人數(shù)為總?cè)藬?shù)的一半時(shí)候,程序停止。四：運(yùn)行結(jié)果圖如下輸出船上的總?cè)藬?shù)輸入報(bào)數(shù)的起始位置輸入報(bào)數(shù)人的間隔之后便是最終界面五：設(shè)計(jì)過程主要問題在設(shè)計(jì)過程中,開始需要掌握是就是思想,主要就是鏈表的創(chuàng)建跟刪除,在設(shè)計(jì)過程中,我不知道如何去循環(huán)查找,以及如何循環(huán)輸出,因此剛剛開始無(wú)從下手。之后我就開始查找資料,網(wǎng)上參考別人的算法實(shí)現(xiàn),在去咨詢同學(xué)跟老師,最主要是這個(gè)程序不是很難,只要思想掌握好,了解指針鏈表的創(chuàng)建刪除就可以編寫。因此在掌握好循環(huán)算法之后就可以完成編寫。六：心得體會(huì)經(jīng)過本次的實(shí)訓(xùn),使我得到了不少的收獲。使我的動(dòng)手能力有了一定的提升,并且學(xué)會(huì)了如何真正去設(shè)計(jì)一個(gè)簡(jiǎn)單的程序,在實(shí)訓(xùn)之前,我對(duì)程序整體的結(jié)構(gòu)基本上沒什么底子,自己從來沒完整的編寫過一個(gè)程序,而這次無(wú)疑對(duì)我來說我一個(gè)最好的練習(xí)。雖然每次去詢問都是很簡(jiǎn)單的問題,很遭反感,但是每次我都有收獲。本次實(shí)訓(xùn)的主要運(yùn)用就是鏈表,從而也加強(qiáng)了我對(duì)鏈表這反面的了解,最主要的收獲就是對(duì)程序整體的結(jié)構(gòu)以及其構(gòu)造,對(duì)我今后的學(xué)習(xí)有很大的幫助,今后我會(huì)多編寫程序來提高自己的綜合水平。附錄：源程序完整代碼#include"iostream.h"#include"stdlib.h"#definemaxsize100//最大人數(shù)structNode{intno;//第幾個(gè)人Node*next;};classJosephring{private: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;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è)人開始數(shù)數(shù),數(shù)到m的人出列{Node*p=head;//工作指針intj=1;//計(jì)數(shù)器while<j!=k>{j++;p=p->next;//指針后移}//找到第k個(gè)人開始數(shù)1的那個(gè)人for<inti=1;i<=totalnum/2;i++>{Node*w=p;//指針w指向開始數(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è)人開始數(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>>