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

1、課 程 設(shè) 計 任 務(wù) 書 理 學(xué)院 數(shù)學(xué)0902 班 學(xué)生 （28） 課程設(shè)計課題：1 猴子吃桃問題： 有一群猴子摘了一堆桃子，它們每天都吃當(dāng)前桃子的一半再多吃一個，到了第10天就剩下一個桃子，用多種方法實現(xiàn)求出原來這群猴子共摘了多少桃子。要求：1）采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解； 2）采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)。2.實現(xiàn)二叉排序樹：要求：用順序表和二叉鏈表作為數(shù)據(jù)結(jié)構(gòu)1） 以回車（n）為輸入結(jié)束標(biāo)志，輸入數(shù)列l(wèi)，生成一棵二叉排序樹t；2） 對二叉排序樹進(jìn)行中序遍歷，輸出結(jié)果；3） 輸入元素m,查找二叉排序樹t，若存在包含m的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)，并做中序遍歷。否則顯示信息“無m這個結(jié)點(diǎn)”。 一、課程設(shè)計

2、工作日自 2012 年 2 月 21 日至 2012 年 3 月 2 日二、同組學(xué)生： 無 三、課程設(shè)計任務(wù)要求（包括課題來源、類型、目的和意義、基本要求、完成時間、主要參考資料等）：課題來源：教師提供課題類型：設(shè)計課題的目的和意義：通過課程設(shè)計了解c語言中結(jié)構(gòu)體的使用以及利用數(shù)據(jù)結(jié)構(gòu)設(shè)計大型程序主要參考資料：黃劉生.數(shù)據(jù)結(jié)構(gòu).北京：經(jīng)濟(jì)科學(xué)出版社，2005黃楊銘.數(shù)據(jù)結(jié)構(gòu).北京：科學(xué)出版社，2001嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)（c語言版） m. 北京：清華大學(xué)出版社. 2008.蘇光奎.數(shù)據(jù)結(jié)構(gòu)導(dǎo)學(xué).北京：清華大學(xué)出版社，2002百度文庫指導(dǎo)教師簽字： 教研室主任簽字： 課 程 設(shè) 計 評 審 表 理

3、 學(xué)院 數(shù)學(xué)0902 班 學(xué)生 （28） 設(shè)計任務(wù)完成情況及指導(dǎo)教師評語答辯情況評定成績成績： 指導(dǎo)教師簽字： 日期： 教研室主任： 院長簽字： 日期： 日期： 問題一、猴子吃桃問題 具體程序及運(yùn)行結(jié)果如下：#include #include#include #define null 0#define day 9/*函數(shù)聲明*void creat();void print();void array();void end();void display();void fanhui();void display() system(cls);printf(n * 猴子吃桃子的問題 *n);printf

