數據結構課程設計敢死隊問題終極版

1、數據結構課程設計：敢死隊問題（終極版）*實踐教學*計算機與通信學院 2011年春季學期 算法與數據結構 課程設計 題 目 : 敢死隊問題 專業(yè)班級 : 軟件一班 姓 名 : 唐振乙 學 號 : 09240302 指導教師 : 張 永 成 績 :目錄摘要2、八前言.正3文.4一、需求分析41. 數據需求分析42. 功能需求分析4二、程序總體設計51. 模塊劃分52. 總體流程圖53. 函數調用關系圖64. 部分偽代碼7三、調試分析11A. 調試中遇到的問題及解決方法11B. 運行演示12總結13參考文獻.14致謝.15附錄: 源代碼（帶注釋）161摘要敢死隊問題是根據著名的“約瑟夫環(huán)”演變而來的

2、敢死隊問題的處理與計算來設計的一個系統。整個系統從符合操作簡便、界面友好、靈活、實用、安全的要求 出發(fā)，完成敢死隊問題的全過程，包括創(chuàng)建四個數據結構 ( 順序存儲結構、單鏈表 存儲結構、循環(huán)隊列存儲結構、數組存儲結構 ) 、數據的處理與計算、數據的分 析、結果的輸出。關鍵字 : 敢死隊問題 順序表 單向循環(huán)鏈表 循環(huán)隊列 數組2、八前言有 M 個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數數的辦 法來決定哪個戰(zhàn)士去執(zhí)行任務。如果前一個戰(zhàn)士沒完成任務，則要再派一個戰(zhàn)士上 去?，F給每個戰(zhàn)士編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數，當數 到 5 時，對應的戰(zhàn)士就去執(zhí)行任務，且此

3、戰(zhàn)士不再參加下一輪計數。如果此戰(zhàn)士沒 完成任務，再從下一個戰(zhàn)士開始數數，被數到第 5 時，此戰(zhàn)士接著去執(zhí)行任務。以 此類推，直到任務完成為止。排長是不愿意去的，假設排長為 1 號，請你設計一程序，求出從第幾號戰(zhàn)士開 始計數才能讓排長最后一個留下來而不去執(zhí)行任務。3正文一、需求分析1、數據需求分析 :本系統的主要數據是正整數、結構體、指針(1) 正整數信息包括 : 隊伍的人數，報數的數值，報數開始的位置。 (2) 結構體 儲存每個戰(zhàn)士的信息。(3) 指針包括鏈表的頭指針、尾指針、當前指針。2、功能分析 :本系統要實現對敢死隊問題的模擬解決需要實現一下幾個功能(1)創(chuàng)建存儲結構：創(chuàng)建順序表，創(chuàng)建單

4、鏈表，創(chuàng)建數組。 (2)數據的輸入：把隊伍的人數，報數 的數值輸入。(3)數據的處理；對隊伍的人數，報數的數值進行計算。 (4)結果的 輸出:每執(zhí)行一次任務的戰(zhàn)士的編號、執(zhí)行結果、報數開始的位置輸出，包括顯示器和文件輸出。4二、程序總體設計1、模塊劃分(1)、操作界面模塊 提供操作界面的信息輸出模式。(2)、單循環(huán)鏈表存儲結 構模塊 用于通過運用順序結構模塊來計算結果。(3) 、循環(huán)隊列存儲結構模塊用于通過運用單鏈表結構模塊來計算結果。(4) 、順序表模塊用于通過運用數組結構模塊來計算結果。(5)、數組表模塊用于通過運用數組結構模塊來計算結果。2、總體流程圖、函數調用關系圖(1)總體流程圖dx

