猴子選大王 課程設(shè)計(jì)文檔

《猴子選大王 課程設(shè)計(jì)文檔》由會(huì)員分享，可在線閱讀，更多相關(guān)《猴子選大王 課程設(shè)計(jì)文檔（15頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、湖南人文科技學(xué)院·課程設(shè)計(jì) XXXX大學(xué)計(jì)算機(jī)系 課程設(shè)計(jì)說(shuō)明書 課程名稱 : 數(shù)據(jù)結(jié)構(gòu) 課程代碼 : 題 目 : 猴子選大王 年級(jí)/專業(yè)/班 : 學(xué)生姓名 : 學(xué) 號(hào) : 指導(dǎo)老師 : 開題時(shí)間 : 完成時(shí)間 : 2009 年 月 日 目 錄 摘 要 2 一、引 言(小三號(hào)、黑體、加粗) 3 二、設(shè)計(jì)目的與任務(wù) 3 1、課程設(shè)計(jì)的目的 3 2、課程設(shè)計(jì)的任務(wù) 4 三、設(shè)計(jì)方案與實(shí)施(小三號(hào)、黑體、加粗) 4 1、總體設(shè)計(jì) 4 2、詳細(xì)設(shè)計(jì) 6

2、3、程序清單 7 4、程序調(diào)試與體會(huì) 9 5、運(yùn)行結(jié)果（截圖） 10 四、結(jié) 論 11 五、致 謝 12 六、參考文獻(xiàn) 12 1、設(shè)計(jì)的目的與要求： 13 2、設(shè)計(jì)進(jìn)度及完成情況 13  摘 要 線性鏈表是一種重要而且使用廣泛的數(shù)據(jù)結(jié)構(gòu)，用鏈表所表示數(shù)據(jù)元素之間的邏輯關(guān)系是由節(jié)點(diǎn)中的指針指示的，而循環(huán)鏈表的特點(diǎn)是表種最后一個(gè)節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，用循環(huán)鏈表作為本課題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，充分考慮了循環(huán)鏈表的特點(diǎn)僅通過(guò)對(duì)兩個(gè)循環(huán)鏈表的出、入列操作，大大降低空間復(fù)雜度就簡(jiǎn)單的實(shí)現(xiàn)了要求，動(dòng)態(tài)地模擬出了猴子選大王問(wèn)題中猴子循環(huán)報(bào)數(shù)的情況。 關(guān)鍵詞：數(shù)據(jù)結(jié)

3、構(gòu) 線性鏈表 存儲(chǔ)結(jié)構(gòu) 空間復(fù)雜度（3~5個(gè)） Abstract Linear list is an important and extensive use of the data structure,List said that the data used by the logic of relations between the elements by the node in the direction of the pointer,The circulation list of the characteristics of the species list is

4、the last node of the indicators point to the first node, the entire list to form a ring,With the cycle of the list as the subject of data storage structures, taking into account the full cycle through the list of the characteristics of only two out of circulation list, out into operation, greatly r

5、educe the complexity of space on the realization of a simple request,To simulate the dynamics of the monkey king election issue in a number of monkeys circulation Situation Key words: Data Structure, Linear List, Storage structure, Space complexity 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)

6、 --猴子選大王問(wèn)題設(shè)計(jì) 一、引 言 數(shù)據(jù)結(jié)構(gòu)是一門專業(yè)技術(shù)基礎(chǔ)課，它對(duì)學(xué)習(xí)者的的要求很明確：學(xué)會(huì)分析、研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用設(shè)計(jì)所需的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。其次，該課程的學(xué)習(xí)過(guò)程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，要求學(xué)習(xí)者編寫的程序結(jié)構(gòu)或設(shè)計(jì)的程序結(jié)構(gòu)體清楚、正確、易讀，符合軟件工程的規(guī)范。 循環(huán)鏈表是一種重要的鏈?zhǔn)浇Y(jié)構(gòu)，其特殊性在于需附設(shè)兩個(gè)指針?lè)謩e指示表頭元素及表尾元素的位置且表頭和表尾相鄰接，臆造的環(huán)狀空間巧妙的解決了需循環(huán)依次刪除元素的約瑟夫問(wèn)題。 本設(shè)計(jì)采用目前最通用的程序設(shè)計(jì)語(yǔ)言

