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

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

3、gt;<p>　　Ⅲ、主要參考文獻(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ì) 清華大學(xué)出版社</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、lt;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ì)中我選擇的題目是圖書管理。傳統(tǒng)的人工圖書管理，基本業(yè)務(wù)活動(dòng)有對(duì)一本書的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等，但是人工統(tǒng)計(jì)操作起來(lái)效率相對(duì)來(lái)說(shuō)要低，也容易出錯(cuò)。但是現(xiàn)在這些業(yè)務(wù)借助計(jì)算機(jī)系統(tǒng)完成后，效率可以得到提高，也可以減

9、少出錯(cuò)的幾率?？梢允箞D書管理的日常業(yè)務(wù)更加的方便，迅捷，減少很多勞動(dòng)量。</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ì)的問(wèn)題：敢死隊(duì)問(wèn)題</p><p>　　有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡，誰(shuí)都不想去，排長(zhǎng)決定用輪回?cái)?shù)

10、數(shù)的辦法來(lái)決定哪個(gè)戰(zhàn)士去執(zhí)行任務(wù)。如果前一個(gè)戰(zhàn)士沒(méi)完成任務(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)士沒(méi)完成任務(wù)，再?gòu)南乱粋€(gè)戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時(shí)，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。</p><p>　　排長(zhǎng)是不愿意去的，假設(shè)排長(zhǎng)為1號(hào)，請(qǐng)你設(shè)計(jì)一程序，求出從第幾號(hào)戰(zhàn)士開始計(jì)數(shù)

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

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

13、;b>　　測(cè)試數(shù)據(jù)。</b></p><p><b>　　1 5 13 </b></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>

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

15、接口為：array(n);</p><p>　　兩模塊算法基本一致，數(shù)據(jù)結(jié)構(gòu)形式不同而已</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>　　對(duì)每個(gè)位置進(jìn)行模擬/調(diào)用del /delx 函數(shù)進(jìn)行模擬</p><p><b>　　判斷是否安全</b></p><p><b>　　}</b></p><p>　　Printf->安全的位置；</p><p&

17、gt;<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></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報(bào)數(shù)的位置為"<<k<<"時(shí)的排長(zhǎng)之前

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) //構(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;</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;// 設(shè)置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; //漏洞檢測(cè)</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個(gè)位置開始數(shù)數(shù)的死亡的順序號(hào)\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報(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><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 表示已死 其它表示幸存者編號(hào)\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無(wú)安全位置可選\n"<<endl;// 漏洞檢測(cè)</p><p><b>　　}</b></p><p>　　3 ： 主函數(shù)部分</p><p>　　int main()</p><p><b>　　{</b></p><p>　　co

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

51、模擬每個(gè)開始位置的人員死亡順序-----------------\n";</p><p>　　//system("cls");</p><p><b>　　do{</b></p><p>　　cout<<"請(qǐng)選擇模擬的形式：\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<<"輸入錯(cuò)誤\n";continue;</p><p

53、><b>　　}</b></p><p>　　cout<<"\n請(qǐng)輸入隊(duì)員的數(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<<"輸入錯(cuò)誤\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>　　第五章 運(yùn)行與測(cè)試</b></p>

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

58、循環(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é)與心得</b></p><p>　　通過(guò)這一課程設(shè)計(jì)，加深了我對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門課程所學(xué)內(nèi)容的進(jìn)一步的理解與掌握；同時(shí)，通過(guò)對(duì)循環(huán)隊(duì)列和數(shù)組的應(yīng)用

59、，使得我將計(jì)算機(jī)課程所學(xué)知識(shí)與實(shí)際問(wèn)題很好地相聯(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ì)帶來(lái)極大的不便?。?！對(duì)于每個(gè)子函數(shù)都要考慮到一些特殊值。</p><p>　　最大的收獲還是感覺(jué)到數(shù)據(jù)結(jié)構(gòu)的實(shí)用性，不像看課本和考試那樣，總是參生厭煩情緒，離

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

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