實用文檔20數(shù)據(jù)結構課程設計報告題目：猴子選大王——采用循環(huán)鏈表及動態(tài)存儲的實現(xiàn)班級：計算機082班姓名：指導教師：成績：信息工程學院2010年01月20日目錄課程設計摘要(題目)………………031.引言………………032.需求分析…………042.1問題分析…………………042.2總體設計…………………053.概要設計…………073.1模塊分析……………………073.1.1鏈表循環(huán)輸入刪除輸出…………………073.1.2各個函數(shù)之間的調用關系……………093.2函數(shù)的流程分析……………104.詳細設計…………124.1函數(shù)設計……………………124.2程序源代碼…………………135.測試結果…………166.設計體會…………187.結束語…………19參考文獻…………20摘要(題目):猴子選大王任務：一堆猴子都有編號，編號是1，2，3...m,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：輸入數(shù)據(jù)：輸入m,n；m,n為整數(shù)（n<m）輸出形式：中文提示按照m個猴子，數(shù)n個數(shù)的方法，輸出為大王的猴子是幾號，建立一個函數(shù)來實現(xiàn)此功能1.引言隨著計算機科學的迅速發(fā)展，計算機已深入到揉合社會的各個領域，它的應用已不再局限于科學計算，以解決一些數(shù)學問題，而且可以解決一些抽象化的具體問題，更多地用于控制，管理及數(shù)據(jù)處理等非數(shù)值計算的處理工作，這便為我們的日常生活提供了很多的方便，譬如說火車、飛機售票系統(tǒng)，學生成績管理，商品管理系統(tǒng)，醫(yī)院選址等實際問題。如今程序設計的語言很多，有發(fā)展比較完善高級語言，也有最基本的低級語言，然而再好的程序設計也要有一個比較清晰的思路——算法。為了編寫好一個好程序，必須分析待處理對象的特性以及各處理對象之間的關系，于是數(shù)據(jù)結構便成為我們絕佳的選擇。數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎，它不僅是計算機科學的核心課程，而且已成為其他理工專業(yè)的熱門選修課。數(shù)據(jù)結構是計算機程序設計的重要理論基礎，它不僅是計算機學科一門專業(yè)技術基礎課，它對學習者的的要求很明確：學會分析、研究計算機加工的數(shù)據(jù)結構的特性，以便為應用設計所需的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構、存儲結構及其相應的算法，并初步掌握算法的時間分析和空間分析的技術。其次，該課程的學習過程也是復雜程序設計的訓練過程，要求學習者編寫的程序結構或設計的程序結構體清楚、正確、易讀，符合軟件工程的規(guī)范。循環(huán)鏈表是一種重要的鏈式結構，其特殊性在于需附設兩個指針分別指示表頭元素及表尾元素的位置且表頭和表尾相鄰接，臆造的環(huán)狀空間巧妙的解決了需循環(huán)依次刪除元素的約瑟夫問題。本設計采用目前最通用的程序設計語言之一——C語言作為數(shù)據(jù)結構和算法的描述語言，單循環(huán)鏈表作為數(shù)據(jù)存儲結構。充分考慮了循環(huán)鏈表的特點僅通過對兩個循環(huán)鏈表的出、入列操作，就簡單的實現(xiàn)了要求，動態(tài)的模擬出了猴子選大王問題中猴子循環(huán)報數(shù)的情況。該程序通俗易懂且實用性強，其他類似的算法均可借鑒和參考使用。并且該程序清單詳細具體、全面、具有很強的可讀性。2.需求分析2.1問題分析根據(jù)問題描述得知，該問題中m個猴子圍坐在一起形成首尾相接的環(huán)，因此可用循環(huán)鏈表解決。從第n個猴子開始出列相當于從鏈表中刪除一個結點。該程序主要有三個模塊組成，建立循環(huán)鏈表，報數(shù)利用循環(huán)鏈表實現(xiàn)猴子的出列，最終剩下的猴子即猴王。具體步驟如下：

第一步

首先創(chuàng)建循環(huán)鏈表。第二步向鏈表中填入猴子的編號

第二步

找第一個開始報數(shù)的猴子。

第三步

數(shù)到n讓這個猴子出列第四步

