數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---敢死隊(duì)問題

1、<p>　　課 程 設(shè) 計(jì)</p><p><b>　?。〝?shù)據(jù)結(jié)構(gòu)）</b></p><p><b>　　二○一一年一月十日</b></p><p>　　課程設(shè)計(jì)任務(wù)書及成績(jī)?cè)u(píng)定</p><p>　　Ⅰ、題目的目的和要求： </p><p>　　鞏固和加深對(duì)數(shù)

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

3、gt;<p>　?、蟆⒅饕獏⒖嘉墨I(xiàn)及資料</p><p>　　[1] 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）清華大學(xué)出版社 1999</p><p>　　[2] 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）清華大學(xué)出版社 1999</p><p>　　[3] 徐寶文等譯 C語(yǔ)言程序設(shè)計(jì) 機(jī)械工業(yè)出版社 </p><p>　　[4] 與所用編程環(huán)境

4、相配套的C語(yǔ)言或C++相關(guān)的資料</p><p><b>　?、?、成績(jī)?cè)u(píng)定：</b></p><p>　　設(shè)計(jì)成績(jī)： （教師填寫）</p><p>　　指導(dǎo)老師： （簽字）</p><p>　　二○一一 年 一 月 十 日</p>

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

6、詳細(xì)設(shè)計(jì)………………………………………………………4</p><p>　　第五章 運(yùn)行與測(cè)試……………………………………………………9</p><p>　　第六章 總結(jié)與心得……………………………………………………13</p><p>　　參考文獻(xiàn)………………………………………………………………14</p><p><b>　　第一

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

8、示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。</p><p>　　在這次的課程設(shè)計(jì)中我選擇的題目是敢死隊(duì)問題。加強(qiáng)版的約瑟夫環(huán)問題（  用戶輸入M,N值，從1至N開始順序循環(huán)數(shù)數(shù)，每數(shù)到M輸出該數(shù)值，直至全部輸出，最后一個(gè)為獲勝者 ），增加了保證1 號(hào)安全這一條件限制。并且模擬各

9、個(gè)開始位置，隊(duì)員死亡的順序，以及最后的獲勝者。</p><p>　　課程設(shè)計(jì)的目的意義：加深對(duì)循環(huán)隊(duì)列和數(shù)組的理解，以及對(duì)循環(huán)隊(duì)列和數(shù)組的實(shí)際應(yīng)用，加強(qiáng)自己的動(dòng)手操作能力，增加對(duì)課程的興趣，而不是枯燥的看課本。</p><p>　　課程設(shè)計(jì)的問題：敢死隊(duì)問題</p><p>　　有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡，誰(shuí)都不想去，排長(zhǎng)決定用輪回?cái)?shù)數(shù)的辦法來決定哪個(gè)戰(zhàn)士去執(zhí)

10、行任務(wù)。如果前一個(gè)戰(zhàn)士沒完成任務(wù)，則要再派一個(gè)戰(zhàn)士上去?，F(xiàn)給每個(gè)戰(zhàn)士編一個(gè)號(hào)，大家圍坐成一圈，隨便從某一個(gè)戰(zhàn)士開始計(jì)數(shù)，當(dāng)數(shù)到5時(shí)，對(duì)應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計(jì)數(shù)。如果此戰(zhàn)士沒完成任務(wù)，再?gòu)南乱粋€(gè)戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時(shí)，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。排長(zhǎng)是不愿意去的，假設(shè)排長(zhǎng)為1號(hào)，請(qǐng)你設(shè)計(jì)一程序，求出從第幾號(hào)戰(zhàn)士開始計(jì)數(shù)才能讓排長(zhǎng)最后一個(gè)留下來而不去執(zhí)行任務(wù)。</p><

