数据结构课程设计说明书排序二叉树的建立及遍历的实现_第1页
数据结构课程设计说明书排序二叉树的建立及遍历的实现_第2页
数据结构课程设计说明书排序二叉树的建立及遍历的实现_第3页
数据结构课程设计说明书排序二叉树的建立及遍历的实现_第4页
数据结构课程设计说明书排序二叉树的建立及遍历的实现_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、课程设计任务书学生姓名: xxx 专业班级: 计算机0502 指导教师: xxx 工作单位:计算机科学与技术学院 题 目: 二叉排序树的建立及遍历的实现初始条件:理论:学习了数据结构课程,掌握了基本的数据结构和常用的算法;实践:计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)1、系统应具备的功能:(1)建立二叉排序树;(2)中序遍历二叉排序树并输出排序结果;2、数据结构设计;3、主要算法设计;4、编程及上机实现;5、撰写课程设计报告,包括:(1)设计题目;(2)摘要和关键字;(3)正文,包括引言、需求分析、数据结构设

2、计、算法设计、程序实现及测试、设计体会等;(4)结束语;(5)参考文献。时间安排: 2007年7月2日7日 (第18周)7月2日 查阅资料7月3日 系统设计,数据结构设计,算法设计7月4日-5日 编程并上机调试7月6日 撰写报告7月7日 验收程序,提交设计报告书。指导教师签名: 2007年7月2日系主任(或责任教师)签名: 2007年7月2日排序二叉树的建立及其遍历的实现摘要:我所设计的课题为排序二叉树的建立及其遍历的实现,它的主要功能是将输入的数据组合成排序二叉树,并进行,先序,中序和后序遍历。设计该课题采用了c语言程序设计,简洁而方便,它主要运用了建立函数,调用函数,建立递归函数等等方面来

3、进行设计。 关键字:排序二叉树,先序遍历,中序遍历,后序遍历0引言我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树;或是具有以下性质的二叉树:(1)若它的左子树不空,则作子树上所有的结点的值均小于它的根结点的值;(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)它的左,右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树,遍历及其输出结果。该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历,其关键是运用递归调用,这将极大的方便算法设计。1需求分析建立排序二叉树,主要是需要建立节点用来存储输入的数据,需要建

4、立函数用来创造排序二叉树,在函数内,需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中,需要建立递归函数进行遍历。该题目包含两方面的内容,一为排序二叉树的建立;二为排序二叉树的遍历,包括先序遍历,中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行,对遍历算法运用了递归语句来进行。2数据结构设计在写算法之前,应对其进行数据结构设计。本题目主要会用到建立结点,构造指针变量,插入结点函数和建立排序二叉树函数,求深度函数,以及先序遍历函数,中序遍历函数和后序遍历函数,还有一些常用的输入输出语句。对建立的函明确其作用,先理清函数内部的程序以及算法在将其应用到整个程序中,在建立

5、排序二叉树时,主要用到建立节点函数,建立树函数,深度函数,在遍历树是,用到先序遍历函数,中序遍历函数和后序遍历函数。结点结构体定义:typedef struct tnode /*建立节点*/ int data; struct tnode *lchild,*rchild;tnode; 3算法设计 在进行算法设计时,应将题目分为两部分,排序二叉树的建立,排序二叉树的遍历。3.1 定义结点typedef struct tnode /*建立节点*/ int data; struct tnode *lchild,*rchild;tnode;tnode *q; /*构造指针变量*/tnode *bt;3.

6、2 插入结点函数insert() void insert(tnode *b,tnode *s)/*排序二叉树中插入节点*/ if(*b)=null)(*b)=s; else if(s-data=(*b)-data) return; else if(s-datadata) insert(&(*b)-lchild),s); else if(s-data(*b)-data) insert(&(*b)-rchild),s); 3.3 创建树函数creat()void creat(tnode *b) /*建立排序二叉树*/ int x; tnode *s; b=null; /*初始化二叉数*/ scan

