树的应用 课程设计报告

1、课 程 设 计课程设计名称： 算法分析与综合课程设计专 业 班 级 ： 计 科 0604 学 生 姓 名 ： 杨 恒 学 号 ： 20064140405 指 导 教 师 ： 白 浩 课程设计时间：2008.06.22-2008.06.27 计算机科学与技术专业课程设计任务书学生姓名杨恒专业班级计科0604学号20064140405题 目树的应用课题性质其它课题来源自拟课题指导教师白 浩同组姓名无主要内容 实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。任务要求 1.实现对树的建立。2.实现几种树的遍历算法 参考文献 1.c语言程序设

2、计（第三版） 清华大学出版社 谭浩强 著 2数据结构（c语言版） 清华大学出版社 严蔚敏 吴伟民 编著审查意见指导教师签字：教研室主任签字： 2008年 5 月 8 日 一、需求分析1首先选择一种结点实现树结点的存储。2首先建立树，在用户输入各结点信息时，应提示用户输入结点的父亲，孩子，和兄弟的信息，即要让用户明确选择各结点之间的相互联系。3实现树的遍历算法。在该实验中，实现了树的先根的递归和非递归算法，后根的递归算法以及按层次序的非递归算法。4用户界面的设计应满足用户的选择，可以选择不同的遍历算法显示遍历结果。二、概要设计 1用孩子兄弟表示法作为树结点的存储结构typedef struct