7、之一——C語(yǔ)言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語(yǔ)言，循環(huán)鏈表作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。 充分考慮了循環(huán)鏈表的特點(diǎn)僅通過(guò)對(duì)兩個(gè)循環(huán)鏈表的出、入列操作，就簡(jiǎn)單的實(shí)現(xiàn)了要求，動(dòng)態(tài)的模擬出了猴子選大王問(wèn)題中猴子循環(huán)報(bào)數(shù)的情況。該程序通俗易懂且實(shí)用性強(qiáng)，其他類似的算法均可借鑒和參考使用。并且該程序清單詳細(xì)具體、全面、具有很強(qiáng)的可讀性。 二、設(shè)計(jì)目的與任務(wù) 1、課程設(shè)計(jì)的目的 1) 初步掌握軟件開發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能； 訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)，熟練的完成問(wèn)題分析、算 2) 法設(shè)計(jì)、編寫程序，求解出指定的問(wèn)題； 3) 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟

8、件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過(guò)程中培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)； 4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力。 2、課程設(shè)計(jì)的任務(wù) 問(wèn)題描述：一堆猴子都有編號(hào)，編號(hào)是1，2，3 ...m ,這群猴子（m個(gè)）按照1到m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第n個(gè)，該猴子就要離開此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。 課題要求：輸入數(shù)據(jù)m,n 其中m,n 為整數(shù)，n輸出形式為提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) 三、設(shè)計(jì)方案與實(shí)施 1、總體設(shè)計(jì) //寫總體的設(shè)

9、計(jì)思想 采用兩個(gè)循環(huán)隊(duì)列反復(fù)出隊(duì)列與入隊(duì)列來(lái)進(jìn)行“舞伴配對(duì)”。程序中主要用到以下抽象數(shù)據(jù)類型： 1) 設(shè)定鏈表抽象數(shù)據(jù)類型的定義 ADT struct {對(duì)象數(shù)據(jù)＝（整數(shù)） 操作對(duì)象:struct monkey *create() 建立鏈表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一個(gè) Struct monkey *letout(last) 刪掉被淘汰的猴子，返回的指針值指向下一個(gè)猴子}。 基本操作 (1) initring(int n,linklist r) 操作結(jié)果：構(gòu)造一個(gè)具有n個(gè)元素的循環(huán)鏈表r。

10、 (2) iinklist delete(int n,int k,linklist r) 初始條件：鏈表r已存在。 操作結(jié)果：循環(huán)依次刪除問(wèn)題對(duì)應(yīng)所需位置的元素并當(dāng)即輸出其值，用指針r記錄其最后元素的位置。 }ATD linklist (3) outring(int n,linklist r) 特殊輸出鏈表保留的最后一個(gè)元素，即猴子大王的序號(hào)。 程序包含兩個(gè)模塊 (1) 主程序模塊，其中主函數(shù)為 int main{ 輸入信息； 根據(jù)輸入要求進(jìn)行刪除和輸出； 輸出結(jié)果； } (2) 循環(huán)鏈表模塊——實(shí)現(xiàn)具體刪除輸出操作。 2) 兩模塊之間的簡(jiǎn)單調(diào)用

11、關(guān)系 主函數(shù)模塊 循環(huán)隊(duì)列模塊 循環(huán)鏈表模塊 圖1 模塊調(diào)用圖 2、詳細(xì)設(shè)計(jì) //對(duì)幾個(gè)主要功能函數(shù)作出相應(yīng)的說(shuō)明 1) 各個(gè)函數(shù)之間的調(diào)用關(guān)系 主函數(shù) 最后元素輸出操作 鏈表循環(huán)刪除輸出操作 數(shù)據(jù)輸入 輸出 序號(hào) 圖2 函數(shù)調(diào)用關(guān)系圖 2) 函數(shù)設(shè)計(jì) 程序設(shè)計(jì)中主要包括下列函數(shù) LinkList initring(int n,linklist r) { 構(gòu)造一個(gè)含n個(gè)元素的循環(huán)鏈表; } LinkList delete(int n,int k,linklist r) { 循環(huán)刪除報(bào)k號(hào)的元素； 循環(huán)輸

