數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-敢死隊問題

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告</p><p>　　題 目: 　敢死隊問題__________</p><p>　　院 系： ______________________</p><p>　　專業(yè)班級： ____</p><p>　　學 號：

2、 _______</p><p>　　學生姓名： ______</p><p>　　指導教師： ______</p><p>　　實驗地點：_________________________</p><p>　　2011年 12 月 27 日<

3、/p><p><b>　　一、程序題目：</b></p><p>　　問題描述: 敢死隊問題 </p><p>　　有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)的辦法來決</p><p>　　定哪個戰(zhàn)士去執(zhí)行任務。如果前一個戰(zhàn)士沒完成任務，則要再派一個戰(zhàn)士上去。現(xiàn)給每個戰(zhàn)</p><p

4、>　　士編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數(shù)，當數(shù)到5時，對應的戰(zhàn)士就去</p><p>　　執(zhí)行任務，且此戰(zhàn)士不再參加下一輪計數(shù)。如果此戰(zhàn)士沒完成任務，再從下一個戰(zhàn)士開始數(shù)</p><p>　　數(shù)，被數(shù)到第5時，此戰(zhàn)士接著去執(zhí)行任務。以此類推，直到任務完成為止。 </p><p>　　排長是不愿意去的，假設(shè)排長為1號，請你設(shè)計一程序，求出從第幾

5、號戰(zhàn)士開始計數(shù)</p><p>　　才能讓排長最后一個留下來而不去執(zhí)行任務。 </p><p>　　要求：至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。</p><p>　　二、算法的主要思想：</p><p>　　分別采用單循環(huán)鏈表和循環(huán)隊列兩種數(shù)據(jù)結(jié)構(gòu)解決此問題。</p><p><b>　　單循環(huán)鏈表結(jié)構(gòu)<

6、;/b></p><p><b>　　需求分析</b></p><p>　　1.本程序輸入隊伍人數(shù)M為任意的，最終輸出記數(shù)的初始位置，首先報數(shù)上限為5，當達到報數(shù)上限時，那名士兵出列執(zhí)行任務，從下個人開始記數(shù)，再次循環(huán)，直到只剩一人，得到其在隊伍中的位置，通過數(shù)學思想求得題目要求即隊長為首的情況下 需要記數(shù)初始位置。</p><p>　　

7、2.程序執(zhí)行的命令包括：</p><p>　?。?）構(gòu)造鏈表；（2）數(shù)據(jù)輸入；（3）執(zhí)行刪除；（4）輸出要求數(shù)值</p><p><b>　　（5）結(jié)束。</b></p><p><b>　　概要設(shè)計</b></p><p>　　以單循環(huán)鏈表為存儲結(jié)構(gòu)，包含三個模塊： </p><

8、;p><b>　　1.主程序模塊 </b></p><p>　　2.構(gòu)造鏈表并初始化</p><p><b>　　3．刪除</b></p><p><b>　　詳細設(shè)計</b></p><p>　　#include<iostream></p>&

9、lt;p>　　using namespace std;</p><p>　　typedef struct node</p><p><b>　　{</b></p><p><b>　　int num;</b></p><p>　　node *next;</p><p>

10、　　}lnode;//定義一個結(jié)構(gòu)體，num表示士兵的編號</p><p>　　void main()</p><p><b>　　{</b></p><p>　　int M;//士兵個數(shù)</p><p><b>　　int i;</b></p><p>　　int star

11、t,count;</p><p><b>　　lnode*l;</b></p><p>　　cout<<"input the value of M:";</p><p><b>　　cin>>M; </b></p><p>　　for(start=1;st

12、art<=M;start++)//start表示從哪個士兵開始</p><p><b>　　{</b></p><p>　　lnode*p=new lnode;//分配空間</p><p>　　l=p;//l為始終指向第一個節(jié)點的指針</p><p>　　l->num=1;//第一個節(jié)點代表的士兵的編號賦值為

13、1</p><p>　　for(i=2;i<=M-1;i++)</p><p><b>　　{</b></p><p>　　lnode*q=new lnode;</p><p><b>　　q->num=i;</b></p><p>　　p->next=q;

14、//創(chuàng)建其他節(jié)點，并將它接到鏈表尾部</p><p>　　p=q;//把指針p移一位，使他指向剛鏈上的節(jié)點</p><p><b>　　}</b></p><p>　　lnode*t=new lnode;//從這里開始創(chuàng)建最后一個節(jié)點</p><p>　　t->num=M;//節(jié)點編號為M</p>&

15、lt;p>　　p->next=t;</p><p><b>　　p=t;</b></p><p>　　t->next=l;//并將最后一個節(jié)點與第一個節(jié)點相連，變成循環(huán)鏈表</p><p>　　p=l;//p指向第一個節(jié)點</p><p>　　for(i=1;i<start;i++)</p&

16、gt;<p><b>　　{</b></p><p>　　p=p->next;</p><p>　　}//一個一個往下找，一直找到編號為start的那個節(jié)點，從這里開始計數(shù)</p><p>　　count=0;//刪除節(jié)點個數(shù)</p><p>　　while(count<M-1)</p&g

17、t;<p><b>　　{</b></p><p>　　for(i=1;i<5;i++)</p><p><b>　　{</b></p><p><b>　　t=p;</b></p><p>　　p=t->next;</p><p&

18、gt;<b>　　}//數(shù)到5就停下</b></p><p>　　t->next=p->next;//刪除該節(jié)點</p><p><b>　　count++;</b></p><p>　　p=t->next;//從下個節(jié)點開始繼續(xù)數(shù)</p><p>　　}//當刪除節(jié)點為M-1個時

19、，結(jié)束</p><p>　　if(p->num==1) break;</p><p><b>　　}</b></p><p>　　cout<<"start from:"<<start<<endl;</p><p><b>　　} </b>

