約瑟夫生死游戲C++數(shù)據(jù)結構實現(xiàn)

./題目二：約瑟夫生者死者游戲〔鏈表存儲一：[內(nèi)容與要求]約瑟夫游戲的大意是：每30個旅客同乘一條船,因為嚴重超載,加上風高浪大,危險萬分；因此船長告訴乘客,只有將全船一半的旅客投入還中,其余人才能幸免遇難。無奈,大家只得同意這種辦法,并議定30個人圍成一圈,由第一個人數(shù)起,依次報數(shù),數(shù)到第9人,便把他投入大海中,然后再從他的下一個人數(shù)起,數(shù)到第9人,再將他扔進大海中,如此循環(huán)地進行,直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。二：概要設計利用鏈表循環(huán)來解決。首先,就必須先定義一個鏈表,按照所需要的長度進行定義,然后令其為指針指向頭指針,即完成了一個循環(huán)鏈表的創(chuàng)建。接下來先打印鏈表輸出。其次,就是算法實現(xiàn),需要利用指針來進行,數(shù)據(jù)域標記人員編號,先用一個指針循環(huán)查找,找到第一個需要刪除的人,標記為1,先輸出節(jié)點數(shù),再進行刪除。依次循環(huán)查找,直到被刪除的節(jié)點數(shù)量為總人數(shù)的一半的時候則結束。三：程序執(zhí)行流程圖開始開始否是輸出該節(jié)點并且刪除,指針后移,標記下一次的起始位置從報數(shù)位置起,依次循環(huán)數(shù)到找到第m個人程序結束判定剩下人數(shù)是否為一半循環(huán)找到報數(shù)起始位置,用指針標記創(chuàng)建N個節(jié)點的循環(huán)鏈表打印輸出鏈表否是輸出該節(jié)點并且刪除,指針后移,標記下一次的起始位置從報數(shù)位置起,依次循環(huán)數(shù)到找到第m個人程序結束判定剩下人數(shù)是否為一半循環(huán)找到報數(shù)起始位置,用指針標記創(chuàng)建N個節(jié)點的循環(huán)鏈表打印輸出鏈表三：詳細代碼結構鏈表的創(chuàng)建創(chuàng)建頭節(jié)點Josephring<> {head=newNode;//為頭結點申請空間 head->no=1;//為數(shù)據(jù)域賦值head->next=head;//形成循環(huán)鏈表}<2>循環(huán)插入鏈表voidJosephring::CreateJosephus<intn>{ Node*s=head;//標記頭結點 totalnum=n; for<inti=2;i<=n;i++> {Node*w=newNode;//新建一個節(jié)點 w->no=i; w->next=head; s->next=w; s=w;//S作為尾指針 }}首先申請一個節(jié)點,并且W指針指向它,然后從2開始賦值,此時先令新節(jié)點的W指針指向頭結點,再令S指針指向它,依次循環(huán)插入創(chuàng)建。打印輸出鏈表voidJosephring::show<>{cout<<head->no<<"\t";//先輸出頭節(jié)點 Node*q=head->next; while<q!=head> { cout<<q->no<<"\t"; q=q->next;}}先打印輸出頭結點,然后循環(huán)判定,將不等于頭結點的全部輸出。程序主算法voidJosephring::Joseph<intk,intm>//從第k個人開始數(shù)數(shù),數(shù)到m的人出列{ Node*p=head;//工作指針 intj=1;//計數(shù)器 while<j!=k> { j++; p=p->next;//指針后移 }//找到第k個人開始數(shù)1的那個人 for<inti=1;i<=totalnum/2;i++> { Node*w=p;//指針w指向開始數(shù)1的第k個人 j=1;//計數(shù)器,為了找到數(shù)m的那個人 while<j!=m> { j++; p=w; w=w->next; }//找到了數(shù)m的那個人 cout<<w->no<<"\t";//輸出此人的編號 p->next=w->next;//此人出列并刪除節(jié)點 p=p->next; }}首先,先要找到第一個報數(shù)人的位置,用一個計數(shù)器進行循環(huán)對比查找,從第一個位置起依次后移一個位置,直到輸入的數(shù)值等于鏈表上的某個位置數(shù)據(jù)域上的數(shù)值時,停止查找并且標記為P指針。其次,從P位置開始,再用一個W指針標記,兩個指針一次后移循環(huán)查找,當W指針指向的數(shù)據(jù)域等于所輸入的報數(shù)間隔M時,則打印輸出該節(jié)點上的數(shù)據(jù),并且刪除該節(jié)點,P指針后移,作為下一次開始數(shù)的起始位置。最后,依次循環(huán)打印輸出,知道人數(shù)為總人數(shù)的一半時候,程序停止。四：運行結果圖如下輸出船上的總人數(shù)輸入報數(shù)的起始位置輸入報數(shù)人的間隔之后便是最終界面五：設計過程主要問題在設計過程中,開始需要掌握是就是思想,主要就是鏈表的創(chuàng)建跟刪除,在設計過程中,我不知道如何去循環(huán)查找,以及如何循環(huán)輸出,因此剛剛開始無從下手。之后我就開始查找資料,網(wǎng)上參考別人的算法實現(xiàn),在去咨詢同學跟老師,最主要是這個程序不是很難,只要思想掌握好,了解指針鏈表的創(chuàng)建刪除就可以編寫。因此在掌握好循環(huán)算法之后就可以完成編寫。六：心得體會經(jīng)過本次的實訓,使我得到了不少的收獲。使我的動手能力有了一定的提升,并且學會了如何真正去設計一個簡單的程序,在實訓之前,我對程序整體的結構基本上沒什么底子,自己從來沒完整的編寫過一個程序,而這次無疑對我來說我一個最好的練習。雖然每次去詢問都是很簡單的問題,很遭反感,但是每次我都有收獲。本次實訓的主要運用就是鏈表,從而也加強了我對鏈表這反面的了解,最主要的收獲就是對程序整體的結構以及其構造,對我今后的學習有很大的幫助,今后我會多編寫程序來提高自己的綜合水平。附錄：源程序完整代碼#include"iostream.h"#include"stdlib.h"#definemaxsize100//最大人數(shù)structNode{intno;//第幾個人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個節(jié)點的鏈表{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個人開始數(shù)數(shù),數(shù)到m的人出列{Node*p=head;//工作指針intj=1;//計數(shù)器while<j!=k>{j++;p=p->next;//指針后移}//找到第k個人開始數(shù)1的那個人for<inti=1;i<=totalnum/2;i++>{Node*w=p;//指針w指向開始數(shù)1的第k個人Node*q;j=1;//計數(shù)器,為了找到數(shù)m的那個人while<j!=m>{j++;q=w;w=w->next;}//找到了數(shù)m的那個人cout<<w->no<<"\t";//輸出此人的編號q->next=w->next;//此人出列并刪除節(jié)點p=q->next;}}intmain<>{intk,m;//船上的總數(shù),k為從第幾個人開始數(shù),m為數(shù)到m的那個人出列Josephringjosephus;cout<<"船上的總人數(shù)為:";cin>>k;while<k>maxsize||k<0>{cout<<"超出范圍,請重新輸入:";cin>>k;cout<<endl;}cout<<endl<<endl;josephus.CreateJosephus<k>;cout<<"報數(shù)起始的位置:";cin>>