12、出所刪除的元素； 記錄鏈表最后所保留的元素的位置； } void outring(int n,linklist r) { 輸出鏈表最后保留的元素，即猴子大王的序號(hào)； } 3、程序清單 //整個(gè)程序的運(yùn)行清單 #include "stdio.h" #include "stdlib.h" typedef struct node{ int data; struct node *next; }listnode,*linklist; linklist initring(int n,linklist r) //創(chuàng)建一個(gè)循環(huán)單鏈表

13、 { linklist p,q; int i; r=q=(listnode *)malloc(sizeof(listnode)); //兩個(gè)指針指向首位置 for(i=1;idata=i; q->next=p; q=p; } p->data=n; p->next=r; //頭尾相連 r=p; //指向頭

14、節(jié)點(diǎn)位置 return r; } linklist deleted(int n,int k,linklist r) { int i,j; linklist p,q; p=r; //p移至頭節(jié)點(diǎn)位置 for(i=1;i<=n-1;i++) //循環(huán)n-1次，即只需刪除n-1個(gè)節(jié)點(diǎn),最后剩下猴子大王 { for(j=1;j<=k-1;j++) p=p->next; //p循環(huán)移至下一個(gè)位置 q=p->next; p->next=q->nex

15、t; //報(bào)k號(hào)的猴子出列，即刪除p->next printf("%4d",q->data); if(i % 6==0) printf("\n"); free(q); } printf("\n"); r=p;return r; //記錄猴子大王位置并傳遞 } void outring(int n,linklist r) { int i; linklist p; p=r; //獲得猴子大王位置 printf("猴子大王："); print

16、f("%4d\n",p->data); } void main() //主函數(shù) { linklist r; int n,k; linklist initring(int n,linklist r); linklist deleted(int n,int k,linklist r); void outring(int n,linklist r); printf("請(qǐng)輸入猴子總數(shù) monkey number= "); scanf("%d",&n); printf("請(qǐng)輸入將出列猴子的報(bào)數(shù)號(hào)：");

17、scanf("%d",&k); printf("下列序號(hào)的猴子因報(bào)%d號(hào)而依次出列：\n",k); r=initring(n,r); r=deleted(n,k,r); outring(n,r); } 4、程序調(diào)試與體會(huì) 通過(guò)這次課程設(shè)計(jì)，我們受益頗多： 首先，上課時(shí)請(qǐng)的理論知識(shí)，似乎很容易接受，以及各種算法都能夠比較輕松的理解，但是在真正的運(yùn)用過(guò)程中，并不能把理論知道很好的和實(shí)踐結(jié)合起來(lái)。在平時(shí)做實(shí)驗(yàn)時(shí)，尤其是這次課程設(shè)計(jì)，總感到有些無(wú)從下手。因此，在學(xué)知識(shí)的過(guò)程中，一定要多動(dòng)手、動(dòng)腦，將所學(xué)的知識(shí)熟練掌握，自如運(yùn)用。 其次，通過(guò)這次課程設(shè)計(jì)，對(duì)

18、我的邏輯思維能力是一個(gè)很大的鍛煉，再有，它還加強(qiáng)了我們的系統(tǒng)思考問(wèn)題的能力，在編程方面，我們開始從整體的角度來(lái)考慮問(wèn)題了，而不再像以前一樣的，胡亂動(dòng)手。也就是因?yàn)橄惹暗倪@種編程習(xí)慣，使得我們?cè)谡n程設(shè)計(jì)過(guò)程中浪費(fèi)了不少的時(shí)間，嘗到了教訓(xùn)。 另外，此次課程設(shè)計(jì)也對(duì)我的獨(dú)自解決問(wèn)題的能力有了極大的提高，以前做的都是小程序，就都是一個(gè)人做，做了后，甚至還洋洋得意，可這一次，一開始是對(duì)我們的一個(gè)打擊，沒(méi)有一個(gè)人能單獨(dú)完成，最后還是大家一齊出力，共同商討，才得出了最后的結(jié)果，并且在這個(gè)過(guò)程中，我們相互之間還掌握了其他人掌握了但自己還沒(méi)有掌握的知識(shí)，是一次知識(shí)的大匯總，并且在這個(gè)討論的過(guò)程中，還更正了不少