接著開始報數(shù)，重復第三步，直到剩下最后一個猴子，它就為大王！??！2.2總體設計采用兩個循環(huán)隊列反復出隊列與入隊列來進行“舞伴配對”。程序中主要用到以下抽象數(shù)據(jù)類型：設定鏈表抽象數(shù)據(jù)類型的定義ADTstruct{對象數(shù)據(jù)＝（整數(shù)）操作對象:structmonkey*create()建立循環(huán)鏈表structmonkey*findout(start,n)找出被淘汰的猴子的上一個Structmonkey*letout(last)刪掉被淘汰的猴子，返回的指針值指向下一個猴子}。 基本操作initring(intn,linklistr)操作結果：構造一個具有n個元素的循環(huán)鏈表r。iinklistdelete(intn,intk,linklistr)初始條件：鏈表r已存在。操作結果：循環(huán)依次刪除問題對應所需位置的元素并當即輸出其值，用指針r記錄其最后元素的位置。}ATDlinklistoutring(intn,linklistr)特殊輸出鏈表保留的最后一個元素，即猴子大王的序號。程序包含兩個模塊a.主程序模塊，其中主函數(shù)為voidmain{ 輸入猴子的信息； 根據(jù)輸入要求進行刪除和輸出； 剩下一個猴子后，輸出結果；}b.循環(huán)鏈表模塊——實現(xiàn)具體刪除輸出操作。兩模塊之間的簡單調用關系主函數(shù)模塊循環(huán)隊列模塊主函數(shù)模塊循環(huán)隊列模塊循環(huán)鏈表模塊圖1模塊調用圖3.概要設計3.1模塊分析3.1.1鏈表循環(huán)輸入刪除輸出程序包含兩個模塊(1)主程序模塊，其中主函數(shù)為voidmain{ 輸入猴子的信息； 根據(jù)輸入要求進行刪除和輸出； 剩下一個猴子后，輸出結果；}(2)循環(huán)鏈表模塊——實現(xiàn)具體刪除輸出操作。a.輸入功能：當用戶執(zhí)行的猴子信息時，系統(tǒng)會提示用戶輸入猴子總數(shù)m和猴子的報號數(shù)n，輸入完后，執(zhí)行收索查找功能b.收索查找功能：在輸入的猴子總數(shù)和猴子報號數(shù)后，猴子開始進行按1至n循環(huán)報數(shù)（第1個猴子開始報數(shù)1，第2個猴子報數(shù)2，……，第n個猴子報數(shù)n，找出該猴子，第n+1個猴子報數(shù)1，第n+2個猴子報數(shù)2，……，在循環(huán)鏈表循環(huán)報數(shù)至釋放剩最后一個猴子）釋放節(jié)點，找出猴子王結點。c.釋放功能：當用戶執(zhí)行的檢索完猴子信息后，系統(tǒng)會提示用戶已釋放出費猴子大王節(jié)點和猴子大王結點的編號信息，該算法具體的實現(xiàn)：設計一個循環(huán)，找到要刪除的結點p以及它的前驅結點front，然后執(zhí)行front->next=p->next;e=p->shifang;釋放結點p并且返回被刪除猴子的編號。刪除函數(shù)為：voidDelete--()刪除算法的圖形表示為：當猴子報號數(shù)n時：圖2循環(huán)鏈表釋放結點循環(huán)鏈表模塊圖層分析（具體如下圖2所示）循環(huán)鏈表模塊輸入功能循環(huán)鏈表模塊輸入功能刪除釋放功能報數(shù)查找功能釋放出非猴子大王結點釋放出猴子大王圖3鏈表循環(huán)刪除輸出模塊3.1.2各個函數(shù)之間的調用關系整個函數(shù)調用關系：主函數(shù)由數(shù)據(jù)輸入、鏈表循環(huán)刪除輸出操作、數(shù)據(jù)輸出等組成（如下圖3所示）主函數(shù)最后元素輸出操作主函數(shù)最后元素輸出操作鏈表循環(huán)刪除輸出操作數(shù)據(jù)輸入輸出猴子大王序號圖4函數(shù)調用關系圖3.2函數(shù)的流程分析（如下圖5流程圖所示）設定鏈表抽象數(shù)據(jù)類型的定義ADTstruct{對象數(shù)據(jù)＝（猴子總數(shù)，m為整數(shù)）操作對象:structmonkey*create()建立循環(huán)鏈表structmonkey*findout(start,n)找出被淘汰的猴子的上一個Structmonkey*letout(last)刪掉被淘汰的猴子，返回的指針值指向下一個猴子}。在循環(huán)鏈表填入數(shù)據(jù)：猴子總數(shù)m、報號數(shù)n在循環(huán)鏈表填入數(shù)據(jù)：猴子總數(shù)m、報號數(shù)nfrontdata==n?==n-1？建立循環(huán)單鏈表定義結構體及變量front、rear、m、n結束開始釋放第n個猴子，指針front指向第n+1個結點rear=rear->next猴王就是第rear-〉data個猴子front==rear?==n-1？front++YNNY輸出已刪除的猴子節(jié)點和猴子大王結點圖5流程圖4.詳細設計4.1函數(shù)設計程序設計中主要包括下列函數(shù)LinkListinitring(intn,linklistr){構造一個含n個元素的循環(huán)鏈表;}LinkListdelete(intn,intk,linklistr){循環(huán)刪除報k號的元素； 循環(huán)輸出所刪除的元素； 記錄鏈表最后所保留的元素的位置；}voidmain()voidoutring(intn,linklistr){輸出鏈表最后保留的元素，即猴子大王的序號；}4.2程序源代碼#include"stdio.h"#include"stdlib.h"typedefstructnode{intdata;structnode*next;}listnode,*linklist;//**************************************************************************//**函數(shù)名稱:創(chuàng)建一個循環(huán)鏈表//**功能描述:輸入猴子總數(shù)數(shù)據(jù)m和猴子報數(shù)數(shù)據(jù)n，每報到n的猴子就刪除此猴子結點，//下一個猴子開始報數(shù)，每報到n的均刪除，如此循環(huán)，循環(huán)m-1次，即只需刪除m-1個//節(jié)點,最后剩下猴子大王//**參數(shù):循環(huán)鏈表的頭指針front，尾指針rear//***************************************************************************linklistinitring(intn,linklistr)//創(chuàng)建一個循環(huán)單鏈表{linklistfront,rear;inti;r=rear=(listnode*)malloc(sizeof(listnode));//兩個指針指向首位置for(i=1;i<n;i++){front=(listnode*)malloc(sizeof(listnode));rear->data=i;rear->next=front;rear=front;}front->data=n;front->next=r;//頭尾相連r=front;//指向頭節(jié)點位置returnr;}linklistdeleted(intn,intk,linklistr){inti,j;linklistfront,rear;front=r;//p移至頭節(jié)點位置for(i=1;i<=n-1;i++)//循環(huán)m-1次，即只需刪除m-1個節(jié)點,最后剩下猴子大王{for(j=1;j<=k-1;j++)front=front->next;//front循環(huán)移至下一個位置rear=front->next;front->next=rear->next;//報n號的猴子出列，即刪除front->nextprintf("%4d",rear->data);if(i%6==0)printf("\n");free(rear);}printf("\n");r=front;returnr;//記錄猴子大王位置并傳遞}voidoutring(intn,linklistr){inti;linklistfront;front=r;//獲得猴子大王位置printf("猴子大王：");printf("%4d\n",front->data);}//***************************************************************************//**函數(shù)名稱:主函數(shù)//**功能描述:輸入猴子總數(shù)m，猴子報數(shù)數(shù)據(jù)n//**參數(shù):m，n，j//***************************************************************************voidmain(){//***************************************************************************//**功能描述:猴子選大王游戲C語言工作界面，動態(tài)顯示日期和時間//***************************************************************************printf("\n");printf("\n");system("date/t");system("time/t");system("color16");printf("\n");printf("\n");printf("〓〓〓〓〓〓〓〓〓〓〓〓\n");printf("〓〓〓〓〓〓〓〓〓〓〓〓\n");printf("〓★★★★★★〓\n");printf("〓...★★★歡迎進入★★★...〓\n");printf("〓〓\n");printf("〓...★★★猴子選大王游戲C語言工作界面★★★...〓\n");printf("〓〓\n");printf("〓〓\n");printf("〓★★★★★★〓\n");printf("〓〓〓〓〓〓〓〓〓〓〓〓\n");printf("〓〓〓〓〓〓〓〓〓〓〓〓\n");intxuliehao;printf("\n");printf("\n");printf("\n");printf("請輸入密碼:");scanf("%d",&xuliehao);printf("\n");while(xuliehao!=39){printf("不好意思，您的序列號輸入錯誤，請重新輸入序列號:"); scanf("%d",&xuliehao); }system("cls");linklistr;intm,n;linklistinitring(intm,linklistr);linklistdeleted(intm,intk,linklistr);voidoutring(intm,linklistr);intj;while(j){printf（"〓〓〓〓〓〓〓〓〓〓〓〓〓\n");printf("〓★★★★★★★★★★★★★★★★★★★★★★★〓\n");printf("〓★★作者:龐康永050120080239★★〓\n");printf("〓★★工具:C-Free4.1★★〓\n");printf("〓★★題目:猴子選大王.★★〓\n");printf("〓★★M個猴子圍成一圈坐在一起,從第一個(1,2,3)開始★★〓\n");printf("〓★★報數(shù),報到n(n<M)的那個退出,然后從退出的下一個重★★〓\n");printf("〓★★新開始報數(shù),如此類推.剩下最后一個為王.★★〓\n");printf("〓★★創(chuàng)建時間:2010年01月20日.★★〓\n");printf("〓★★★★★★★★★★★★★★★★★★★★★★★〓\n");printf("〓〓〓〓〓〓〓〓〓〓〓〓〓\n");printf("請輸入猴子總數(shù)monkeynumberM=");scanf("%d",&m);printf("請輸入將出列猴子的報數(shù)號n=");scanf("%d",&n);printf("下列序號的猴子因報%d號而依次出列：\n",n);r=initring(m,r);r=deleted(m,n,r);outring(m,r);}}5.程序運行結果1登陸主界面2.輸入序列號進入功能界面3.輸入猴子總數(shù)m=54結果顯示界面4.輸入猴子報號n=6后運行結果界面6.設計體會經過了兩周的數(shù)據(jù)結構課程設計，我是受益頗多，從選題到定稿，從理論到實踐，在這短短的兩個星期的日子里，可以說得是苦多于甜，但是可以學到很多很多的的東西，同時不僅可以鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識，使我懂得了理論與實際相結合是很重要的，只有理論知識是遠遠不夠的，只有把所學的理論知識與實踐相結合起來，從理論中得出結論，從而提高自己的實際動手能力和獨立思考的能力。在設計的過程中遇到問題，可以說得是困難重重，這畢竟第一次做的，不可避免會遇到過各種各樣的問題，同時在設計的過程中發(fā)現(xiàn)了自己的不足之處，上課時老師講的理論知識，似乎很容易接受，以及各種算法都能夠較為理解，但是在真正的運用過程中，并不能把理論知道很好的和實踐結合起來。在平時做實驗時，尤其是這次課程設計，總感到有些無從下手。因此，在學知識的過程中，一定要多動手、動腦，將所學的知識熟練掌握，自如運用。通過這次課程設計，對我的邏輯思維能力是一個很大的鍛煉，再有，它還加強了我們的系統(tǒng)思考問題的能力，在編程方面，我們開始從整體的角度來考慮問題了，而不再像以前一樣的，胡亂動手。也就是因為先前的這種編程習慣，使得我們在課程設計過程中浪費了不少的時間，嘗到了教訓。此次課程設計也對我的獨自解決問題的能力有了極大的提高。說實在的，剛看到課程設計題目是《猴子選大王》，一開始我是蒙了，聽都沒聽過的游戲而且還要用算法實現(xiàn)，這對我是一個打擊，第一次要我一個人單獨完成一個課程設計，難度可想而知，后來慢慢的靜下來冷靜思考理解題目，經過較長時間的調試代碼和修改代碼，才得出了最后的結果，并且在這個過程中，我掌握了不少專業(yè)知識，是一次知識的大匯總，并且在這個問題的思考的過程中，還更正了不少我們各自自身對于某個知識點的誤區(qū)。這次程序設計也是一個毅力的考驗過程。有時候往往只是一個小小的錯誤，卻要費很多的時間來解決。在這個過程不能過于急躁，并且要很有耐心才行程序需要反復調試，其過程很可能相當令人頭疼，有時花很長時間設計出來還是需要重做，那時心中未免有點灰心，此時更加需要靜下心，查找原因。7.結束語感謝學校給我提供一次這樣的動手機會，運用循環(huán)鏈表的基本操作順利的解決猴子選大王問題，主要利用循環(huán)鏈表的環(huán)狀結構，循環(huán)地執(zhí)行刪除操作并輸出其值，記錄最后保留元素的位置，而整個過程不需要不需要移動元素使程序在空間復雜度上降小很多，采用指針的移動大大加快了程序的執(zhí)行效率。系統(tǒng)整體上比較完美，可以從鍵盤獲取輸入元素，整體輸出畫面效果整潔、大方。課程設計是培養(yǎng)學生綜合運用所學知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學生實際工作能力的具體訓練和考察過程我想這不只是一次簡簡單單的課程設計，更體現(xiàn)了數(shù)據(jù)結構算法和生活的緊密聯(lián)系。讓人不得不深思，這一個學期的學習，這兩年來的大學學習生涯，自己究竟學會了什么，掌握了多少，是否能勝任以后作編譯人員的職位。我想大家都心里都有很多的感觸。對于自己，我想我已經認識到了自己的不足，在今后的學習過程中，一定會以嚴謹?shù)膽B(tài)度來對待編程，以最好的面貌來迎接大三的計算機專業(yè)課程，并且要經常上機調試，堅持理論與實踐相結合。參考文獻【1】嚴蔚敏,吳偉民數(shù)據(jù)結構(C語言版)清華大學出版社【2】譚浩強C程序設計(第三版)清華大學出版社【3】胡學鋼.數(shù)據(jù)結構算法設計指導[M].北京:清華大學出版社,1999【4】羅宇等.數(shù)據(jù)結構[M].北京:北京郵電大學出版社,2003【5】/【6】目錄TOC\o"1-2"\h\z\u第一章總論 11.1項目概況 11.2可行性研究報告編制單位 41.3承辦單位簡介 41.4項目區(qū)概況 51.5可行性研究依據(jù) 91.6可行性研究的范圍 10第二章項目建設背景及必要性 11