4、(n * 1,用數(shù)組數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。 *n);printf(n * 2,用鏈數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。 *n);printf(n * 3,退出程序。 *n);printf(n *n);printf(n 請輸入您的選擇(1,2,3)：);/*數(shù)組*void array() int aday+1;/定義數(shù)組 int i; aday=1;/第十天的桃子數(shù) for(i=day;i=1;i-) ai-1=(ai+1)*2; /*第一天的桃子數(shù)是第2天桃子數(shù)加1后的2倍*/ printf(the total of peaches are %dn,a0); printf(桃子變化為:n); for(i=0;i

5、0)s=(node*)malloc(sizeof(node);/分配存屬空間s-data=peaches;/用來存放結(jié)點(diǎn)數(shù)據(jù)p-next=s; /把結(jié)點(diǎn)插入鏈表中p=s;peaches=(peaches+1)*2;/第一天的桃子數(shù)是第二天桃子數(shù)加后的2倍；day-;p-next=null;p=head;head=head-next;/使頭指針指向頭結(jié)點(diǎn)free(p); /釋放指針pvoid print()/輸出從這十天每天的桃子數(shù) node *p;p=head;int day=10;printf(請確定您輸入天數(shù)：);scanf(%d,&day);while(p&day0) printf(第%

6、d天的桃子數(shù):%d個n,day,p-data);p=p-next;day-;void end()printf(nnnn); printf( 1 謝謝觀看 1n);printf( n 0772900227n); printf( n nnnn);/*主函數(shù)*void main() flg:display();int a;int b; scanf(%d,&a);if(a4) /system(cls); goto flg;else switch(a) case 1: system(cls); printf(n *使用數(shù)組的方法:*nnn); array(); printf(nnn*按鍵返回主菜單!按任

7、意數(shù)字鍵退出程序!*n); scanf(%d,&b); if(b=0) goto flg; else system(cls); end(); break; case 2: system(cls); printf(n *使用鏈表的方法：*nnn); creat(); print(); printf(nnn*任意鍵返回主菜單!按0退出程序!*n); scanf(%d,&b); if(b=0) goto flg; else system(cls); end(); break; case 3: system(cls); end(); exit(0); #include #include#include

8、 #define null 0#define day 9/*函數(shù)聲明*void creat();void print();void array();int digui();void end();void display();void fanhui();void display() system(cls);printf(n * 猴子吃桃子的問題 *n);printf(n * 1,用數(shù)組數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。 *n);printf(n * 2,用鏈數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。 *n);printf(n * 3,退出程序。 *n);printf(n *n);printf(n 請輸入您的選擇(1,2,3)：);

9、/*數(shù)組*void array() int aday+1;/定義數(shù)組 int i; aday=1;/第十天的桃子數(shù) for(i=day;i=1;i-) ai-1=(ai+1)*2; /*第一天的桃子數(shù)是第2天桃子數(shù)加1后的2倍*/ printf(the total of peaches are %dn,a0); printf(桃子變化為:n); for(i=0;i0)s=(node*)malloc(sizeof(node);/分配存屬空間s-data=peaches;/用來存放結(jié)點(diǎn)數(shù)據(jù)p-next=s; /把結(jié)點(diǎn)插入鏈表中p=s;peaches=(peaches+1)*2;/第一天的桃子數(shù)是第

10、二天桃子數(shù)加后的2倍；day-;p-next=null;p=head;head=head-next;/使頭指針指向頭結(jié)點(diǎn)free(p); /釋放指針pvoid print()/輸出從這十天每天的桃子數(shù) node *p;p=head;int day=10;printf(請確定您輸入天數(shù)：);scanf(%d,&day);while(p&day0) printf(第%d天的桃子數(shù):%d個n,day,p-data);p=p-next;day-;void end()printf(nnnn); printf( 1 謝謝觀看 1n);printf( n 0772900227n); printf( n nn

11、nn);/*主函數(shù)*void main() flg:display();int a;int b; scanf(%d,&a);if(a4) /system(cls); goto flg;else switch(a) case 1: system(cls); printf(n *使用數(shù)組的方法:*nnn); array(); printf(nnn*按鍵返回主菜單!按任意數(shù)字鍵退出程序!*n); scanf(%d,&b); if(b=0) goto flg; else system(cls); end(); break; case 2: system(cls); printf(n *使用鏈表的方法：

12、*nnn); creat(); print(); printf(nnn*任意鍵返回主菜單!按0退出程序!*n); scanf(%d,&b); if(b=0) goto flg; else system(cls); end(); break; case 3: system(cls); end(); exit(0); 按1：鏈?zhǔn)浇Y(jié)構(gòu)：按2：輸入10天剩余一個桃子，運(yùn)行的結(jié)果為：2.實現(xiàn)二叉排序樹的程序如下：#include using namespace std;class nodepublic: node(int i):data(i),left(null),right(null) void in

13、order(node *&root) /中序遍歷，符合升序輸出 if(root!=null) inorder(root-left); coutdataright); void insert(node *&ptr,int item) /在查找樹中插入元素 if(ptr=null) ptr=new node(item); else if(itemdata) insert(ptr-left,item); else insert(ptr-right,item); node *find(node *&ptr,int item) /在查找樹中查找元素,找到返回所在結(jié)點(diǎn)指針，找不到返回空指針。 if(ptr

14、=null) return null; if(ptr-data=item) return ptr; else if(itemdata) find(ptr-left,item); else find(ptr-right,item); node *&findy(node *&ptr,int item) /在查找樹中查找肯定存在的元素,并返回其引用 if(ptr-data=item) return ptr; else if(itemdata) findy(ptr-left,item); else findy(ptr-right,item); node* rl()return left; node* rr()return right; void dele(node *&ptr) /刪除值為item所在結(jié)點(diǎn) if(ptr-rl()=null&ptr-rr()=null) ptr=null; else if(ptr-rr()=null) ptr=ptr-rl(); else ptr=ptr-rr(); private: int data; node *left; /左孩子結(jié)點(diǎn) node *right; /右孩子結(jié)點(diǎn);int main() int t,i=0,j; coutt; cout輸入tj; node *x=new node(j