3、csnode char data; struct csnode *firstchild; struct csnode *nextbiling; 2一些全局变量的声明 struct csnode * root;struct btree * x;char flag;3树建立的算法描述 建立根结点： void create_root() root = (struct csnode*)malloc(sizeof(struct csnode); printf(请输入根结点信息:); scanf(%c,&root-data);递归建树： voidcreate(structcsnode*temp) /构造树

4、 递归建树 if(temp!=null) /输入长子信息 printf( 是否有孩子?(y/n)n); flag=getchar(); if(flag = y | flag = y) t =(struct csnode*)malloc(sizeof(struct csnode); printf( 请输入长子信息:n ); t-data=getchar(); temp - firstchild = t;/指向长子 else temp - firstchild = null; /输入兄弟信息 printf(是否有兄弟?(y/n)n ); if(flag = y | flag = y) m = (s

5、truct csnode*)malloc(sizeof(struct csnode); printf( 请输入兄弟信息:n); m-data=getchar(); temp - nextbiling = m; /指向兄弟 else temp - nextbiling = null;/递归建立结点 create(temp - firstchild); create(temp - nextbiling); 4树的先根和后根的递归算法描述/先序遍历的递归算法void recur_pre_order(struct csnode *root)if(root)printf(%c,root-data);re

6、cur_pre_order(root-firstchild);recur_pre_order(root-nextbiling);/后序遍历的递归算法 void recur_post_order(struct csnode *root)if(root!=null) recur_post_order(root-firstchild); recur_post_order(root-nextbiling); printf(%c,root-data); 5树的先根的非递归算法预备工作之栈的设计struct csnode*base100=null;struct csnode*top=base;struct

7、 csnode* pop(struct csnode*top)/ 如果栈空，返回 error ；如果栈不空，删除栈顶元素，用 e 返回其值，并返回 ok 。push(struct csnode*top,struct csnode*p)/将元素 p插入到栈 s 中，成为新的栈顶元素 6.树的先根非递归算法void non_recur_pre_order(struct csnode *t)struct csnode *p=t; while (p!=null|!stackempty(top) while (p!=null) /遍历左子树 printf(%c,p-data); push(top,p);

8、 p=p-firstchild; /endwhile if(!stackempty(top) /通过下一次循环中的内嵌while实现右子树遍历 p=pop(top); p=p-nextbiling; /endif 7树的按层次序的非递归算法 /层次遍历算法 void levelorder(struct csnode *t) struct csnode *p; struct csnode *qumaxsize; int front,rear; front=rear=-1; rear+; qurear=t; while(front!=rear) front=(front+1)%maxsize; p

9、=qufront; printf(%c ,p-data); if(p-firstchild!=null) rear=(rear+1)%maxsize; qurear=p-firstchild; if(p-nextbiling!=null) rear=(rear+1)%maxsize; qurear=p-nextbiling; 三、 运行环境1硬件环境pc2软件环境止上下windows xpmicrosoft visual c+6.0四、开发工具和编程语言1开发工具microsoft visual studio c+ 6.02编程语言c语言五、详细设计1树建立的算法实现 void create_

10、root() root = (struct csnode*)malloc(sizeof(struct csnode); printf(请输入根结点信息:); scanf(%c,&root-data); x = (struct btree*)malloc(sizeof(struct btree); x - data = root - data;voidcreate(struct csnode *temp) /构造树 递归建树 struct csnode *t=null; struct csnode *m=null; if(temp!=null) /输入长子信息 printf(%c, temp -

11、 data );flag=getchar();printf( 是否有孩子?(y/n)n); flag=getchar();if(flag = y | flag = y) flag=getchar(); t =(struct csnode*)malloc(sizeof(struct csnode); printf( 请输入长子信息:n ); t-data=getchar(); temp - firstchild = t; else temp - firstchild = null; /输入兄弟信息 printf(%c, temp - data );flag=getchar();printf(是否

12、有兄弟?(y/n)n ); flag=getchar(); if(flag = y | flag = y) flag=getchar(); m = (struct csnode*)malloc(sizeof(struct csnode); printf( 请输入兄弟信息:n); m-data=getchar(); temp - nextbiling = m; else temp - nextbiling = null;/递归建立结点 create(temp - firstchild); create(temp - nextbiling); 2树的先根和后根的递归算法描述 与概要设计中的算法基本

13、一致 3树的先根的非递归算法预备工作之栈的实现struct csnode* pop(struct csnode*top) struct csnode*t;if (top=base)return null;elset=*top;*top=null;top-;return t; push(struct csnode*top,struct csnode*p)top+;*top=p;int stackempty(struct csnode*top) if(top=base) return 1; else printf (fdhsd);return 0; 4树的先根非递归算法，树的按层次序的非递归算法

14、具体代码与算法描述一致 5主函数的设计main() int cord; do printf(n 主菜单 n); printf( 1 建立树 n); printf( 2 先根递归遍历 n); printf( 3 先根非递归遍历 n); printf( 4 后根递归遍历 n); printf( 5 按层次非递归遍历 n); printf( 6结束程序运行 n); printf(-n); printf(请输入您的选择(1，2，3，4，5，6) ); scanf(%d,&cord); getchar(); switch (cord) case 1: /构建树 create_root(); create

15、(root); printf(树构建成功); printf(n); break; case 2: /先序遍历的递归算法 recur_pre_order(root); printf(n); break; case 3: /先序遍历的非递归算法 non_recur_pre_order(root); break;case 4: /后序遍历的递归算法recur_post_order(root);printf(n); break; case 5: /按层次遍历的非递归算法 levelorder(root); break; case 6:printf( 欢迎使用 n ); break;while(cord

16、6);六、调试分析 1在设实现树建立算法时遇到了一些问题，当输入根结点信息后，选择输入其长子信息时总不能正确输入。调试过后发现问题是没有设计当接受输入结点信息后结束用的回车键的语句，从而导致判断是否有长子时，总是判断为无。同样的问题，在输入兄弟信息时遇到。之后才发现虽然只是小小的几个getchar()语句在考虑不周时也是不容易发现错误的。 2在设计先根和后根的递归算法时，因为程序简单一次便通过 3在设计栈的相关操作总是出现问题，后来发现原因是。因为对栈的实现我采用的是指针数组，所以指向数组的应是指向指针的指针，而我在传递参数却只用了一重指针导致错误的出现。 4在设计树的先根和按层次的非递归算法时，因为算法接近源码，所以当栈的操作设计成功后，很快就能运行，只是花了相当一段时间理解这两个算法。八、心得体会课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.平常我们只学习课本上的知识，做一些比较小的程序，起不到运用到实际