20、</p><p><b>　　調(diào)試分析</b></p><p><b>　　調(diào)試結(jié)果：</b></p><p><b>　　算法分析：</b></p><p>　　在程序設(shè)計前，如果按原題所設(shè)，則需設(shè)隊長為第一位，再分別測試從第幾個開始才能符合條件?，F(xiàn)在改變思想，通過數(shù)學思想：

21、單循環(huán)鏈表本身是一個循環(huán)體，可先求出當從第一個出發(fā)的話，求出每隔5個出去一個，剩下最后一個再令他與1號（排長）對比，如果是1則符題目要求，輸出結(jié)果。</p><p><b>　　總結(jié)</b></p><p>　　通過這次課程設(shè)計我又學到了很多東西,如程序的模塊化設(shè)計思想，同時也加深了對數(shù)據(jù)結(jié)構(gòu)這門課程的理解和學會了如何在實際中應用數(shù)據(jù)結(jié)構(gòu).</p>&l

22、t;p>　　這個方法是用單循環(huán)鏈表來做的，實現(xiàn)的方法是這樣的：首先從第一號開始報數(shù)，循環(huán)到指定的偏移位置刪除結(jié)點，直至剩下一個結(jié)點。然后設(shè)計輸出，如果最后一個為隊長，則第一個報數(shù)的人的編號即為所求，輸出，結(jié)束。</p><p><b>　　循環(huán)隊列結(jié)構(gòu)</b></p><p><b>　　需求分析</b></p><p&

23、gt;　　本程序輸入隊伍人數(shù)M為任意的，最終輸出記數(shù)的初始位置，首先知道報數(shù)上限為5，當達到報數(shù)上限時，那名士兵前面的人出列后按順序插到對尾，之后該士兵出列執(zhí)行任務，從下個人開始記數(shù)，再次重復，直到只剩一人，得到其在隊伍中的位置，通過數(shù)學思想求得題目要求即隊長為首的情況下 需要記數(shù)初始位置。</p><p>　　程序執(zhí)行的命令包括：</p><p>　?。?）構(gòu)造隊列；（2）數(shù)據(jù)輸入；（3

24、）執(zhí)行刪除；（4）輸出要求數(shù)值</p><p><b>　　（5）結(jié)束。</b></p><p><b>　　程序測試</b></p><p>　　當輸入的總數(shù)是10時，輸出結(jié)果應該是從第9個戰(zhàn)士開始計數(shù)。</p><p><b>　　概要設(shè)計</b></p>&

25、lt;p>　　本程序其實質(zhì)是約瑟夫環(huán)問題,本次實驗用了循環(huán)隊列結(jié)構(gòu),并運用模塊化的程序設(shè)計思想,算法的實現(xiàn)是這樣的:</p><p>　　1. 定義結(jié)構(gòu)體類型</p><p><b>　　定義變量并初始化</b></p><p><b>　　隊列循環(huán)模塊初始化</b></p><p><

26、b>　　判斷隊列是否滿</b></p><p><b>　　滿足題目條件,輸出</b></p><p><b>　　詳細設(shè)計</b></p><p><b>　　模塊的分析：</b></p><p>　　#include<iostream> <

27、;/p><p>　　using namespace std; </p><p>　　#define maxlen 100 //假定預分配的隊列空間最多為100個元素 </p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　int data[ma

28、xlen]; </p><p>　　int front; //代表數(shù)組存放的第一個數(shù)據(jù)對應的下標，即對頭</p><p>　　int rear; //代表數(shù)組存放的最后一個數(shù)據(jù)對應的下標，對尾</p><p>　　int count; //計數(shù)器，記錄隊中元素總數(shù) </p><p>　　}CirQueue; </p>

29、<p>　　// 初始化對 令隊為空 </p><p>　　void queue(CirQueue *Q) </p><p><b>　　{ </b></p><p>　　Q->front=Q->rear=0; //對頭等于對尾代表隊列為空</p><p>　　Q->count=0;

30、 </p><p><b>　　} </b></p><p>　　// 判隊列是否為空 </p><p>　　int empty(CirQueue *Q) </p><p><b>　　{ </b></p><p>　　if(Q->count==0) return

31、 1; //如果隊里的元素個數(shù)為0，隊列空，返回1</p><p>　　else return 0;</p><p><b>　　} </b></p><p><b>　　//判隊列是否滿 </b></p><p>　　int full(CirQueue *Q) </p><p

