1、數據結構課程設計報告題目：猴子選大王采用循環鏈表及動態存儲的實現班 級：計算機082班姓 名：指導教師：成 績： 信息工程學院 2010年01 月 20 日 目錄課程設計摘要(題目) 03 032.需求分析 04 問題分析 04 總體設計 05 07模塊分析 07鏈表循環輸入刪除輸出07各個函數之間的調用關系 09 10 12函數設計 12 135.測試結果 16 18 19參考文獻 20摘要(題目):猴子選大王任務：一堆猴子都有編號，編號是1，2，3 .m ,這群猴子m個按照1-m的順序圍坐一圈，從第1開始數，每數到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，那么該

2、猴子為大王。要求：輸入數據：輸入m,n ；m,n 為整數n<m輸出形式：中文提示按照m個猴子，數n 個數的方法，輸出為大王的猴子是幾號 ，建立一個函數來實現此功能隨著計算機科學的迅速開展，計算機已深入到揉合社會的各個領域，它的應用已不再局限于科學計算，以解決一些數學問題，而且可以解決一些抽象化的具體問題，更多地用于控制，管理及數據處理等非數值計算的處理工作，這便為我們的日常生活提供了很多的方便，譬如說火車、飛機售票系統，學生成績管理，商品管理系統，醫院選址等實際問題。如今程序設計的語言很多，有開展比擬完善高級語言，也有最根本的低級語言，然而再好的程序設計也要有一個比擬清晰的思路算法。為了

3、編寫好一個好程序，必須分析待處理對象的特性以及各處理對象之間的關系，于是數據結構便成為我們絕佳的選擇。數據結構是計算機程序設計的重要理論技術根底，它不僅是計算機科學的核心課程，而且已成為其他理工專業的熱門選修課。數據結構是計算機程序設計的重要理論根底，它不僅是計算機學科一門專業技術根底課，它對學習者的的要求很明確：學會分析、研究計算機加工的數據結構的特性，以便為應用設計所需的數據選擇適當的邏輯結構、存儲結構及其相應的算法，并初步掌握算法的時間分析和空間分析的技術。其次，該課程的學習過程也是復雜程序設計的訓練過程，要求學習者編寫的程序結構或設計的程序結構體清楚、正確、易讀，符合軟件工程的標準。循

4、環鏈表是一種重要的鏈式結構，其特殊性在于需附設兩個指針分別指示表頭元素及表尾元素的位置且表頭和表尾相鄰接，臆造的環狀空間巧妙的解決了需循環依次刪除元素的約瑟夫問題。本設計采用目前最通用的程序設計語言之一C語言作為數據結構和算法的描述語言，單循環鏈表作為數據存儲結構。 充分考慮了循環鏈表的特點僅通過對兩個循環鏈表的出、入列操作，就簡單的實現了要求，動態的模擬出了猴子選大王問題中猴子循環報數的情況。該程序通俗易懂且實用性強，其他類似的算法均可借鑒和參考使用。并且該程序清單詳細具體、全面、具有很強的可讀性。2.需求分析 根據問題描述得知，該問題中m個猴子圍坐在一起形成首尾相接的環，因此可用循環鏈表解

5、決。從第n個猴子開始出列相當于從鏈表中刪除一個結點。該程序主要有三個模塊組成，建立循環鏈表，報數利用循環鏈表實現猴子的出列，最終剩下的猴子即猴王。具體步驟如下：    第一步  首先創立循環鏈表。第二步 向鏈表中填入猴子的編號    第二步  找第一個開始報數的猴子。    第三步  數到n讓這個猴子出列第四步  接著開始報數，重復第三步，直到剩下最后一個猴子，它就為大王！ 2.2總體設計 采用兩個循環隊列反復出隊列與入隊列來進行“舞伴配對。程序中主要用到

6、以下抽象數據類型：1) 設定鏈表抽象數據類型的定義ADT struct 對象數據整數 操作對象:struct monkey *create() 建立循環鏈表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一個 Struct monkey *letout(last) 刪掉被淘汰的猴子，返回的指針值指向下一個猴子。根本操作(1) initring(int n,linklist r) 操作結果：構造一個具有n個元素的循環鏈表r。(2) iinklist delete(int n,int k,linklist r)初始條件：鏈表r已存在。操作結果：循環依次刪除問題

