猴子吃桃問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

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

猴子吃桃問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計_第1頁

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

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

文檔簡介

1、　　設(shè)計題目猴子吃桃子問題 　　有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一　　個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。　　二、運行環(huán)境（軟、硬件環(huán)境）　　VC++6.0 P

2、C電腦一臺　　算法的需求分析 　　1) 采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解　　2) 采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解　　3) 采用遞歸實現(xiàn)上述求解　　4) 如果采用

3、4種方法者,適當(dāng)加分　　//用戶界面　　int Desk(int n)　　{　　printf("*********************************************

4、*****\n");　　printf("| 歡迎進入猴子吃桃子系統(tǒng) |\n");　　printf("| 1-數(shù)組法 2-鏈表法 3-遞歸法 4-二叉樹法 5-退出 |\n");　　printf("***

5、************************************************\n");　　printf("請輸入要選擇的方法: ");　　scanf("%d",&n);　　getchar();

6、;　　system("cls"); //刷新屏幕　　while(n<1 || n>5)　　{　　printf("***輸入錯誤 ! 請重新輸入***\n");　　scanf(&q

7、uot;%d",&n);　　}　　return n;　　}　　四、算法概要設(shè)計

8、　　//采用鏈數(shù)據(jù)結(jié)構(gòu) (棧) 實現(xiàn)上述求解　　typedef struct　　{　　int *top;　　int *base;<

9、b>　　}stack;　　//初始化一個棧　　stack Init(stack *s)　　{　　s->base=(int *)malloc(STACK_SIZE*s

10、izeof(int));　　if(s->base == NULL)　　{　　printf("Init failed !\n");　　exit(-1);

11、　　}　　s->top = s->base;　　return *s;　　}　　//二叉樹<p&

12、gt;　　創(chuàng)建一個大小為DAYS(由用給出)的二叉樹,二叉樹的左孩子節(jié)點存放當(dāng)天的桃子數(shù)，右節(jié)點存放數(shù)字1，即為多吃的一個桃子。　　typedef struct TNode　　{　　int data;<p&g

13、t;　　struct TNode *lchild;　　struct TNode *rchild;　　}tree;　　//創(chuàng)建一個二叉樹　　tree CreatTree(tree *T) //T

14、為指針類型　　{ 　　int n=0,i=0;　　tree *p,*pr,*T1;　　T=(tree *)malloc(sizeof(TNode));　　T1=T;<

15、/b>　　T->data=1; //根節(jié)點內(nèi)的數(shù)據(jù)為第DAYS天的桃子數(shù)　　for(i=1; i<DAYS; i++)　　{　　p=(tree *)malloc(sizeof(TNode));

16、　　pr=(tree *)malloc(sizeof(TNode));　　pr->lchild=NULL;　　pr->rchild=NULL;　　p->data=0;　　pr->data=1;<p&

17、gt;　　T1->lchild=p;　　T1->rchild=pr;　　T1=p;　　}　　T1->lchild=NULL;　　T1-&

18、gt;rchild=NULL;　　return *T; //返回T的地址　　}　　//算法框架圖　　N<b

19、>　　Y N　　Y　　算法詳細(xì)設(shè)計　　#include <stdio.h>　　#include <stdlib.h>

20、　　#include "peach.h"　　//函數(shù)聲明　　int Desk(int n);　　void peach_1(void);　　stack Init(stack *s);</p&g

21、t;　　void Push(stack *s,int num);　　void Pop(stack *s,int &num);　　void peach_2(stack *s);　　void peach_3(int n,int i);　　tree

22、 CreatTree(tree *T);　　void calculate(tree *T);　　void peach_4(tree *T);　　int main()　　{　　int data=

23、0;　　int n=1,i=1;　　stack s;　　tree T;　　s=Init(&s);　　T=CreatTree(&T);<

24、;/p>　　while(1)　　{　　switch(Desk(n))　　{　　case 1:peach_1();</

25、p>　　break;　　case 2: peach_2(&s);　　break;　　case 3:peach_3(n,i);<b&g

26、t;　　break;　　case 4:peach_4(&T);　　break;　　case 5:exit(0);　　break;&l

27、t;p>　　}　　}　　return 0;　　}　　//頭文件代碼</

