数据结构课程设计——猴子吃桃问题及二叉树

1、天津职业技术师范大学课 程 设 计 任 务 书 理 学院 数学0902 班 学生 张翔（28） 课程设计课题：1 猴子吃桃问题： 有一群猴子摘了一堆桃子，它们每天都吃当前桃子的一半再多吃一个，到了第10天就剩下一个桃子，用多种方法实现求出原来这群猴子共摘了多少桃子。要求：1）采用数组数据结构实现上述求解； 2）采用链式数据结构。2.实现二叉排序树：要求：用顺序表和二叉链表作为数据结构1） 以回车（n）为输入结束标志，输入数列L，生成一棵二叉排序树T；2） 对二叉排序树进行中序遍历，输出结果；3） 输入元素m,查找二叉排序树T，若存在包含m的结点，则删除该结点，并做中序遍历。否则显示信息“无m这

2、个结点”。 一、课程设计工作日自 2012 年 2 月 21 日至 2012 年 3 月 2 日二、同组学生： 无 三、课程设计任务要求（包括课题来源、类型、目的和意义、基本要求、完成时间、主要参考资料等）：课题来源：教师提供课题类型：设计课题的目的和意义：通过课程设计了解c语言中结构体的使用以及利用数据结构设计大型程序主要参考资料：黄刘生.数据结构.北京：经济科学出版社，2005黄杨铭.数据结构.北京：科学出版社，2001严蔚敏. 数据结构（C语言版） M. 北京：清华大学出版社. 2008.苏光奎.数据结构导学.北京：清华大学出版社，2002百度文库指导教师签字： 教研室主任签字： 天津职

3、业技术师范大学课 程 设 计 评 审 表 理 学院 数学0902 班 学生 张翔（28） 设计任务完成情况及指导教师评语答辩情况评定成绩成绩： 指导教师签字： 日期： 教研室主任： 院长签字： 日期： 日期： 问题一、猴子吃桃问题 具体程序及运行结果如下：#include<stdio.h> #include<stdlib.h>#include <malloc.h>#define NULL 0#define Day 9/*函数声明*void creat();void print();void array();void End();void display();