7、f(%d,&x); s=(tnode *)malloc(sizeof(tnode); q=s; /*将根结点指针地址赋值给q*/ while(x!=-1) /*反复读入节点,直至-1结束*/ s-data=x; s-lchild=null; s-rchild=null; insert(&bt,s); scanf(%d,&x); /*节点插入排序二叉树中*/ s=(tnode *)malloc(sizeof(tnode); n=n+1; 3.4 求排序二叉树的深度int deep(tnode *t) /*求排序二叉树的深度 */ int rd; int ld; if(!t) return 0;

8、else ld=deep(t-lchild); rd=deep(t-rchild); if(ldrd) return ld+1; else return rd+1; 3.5 建立先序遍历函数void preorder(tnode *p) /*先序遍历二叉树*/ if(p) printf(%4d,p-data) ; preorder(p-lchild); preorder(p-rchild); 3.6 中序遍历void inorder(tnode *p) /*中序遍历二叉树*/ if(p) inorder(p-lchild); printf(%4d,p-data) ; inorder(p-rch

9、ild); 3.7 后序遍历void postorder(tnode *p) /*后序遍历二叉树*/ if(p) postorder(p-lchild); postorder(p-rchild); printf(%4d,p-data) ; 这三个函数都应用了递归调用。最后,在主函数中分别调用所建立的函数,3.8 有关技术的讨论 在设计程序时,我发现用递归函数来写程序会简洁很多,能大大的缩小程序的代码,在求排序二叉树的深度,先序遍历排序二叉树,中序遍历排序二叉树以及和;后序遍历排序二叉树中,都用到了递归函数,大大简化了源程序的代码。在输入数据时,用 while函数会使数据能够不断的输入进来,解决

10、了无法从外部输入数据的问题,用的很巧妙。4程序实现 4.1 调入文件#include#include#include 4.2 主函数main()void main() /*主函数*/ printf(please insert the numbers(when you finish inserting numbers,please insert -1 to the end):n); creat(bt); /*构造排序二叉树*/ printf(the numbers of the nodes are:%4d,n); /*输出排序二叉树的结点数*/ printf(nthe depth of the

11、tree:); printf(%4d,deep(q); /*求二叉树的深度*/ printf(npreorder,the result is:); preorder(q); /*先序遍历排序二叉树*/ printf(ninorder,the result is:); inorder(q); /*中序遍历排序二叉树*/ printf(npostorder ,the result is:); postorder(q); /*后序遍历排序二叉树*/ getchar();然后输出结果。在设计中,最难的那一部分为求插入结点函数,在函数内部要进行比较,将较小的数赋给左子树,将将较大的数赋给右子树。在其他的

12、算法设计中,只要理清思路就不会太难。4.3 运行结果 显示程序:输入数据: 输出结果: 5.设计体会我感受最深的一点是以前用c编程,只是注重如何编写函数能够完成所需要的功能,似乎没有明确的思路该怎么设计,在哪一阶段该设计什么。经过这一次设计,我学会了怎样设计程序,怎样控制整个程序,它使我学会了怎样设计程序,设计算法,设计课题。通过这个星期的课程设计,我的收获还是不少。我的c语言水平有了比较大的提高,其中c语言关于指针,链表的操作理解的比以前深刻不少。另外是数据结构方面的提高,对存储结构,及各种查找排序方面也有不少的提高。虽然我做的程序里还有写问题,做的不够深入,但独立完成一个比较大一点的程序的

13、经历也是很宝贵的。通过这次课程设计我觉得我们学习数据结构的方法存在一定的弊端数据结构的效果直接影响到我们对其它专业课的学习和今后业务的成长。我觉得我们对于数据结构的学习不仅包括理论部分的学习,还要让我们勤动手,多实践。整个实验过程要结合教学进度与我们的实际情况,制定实验的内容。实验分两部分,一是验证性的,主要结合课堂理论教学内容展开,学生可以对在课堂上学到的基本算法进行验证;二是设计性实验,坚持“学以致用”的原则,目的是让学生充分利用所学的理论知识进行相对复杂的应用设计,以进一步提高综合能力和创新实践能力。通过这次设计,我感慨颇多,的确,从选题到定稿,从理论到实践,在一个星期的日子里,可以说得是苦多于甜,但是可以学到很多很多的的东西,同时不仅可以巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才能真正为社会服务,从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题,可以说得是困难重重,这毕竟第一次做的,难免会遇到过各种各样的问题,同时在设计的过程中发现了自己的不足之处,对以前所学过的知识理解得不够深刻,掌握得不够牢固,通过这次课程设计之后,一定把以前所学过的知识重新温故。6.结

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论