數(shù)據(jù)結構課程設計報告--- 敢死隊問題

1、<p>　　課 程 設 計</p><p><b>　?。〝?shù)據(jù)結構）</b></p><p><b>　　二○一一年一月十日</b></p><p>　　課程設計任務書及成績評定</p><p>　　Ⅰ、題目的目的和要求： </p><p>　　鞏固和加深對數(shù)

2、據(jù)結構的理解，通過上機實驗、調試程序，加深對課本知識的理解，最終使學生能夠熟練應用數(shù)據(jù)結構的知識寫程序。</p><p>　?。?）通過本課程的學習，能熟練掌握幾種基本數(shù)據(jù)結構的基本操作。</p><p>　?。?）能針對給定題目，選擇相應的數(shù)據(jù)結構，分析并設計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。</p><p>　?、颉⒃O計進度及完成情況</p&

3、gt;<p>　?、?、主要參考文獻及資料</p><p>　　[1] 嚴蔚敏 數(shù)據(jù)結構（C語言版）清華大學出版社 1999</p><p>　　[2] 嚴蔚敏 數(shù)據(jù)結構題集（C語言版）清華大學出版社 1999</p><p>　　[3] 徐寶文等譯 C語言程序設計 清華大學出版社</p><p>　　[4] 與所用編程環(huán)境相

4、配套的C語言或C++相關的資料</p><p><b>　?、?、成績評定：</b></p><p>　　設計成績： （教師填寫）</p><p>　　指導老師： （簽字）</p><p>　　二○一一 年 一 月 十 日</p>&

5、lt;p><b>　　目 錄</b></p><p>　　第一章 概述……………………………………………………………1</p><p>　　第二章 系統(tǒng)分析………………………………………………………2</p><p>　　第三章 概要設計………………………………………………………3</p><p>　　第四章 詳

6、細設計………………………………………………………4</p><p>　　第五章 運行與測試……………………………………………………9</p><p>　　第六章 總結與心得……………………………………………………13</p><p>　　參考文獻………………………………………………………………14</p><p><b>　　第一章

7、 概述</b></p><p>　　課程設計是實踐性教學中的一個重要環(huán)節(jié)，它以某一課程為基礎，可以涉及和課程相關的各個方面，是一門獨立于課程之外的特殊課程。課程設計是讓同學們對所學的課程更全面的學習和應用，理解和掌握課程的相關知識。《數(shù)據(jù)結構》是一門重要的專業(yè)基礎課，是計算機理論和應用的核心基礎課程。</p><p>　　數(shù)據(jù)結構課程設計，要求學生在數(shù)據(jù)結構的邏輯特性和物理表示

8、、數(shù)據(jù)結構的選擇和應用、算法的設計及其實現(xiàn)等方面，加深對課程基本內容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。</p><p>　　在這次的課程設計中我選擇的題目是圖書管理。傳統(tǒng)的人工圖書管理，基本業(yè)務活動有對一本書的采編入庫、清除庫存、借閱和歸還等等，但是人工統(tǒng)計操作起來效率相對來說要低，也容易出錯。但是現(xiàn)在這些業(yè)務借助計算機系統(tǒng)完成后，效率可以得到提高，也可以減

9、少出錯的幾率?？梢允箞D書管理的日常業(yè)務更加的方便，迅捷，減少很多勞動量。</p><p>　　課程設計的目的意義：加深對循環(huán)隊列和數(shù)組的理解，以及對循環(huán)隊列和數(shù)組的實際應用，加強自己的動手操作能力，增加對課程的興趣，而不是枯燥的看課本。</p><p>　　課程設計的問題：敢死隊問題</p><p>　　有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)

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

11、才能讓排長最后一個留下來而不去執(zhí)行任務。</p><p><b>　　第二章 系統(tǒng)分析</b></p><p>　　敢死隊問題包括：兩個數(shù)據(jù)的輸入，一個是隊員的數(shù)量，另一個是模擬的形式。由于問題給出的數(shù)數(shù)的數(shù)量為5 ，所以k 值就默認為5 ，不再設置數(shù)據(jù)輸入。故重點是要完成兩種數(shù)據(jù)結構形式的刪除，循環(huán)標記等操作。</p><p>　　演示程序是