28、p>　　#define DAYS 10 //定義給定的天數(shù)　　#define STACK_SIZE 5 //棧的容量,實際只用了一個　　#define TRUE 1　　#define ERROR 0　　void peach_3(int n,

29、int i);　　//用戶界面　　int Desk(int n)　　{　　printf("************************************************

30、**\n");　　printf("| 歡迎進入猴子吃桃子系統(tǒng) |\n");　　printf("| 1-數(shù)組法 2-鏈表法 3-遞歸法 4-二叉樹法 5-退出 |\n");　　printf("******

31、*********************************************\n");　　printf("請選擇要使用的方法: ");　　scanf("%d",&n);　　getchar();　　s

32、ystem("cls"); //刷新屏幕　　while(n<1 || n>5)　　{　　printf("***輸入錯誤 ! 請重新輸入***\n");　　scanf("

33、%d",&n);　　}　　return n;　　}　　//采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解　　void

34、 peach_1(void)　　{　　int peach[50]={0};　　int i=0,j=0;　　peach[DAYS-1]=1; //最后一天的桃子數(shù)　　for(i=DAYS ;

35、i>0; --i , j=i-1)　　{　　peach[j] = 2*(peach[i] + 1);　　}　　printf("* * * * * * * * * * * * * *

36、 * * * * * * *\n");　　printf("* 數(shù) 組法 * \n");　　printf("* 這群猴子共摘了 %d 個桃子 *\n",peach[0]);　　p

37、rintf("* * * * * * * * * * * * * * * * * * * * *\n");　　}　　//采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解　　typedef struct　　{</

38、b>　　int *top;　　int *base;　　}stack;　　//初始化一個棧　　stack Ini

39、t(stack *s)　　{　　s->base=(int *)malloc(STACK_SIZE*sizeof(int));　　if(s->base == NULL)　　{</p

40、>　　printf("Init failed !\n");　　exit(-1);　　}　　s->top = s->base;　　retu

41、rn *s;　　}　　//把當(dāng)天的桃子數(shù)進棧　　void Push(stack *s,int num)　　{　　*s->top++ = 2*(num

42、 + 1);　　}　　//把前一天的桃子數(shù)出棧　　void Pop(stack *s,int &num) //&num位地址傳遞，可以直接對參數(shù)進行修改　　{&l

43、t;/p>　　num = *--s->top;　　}　　void peach_2(stack *s)　　{　　int i=0;

44、;　　int num=0;　　Push(s,1); //先把最后一天的桃子數(shù)進棧　　i++;　　while(i < DAYS)　　{</p&

45、gt;　　Pop(s,num);　　Push(s,num);　　i++;　　}　　printf("* * * * * * * * * * * * * * * * *

46、 * * * *\n");　　printf("* 鏈表法 * \n");　　printf("* 這群猴子共摘了 %d 個桃子 *\n",num);　　printf("

47、;* * * * * * * * * * * * * * * * * * * * *\n");　　}　　void peach_3(int n,int i)　　{　　if(i ==DAY

48、S) //DAYS 為遞歸終止條件由用戶給出　　{　　printf("* * * * * * * * * * * * * * * * * * * * *\n");　　printf("* 遞歸法

49、 *\n");　　printf("* 這群猴子共摘了 %d 個桃子 *\n",n);　　printf("* * * * * * * * * * * * * * * * * * * * *\n");

50、　　}　　else　　{　　n = 2*(n + 1);　　peach_3(n,i+1);　　}

51、　　}　　//二叉樹　　typedef struct TNode　　{　　int data;<

52、;/b>　　struct TNode *lchild;　　struct TNode *rchild;　　}tree;　　tree CreatTree(tree *T) //T 為指針類型