7、對應所需位置的元素并當即輸出其值，用指針r記錄其最后元素的位置。ATD linklist(3) outring(int n,linklist r)特殊輸出鏈表保存的最后一個元素，即猴子大王的序號。程序包含兩個模塊a. 主程序模塊，其中主函數為void main輸入猴子的信息；根據輸入要求進行刪除和輸出；剩下一個猴子后，輸出結果；b. 循環鏈表模塊實現具體刪除輸出操作。2) 兩模塊之間的簡單調用關系主函數模塊循環隊列模塊循環鏈表模塊圖1 模塊調用圖3.概要設計鏈表循環輸入刪除輸出程序包含兩個模塊(1) 主程序模塊，其中主函數為void main輸入猴子的信息；根據輸入要求進行刪除和輸出；剩下一個

8、猴子后，輸出結果；(2) 循環鏈表模塊實現具體刪除輸出操作。 a.輸入功能：當用戶執行的猴子信息時，系統會提示用戶輸入猴子總數m和猴子的報號數n，輸入完后，執行收索查找功能 b.收索查找功能：在輸入的猴子總數和猴子報號數后，猴子開始進行按1至n循環報數第1個猴子開始報數1，第2個猴子報數2，第n個猴子報數n，找出該猴子，第n+1個猴子報數1，第n+2個猴子報數2，在循環鏈表循環報數至釋放剩最后一個猴子釋放節點，找出猴子王結點。c.釋放功能：當用戶執行的檢索完猴子信息后，系統會提示用戶已釋放出費猴子大王節點和猴子大王結點的編號信息，該算法具體的實現：設計一個循環，找到要刪除的結點p以及它的前驅結

9、點front，然后執行front->next=p->next; e=p->shifang;釋放結點p并且返回被刪除猴子的編號。刪除函數為：void Delete - ()刪除算法的圖形表示為：當猴子報號數n時： 圖2 循環鏈表釋放結點循環鏈表模塊圖層分析具體如以下圖2所示循環鏈表模塊輸入功能刪除釋放功能報數查找功能釋放出非猴子大王結點釋放出猴子大王圖3 鏈表循環刪除輸出模塊各個函數之間的調用關系整個函數調用關系：主函數由數據輸入、鏈表循環刪除輸出操作、數據輸出等組成如以下圖3所示主函數最后元素輸出操作鏈表循環刪除輸出操作數據輸入輸出猴子大王序號圖4 函數調用關系圖如以下圖5

10、流程圖所示設定鏈表抽象數據類型的定義ADT struct 對象數據猴子總數，m為整數 操作對象:struct monkey *create() 建立循環鏈表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一個 Struct monkey *letout(last) 刪掉被淘汰的猴子，返回的指針值指向下一個猴子。在循環鏈表填入數據：猴子總數m、報號數nfrontàdata= =n?= = n-1？建立循環單鏈表定義結構體及變量front、rear、m、n結束開始釋放第n個猴子，指針front指向第n+1個結點rear=rear->next猴王

11、就是第rear-data 個猴子front= =rear?= = n-1？front +YNNY輸出已刪除的猴子節點和猴子大王結點 圖5 流程圖4.詳細設計4.1函數設計程序設計中主要包括以下函數LinkList initring(int n,linklist r) 構造一個含n個元素的循環鏈表;LinkList delete(int n,int k,linklist r) 循環刪除報k號的元素； 循環輸出所刪除的元素；記錄鏈表最后所保存的元素的位置；void main ( )void outring(int n,linklist r) 輸出鏈表最后保存的元素，即猴子大王的序號；4.2程序源代

12、碼#include "stdio.h" #include "stdlib.h" typedef struct node int data; struct node *next; listnode,*linklist; /* /* 函數名稱:創立一個循環鏈表 /* 功能描述:輸入猴子總數數據m和猴子報數數據n，每報到n的猴子就刪除此猴子結點， /下一個猴子開始報數，每報到n的均刪除，如此循環，循環m-1次，即只需刪除m-1個 / 節點,最后剩下猴子大王 /* 參數:循環鏈表的頭指針front，尾指針rear /* linklist initring(int

13、 n,linklist r) /創立一個循環單鏈表 linklist front,rear; int i; 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; /指向頭節點位置 return r; linklist d