12、以用戶于計算機的對話方式執(zhí)行，這需要調用一個清屏函數(shù)來完成使用者與計算機語言之間界面的處理。</p><p><b>　　程序執(zhí)行時的命令：</b></p><p>　　本程序為了使用時的方便，采用阿拉伯數(shù)字的方式來完成程序的等各種選擇輸入，幾乎不用輸入什么特殊的命令。（要注意輸入時必須用數(shù)字，否者可能會引起一些死循環(huán)）</p><p><

13、;b>　　測試數(shù)據(jù)。</b></p><p><b>　　1 5 13 </b></p><p>　　數(shù)據(jù)運行結果 在第五章有詳細的截圖</p><p><b>　　第三章 概要設計</b></p><p>　　數(shù)據(jù)結構類型： 一種是循環(huán)隊列，另一種是數(shù)組形式</p>

14、;<p>　　其中循環(huán)隊列操作只需要刪除操作，用數(shù)組形式處理和運算上則較復雜些</p><p>　　因此，循環(huán)隊列占優(yōu)勢</p><p>　　程序總體上分為兩大塊，一塊是循環(huán)隊列的模擬，一塊是數(shù)組形式的模擬</p><p>　　這兩種形式功能都是模擬每個開始數(shù)數(shù)的位置對員的死亡順序，其中循環(huán) 隊列的函數(shù)接口為：lianbiao(n) ，數(shù)組的函數(shù)

15、接口為：array(n);</p><p>　　兩模塊算法基本一致，數(shù)據(jù)結構形式不同而已</p><p><b>　　算法概述：</b></p><p>　　For(int i=1;i<=n;i++)</p><p><b>　　{</b></p><p><b&

16、gt;　　初始化數(shù)據(jù)</b></p><p>　　對每個位置進行模擬/調用del /delx 函數(shù)進行模擬</p><p><b>　　判斷是否安全</b></p><p><b>　　}</b></p><p>　　Printf->安全的位置；</p><p&

17、gt;<b>　　第四章 詳細設計</b></p><p><b>　　1：存儲結構形式</b></p><p>　　struct node</p><p><b>　　{</b></p><p><b>　　int data;</b></p>

18、<p>　　node *next;</p><p><b>　　};</b></p><p>　　struct nodel</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　

19、}sqlist[N];</p><p><b>　　2：成員函數(shù)部分</b></p><p>　　int del(node *p,node *q) // 鏈表的刪除操作</p><p><b>　　{</b></p><p>　　while(q->next!=q)</p>&l

20、t;p><b>　　{</b></p><p><b>　　int k=4;</b></p><p>　　while(k--)</p><p><b>　　{</b></p><p>　　p=p->next;</p><p>　　q=q-&g

21、t;next;</p><p><b>　　}</b></p><p>　　if(q->data==1)</p><p><b>　　{</b></p><p><b>　　return 0;</b></p><p><b>　　}<

22、;/b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cout<<q->data<<" ";</p><p>　　q=q->next; p->next=q;</

23、p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(q->next==q)</p><p><b>　　{</b></p><p><b>　　return 1;</b></

24、p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void lianbiao(int n)</p><p><b>　　{</b></p><p>　　int i,flag=0;</p><p

25、>　　for( i=1;i<=n;i++)// 循環(huán)找出安全的開始位置</p><p><b>　　{</b></p><p><b>　　int k=i;</b></p><p>　　cout<<"\n\n報數(shù)的位置為"<<k<<"時的排長之前

26、的人員死亡順序:\n";</p><p>　　node *head=new node,*t=head;</p><p>　　head->data=1;</p><p>　　head->next=head;</p><p><b>　　int j=1;</b></p><p>

27、　　while(++j<=n) //構造循環(huán)隊列</p><p><b>　　{</b></p><p>　　node *p=new node;</p><p>　　p->data=j;</p><p>　　p->next=t->next;</p><p>　　t-&g

28、t;next=p;</p><p>　　t=t->next;</p><p><b>　　}</b></p><p><b>　　t=head;</b></p><p>　　node *p=head,*q;// 設置p q 指針</p><p>　　while(p-&g

29、t;next!=head)</p><p>　　p=p->next;</p><p><b>　　q=head;</b></p><p>　　while(--k) //循環(huán)找開始的位置</p><p><b>　　{</b></p><p>　　p=p->

30、next;</p><p>　　q=q->next;</p><p><b>　　}</b></p><p>　　if(del(p,q)==1) //判斷位置是否安全</p><p><b>　　{</b></p><p>　　cout<<endl<

