猴子選王問題求解和二叉樹建立——課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-04-02 格式：doc 頁數(shù)：14 大?。?15.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩13頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)》課程設計　　———————猴子選王問題求解和二叉樹的建立　　專業(yè) 計算機科學與技術(shù)　　班級 　　指導教師 <p

2、>　　編寫日期 2012年6月24日　　目錄　　一、課程設計的目的………………………………………………3　　二、課程設計的要求………………………………………………3　　三、相關(guān)知識………………………………………

3、………………3　　四、問題的分析……………………………………………………3　　五、數(shù)據(jù)結(jié)構(gòu)的描述………………………………………………4　　六、算法的設計……………………………………………………4　　七、代碼實現(xiàn)………………………………………………………6&

4、lt;/p>　　八、程序運行成功展示……………………………………………11　　九、心得體會………………………………………………………14　　十、參考資料………………………………………………………14　　一、課程設計的目的</p&g

5、t;　　課程設計是學生對課程所學知識的綜合運用，它與課堂聽講、上機實驗、課外練習、自學研究相輔相成，構(gòu)成一個完整的課程教學體系?！稊?shù)據(jù)結(jié)構(gòu)》是一門實踐性強的課程，其中對算法設計和程序編寫的掌握尤為重要。學生雖然可以通過與課堂教學同步的上機實驗完成相關(guān)內(nèi)容的練習，但卻往往局限于一些功能簡單、彼此之間關(guān)系獨立的算法和程序。課程設計是一種綜合訓練，致力于培養(yǎng)學生全面、靈活的算法設計思想和較高的編程能力，為今后從事計算機開

6、發(fā)與應用打下基礎。新世紀需要具有豐富科學知識、獨立解決實際問題、有創(chuàng)造能力的新型人才，這也是該課程設計的最終目的。　　二、課程設計的要求　　1、猴子選王問題描述　　一堆猴子都有編號，編號是1，2，3 ...m ,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第

7、n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。　　2、二叉樹的建立描述　　已知二叉樹T中結(jié)點的前序和中序遍歷序列，編寫算法實現(xiàn)構(gòu)造滿足上述條件的二叉樹。 　　3、界面設計模塊問題描述　　設計一個菜單式界面，讓用戶可以選擇要解決的問題，

8、同時可以退出程序。界面要求簡潔明了，大方得體，便于用戶的使用，同時，對于用戶的錯誤選擇可以進行有效的處理。　　三、相關(guān)知識　　1、猴子選王求解　　約瑟夫環(huán)（Josephus）問題是由古羅馬的史學家約瑟夫（Josephus）提出的，他參加并

9、記錄了公元66—70年猶太人反抗羅馬的起義。約瑟夫作為一個將軍，設法守住了裘達伯特城達47天之久，在城市淪陷之后，他和40名死硬的將士在附近的一個洞穴中避難。在那里，這些叛亂者表決說“要投降毋寧死”。于是，約瑟夫建議每個人輪流殺死他旁邊的人，而這個順序是由抽簽決定的。約瑟夫有預謀地抓到了最后一簽，并且，作為洞穴中的兩個幸存者之一，他說服了他原先的犧牲品一起投降了羅馬。 　　約瑟夫環(huán)問題的具體描述

10、是：設有編號為1，2，……，n的n(n>0)個人圍成一個圈，從第1個人開始報數(shù)，報到m時停止報數(shù)，報m的人出圈，再從他的下一個人起重新報數(shù)，報到m時停止報數(shù)，報m的出圈，……，如此下去，直到所有人全部出圈為止。當任意給定n和m后，設計算法求n個人出圈的次序　　2、二叉樹的建立　　二叉樹的存儲結(jié)構(gòu)為二叉鏈表<

11、;/p>　　C語言　　二叉樹的遍歷　　四、問題的分析　　1、猴子選王問題的分析　　通過問題的文字描述可以先把問題簡化為一個簡單的線

12、性順序表，然后通過順序查找來刪除所需元素，但是因為該題的需要進行循環(huán)計數(shù)，因此需要將此線性順序表改造成為一個循環(huán)鏈表，通過指針將表頭和表尾連接起來，再通過指針計數(shù)將所需刪除的元素導出，最后通過重復操作將元素逐一刪除，得到自己最后想要得到的元素，即猴王。　　2、二叉樹的建立　　由于要根據(jù)二叉樹中結(jié)點的中序和后序遍歷序列

