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

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

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

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

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

文檔簡(jiǎn)介

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

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

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

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

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

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

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

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

9、b>　　}stack;　　//初始化一個(gè)棧　　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;　　}　　//二叉樹(shù)<p&

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

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

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

15、/b>　　T->data=1; //根節(jié)點(diǎn)內(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è)計(jì)　　#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 //棧的容量,實(shí)際只用了一個(gè)　　#define TRUE 1　　#define ERROR 0　　void peach_3(int n,

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

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

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

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

33、%d",&n);　　}　　return n;　　}　　//采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(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 個(gè)桃子 *\n",peach[0]);　　p

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

38、b>　　int *top;　　int *base;　　}stack;　　//初始化一個(gè)棧　　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ù)進(jìn)棧　　void Push(stack *s,int num)　　{　　*s->top++ = 2*(num

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

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

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

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

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

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

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

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

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

51、　　}　　//二叉樹(shù)　　typedef struct TNode　　{　　int data;<

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

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é)點(diǎn)內(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的地址　　}　　//對(duì)二叉樹(shù)進(jìn)行賦值計(jì)算　　void calculate(tree *T)　　{<p&g

58、t;　　int i=0; 　　tree *T1,*T2,*T3; //T1,T3分別為T(mén)2的左右孩子　　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;　　}　　}　　//二叉樹(shù)遍歷最左下角的孩子節(jié)點(diǎn)　　void peach_4(tree *T)　　{　　cal

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

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

63、a);　　printf("* * * * * * * * * * * * * * * * * * * * *\n");　　}　　六、算法的測(cè)試　　//主函數(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)實(shí)現(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 個(gè)桃子 *\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ù)進(jìn)棧　　i++;　　while(i < DAYS)　　{　　Pop(s,num);　　Push

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

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

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

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

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

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

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

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

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

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

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

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

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

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

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

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

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載