31、;<i<<"位置安全\n";</p><p><b>　　flag=i;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p

32、><p>　　cout<<endl<<i<<"位置不安全\n";</p><p>　　continue ;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(flag)

33、 cout<<"\n\n安全位置是： "<<flag<<"\n\n";</p><p>　　else cout<<"所有的位置都不安全"<<endl; //漏洞檢測</p><p><b>　　}</b></p><p&

34、gt;　　int delx(nodel sq[],int key,int n,int sum) //數(shù)組的偽刪除操作</p><p><b>　　{</b></p><p>　　// printf("第%d個位置開始數(shù)數(shù)的死亡的順序號\n",key);</p><p><b>　　do</b></

35、p><p><b>　　{</b></p><p><b>　　int k=4;</b></p><p><b>　　while(k)</b></p><p><b>　　{</b></p><p><b>　　key++;&

36、lt;/b></p><p>　　if(key>13) key-=13;</p><p>　　if(sq[key].data!=0)</p><p><b>　　k--;</b></p><p><b>　　}</b></p><p>　　if(key==1)&l

37、t;/p><p><b>　　{</b></p><p>　　if(sum==1) return 1;</p><p>　　else return 0;</p><p><b>　　}</b></p><p><b>　　else</b></p>

38、;<p><b>　　{</b></p><p>　　sum-=sq[key].data;</p><p>　　sq[key].data=0;</p><p>　　cout<<key<<" ";</p><p>　　key++;if(key>13) ke

39、y-=13;</p><p>　　// cout<<sq[key].data<<" "<<key<<endl;</p><p>　　while(sq[key].data==0)</p><p><b>　　{</b></p><p><b>　

40、　key++;</b></p><p>　　if(key>13) key-=13;</p><p><b>　　}</b></p><p>　　// cout<<sq[key].data<<" "<<key<<endl;</p><p>

41、;<b>　　}</b></p><p><b>　　}</b></p><p><b>　　while(1);</b></p><p><b>　　}</b></p><p>　　void array(int n)</p><p>

42、;<b>　　{</b></p><p>　　int i,flag=0;</p><p>　　for( i=1;i<=n;i++)// 循環(huán)找出安全的開始位置</p><p><b>　　{</b></p><p><b>　　int k=i;</b></p>

43、<p>　　cout<<"\n\n報數(shù)的位置為"<<k<<"時的排長之前的人員死亡順序:\n";</p><p>　　int j=1,sum=0;</p><p>　　while(j <= n) //構造循環(huán)隊列</p><p><b>　　{</b

44、></p><p>　　sqlist[j].data=j;</p><p><b>　　sum+=j++;</b></p><p><b>　　}</b></p><p>　　if( delx(sqlist,k,n,sum)==1)</p><p><b>　