11、p><b>　　第二章 系統(tǒng)分析</b></p><p>　　敢死隊(duì)問題包括：兩個(gè)數(shù)據(jù)的輸入，一個(gè)是隊(duì)員的數(shù)量，另一個(gè)是模擬的數(shù)據(jù)結(jié)構(gòu)形式。由于問題給出的計(jì)數(shù)值為5 ，所以k 值就默認(rèn)為5 ，不再設(shè)置數(shù)據(jù)輸入。故重點(diǎn)是要完成兩種數(shù)據(jù)結(jié)構(gòu)形式的刪除，循環(huán)標(biāo)記等基本操作。</p><p>　　演示程序是以用戶于計(jì)算機(jī)的對(duì)話方式執(zhí)行，這需要調(diào)用一個(gè)清屏函數(shù)來完成使用者

12、與計(jì)算機(jī)語(yǔ)言之間界面的處理。使界面不至于拖沓冗長(zhǎng)。</p><p><b>　　程序執(zhí)行時(shí)的命令：</b></p><p>　　本程序?yàn)榱耸褂脮r(shí)的方便，采用阿拉伯?dāng)?shù)字的方式來完成程序的等各種選擇輸入，幾乎不用輸入什么特殊的命令。（要注意輸入時(shí)必須用數(shù)字，否者可能會(huì)引起一些死循環(huán)）</p><p><b>　　測(cè)試數(shù)據(jù)。</b&g

13、t;</p><p>　　1 5 13 </p><p>　　數(shù)據(jù)運(yùn)行結(jié)果 在第五章有詳細(xì)的截圖</p><p><b>　　第三章 概要設(shè)計(jì)</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)類型： 一種是循環(huán)隊(duì)列，另一種是數(shù)組形式</p><p>　　其中循環(huán)隊(duì)列操作只需要?jiǎng)h除操作，用數(shù)組形式

14、處理和運(yùn)算上則較復(fù)雜些 因此，循環(huán)隊(duì)列占優(yōu)勢(shì)程序總體上分為兩大塊，一塊是循環(huán)隊(duì)列的模擬，一塊是數(shù)組形式的模擬這兩種形式功能都是模擬每個(gè)開始數(shù)數(shù)的位置對(duì)員的死亡順序，其中循環(huán)隊(duì)列的函數(shù)接口為：lianbiao(n) ，數(shù)組的函數(shù)接口為：array(n);</p><p>　　兩模塊算法基本一致，數(shù)據(jù)結(jié)構(gòu)形式不同而已</p><p><b>　　算法概述：</b><

15、/p><p>　　For(int i=1;i<=n;i++)</p><p><b>　　{</b></p><p><b>　　初始化數(shù)據(jù)</b></p><p>　　對(duì)每個(gè)位置進(jìn)行模擬/調(diào)用del /delx 函數(shù)進(jìn)行模擬</p><p><b>　　判斷是否

16、安全</b></p><p>　　安全-> 標(biāo)記變量—>i；</p><p>　　否則 --> 輸出 不安全的信息</p><p><b>　　} </b></p><p>　　Printf->安全的位置；</p><p>　　鏈表的刪除操作算法描述</p

17、><p>　　int del(node *p,node *q) //鏈表的刪除操作</p><p><b>　　{</b></p><p>　　while(q->next!=q)</p><p><b>　　{</b></p><p>　　p,q 分別向后移動(dòng)4個(gè)&l

18、t;/p><p>　　判斷 q 數(shù)據(jù)是否為1 </p><p><b>　　若是 則返回 0；</b></p><p>　　否則 刪除 q ； </p><p><b>　　}</b></p><p>　　判斷是否只有第一個(gè)位置有人</p><p><

19、;b>　　若是 返回 1；</b></p><p><b>　　} </b></p><p>　　循環(huán)鏈表的刪除函數(shù)：</p><p>　　int del(node *p,node *q)；</p><p><b>　　循環(huán)鏈表的函數(shù)：</b></p><p&

20、gt;　　void lianbiao(int n)；</p><p>　　數(shù)組的位操作刪除函數(shù)</p><p>　　int delx(nodel sq[],int key,int n,int sum)；</p><p><b>　　數(shù)組形式 的函數(shù)</b></p><p>　　void array(int n)；<

21、/p><p><b>　　第四章 詳細(xì)設(shè)計(jì)</b></p><p><b>　　1：存儲(chǔ)結(jié)構(gòu)形式</b></p><p>　　struct node</p><p><b>　　{</b></p><p><b>　　int data;</b

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

23、;<p>　　}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)