32、><b>　　{ </b></p><p>　　if(Q->count==maxlen) return 1;</p><p>　　else return 0;</p><p><b>　　} </b></p><p><b>　　//將元素進隊 </b></p

33、><p>　　void append(CirQueue *Q,int x) </p><p><b>　　{ </b></p><p>　　if (full(Q)) </p><p><b>　　{ </b></p><p>　　cout<<"列滿\n&qu

34、ot;; </p><p><b>　　exit(1); </b></p><p>　　} //如果堆滿就退出程序</p><p>　　Q->count ++; //否則就進入，元素總數(shù)加一</p><p>　　Q->data[Q->rear]=x; //數(shù)組的最后一位賦值為x</p&g

35、t;<p>　　Q->rear=(Q->rear+1)%maxlen; </p><p><b>　　} </b></p><p><b>　　//元素出隊列 </b></p><p>　　int serve(CirQueue *Q) </p><p><b>　

36、　{ </b></p><p>　　int temp; </p><p>　　if(empty(Q)) </p><p><b>　　{ </b></p><p>　　cout<<"隊列為空\n"; //下溢,退出運行 </p><p><b>

37、;　　exit(1); </b></p><p><b>　　} </b></p><p>　　temp=Q->data[Q->front]; //將隊頭的元素取出到temp里面</p><p>　　Q->count--; //隊列元素個數(shù)減1 </p><p>　　Q->front

38、=(Q->front+1)%maxlen; //循環(huán)意義下的頭指針后移（即數(shù)組中第一個元素存放的位置的下標加1） </p><p>　　return temp; </p><p><b>　　} </b></p><p>　　void main() </p><p><b>　　{ </b>&

39、lt;/p><p>　　int M,i,start,count,j; </p><p>　　CirQueue s; </p><p>　　cout<<"input the value of M :"; </p><p><b>　　cin>>M; </b></p>&

40、lt;p>　　for(start=1;start<=M;start++)//start為測試起點 </p><p><b>　　{ </b></p><p>　　queue(&s); </p><p>　　for(i=1;i<=M;i++) </p><p><b>　　{ </

41、b></p><p>　　append(&s,i); </p><p>　　} //將所有士兵的編號依次進隊</p><p>　　for(i=1;i<start;i++) </p><p><b>　　{ </b></p><p>　　j=serve(&s);

42、</p><p>　　append(&s,j); //這兩句是把對頭的元素取出來然后放到對尾去，經(jīng)過這個循環(huán)以后，要從那個開始的士兵的編號就會在隊的對頭位置了</p><p><b>　　} </b></p><p>　　count=0; //刪除結(jié)點數(shù)</p><p>　　while(count<

43、;M-1) </p><p><b>　　{ </b></p><p>　　for(i=1;i<5;i++) </p><p><b>　　{ </b></p><p>　　j=serve(&s); </p><p>　　append(&s,j); //

44、這兩句是把對頭的元素取出來然后放到對尾</p><p>　　} //經(jīng)過這個循環(huán)以后，對頭的那個節(jié)點的值就是數(shù)到5對應的節(jié)點</p><p>　　j=serve(&s); //把這個節(jié)點出隊，但是沒有在把它放到對尾，就相當于把它刪除了</p><p>　　count++; </p><p>　　} //同第一個方法是一樣，刪除點數(shù)

45、為m-1是結(jié)束循環(huán)</p><p>　　if(s.data[s.front]==1) break; //此時隊只剩一個點，如果是排長就輸出</p><p><b>　　} </b></p><p>　　cout<<"start from :"<<start<<endl; </p&g

46、t;<p><b>　　}</b></p><p><b>　　調(diào)試結(jié)果</b></p><p><b>　　系統(tǒng)界面</b></p><p><b>　　算法分析</b></p><p>　　本次采用循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)方法實現(xiàn)，但其先進先出

47、的算法結(jié)構(gòu)加大了本程序的時間及空間復雜度。</p><p><b>　　總結(jié)</b></p><p>　　這個方法是用循環(huán)隊列來做的，實現(xiàn)的方法是這樣的：首先從第一號開始報數(shù)，循環(huán)到指定的偏移位置其前面節(jié)點出對后插到隊尾，該結(jié)點出對即刪除，直至剩下一個結(jié)點。然后設(shè)計輸出，令這個位置為隊長位置，隊首為開始報數(shù)的位置，并按此輸出即為所求。</p><p

48、><b>　　體會與感受：</b></p><p>　　在程序的編寫中不能一味得向已有的程序進行模仿,而要自己去摸索,去尋求最好的解決方式,只有帶著問題去反復進行實踐,才能更熟練的掌握和運用,當然,對現(xiàn)有的程序也要多去接觸,因為有些程序是我們無法在短時間內(nèi)想出來的.最重要的一點就是要持之以恒,要經(jīng)常性的復習原來所接觸的程序,這樣才能保證我們有足夠的經(jīng)驗去面對程序問題。</p>