53、;　　{ 　　int n=0,i=0;　　tree *p,*pr,*T1;　　T=(tree *)malloc(sizeof(TNode));　　T1=T;<p&g

54、t;　　T->data=1; //根節(jié)點內(nèi)的數(shù)據(jù)為第DAYS天的桃子數(shù)　　for(i=1; i<DAYS; i++)　　{　　p=(tree *)malloc(sizeof(TNode));　　pr=(tree *)ma

55、lloc(sizeof(TNode));　　pr->lchild=NULL;　　pr->rchild=NULL;　　p->data=0;　　pr->data=1;　　T1->lchild=p;<

56、/p>　　T1->rchild=pr;　　T1=p;　　}　　T1->lchild=NULL;　　T1->rchild=NULL;

57、　　return *T; //返回T的地址　　}　　//對二叉樹進行賦值計算　　void calculate(tree *T)　　{<p&g

58、t;　　int i=0; 　　tree *T1,*T2,*T3; //T1,T3分別為T2的左右孩子　　T2=T;　　for(i=0; i<DAYS-1; i++)　　{&

59、lt;/b>　　T1=T2->lchild;　　T3=T2->rchild;　　T1->data=2*(T2->data + T3->data);　　T2=T1;<p&

60、gt;　　}　　}　　//二叉樹遍歷最左下角的孩子節(jié)點　　void peach_4(tree *T)　　{　　cal

61、culate(T);　　while(T->lchild != NULL)　　{　　T=T->lchild;　　}　　printf("

62、* * * * * * * * * * * * * * * * * * * * *\n");　　printf("* 二叉樹法 *\n");　　printf("* 這群猴子共摘了 %d 個桃子 *\n",T->dat

63、a);　　printf("* * * * * * * * * * * * * * * * * * * * *\n");　　}　　六、算法的測試　　//主函數(shù)

64、　　#include <stdio.h>　　#include <stdlib.h>　　#include "peach.h"　　//函數(shù)聲明<

65、p>　　int Desk(int n);　　void peach_1(void);　　stack Init(stack *s);　　void Push(stack *s,int num);　　void Pop(stack *s,int &num);</

66、p>　　void peach_2(stack *s);　　void peach_3(int n,int i);　　tree CreatTree(tree *T);　　void calculate(tree *T);　　void peach_4(

67、tree *T);　　int main()　　{　　int data=0;　　int n=1,i=1;　　stack s;<

68、p>　　tree T;　　s=Init(&s);　　T=CreatTree(&T);　　while(1)　　{

69、　　switch(Desk(n))　　{　　case 1:　　peach_1();　　break;

70、;　　case 2: 　　peach_2(&s); 　　break;　　case 3:　　peach_3(n,

71、i);　　break;　　case 4:　　peach_4(&T);　　break;　　c

72、ase 5:　　exit(0);　　break;　　}　　}<p&

73、gt;　　return 0;　　}　　//采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解　　void peach_1(void)　　{

74、　　int peach[50]={0};　　int i=0,j=0;　　peach[DAYS-1]=1; //最后一天的桃子數(shù)　　for(i=DAYS ; i>0; --i , j=i-1)　　{<