5、KUMW,ft- 31牟向斗 K 敦I歯斗隊芋廿順耳+裊扳如Id(2)函數調用關系圖3、部分偽代碼(1)主函數void mai n()display1();in t choice;/菜單選擇int num;/戰(zhàn)士數目while(ci n >> choice)7if(choice<1 | choice>4)cout << " 請選擇正確的菜單 :"continue;if(choice=1 | choice=3 | choice=4)的戰(zhàn)士數目 ( 數cout << " 請輸入不超過 " << Qu

6、eueSize <<elsecout <<" 請輸入戰(zhàn)士數目 (數字) :"/ 輸入戰(zhàn)士數目 while(!(cin >> num)cin.clear();while(cin.get()!='n')continue;cout << " 請正確輸入 : "clearline();while(num<2)if(num<1) /對輸入的樹木小于 1，作出反應 cout << " 戰(zhàn)士數目不能少于一人 !n 請重新輸入 :" cin>>num;

7、continue;else if(num=1)/ 對輸入戰(zhàn)士數目為 1 的情況，作出反 應cout << " 只有一個戰(zhàn)士，別無選擇 !n 請重新輸入 :" cin>>num;continue;switch(choice)/ 當輸入大于 1 人時，根據選擇的數據類 型，進行處理case 1: Nlist(num); break;case 2: One_way(num); break;case 3: Cirqueue(num); break;case 4: Array(num); break;display2();/ 再次輸出選擇菜單8(2) 循環(huán)隊列

8、方法void Cirqueue(int num,int CCC)int i,start,count,j;CirQueue s;for(start=1;start<=num;start+)/start 為測試起點Initial(&s); /初始化隊列for(i=1;i<=num;i+) / 將所有士兵的編號依次進隊EnQueue(&s,i); ;for(i=1;i<start;i+)j=DeQueue(&s); / 刪除隊頭結點EnQueue(&s,j);/ 這兩句是把隊頭的元素取出來然后放到 隊尾去，經過這個循環(huán)以后，要從那個開始的士兵的編號就

9、會在隊的 9隊頭位置了;count=0; / 刪除結點數while(count<num-1)for(i=1;i<CCC;i+)j=DeQueue(&s);EnQueue(&s,j); / 這兩句是把隊頭的元素取出來然后放到對尾;/ 經過這個循環(huán)以后，隊頭的那個節(jié)點的值就是數到 5 對應的節(jié)點 j=DeQueue(&s); / 把這個節(jié)點出隊，但是沒有在把它放到隊尾，就相當于把 它刪除了count+; /同第一個方法是一樣，刪除點數為m-1是結束循環(huán)if(s.datas.front=1) break;/此時隊只剩一個點，如果是排長就輸出cout<<

10、" 應從第 :"<<start<< " 位戰(zhàn)士開始計數 "<< endl;10三、 調試分析A、調試中遇到的問題及解決方法說明:(1) 本程序運行的環(huán)境是 Visual C+ 2010;(2) 程序運行后，顯示的提示信息為選擇使用數據類型的菜單，正確輸入 后， 會依次出現提示輸入戰(zhàn)士數目，報數數字。均正確輸入后，即可輸出相應的計算結 果。(3) 調試調試過程中，出現如下錯誤信息 :發(fā)現錯誤為：“using namespace std ”指令只聲明在main()內部。改正為：將“using namespace std ”

11、指令聲明為全局范圍，即可正確運行11B：程序運行演示:12通過這次課程設計我又學到了很多東西 , 如程序的模塊化設計思想等，同時也 加深了對數據結構這門課程的理解和學會了如何在實際中應用數據結構編程。 經過分析，了解到此次課程設計敢死隊問題的核心其實就是經典的約瑟夫環(huán)問 題，只是在其輸出上稍有不同而已。這個方法是用單循環(huán)鏈表來做的，實現的方法是這樣的 : 首先從第一號開始報 數，循環(huán)到指定的偏移位置刪除結點，直至剩下一個結點。然后設計輸出，令這個 位置為隊長位置，隊首為開始報數的位置，并按此輸出即為所求。這種方法大大的 降低了時間復雜度，復雜度為 O（mn）。13參考文獻1 嚴蔚敏，吳偉民 .

12、 數據結構 （C 語言版）. 清華大學出版社 .2 嚴蔚敏，吳偉民 . 數據結構題集 （C 語言版 ） . 清華大學出版社.3 DATA STRUCTURE WITH C+.+William Ford,William Topp .清華大學出版社 （影印版 ）.4 譚浩強 . c 語言程序設計 . 清華大學出版社 .5（ 數據結構與算法分析 （Java 版） , A Practical Introduction to DataStructures and Algorithm Analysis Java Edition Clifford A. Shaffer ,張銘,劉曉丹譯 電子工業(yè)出版社 20

13、01 年 1月14致謝感謝指導老師，及同學們對我的幫助。15即對頭對尾開始菜單，版權聲明循環(huán)隊列函數聲附錄: 源代碼( 帶注釋 )#include <iostream> using namespace std; const int QueueSize = 100; / 單向循環(huán)鏈表結點定義typedef struct lnode int num; / 戰(zhàn)士編號struct lnode *next; /指向下個結點的指針 lnode;/ 順序表定義typedef struct NList int length;int mark100;NList;/ 循環(huán)隊列定義typedef str

14、uct CirQueue int dataQueueSize;int front; /代表數組存放的第一個數據對應的下標，int rear; /代表數組存放的最后一個數據對應的下標，int count; / 計數器，記錄隊中元素總數 CirQueue;/ 函數聲明/void display1(); / 含有聲明void display2();/選擇菜單void clearline();/清除多余的輸入/明 void Initial(CirQueue *Q);/初始化隊列函數 int IsEmpty(CirQueue*Q);/ 判斷隊是否為空 int IsFull(CirQueue *Q);/判

15、斷隊列是否為空 voidEnQueue(CirQueue *Q,int x);/ 入隊操作16int DeQueue(CirQueue *Q);/ 刪除操作void Cirqueue(int num, int CCC);/隊列方法處理數據/void One_way(int M, int CCC);/單向循環(huán)鏈表算法/void Array(int people, int CCC);/數組算法 /void Nlist(int num, int CCC);/順序表算法 /void main()display1();int choice;/ 菜單選擇int num;/ 戰(zhàn)士數目int CCCC;/ 報

16、數數字while(cin >> choice)/對輸入非菜單選項的數字作出反應if(choice<1 | choice>4)cout << " 請選擇正確的菜單 :"continue;/ 輸入戰(zhàn)士數目if(choice=1 | choice=3 | choice=4)/ 當選擇的數據結構中含有數 組時，提示最大值cout << " 請輸入不超過 " << QueueSize << " 的戰(zhàn)士數目 ( 數字 ):"elsecout <<" 請輸

17、入戰(zhàn)士數目 (數字) :"while(!(cin >> num)/ 對輸入進行檢測并作出反應cin.clear();while(cin.get()!='n')continue;cout << " 請正確輸入 : "clearline();/對輸入如“ 123abc”的情況作出處理，清除結尾的字符while(num<2)if(num<1) / 對輸入的樹木小于 1，作出反應 cout << " 戰(zhàn)士數目不能少于一人 !n 請重新輸入 :"cin>>num;17contin

18、ue;else if(num=1)/對輸入戰(zhàn)士數目為 1 的情況，作出反應cout << " 只有一個戰(zhàn)士，別無選擇 !n 請重新輸入 :"cin>>num;continue;cout << " 請輸入報數數字 :"cin >> CCCC;switch(choice)/ 當輸入大于 1 人時，根據選擇的數據類型，進行 處理case 1: Nlist(num,CCCC); break;case 2: One_way(num,CCCC); break;case 3: Cirqueue(num,CCCC); br

19、eak;case 4: Array(num,CCCC); break;輸出菜單，進行下一次測試display2();/開始菜單和版權聲明函/ 數定義void display1()cout <<H *'、<< endl<< " * 敢死隊 唐振乙 *" << endl<< " * 版權所有 翻版必究 *" << endl<<H *'、<< "nnnnn"cout << " 請選擇數據類型 : 1 、順序表

20、 2 、單向循環(huán)鏈表 3 、循環(huán)隊列 4 、數 組 Q 、退出 " << endl;void display2 ()/ 選擇菜單cout << "nn 請選擇數據類型 : 1 、順序表 2 、單向循環(huán)鏈表 3 、循環(huán)隊列4、數組Q、退出"<< endl;18void clearline() /清除當前行多余的部分while(cin.get()!='n') continue;循環(huán)隊/列方法 / 初始化對 令隊為空void Initial(CirQueue *Q) Q->front=Q->rear=0;

21、/ 對頭等于對尾代表隊列為空Q->count=0;/ 判隊列是否為空int IsEmpty(CirQueue *Q) if(Q->count=0) return 1; / 如果隊里的元素個數為 0，隊列空，返回 1 else return 0;/ 判隊列是否滿int IsFull(CirQueue *Q) if(Q->count=QueueSize) return 1;else return 0;/ 將元素進隊void EnQueue(CirQueue *Q,int x)if (IsFull(Q)printf(" 列滿 n");exit(1); ;/ 如果

22、堆滿就退出程序Q->count +; / 否則就進入，元素總數加一Q->dataQ->rear=x; / 數組的最后一位賦值為 xQ->rear=(Q->rear+1)%QueueSize; / 改變數組最后一位的下標值，如果不是 循環(huán)的隊列那么下標只要簡單的加 1 就 行，但是循環(huán)的話要考慮下標已經為最大而再加 1 就要到下標為 0(即又循環(huán)到 最開始 )的情況，所以要用 (Q->rear+1)%QueueSize / 元素出隊列int DeQueue(CirQueue *Q) int temp;19if(IsEmpty(Q)printf(" 隊

23、列為空 n"); / 下溢, 退出運行exit(1);temp=Q->dataQ->front; / 將隊頭的元素取出到 temp 里面Q->count-; / 隊列元素個數減 1Q->front=(Q->front+1)%QueueSize; / 循環(huán)意義下的頭指針后移 ( 即數組中第 一個元素存放的位置的下標加 1)return temp;/方法void Cirqueue(int num,int CCC) int i,start,count,j;CirQueue s;for(start=1;start<=num;start+)/start 為測

24、試起點Initial(&s); / 初始化隊列for(i=1;i<=num;i+) / 將所有士兵的編號依次進隊EnQueue(&s,i); ;for(i=1;i<start;i+)j=DeQueue(&s); / 刪除隊頭結點EnQueue(&s,j);/ 這兩句是把隊頭的元素取出來然后放到隊尾去，經過這個 循環(huán)以后，要從那個開始的士兵的編號就會在隊的隊頭位置了;count=0; / 刪除結點數while(count<num-1)for(i=1;i<CCC;i+)j=DeQueue(&s);EnQueue(&s,j);

25、/ 這兩句是把隊頭的元素取出來然后放到對尾;/ 經過這個循環(huán)以后，隊頭的那個節(jié)點的值就是數到 5 對應的節(jié)點 j=DeQueue(&s); / 把這個節(jié)點出隊，但是沒有在把它放到隊尾，就相當于 把它刪除了20count+; /同第一個方法是一樣，刪除點數為m-1是結束循環(huán)if(s.datas.front=1) break;/此時隊只剩一個點，如果是排長就輸出cout<<" 應從第 :"<<start<< " 位戰(zhàn)士開始計數 "<< endl; /單向循環(huán)鏈表方法 void One_way(int M

26、, int CCC) /M 為士兵個數int i;int start,count;lnode *l;for(start=1;start<=M;start+)/ start表示從哪個士兵開始數/ 初始化鏈表lnode *p=new lnode; / 分配空間l=p; / l 為始終指向第一個節(jié)點的指針l->num=1; / 第一個節(jié)點代表的士兵編號賦值為 1，至此第一個節(jié)點創(chuàng)建完畢for(i=2;i<=M-1;i+)lnode *q=new lnode;q->num=i;p->next=q; / 創(chuàng)建其他節(jié)點，并將它接到鏈表尾部p=q; / 把指針 p 移后一位，使

27、他指向剛鏈上的節(jié)點，也就是當前的 最后一個節(jié)點lnode *t=new lnode; /從這里開始創(chuàng)建最后一個節(jié)點t->num=M; / 節(jié)點編號為 Mp->next=t; / 連上去p=t;t->next=l; / 并將最后一個節(jié)點與第一個節(jié)點相連，變成循環(huán)鏈表/ 找到起點p=l; / P 指向第一個節(jié)點for(i=1;i<start;i+)p=p->next;/ 一個一個往下找，一直到找到編號為 start 的那個節(jié)點，從這里開始計 數21count=0; / 刪除的節(jié)點的個數while(count<M-1)for(i=1;i<CCC;i+)t=p

28、;p=t->next; ; / 數到 5 就停下t->next=p->next; / 將該節(jié)點刪除count+;/ 刪除結點的個數加 1 p=t->next; /從下一個節(jié)點開始繼續(xù)數 / 當刪除的節(jié)點為 M-1 個時，就結束if(p->num=1)break;/ 此時表里面應該只有一個節(jié)點了，判斷節(jié)點的編號是不是等于1，也就是是不是代表排長 ，如果是就結束循環(huán)cout<<" 應從第 :"<<start<< " 位戰(zhàn)士開始計數 "<< endl; / 將從哪里開始的那 個士兵編號輸出來/ 數組算法 / 數組算法/ 數組 算法 void Array(int num, int CC