24、</p><p><b>　　{</b></p><p><b>　　int k=4;</b></p><p>　　while(k--)</p><p><b>　　{</b></p><p>　　p=p->next;</p><

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

26、lt;b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cout<<q->data<<" ";</p><p>　　q=q->next; p-&g

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

28、lt;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void lianbiao(int n) //循環(huán)鏈表的形式</p><p><b>　　{</b></p><p>　　int i

29、,flag=0;</p><p>　　for( i=1;i<=n;i++)// 循環(huán)找出安全的開始位置</p><p><b>　　{</b></p><p><b>　　int k=i;</b></p><p>　　cout<<"\n\n報(bào)數(shù)的位置為"<

30、<k<<"時(shí)的排長(zhǎng)之前的人員死亡順序:\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

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

32、t;/p><p>　　t->next=p;</p><p>　　t=t->next;</p><p><b>　　}</b></p><p>　　node *p=t,*q=head;// 設(shè)置p q 指針</p><p>　　while(--k) //循環(huán)找開始的位置</p&

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

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

35、t;　　else</b></p><p><b>　　{</b></p><p>　　cout<<endl<<i<<"位置不安全\n";</p><p>　　continue ;</p><p><b>　　}</b></p&

36、gt;<p><b>　　}</b></p><p>　　if(flag) cout<<"\n\n安全位置是： "<<flag<<"\n\n";</p><p>　　else cout<<"所有的位置都不安全"<<endl;

37、//漏洞檢測(cè)</p><p><b>　　}</b></p><p>　　int delx(nodel sq[],int key,int n,int sum) //數(shù)組的偽刪除操作</p><p><b>　　{</b></p><p><b>　　do</b></p&g

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

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

40、gt;<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>

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

42、n;</p><p>　　while(sq[key].data==0)</p><p><b>　　{</b></p><p><b>　　key++;</b></p><p>　　if(key>n) key-=n;</p><p><b>　　}</b

43、></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　while(1);</b></p><p><b>　　}</b></p><p>　　void array(in

44、t n) //數(shù)組的形式</p><p><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&

45、gt;　　int k=i;</b></p><p>　　cout<<"\n\n報(bào)數(shù)的位置為"<<k<<"時(shí)的排長(zhǎng)之前的人員死亡順序:\n";</p><p>　　int j=1,sum=0;</p><p>　　while(j <= n) //構(gòu)造循環(huán)隊(duì)列</p

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

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

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

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

50、ata<<" ";</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　if(flag) cout<<"安全的位置是："<<flag<<"\n\n\n";</p>

51、<p>　　else cout<<"\n\n無安全位置可選\n"<<endl;// 漏洞檢測(cè)</p><p><b>　　}</b></p><p>　　3 ： 主函數(shù)部分</p><p>　　int main()</p><p><b>　　{&l

52、t;/b></p><p>　　cout<<"----------------敢死隊(duì)之死亡游戲模擬------------\n";</p><p>　　int n,cas;</p><p>　　system("color 3f");</p><p>　　cout<<&quo

53、t;作為一名行政長(zhǎng)官，報(bào)數(shù)開始位置很重要\n"<<endl;</p><p>　　cout<<"下面將模擬每個(gè)開始位置的人員死亡順序-----------------\n";</p><p>　　//system("cls");</p><p><b>　　do{</b>

54、</p><p>　　cout<<"請(qǐng)選擇模擬的形式：\n 1：鏈表 2：數(shù)組 3: 退出程序\n";</p><p><b>　　cin>>cas;</b></p><p>　　if(cas>3||cas<=0)</p><p><b>　　{</

55、b></p><p>　　cout<<"輸入錯(cuò)誤\n"; continue;</p><p><b>　　}</b></p><p>　　cout<<"\n請(qǐng)輸入隊(duì)員的數(shù)量~~~~"<<endl;</p><p><b>　　ci