19、我們各自自身對(duì)于某個(gè)知識(shí)點(diǎn)的誤區(qū)。這次程序設(shè)計(jì)也是一個(gè)毅力的考驗(yàn)過(guò)程。有時(shí)候往往只是一個(gè)小小的錯(cuò)誤，卻要費(fèi)很多 的時(shí)間來(lái)解決。在這個(gè)過(guò)程不能過(guò)于急躁，并且要很有耐心才行程序需要反復(fù)調(diào)試，其過(guò)程很可能相當(dāng)令人頭疼，有時(shí)花很長(zhǎng)時(shí)間設(shè)計(jì)出來(lái)還是需要重做，那時(shí)心中未免有點(diǎn)灰心，有時(shí)還特別想放棄，此時(shí)更加需要靜下心，查找原因。 通過(guò)這次課程設(shè)計(jì)，我學(xué)習(xí)了很多平時(shí)很少關(guān)注的知識(shí)點(diǎn)，比如循環(huán)鏈；也明白了很多道理，比如做不要事萎縮害怕，要盡力去思考，努力去解決，不要太依賴別人，要有團(tuán)結(jié)精神，齊心協(xié)力一起解決。 5、運(yùn)行結(jié)果（截圖） 程序運(yùn)行如下： 圖（1）、輸入總元素個(gè)數(shù)

20、 圖（2）、輸入循環(huán)中所需刪除元素的位置 圖（3）、程序運(yùn)行的輸出結(jié)果 四、結(jié) 論 運(yùn)用循環(huán)鏈表的基本操作順利的解決約瑟夫—猴子選大王問(wèn)題，主要利用循環(huán)鏈表的環(huán)狀結(jié)構(gòu)，循環(huán)地執(zhí)行刪除操作并輸出其值，記錄最后保留元素的位置，而整個(gè)過(guò)程不需要不需要移動(dòng)元素使程序在空間復(fù)雜度上降小很多，采用指針的移動(dòng)大大加快了程序的執(zhí)行效率。系統(tǒng)整體上比較完美，可以從鍵盤獲取輸入元素，整體輸出畫面效果整潔、大方。 五、致 謝 首先，我要感謝學(xué)校給我們提供了此次課程設(shè)計(jì)的機(jī)會(huì)，能讓同學(xué)們?cè)谝黄饘W(xué)習(xí)與研究，讓我們有機(jī)會(huì)對(duì)所學(xué)的理論知識(shí)進(jìn)行實(shí)踐。 其次，在論文

21、的寫作過(guò)程中，也得到了許多同學(xué)的寶貴建議，同時(shí)還得到許多學(xué)長(zhǎng)的支持和幫助，在此一并致以誠(chéng)摯的謝意。 最后，我們還要特別感謝我們的輔導(dǎo)老師，在她的精心輔導(dǎo)和幫助下，我們的設(shè)計(jì)才得以順利完成。對(duì)她為我們的設(shè)計(jì)所提出的寶貴意見(jiàn)表示忠心的感謝！ 六、參考文獻(xiàn) [ 1 ]譚浩強(qiáng). C程序設(shè)計(jì)[M ]. 北京:清華大學(xué)出版社,2005 [ 2]羅宇等. 數(shù)據(jù)結(jié)構(gòu)[M ]. 北京:北京郵電大學(xué)出版社, 2003 [ 3]嚴(yán)藯敏. 數(shù)據(jù)結(jié)構(gòu)[M ]. 北京:清華大學(xué)出版社, 2001 [ 4 ]胡學(xué)鋼. 數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo)[M ]. 北京:清華大學(xué)出版社,1999 課程設(shè)計(jì)任務(wù)書及成績(jī)?cè)u(píng)定

22、 課題名稱： 猴子選大王 完成者： 1、設(shè)計(jì)的目的與要求： 1) 靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問(wèn)題分析。 2) 初步掌握軟件開發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等方法。 3) 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)。 4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力。 2、設(shè)計(jì)進(jìn)度及完成情況 日 期 內(nèi) 容 2008．12．22-2008．12．23 分析問(wèn)題，找出所要解決問(wèn)題的關(guān)鍵 2008．12．24-2008．12．25 總體設(shè)計(jì)，找出解決方案 2008．12．26-2008．12．28 詳細(xì)設(shè)計(jì)，列出解決步驟 2008．12．29-2009．1．1 程序編碼 2009．1．2-2009．1．3 程序調(diào)試，修改加以完善 2009．1．4-2009．1．5 書寫文檔 3、成績(jī)?cè)u(píng)定： 設(shè)計(jì)成績(jī)： （教師填寫） 指導(dǎo)老師： （簽字） 二00 年 月 日