13、，建立的二叉樹以二叉鏈表的存儲結(jié)構(gòu)進行存儲，并且輸出二叉樹的先序遍歷序列，所以我們先根據(jù)后序遍歷序列的最后一個結(jié)點是根節(jié)點出發(fā)，再在中序遍歷序列中找個該字符，則左右兩邊分別為左右子數(shù)的字符序列.以這個思想遞歸調(diào)用函數(shù)建立起二叉樹.然而先序遍歷是先遍歷根節(jié)點再遍歷左右字數(shù)，我們就編寫相關(guān)的函數(shù)調(diào)用即可　　五、數(shù)據(jù)結(jié)構(gòu)描述

14、;　　typedef struct Lnode{　　int data;　　struct Lnode *next;　　}linklist;//單鏈表解決猴子選王時儲存結(jié)點信息　　typedef struct node{ </p&g

15、t;　　char data;　　struct node * lch,*rch;　　}BTNode,*BTree;//樹的二叉鏈表儲存表示　　六、算法的設計　　1、程序功能模塊圖

16、;　　2、算法設計　?。?）猴子選擇問題　　head = (linklist*) malloc(sizeof(linklist)); /* 創(chuàng)建循環(huán)鏈表，頭節(jié)點也存信息*/　　p

17、 = head;　　p->data = 1;　　p->next = p;　　for (i = 2; i <= n; i++) {　　s = (linklist*) malloc(sizeof(linklist));

18、;　　s->data = i;　　s->next = p->next;　　p->next = s;　　p = p->next;　　} /* 初始化循環(huán)鏈表*/<b&g

19、t;　　p = head;　　for (i = 1; i < k; i++){　　p = p->next;　　} /* 找到第k 個節(jié)點*/　　total = n; /* 保存節(jié)點總數(shù)*/

20、　　printf("\n出局序列為:");　　q = head;　　while (total != 1) /* 只剩一個節(jié)點時停止循環(huán)*/　　{　　for (i = 1;

21、 i < m; i++){　　p = p->next;　　} /* 報數(shù)過程，p指向要刪除的節(jié)點*/　　printf("[%d] ", p->data);/* 打印要刪除的節(jié)點序號*/　　while (q->next !=

22、p){　　q = q->next;　　}/* q 指向p 節(jié)點的前驅(qū)*/　　q->next = p->next; /* 刪除p 節(jié)點*/　　s = p;/* 保存被刪除節(jié)點指針*/　　p = p->next

23、;/* p 指向被刪除節(jié)點的后繼*/　　free(s);/* 釋放被刪除的節(jié)點*/　　total--; /* 節(jié)點個數(shù)減一*/　　}　?。?）二叉樹的建立

24、　　void create(BTree *t,int instart,int inend,int poststart,int postend)　　{int i;　　if(inend>=instart&&postend>=poststart)<

25、b>　　{　　*t=(BTree)malloc(LEN);　　(*t)->data=post[postend];　　i=instart;　　while(pin[i]!=post[postend])i++;<p&

26、gt;　　if(i==instart)　　(*t)->lch=NULL;　　else{　　create(&(*t)->lch,instart,i-1,poststart,poststart+i-1-instart);

27、;　　/*左子樹的中序起始點為整棵樹的中序起始點instart*/　　/* 終止點為根節(jié)點的前一個i-1 */　　/* 后序起始點為整棵樹的后序起始點poststart*/　　/* 后序終止點為后序起始點加上左子樹節(jié)點個數(shù)減一：*/　　/* poststart+(i-1-

28、instart+1)-1*/　　}　　if(i==inend)　　(*t)->rch=NULL; /*如果根在中序序列的最后一個右空*/　　else

29、　　{　　create(&(*t)->rch,i+1,inend,poststart+i-instart,postend-1);　　/*右子樹的中序起始點是根的下一個i+1*/　　/* 終止點是整棵樹中序的終止點inend*/</p&g

30、t;　　/* 后序的起始點是左子樹后序終止點的下一個poststart+i-1-instart+1*/　　/* 終止點是除根外的最后一個節(jié)點，即倒數(shù)第二個*/　　}　　}&l

31、t;b>　　else　　*t=NULL;　　}　　七、代碼實現(xiàn)　　#include "stdafx.h"<

32、/p>　　#include<stdio.h>　　#include <conio.h>　　#include <stdlib.h>　　#define EL 10　　#define TEL 2*EL+1</p

33、>　　#define LEN sizeof(struct node)　　void welcome(){ 　　printf(" ******** WELCOME COME TO OUR SYSTEM ********\n");　　pr