56、n>>n;</b></p><p>　　switch(cas)</p><p><b>　　{</b></p><p>　　case 1: lianbiao(n); break;</p><p>　　case 2: array(n); break;</p><p>　

57、　default : cout<<"輸入錯(cuò)誤\n";break;</p><p><b>　　}</b></p><p>　　cout<<"還要繼續(xù)嗎？ 按3 退出程序,其他輸入繼續(xù)\n";</p><p>　　int ss;cin>>ss;</p>&l

58、t;p>　　if(ss==3) break;</p><p><b>　　else</b></p><p>　　system("cls");</p><p>　　}while(cas!=3);</p><p><b>　　return 0;</b></p>&

59、lt;p><b>　　}</b></p><p><b>　　第五章 運(yùn)行與測(cè)試</b></p><p>　　調(diào)試程序的過程中遇到什么問題</p><p>　　處理過程中經(jīng)常忽視特殊位置的處理 像開始位置為1時(shí)，循環(huán)隊(duì)列就會(huì)出現(xiàn)bugs</p><p>　　而數(shù)組形式中刪除操作不容易處理，用0

60、 標(biāo)記來代替 刪除操作，在循環(huán)數(shù)數(shù)的時(shí)候</p><p>　　經(jīng)常認(rèn)為是5 ，但是 循環(huán)只需要進(jìn)行4 次即可。而刪除操作的判斷則用sum 總和進(jìn)行判斷，替換循環(huán)判斷，省時(shí)！操作方便，在4 層循環(huán)數(shù)數(shù)操作中容易漏 data 為0 的判斷以及 對(duì) key 的變相取余</p><p>　　3.測(cè)試數(shù)據(jù) 1 5 13 </p><p><b>　　總結(jié)與

61、心得</b></p><p>　　通過這一課程設(shè)計(jì)，加深了我對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門課程所學(xué)內(nèi)容的進(jìn)一步的理解與掌握；同時(shí)，通過對(duì)循環(huán)隊(duì)列和數(shù)組的應(yīng)用，使得我將計(jì)算機(jī)課程所學(xué)知識(shí)與實(shí)際問題很好地相聯(lián)接在了一起。在這次課程設(shè)計(jì)中，培養(yǎng)了我開發(fā)一個(gè)小型程序的思想。</p><p>　　調(diào)程序的時(shí)候，要穩(wěn)扎穩(wěn)打，每個(gè)子函數(shù)單調(diào)試后在和主函數(shù)鏈接，效率較高，不然都最后全在一塊，給調(diào)程序會(huì)帶來

62、極大的不便?。?！對(duì)于每個(gè)子函數(shù)都要考慮到一些特殊值。</p><p>　　最大的收獲還是感覺到數(shù)據(jù)結(jié)構(gòu)的實(shí)用性，不像看課本和考試那樣，總是參生厭煩情緒，離開發(fā)一些東西越來越近了，而不像以前那樣很遙遠(yuǎn)。。。但是，數(shù)據(jù)結(jié)構(gòu)和c語(yǔ)音的很好的結(jié)合起來應(yīng)用，對(duì)于c 語(yǔ)言還是有很多欠缺</p><p>　　總之，在這個(gè)的課程設(shè)計(jì)中，我的收獲還是挺大的，不僅對(duì)于專業(yè)課有了更好的認(rèn)識(shí)，而且還學(xué)到做事要細(xì)心

63、、全面周到的重要性。</p><p><b>　　參考文獻(xiàn):</b></p><p>　　[1] 嚴(yán)蔚敏、吳偉民主編 《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版） 清華大學(xué)出版社 2002</p><p>　　[2] 殷人昆等著 《數(shù)據(jù)結(jié)構(gòu)》（C++版） 清華大學(xué)出版社 2001</p><p>　

64、　[3] 金遠(yuǎn)平著 《數(shù)據(jù)結(jié)構(gòu)》（C++描述） 清華大學(xué)出版社 2005 </p><p>　　[4] 許卓群等著 《數(shù)據(jù)結(jié)構(gòu)與算法》 高等教育出版社 2004</p><p>　　[5] Frank M.Carrano 等著 《數(shù)據(jù)結(jié)構(gòu)與Ｃ++高級(jí)教程》清華大學(xué)出版社 2004</p><p>