75、;p>　　peach[j] = 2*(peach[i] + 1);　　}　　printf("* * * * * * * * * * * * * * * * * * * * *\n");　　printf("* 數(shù)

76、組法 * \n");　　printf("* 這群猴子共摘了 %d 個桃子 *\n",peach[0]);　　printf("* * * * * * * * * * * * * * * * * * * * *\n");&l

77、t;p>　　}　　void peach_2(stack *s)　　{　　int i=0;　　int num=0;

78、;　　Push(s,1); //先把最后一天的桃子數(shù)進棧　　i++;　　while(i < DAYS)　　{　　Pop(s,num);　　Push

79、(s,num);　　i++;　　}　　printf("* * * * * * * * * * * * * * * * * * * * *\n");　　printf("

80、;* 鏈表法 * \n");　　printf("* 這群猴子共摘了 %d 個桃子 *\n",num);　　printf("* * * * * * * * * * * * * * * * * * * * *\n");&

81、lt;/p>　　}　　void peach_3(int n,int i)　　{　　if(i ==DAYS) //DAYS 為遞歸終止條件由用戶給出<b&g

82、t;　　{　　printf("* * * * * * * * * * * * * * * * * * * * *\n");　　printf("* 遞歸法 * \n");　　printf(&

83、quot;* 這群猴子共摘了 %d 個桃子 *\n",n);　　printf("* * * * * * * * * * * * * * * * * * * * *\n");　　}　　else</b

84、>　　{　　n = 2*(n + 1);　　peach_3(n,i+1); //循環(huán)體 　　}　　}</b

85、>　　//二叉樹遍歷最左下角的孩子節(jié)點　　void peach_4(tree *T)　　{　　calculate(T);　　while(T->lchild != NULL)<

86、/p>　　{　　T=T->lchild;　　}　　printf("* * * * * * * * * * * * * * * * * * * * *\n");

87、　　printf("* 二叉樹法 *\n");　　printf("* 這群猴子共摘了 %d 個桃子 *\n",T->data);　　printf("* * * * * * * * * * * * *

88、 * * * * * * * *\n");　　}　　運行結(jié)果分析 　　1、數(shù)組法：創(chuàng)建一個大小為DAYS的一維數(shù)組a[DAYS]，a[0],a[1]...a[DAYS-1]分別存放當(dāng)天的桃子數(shù)，其中a[n] = 2*(a[n-

89、1] + 1)。　　鏈表法：創(chuàng)建一個鏈棧，先把第DAYS天的桃子數(shù)進棧，然后出棧，把出戰(zhàn)的數(shù)據(jù)num進行處理，即num = 2*(num + 1)，然后繼續(xù)進棧，出棧如此反復(fù)循環(huán)DAYS次結(jié)束。　　3、遞歸法：首先確定遞歸的終止條件，即i = DAYS（假設(shè)i的初始值為1）,循環(huán)體為　　fac(n,i+1),在遞

90、歸過程中對n進行如下處理，n=2*(n + 1)。　　二叉樹法：創(chuàng)建一個大小為DAYS的二叉樹，其中根節(jié)點為第DAYS天的桃子數(shù)，其中根節(jié)點的左孩子為上一天的桃子數(shù)，右孩子只存一個固定數(shù)據(jù)，即數(shù)字1。對二叉樹作如下處理，對于一個根節(jié)點，其左孩子 = 2 *（根節(jié)點 + 右孩子）。　　經(jīng)過一系列的調(diào)試運行，該程序可以正確執(zhí)行，并能夠按要求完成任務(wù)。<

91、/p>　　收獲及體會　　通過設(shè)計猴子吃桃子這一程序，是我對C語言以及數(shù)據(jù)結(jié)構(gòu)有了更深的了解，通過編寫代碼，是我學(xué)習(xí)和掌握了C的理論知識和實踐程序設(shè)計的各種技能。　　在編寫代碼時也遇到了很多麻煩，例如在用遞歸編寫時，突然忘了遞歸在系統(tǒng)棧內(nèi)是如何運行的，于是我向同學(xué)和老師虛心請教。另外在用二叉

92、樹時，根節(jié)點T總是沒有正確定位，使其成為了野指針。　　總而言之，通過這一課程設(shè)計的學(xué)習(xí)，我對C程序有了更深的認(rèn)識。我深信，一個良好的程序員需要不斷去敲寫代碼，在實踐中總結(jié)經(jīng)驗，從而提高自己的綜合實踐能力，去為社會最初更大的奉獻。　　最后我要感謝我的同學(xué)以及汪文彬老師對我的幫助，我所取得的進步與他們的熱心幫助是離不開的。<p&

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

溫馨提示

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

猴子吃桃問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

猴子吃桃問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

免費下載