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

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

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

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

3、構(gòu) 線性鏈表 存儲結(jié)構(gòu) 空間復(fù)雜度（3~5個） 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è)計

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

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

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

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

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

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

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

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

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

15、t; //報k號的猴子出列，即刪除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("請輸入猴子總數(shù) monkey number= "); scanf("%d",&n); printf("請輸入將出列猴子的報數(shù)號：");

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

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

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

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

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

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