4、void fanhui();void display() system("cls");printf("n * 猴子吃桃子的问题 *n");printf("n * 1,用数组数据结构的方法实现。 *n");printf("n * 2,用链数据结构的方法实现。 *n");printf("n * 3,退出程序。 *n");printf("n *n");printf("n 请输入您的选择(1,2,3)：");/*数组*void array() int ADay+1

5、;/定义数组 int i; ADay=1;/第十天的桃子数 for(i=Day;i>=1;i-) Ai-1=(Ai+1)*2; /*第一天的桃子数是第2天桃子数加1后的2倍*/ printf("the total of peaches are %dn",A0); printf("桃子变化为:n"); for(i=0;i<= Day;i+) printf("第%d天的桃子数为：%dn",i+1,Ai);/*链表算法*typedef struct linknode int data; struct linknode *next

6、;/链表指针node;node *head; /头结点void creat()/创建链表 node *p,*s; int peaches=1;/第十天时只剩下一个桃子int day=10;printf("输入天数");scanf("%d",&day);printf("输入第%d天还剩几个桃子：",day);scanf("%d",&peaches);head=(node*)malloc(sizeof(node);p=head;while(day>0)s=(node*)malloc(sizeof(

7、node);/分配存属空间s->data=peaches;/用来存放结点数据p->next=s; /把结点插入链表中p=s;peaches=(peaches+1)*2;/第一天的桃子数是第二天桃子数加后的2倍；day-;p->next=NULL;p=head;head=head->next;/使头指针指向头结点free(p); /释放指针Pvoid print()/输出从这十天每天的桃子数 node *p;p=head;int day=10;printf("请确定您输入天数：");scanf("%d",&day);whil

8、e(p&&day>0) printf("第%d天的桃子数:%d个n",day,p->data);p=p->next;day-;void End()printf("nnnn"); printf(" 1 谢谢观看 1n");printf(" n 0772900227n"); printf(" n 张翔nnnn");/*主函数*void main() flg:display();int a;int b; scanf("%d",&a);if(

9、a<1|a>4) /system("cls"); goto flg;else switch(a) case 1: system("cls"); printf("n *使用数组的方法:*nnn"); array(); printf("nnn*按<0>键返回主菜单!按任意数字键退出程序!*n"); scanf("%d",&b); if(b=0) goto flg; else system("cls"); End(); break; case 2:

10、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<stdio.h> #

11、include<stdlib.h>#include <malloc.h>#define NULL 0#define Day 9/*函数声明*void creat();void print();void array();int digui();void End();void display();void fanhui();void display() system("cls");printf("n * 猴子吃桃子的问题 *n");printf("n * 1,用数组数据结构的方法实现。 *n");printf(&q

12、uot;n * 2,用链数据结构的方法实现。 *n");printf("n * 3,退出程序。 *n");printf("n *n");printf("n 请输入您的选择(1,2,3)：");/*数组*void array() int ADay+1;/定义数组 int i; ADay=1;/第十天的桃子数 for(i=Day;i>=1;i-) Ai-1=(Ai+1)*2; /*第一天的桃子数是第2天桃子数加1后的2倍*/ printf("the total of peaches are %dn",A

13、0); printf("桃子变化为:n"); for(i=0;i<= Day;i+) printf("第%d天的桃子数为：%dn",i+1,Ai);/*链表算法*typedef struct linknode int data; struct linknode *next;/链表指针node;node *head; /头结点void creat()/创建链表 node *p,*s; int peaches=1;/第十天时只剩下一个桃子int day=10;printf("输入天数");scanf("%d",&

14、amp;day);printf("输入第%d天还剩几个桃子：",day);scanf("%d",&peaches);head=(node*)malloc(sizeof(node);p=head;while(day>0)s=(node*)malloc(sizeof(node);/分配存属空间s->data=peaches;/用来存放结点数据p->next=s; /把结点插入链表中p=s;peaches=(peaches+1)*2;/第一天的桃子数是第二天桃子数加后的2倍；day-;p->next=NULL;p=head;he

15、ad=head->next;/使头指针指向头结点free(p); /释放指针Pvoid print()/输出从这十天每天的桃子数 node *p;p=head;int day=10;printf("请确定您输入天数：");scanf("%d",&day);while(p&&day>0) printf("第%d天的桃子数:%d个n",day,p->data);p=p->next;day-;void End()printf("nnnn"); printf(" 1

16、 谢谢观看 1n");printf(" n 0772900227n"); printf(" n 张翔nnnn");/*主函数*void main() flg:display();int a;int b; scanf("%d",&a);if(a<1|a>4) /system("cls"); goto flg;else switch(a) case 1: system("cls"); printf("n *使用数组的方法:*nnn"); array(

17、); printf("nnn*按<0>键返回主菜单!按任意数字键退出程序!*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(&

18、quot;%d",&b); if(b=0) goto flg; else system("cls"); End(); break; case 3: system("cls"); End(); exit(0); 按1：链式结构：按2：输入10天剩余一个桃子，运行的结果为：2.实现二叉排序树的程序如下：#include <iostream>using namespace std;class nodepublic: node(int i):data(i),left(NULL),right(NULL) void inorder(no

19、de *&root) /中序遍历，符合升序输出 if(root!=NULL) inorder(root->left); cout<<root->data<<' ' inorder(root->right); void insert(node *&ptr,int item) /在查找树中插入元素 if(ptr=NULL) ptr=new node(item); else if(item<ptr->data) insert(ptr->left,item); else insert(ptr->right

20、,item); node *find(node *&ptr,int item) /在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 if(ptr=NULL) return NULL; if(ptr->data=item) return ptr; else if(item<ptr->data) find(ptr->left,item); else find(ptr->right,item); node *&findy(node *&ptr,int item) /在查找树中查找肯定存在的元素,并返回其引用 if(ptr->da

21、ta=item) return ptr; else if(item<ptr->data) findy(ptr->left,item); else findy(ptr->right,item); node* rl()return left; node* rr()return right; void dele(node *&ptr) /删除值为item所在结点 if(ptr->rl()=NULL&&ptr->rr()=NULL) ptr=NULL; else if(ptr->rr()=NULL) ptr=ptr->rl(); else ptr=ptr->rr(); private: int