34、intf(" *******\n");　　printf(" **** ****\n");　　printf(" **

35、 **\n");　　printf(" ** ∩ ∩ **\n"); 　　printf(" ** **\n");

36、　　printf(" ** O **\n");　　printf(" ** **\n");　　printf("

37、 ** _______ **\n");　　printf(" **** ****\n");　　printf(" *****************************

38、*********************\n");　　printf(" * * *\n");　　printf(" * *

39、*\n");　　printf(" * * *\n"); 　　printf(" * *************************** *\n");&l

40、t;/p>　　printf(" * **1.The monkey King Slect** *\n");　　printf(" * *************************** *\n");

41、　printf(" * *\n");　　printf(" ***************** **********\n");　　printf("

42、 **2.Binary Tree** **3.exit**\n");　　printf(" ***************** **********\n");　　}</p&

43、gt;　　/* 以下是二叉樹的程序*/　　char post[TEL]="CEDBHGJIFA";　　char pin[TEL]="CBEDAGHFJI";　　typedef struct node　　{ ch

44、ar data;　　struct node * lch,*rch;　　}BTNode,*BTree;　　BTNode root;　　BTree rt=&root;　　void create(BTree *t,int ins

45、tart,int inend,int poststart,int postend)　　{int i;　　if(inend>=instart&&postend>=poststart)　　{

46、　　*t=(BTree)malloc(LEN);　　(*t)->data=post[postend];　　i=instart;　　while(pin[i]!=post[postend])i++;　　if(i==instart)

47、　　(*t)->lch=NULL;　　else{　　create(&(*t)->lch,instart,i-1,poststart,poststart+i-1-instart);　　/*左子樹的中序起始點為整棵樹的中序起始點instar

48、t*/　　/* 終止點為根節(jié)點的前一個i-1 */　　/* 后序起始點為整棵樹的后序起始點poststart*/　　/* 后序終止點為后序起始點加上左子樹節(jié)點個數(shù)減一：*/　　/* poststart+(i-1-instart+1)-1*/<

49、p>　　}　　if(i==inend) 　　(*t)->rch=NULL; /*如果根在中序序列的最后一個右空*/　　else　　{

50、　　create(&(*t)->rch,i+1,inend,poststart+i-instart,postend-1);　　/*右子樹的中序起始點是根的下一個i+1*/　　/* 終止點是整棵樹中序的終止點inend*/　　/* 后序的起

51、始點是左子樹后序終止點的下一個poststart+i-1-instart+1*/　　/* 終止點是除根外的最后一個節(jié)點，即倒數(shù)第二個*/ 　　}　　}　　else</b&g

52、t;　　*t=NULL;　　}　　void travel(BTree t)　　{if(t)　　{&

53、lt;/b>　　putchar(t->data);　　travel(t->lch);　　travel(t->rch);　　}　　}

54、　　void Binary (){　　printf("*****************************WELCOME BINARY TREE********************************\n");　　printf("

55、小組成員：PPT 演講：張琪\n");　　printf("\n");　　printf(" 資料搜集：施芳\n");　　printf("\n");

56、;　　printf(" 程序編譯：陳孝堅\n");　　printf("\n");　　printf("后序是:CBEDAGHFJI\n");　　printf("中序是：CEDBHGJIFA

57、\n");　　printf("輸入任意字符查看先序序列："); 　　getch(); 　　create(&rt,0,9,0,9);　　if(rt) travel(rt);&

58、lt;p>　　}　　/* 以下是猴子選王的程序*/　　typedef struct Lnode{　　int data;　　struct Lnode *next;<

59、;p>　　}linklist;/* 定義鏈表節(jié)點類型*/　　int mokeyking(){　　int i, n, k, m, total;　　linklist *head, *p, *s, *q; 　　printf("\n");</p&g

60、t;　　printf("\n");　　printf("************************WELCOME THE MONKEY KING SLECT***************************\n"); 　　printf("

61、小組成員：PPT 演講：呂光躍\n");　　printf("\n");　　printf(" 資料搜集：樓冰\n");　　printf("\n");<p&

62、gt;　　printf(" 程序編譯：龍啟昌\n");　　printf("\n");　　printf("請輸入猴子的個數(shù)n:");　　scanf("%d", &n);

63、　　printf("請輸入要從第幾個猴子開始報數(shù)k:");　　scanf("%d", &k);　　printf("請輸入出局數(shù)字m:");　　scanf("%d", &m);

64、 /* 讀入問題條件*/ 　　head = (linklist*) malloc(sizeof(linklist)); /* 創(chuàng)建循環(huán)鏈表，頭節(jié)點也存信息*/　　p = head;　　p->data = 1;<p&g

65、t;　　p->next = p; 　　for (i = 2; i <= n; i++) {　　s = (linklist*) malloc(sizeof(linklist));　　s->data = i;　　s->n

66、ext = p->next;　　p->next = s;　　p = p->next;　　} /* 初始化循環(huán)鏈表*/　　p = head;　　for (i = 1; i

67、 < k; i++){　　p = p->next;　　} /* 找到第k 個節(jié)點*/ 　　total = n; /* 保存節(jié)點總數(shù)*/　　printf("\n出局序列為:");<b&

68、gt;　　q = head;　　while (total != 1) /* 只剩一個節(jié)點時停止循環(huán)*/　　{　　for (i = 1; i < m; i++){　　p = p->next;<

69、/p>　　} /* 報數(shù)過程，p指向要刪除的節(jié)點*/　　printf("[%d] ", p->data);/* 打印要刪除的節(jié)點序號*/　　while (q->next != p){　　q = q->next;<p

70、>　　}/* q 指向p 節(jié)點的前驅(qū)*/　　q->next = p->next; /* 刪除p 節(jié)點*/　　s = p;/* 保存被刪除節(jié)點指針*/　　p = p->next;/* p 指向被刪除節(jié)點的后繼*/　　free(s);/* 釋放被刪除的

71、節(jié)點*/　　total--; /* 節(jié)點個數(shù)減一*/　　}　　printf("\n\n猴子大王為第[%d] 號\n\n", p->data);/* 打印最后剩下的節(jié)點序號*/　　free(p

72、);　　//system("pause");　　return 0;　　}　　int _tmain(int argc, _TCHAR* argv[])<

73、/p>　　{　　int a;　　welcome();　　printf("please choose the function :");　　scanf

74、("%d",&a);　　while(a!=3){　　switch(a){　　case 1:system("cls"); mokeyking(); getch();break;　　case 2:system("cl

75、s"); Binary (); getch();break;　　default: printf("please chooose the right choice!");break;　　}　　system("cls");<

76、;/p>　　welcome();　　printf("please choose the function ：\n"); 　　scanf("%d",&a);　　}

77、;　　return 0;　　}　　八、程序運行成功展示　　1、主鍵面　　2、輸入1<p&g

78、t;　　3、輸入23只猴子，從第1只開始報數(shù)，每數(shù)到5就出局　　4、按任意鍵后返回主鍵面輸入2　　5、按任意鍵　　6、按任意鍵后返回主鍵面輸入3　　7、退出程序<p&

79、gt;　　九、心得體會　　1、猴子選王問題　　設計是培養(yǎng)并提高我們中和運用所學知識的能力，鍛煉我們實際解決問題的能力，是對我們學生實際工作能力的考驗和提高。　　從拿到題目到完成整個編程，從理論到實踐，在這一個多星期的時間里，學到了很多在課

80、堂上不能了解的東西，而且鞏固了以前所學過的知識，能夠做到將理論和實踐相結(jié)合，提高了自己的實際動手能力和獨立思考的能力，在設計過程中發(fā)現(xiàn)自己的不足之處，并且得到了一定的改善，總的來說通過這次課程設計，對程序不斷改善的同時，也是對自身的不斷改善，非常感謝學校提供的這次課程設計的機會　　2、二叉樹的建立　　從本次課程設計中

81、我們了解的二叉樹遍歷的重要性，以及先序遍歷、中序遍歷、后序遍歷的相關(guān)算法.明白了二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，很好的編程思想，在學習中有很多作用. 通過這次課程設計，理論知識和實踐相互結(jié)合才能實現(xiàn)程序,通過查閱資料豐富了以前所遺漏的知識，同時又更加充實了以前所遺漏的知識,了解了算法在編程中的重要性，一個好的算法能極大地優(yōu)化一個程序　　通過這次的課程設計，我們學到了怎么樣從一個實際問題出發(fā)，建立模型

82、，找到相應的儲存結(jié)構(gòu)和實現(xiàn)方法，實際運行，反復調(diào)試和修改，最終實現(xiàn)功能。在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練，學會數(shù)據(jù)組織的方法，把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來并用軟件解決問題，培養(yǎng)了良好的程序設計技能。　　十、參考資料：　　[1] 朱蓉.數(shù)據(jù)結(jié)構(gòu)實驗指導書</

83、p>　　[2]蔡子經(jīng)，施伯樂.數(shù)據(jù)結(jié)構(gòu)教程.上海:復旦大學出版社.1994　　[3]嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版).北京：清華大學出版社.1997；　　[4]嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)題集(C語言版).北京：清華大學出版社.1997；　　[5]孟佳娜,胡瀟琨.算法與數(shù)據(jù)結(jié)構(gòu)實驗與習

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

猴子選王問題求解和二叉樹建立——課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

猴子選王問題求解和二叉樹建立——課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載