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

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

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

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

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

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

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

7、continue;else if(num=1)/ 對輸入戰(zhàn)士數(shù)目為 1 的情況，作出反 應cout << " 只有一個戰(zhàn)士，別無選擇 !n 請重新輸入 :" cin>>num;continue;switch(choice)/ 當輸入大于 1 人時，根據選擇的數(shù)據類 型，進行處理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; / 刪除結點數(shù)while(count<num-1)for(i=1;i<CCC;i+)j=DeQueue(&s);EnQueue(&s,j); / 這兩句是把隊頭的元素取出來然后放到對尾;/ 經過這個循環(huán)以后，隊頭的那個節(jié)點的值就是數(shù)到 5 對應的節(jié)點 j=DeQueue(&s); / 把這個節(jié)點出隊，但是沒有在把它放到隊尾，就相當于把 它刪除了count+; /同第一個方法是一樣，刪除點數(shù)為m-1是結束循環(huán)if(s.datas.front=1) break;/此時隊只剩一個點，如果是排長就輸出cout<<

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

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

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

13、01 年 1月14致謝感謝指導老師，及同學們對我的幫助。15即對頭對尾開始菜單，版權聲明循環(huán)隊列函數(shù)聲附錄: 源代碼( 帶注釋 )#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; /代表數(shù)組存放的第一個數(shù)據對應的下標，int rear; /代表數(shù)組存放的最后一個數(shù)據對應的下標，int count; / 計數(shù)器，記錄隊中元素總數(shù) CirQueue;/ 函數(shù)聲明/void display1(); / 含有聲明void display2();/選擇菜單void clearline();/清除多余的輸入/明 void Initial(CirQueue *Q);/初始化隊列函數(shù) int IsEmpty(CirQueue*Q);/ 判斷隊是否為空 int IsFull(CirQueue *Q);/判

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

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

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

18、ue;else if(num=1)/對輸入戰(zhàn)士數(shù)目為 1 的情況，作出反應cout << " 只有一個戰(zhàn)士，別無選擇 !n 請重新輸入 :"cin>>num;continue;cout << " 請輸入報數(shù)數(shù)字 :"cin >> CCCC;switch(choice)/ 當輸入大于 1 人時，根據選擇的數(shù)據類型，進行 處理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();/開始菜單和版權聲明函/ 數(shù)定義void display1()cout <<H *'、<< endl<< " * 敢死隊 唐振乙 *" << endl<< " * 版權所有 翻版必究 *" << endl<<H *'、<< "nnnnn"cout << " 請選擇數(shù)據類型 : 1 、順序表

20、 2 、單向循環(huán)鏈表 3 、循環(huán)隊列 4 、數(shù) 組 Q 、退出 " << endl;void display2 ()/ 選擇菜單cout << "nn 請選擇數(shù)據類型 : 1 、順序表 2 、單向循環(huán)鏈表 3 、循環(huán)隊列4、數(shù)組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; / 如果隊里的元素個數(shù)為 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 +; / 否則就進入，元素總數(shù)加一Q->dataQ->rear=x; / 數(shù)組的最后一位賦值為 xQ->rear=(Q->rear+1)%QueueSize; / 改變數(shù)組最后一位的下標值，如果不是 循環(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-; / 隊列元素個數(shù)減 1Q->front=(Q->front+1)%QueueSize; / 循環(huán)意義下的頭指針后移 ( 即數(shù)組中第 一個元素存放的位置的下標加 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; / 刪除結點數(shù)while(count<num-1)for(i=1;i<CCC;i+)j=DeQueue(&s);EnQueue(&s,j);

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

26、, int CCC) /M 為士兵個數(shù)int i;int start,count;lnode *l;for(start=1;start<=M;start+)/ start表示從哪個士兵開始數(shù)/ 初始化鏈表lnode *p=new lnode; / 分配空間l=p; / l 為始終指向第一個節(jié)點的指針l->num=1; / 第一個節(jié)點代表的士兵編號賦值為 1，至此第一個節(jié)點創(chuàng)建完畢f(xié)or(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é)點，從這里開始計 數(shù)21count=0; / 刪除的節(jié)點的個數(shù)while(count<M-1)for(i=1;i<CCC;i+)t=p

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