45、　{</b></p><p>　　cout<<endl<<i<<"位置安全\n";</p><p>　　flag=i;//cout<<flag<<endl;</p><p><b>　　}</b></p><p><b>

46、;　　else</b></p><p><b>　　{</b></p><p>　　cout<<endl<<k<<"位置不安全\n";</p><p>　　//cout<<flag<<endl;</p><p><b>

47、　　}</b></p><p>　　cout<<" 所有人員情況： 0 表示已死 其它表示幸存者編號\n\n";</p><p>　　for(int xx=1;xx<=n;xx++)</p><p>　　cout<<sqlist[xx].data<<" ";</p&g

48、t;<p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　if(flag) cout<<"安全的位置是："<<flag<<"\n\n\n";</p><p>　　else cout<<&q

49、uot;\n\n無安全位置可選\n"<<endl;// 漏洞檢測</p><p><b>　　}</b></p><p>　　3 ： 主函數(shù)部分</p><p>　　int main()</p><p><b>　　{</b></p><p>　　co

50、ut<<"----------------敢死隊之死亡游戲模擬------------\n";</p><p>　　int n,cas;</p><p>　　cout<<"作為一名行政長官，報數(shù)開始位置很重要\n"<<endl;</p><p>　　cout<<"下面將

51、模擬每個開始位置的人員死亡順序-----------------\n";</p><p>　　//system("cls");</p><p><b>　　do{</b></p><p>　　cout<<"請選擇模擬的形式：\n 1：鏈表 2：數(shù)組 3: 退出程序\n";</p

52、><p><b>　　cin>>cas;</b></p><p>　　if(cas>3||cas<=0)</p><p><b>　　{</b></p><p>　　cout<<"輸入錯誤\n";continue;</p><p

53、><b>　　}</b></p><p>　　cout<<"\n請輸入隊員的數(shù)量~~~~"<<endl;</p><p><b>　　cin>>n;</b></p><p>　　switch(cas)</p><p><b>　

54、　{</b></p><p>　　case 1: lianbiao(n);break;</p><p>　　case 2: array(n); break;</p><p>　　default : cout<<"輸入錯誤\n";break;</p><p><b>　　}</b>

55、;</p><p>　　cout<<"還要繼續(xù)嗎？ 按3 退出程序,其他輸入繼續(xù)\n";</p><p>　　int ss;cin>>ss;</p><p>　　if(ss==3) break;</p><p><b>　　else</b></p><p&g

56、t;　　system("cls");</p><p>　　}while(cas!=3);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　第五章 運行與測試</b></p>

57、;<p>　　調試程序的過程中遇到什么問題</p><p>　　處理過程中經(jīng)常忽視特殊位置的處理 像開始位置為1時，循環(huán)隊列就會出現(xiàn)bugs</p><p>　　而數(shù)組形式中刪除操作不容易處理，用0 標記來代替 刪除操作，在循環(huán)數(shù)數(shù)的時候</p><p>　　經(jīng)常認為是5 ，但是 循環(huán)只需要進行4 次即可。而刪除操作的判斷則用sum 總和進行判斷，替換

58、循環(huán)判斷，省時！操作方便，在4 層循環(huán)數(shù)數(shù)操作中容易漏 data 為0 的判斷以及 對 key 的變相取余</p><p>　　3.測試數(shù)據(jù) 1 5 13 </p><p><b>　　總結與心得</b></p><p>　　通過這一課程設計，加深了我對《數(shù)據(jù)結構》這門課程所學內容的進一步的理解與掌握；同時，通過對循環(huán)隊列和數(shù)組的應用

59、，使得我將計算機課程所學知識與實際問題很好地相聯(lián)接在了一起。在這次課程設計中，培養(yǎng)了我開發(fā)一個中小型程序的能力。</p><p>　　調程序的時候，要穩(wěn)扎穩(wěn)打，每個子函數(shù)單調試后在和主函數(shù)鏈接，效率較高，不然都最后全在一塊，給調程序會帶來極大的不便?。?！對于每個子函數(shù)都要考慮到一些特殊值。</p><p>　　最大的收獲還是感覺到數(shù)據(jù)結構的實用性，不像看課本和考試那樣，總是參生厭煩情緒，離

60、開發(fā)一些東西越來越近了，而不像以前那樣很遙遠。。。</p><p>　　總之，在這個的課程設計中，我的收獲還是挺大的，不僅對于專業(yè)課有了更好的認識，而且還學到做事要細心、全面周到的重要性。</p><p><b>　　參考文獻:</b></p><p>　　[1] 嚴蔚敏、吳偉民主編 《數(shù)據(jù)結構》（C語言版） 清華大學出版社 2002

61、</p><p>　　[2] 殷人昆等著 《數(shù)據(jù)結構》（C++版） 清華大學出版社 2001</p><p>　　[3] 金遠平著 《數(shù)據(jù)結構》（C++描述） 清華大學出版社 2005 </p><p>　　[4] 許卓群等著 《數(shù)據(jù)結構與算法》 高等教育出版社 20