14、eleted(int n,int k,linklist r) int i,j; linklist front,rear; front=r; /p移至頭節點位置 for(i=1;i<=n-1;i+) /循環m-1次，即只需刪除m-1個節點,最后剩下猴子大王 for(j=1;j<=k-1;j+) front=front->next; /front循環移至下一個位置 rear=front->next; front->next=rear->next; /報n號的猴子出列，即刪除front->next printf("%4d",rear-&g

15、t;data); if(i % 6=0) printf("n"); free(rear); printf("n"); r=front;return r; /記錄猴子大王位置并傳遞 void outring(int n,linklist r) int i; linklist front; front=r; /獲得猴子大王位置 printf("猴子大王："); printf("%4dn",front->data); /* /* 函數名稱:主函數/* 功能描述:輸入猴子總數m，猴子報數數據n /* 參 數:m，n，

16、j /* void main() /* /* 功能描述:猴子選大王游戲C語言工作界面，動態顯示日期和時間 /* printf("n"); printf("n"); system("date /t"); system("time /t"); system("color 16"); printf("n"); printf("n"); printf(" n"); printf(" n"); printf(" n&

17、quot;); printf(" .歡 迎 進 入. n"); printf(" n"); printf(" .猴子選大王游戲C語言工作界面. n"); printf(" n"); printf(" n"); printf(" n"); printf(" n"); printf(" n"); int xuliehao; printf("n"); printf("n"); printf("

18、n"); printf(" 請輸入密碼:"); scanf(" %d",&xuliehao);printf("n"); while(xuliehao!=39) printf("不好意思，您的序列號輸入錯誤，請重新輸入序列號:"); scanf("%d",&xuliehao);system("cls"); linklist r; int m,n; linklist initring(int m,linklist r); linklist deleted

19、(int m,int k,linklist r); void outring(int m,linklist r); int j; while(j) printf" n"); printf(" n"); printf(" 作者: 龐康永 050120210239 n"); printf(" 工具: C-Free 4.1 n"); printf(" 題目: 猴子選大王. n"); printf(" M個猴子圍成一圈坐在一起,從第一個(1,2,3.)開始 n"); printf(&

20、quot; 報數,報到n(n<M)的那個退出,然后從退出的下一個重 n"); printf(" 新開始報數,如此類推.剩下最后一個為王. n"); printf(" 創立時間: 2010年01月20日. n"); printf(" n"); printf(" n"); printf("請輸入猴子總數 monkey number M= "); scanf("%d",&m); printf("請輸入將出列猴子的報數號n= "); sca

21、nf("%d",&n); printf("以下序號的猴子因報%d號而依次出列：n",n); r=initring(m,r); r=deleted(m,n,r); outring(m,r); 5.程序運行結果1登陸主界面2. 輸入序列號進入功能界面3. 輸入猴子總數m=54結果顯示界面4.輸入猴子報號n=6后運行結果界面6.設計體會經過了兩周的數據結構課程設計，我是受益頗多，從選題到定稿，從理論到實踐，在這短短的兩個星期的日子里，可以說得是苦多于甜，但是可以學到很多很多的的東西，同時不僅可以穩固了以前所學過的知識，而且學到了很多在書本上所沒有學到過

22、的知識，使我懂得了理論與實際相結合是很重要的，只有理論知識是遠遠不夠的，只有把所學的理論知識與實踐相結合起來，從理論中得出結論，從而提高自己的實際動手能力和獨立思考的能力。在設計的過程中遇到問題，可以說得是困難重重，這畢竟第一次做的，不可防止會遇到過各種各樣的問題，同時在設計的過程中發現了自己的缺乏之處，上課時老師講的理論知識，似乎很容易接受，以及各種算法都能夠較為理解，但是在真正的運用過程中，并不能把理論知道很好的和實踐結合起來。在平時做實驗時，尤其是這次課程設計，總感到有些無從下手。因此，在學知識的過程中，一定要多動手、動腦，將所學的知識熟練掌握，自如運用。通過這次課程設計，對我的邏輯思維能力是一個很大的鍛煉，再有，它還加強了我們的系統思考問題的能力，在編程方面，我們開始從整體的角度來考慮問題了，而不再像以前一樣的，胡亂動手。也就是因為先前的這種編程習慣，使得我們在課程設計過程中浪費了不少的時間，嘗到了教訓。此次課程設計也對我的單獨解決問題的能力有了極大的提高。說實在的，剛看到課程設計題目是?猴子選大王?，一開始我是蒙了，聽都沒聽過的游戲而且還要用算法實現，這對我是一個打擊，第一次要我一個人單獨完成一個課程設計，難度可想而知，后來慢慢的靜下來冷靜思考理解題目，經過較長時間的調試代碼和修改代碼，才得出了最后的結果，并且在這個過程中，我掌握了不少專業知識，是一