排序二叉树的应用数据结构课程设计报告

《排序二叉树的应用数据结构课程设计报告》由会员分享，可在线阅读，更多相关《排序二叉树的应用数据结构课程设计报告（15页珍藏版）》请在装配图网上搜索。

1、前言 数据结构是研究数据之间关系的一门科学，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。同一逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，程序中的数据采用“二叉树结构”。具体采用的是“二叉排序树”，并且使用“一维数组”作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自左而右、自上而下存储二叉排序树的结点元素；本课程设计实现了二叉排序树的创建、查找、插入、删除，中序遍历输出等基本操作，完美地实现了二叉排序树的大部分功能。 二叉树是树形结构的一个重要抽象数据类型。许多实际问题抽象出来的

2、数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序时计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。排序在我们日常生活中随处可见，经常会用到，因此，学习和研究各种排序方法是计算机工作者的重要课题之一。二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。顺应二叉树的这个

3、特点来进行对二叉树的排序操作，这个问题也就思路清晰，设计起来没那么困难了。二叉树有5种基本形态，二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。即空二叉树，只有一个结点的二叉树，右子树为空的二叉树，左子树为空的二叉树，左右子树均非空的二叉树。这些形态在后面的设计程序中均可以实现.正文1.1课程设计的教学目的及任务(1) 使学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。(2) 使学生初步掌握软件开发过程的问题分析、设计、编码、测试等基本方法和基本技能。(3) 使学生掌握使用各种计算机资料和有关参考资料，提高学生进

4、行程序设计的基本能力。1.2课程设计的主要内容(1) 问题分析和任务定义。根据题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？(2) 逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明）。(3) 物理设计。定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数

5、据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。(4)程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚(5) 程序调试与测试。利用VC+6.0调试程序，能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。(6) 结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 (7) 撰写课程设计报告2.1 课程设计的要求1、 根据所学知识并自主查找相关资料；

6、 2、进行算法设计与分析； 3、算法实现，测试并检验运行结果是否符合要求；4、书写课程设计说明书2.2问题描述排序在我们日常生活中随处可见，经常会用到，因此，学习和研究各种排序方法是计算机工作者的重要课题之一。二叉排序树是一种简单的树的排序方法，排序原理简单易懂，具有较高的易学性与理解性。2.3数据结构分析 2.3.1抽象数据类型定义（ADT） 抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型作用：抽象数据类型可以使我们更容易描述现实世界。例：用

7、线性表描述学生成绩表，用树或图描述遗传关系。 定义：一个数学模型以及定义在该模型上的一组操作。 关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。2.3.2抽象数据类型结构抽象数据类型可用三元组表示 （D,S,P）其中，D是数据对象，S是D上的关系集，P是D的基础操作集。用以下格式定义抽象数据类型：ADT 抽象数据类型名 数据对象： 数据关系： 基础操作：ADT 抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名 初始条件： 操作结果：基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除提供输

8、入值外，还将返回输入结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化情况和应返回的结果。若初始条件为空，则省略之。2.4二叉排序树设计分析2.4.1二叉树的全面定义 二叉树是n（n=0）个结点的有限集合，它或为空树（n=0），或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。二叉树是一个递归定义。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。对满二叉树的结点进行连续编号，一开始就规定编号从根结点起，自上而下，自左而右。2.4.2二叉树的存储结构1） 顺序存储结构

9、：二叉树可以采用顺序存贮结构，即用一维数组来存放二叉树的数据元素。它是按照满二叉树的结点层次编号层次来依次存放二叉树中的数据元素。2）链式存储结构：设计不同的结点结构可构成不同形式的链式存储结构。在本程序中，采用顺序存储结构，对二叉树进行插人、删除、查找、遍历等操作。2.4.3二叉树的建立已知一棵二叉树，共有n个结点，建立的方法如下：1） 照完全二叉树的编号方法，对该二叉树进行编号。2） 次输入一个结点的值x和该结点的编号k，动态申请一块空间来存放该结点，空间的地址为p。3） 把p值赋给adrk中。4） 如果k=1，转到5；否则，把p的值填入其父结点的指针域中。p的父结点地址为adrk/2，若

10、k为偶数，则做adrk/2-lc=p；若为奇数，则做adrk/2-rc=p。5） 重复24，直到全部顶点数据输入完为止。6） 遍历二叉树，即如何按某条搜索路径寻访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。一棵非空二叉树是由根结点（D）、左子树（L）和右子树（R）三个基本部分组成。要遍历这三个基本部分，可以有六种可能的顺序。若限定先左后右，则只有三种情况：先序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）。在本程序中，遍历二叉树函数的核心是以一个简单的case语句来实现的。7)二叉树的插入操作：这个操作首先生成一个新的结点结构，把数据存入新结点，然后搜索二叉树寻找插入结点

11、的位置，再把新结点连接到二叉树。把这个操作定义为一个函数，其函数名为instree。8) 二叉树中元素的查找：在许多情况下，我们需要在一棵已知的二叉树中查找某个元素，以确定树中是否存在这个元素。这种查找与链表数据结构中查找成员的情况极类似。查找函数名字定义为membertree。9) 从二叉树中删除一个成员：进行成员删除操作时，首先必须用递归函数遍历这棵树，找到这个元素。当找到这个元素之后，还要考虑以下四种不同的情况：删除一个终端结点；删除只有一个左孩子的结点；删除只有一个右孩子的结点；删除带有两个孩子的结点。删除函数名字定义为deltree。2.4.4二叉排序树的查找步骤：若根结点的关键字值

12、等于查找的关键字，成功。 否则，若小于根结点的关键字值，递归查左子树。 若大于根结点的关键字值，递归查右子树。 若子树为空，查找不成功。 平均情况分析（在成功查找两种的情况下） 在一般情况下，设 P（n，i）且它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 / 6 = 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 / 6 注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。

13、在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。 P(3) = （1+2+2）/ 3 = 5/3 P(2) = （1+2）/ 2 = 3/2 P（n,i）= 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) / n n -1 P（n）= P（n,i）/ n = 2(1+I/n)lnn i=0 因为 2(1+I/n)lnn1.38logn 故P(n)=O(logn)2.5设计思路2.5.1二叉排序树的操作实现目的主函数main() ：由简单的if语句外加自定义函数，支持程序选择，当运行时，可以执行有关二叉树的操作：建立二叉排序树，如插入

14、一个元素、删除一个元素、查找一个元素、等。此次设计仅此设立简单的几种操作，主要是让大家认识和真正理解二叉排序树。2.5.2二叉排序树的分块流程图2.5.3简单举例分析例如：给定一组序列8，,1,6,78,5,96,56,7利用二叉排序树的特点构造一个二叉排序树。具体做法如下（全例流程图解）： （a） （b） （c） （d） （e）先序：（先根遍历）中序：（中根遍历）后序：（后根遍历）以上（a）（e）过程就是二叉排序树的构建与排序的过程，简单说，就是在一组数中，取一个元素为根节点，以所选根节点为准，比根节点大的为左子树，比根节点小的做为右子树，另外，左右子树又可以做为根节点，同样原理对二叉树进行

15、排序，直到左右子树后再无其他可以排序的元素为止。在进行遍历操作的时候，除根节点便利是顺序变化，其余的都是先左子树，后右子树的顺序。2.5.4主要的树函数的说明及关键代码分析部分1）void prttree(treeptr tnode,int t)；/打印树。该函数在屏幕上打印出存放在树中的元素，如果是空树，则无输出。参数：tnode-指向根结点的指针； If Else 语句 While 语句 结构体定义类型（struct） Break 语句 t-打印方式：0：先序 1：中序 2：后序（用递归算法遍历二叉树）。 #include ： 库函数的头文件，stdlib.h里面定义了五种类型、一些宏和通

16、用工具函数。类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、 srand()、exit()等等。 struct btree *left; struct btree *right; BTR,*PBTR;这就利用了struct结构类型定义建立的二叉排序树。第一块：函数功能：实现非递归建立二叉树 函数原型：void creat_

17、btree(int *a,int size) 函数参数：int *a :保存二叉树节点的数组首地址 int size:节点数目函数返回值：void 优点：建立的二叉树按中序遍历后：是从小到大有序的可以是一种排序算法 第二块：函数功能：实现递归前序遍历二叉树 函数原型：void preorder(PBTR head) 函数参数：PBTR :保存二叉树根节点 函数返回值：void 第三块：函数功能：实现递归中序遍历二叉树 函数原型：void midorder(PBTR head) 函数参数：PBTR :保存二叉树根节点 函数返回值：void 第四块：函数功能：递归求二叉树的深度 函数原型：int

18、btreedepth(PBTR head) 函数参数：PBTR :保存二叉树根节点 函数返回值：int :二叉树的深度 第五块：程序测试部分2.6整体算法流程图解：开始建一个二叉排序树输入选择的操作（x1，x2，x3，x4）nX4|n0否n=0n=1n=2n=3n=4否或或或是是是是创建二叉排序树 遍历结点 插入结点求二叉排序树深度结束2.7算法的的测试分析与实现：2.7.1 测试结果分析及截图编好的C语言程序要经过编译（输入）、编译和连接后才能形成可执行的程序运用VC+6.0软件 测试程序结果（1） 经输入调试后：（2） 当程序段是任意输入的时候，运行结果：（3） 源程序段经调试后有以下结果

19、：对于原程序段，输入一组数，则对应的二叉排序树的先序、中序、后序以及该二叉排序树的深度。当查看并调试程序段发现没有错误时，就可以运行了，通过测试程序我们可以得到本次课程设计的预期结果。2.7.2二叉排序树的算法复杂度：平衡二叉排序树的时间复杂度为 O（logn），一般的在排序操作中，快排 ： 是 O(nlog n)的 堆排：速度不稳定 ，但 100W时 ，效率比快排高很多！ 二叉排序树在特定的情况下才使用，效率也很高 ，不过 ，程序复杂度比堆排、快排也高很多。2.7.3 二叉排序树的优缺点分析：优点：插入，删除操作的时间复杂度都是O(log(n)级的，即经过O(log(n)时间搜索到了需插入和

20、删除的节点的位置，后经过O(1)级的时间就可以直接插入和删除，比有序顺序表的插入和删除O(n)(查找O(log(n)，移动节点O(n)快，而和无序顺序表插入O(1)，删除O(n)比，因为是有序的，所以查找的速度要快很多。缺点：二叉排序树的构造不止和最终节点的顺序有关，还和节点插入和删除的顺序有关，在某些特殊的情况下，树的高度可以等于节点的数量，于是查找的时间复杂度就退化成了O(n)了,相当也无序顺序表的查找小结课本刚结束，我就开始了数据结构的课程设计。通过课程设计我进一步掌握了许多课本知识，同时还了解了许多课外的有关数据结构的知识，这对于我来说是受益匪浅的。在此次课程设计中，我不但运用了数据结

21、构的知识，还利用了所学的c语言和C+中各方面的知识。这对于我来说是一个突破。从中我也学习到了许多知识，它有助于增强我的自信心，帮助我提高编写程序的能力，也使我懂得：光靠课堂和书本是难以真正掌握数据结构的。衡量学习好坏的标准不是“懂不懂”，而是“敢不敢在知识的道路上迈出你的第一步”。所以，还是马克思说的那句话“理论与实践结合”，是我们能够更好掌握知识的最直接的手段。在这两周的课程设计时光里，对于我的第一次课程设计，我还是感觉有些摸不着头脑，刚开始着手的时候遇到了不少理论与实际上的难题，我照着老师给的模板一点一点写，很慢，最后通过查资料，与同学交流，终于写好了，但是不对，还是有很多地方要改就这样一

22、步一步做出来了，但是我从未因困难而退缩。没有辛苦的历程就无法感受甜美的收获，以上是我两周构想的二叉排序树的设计思路以及通过查阅书本，阅览资料得出的程序段，这个程序设计是学者正确掌握并快速学习二叉排序树的很好利器。通过学习，我们可以知道什么事二叉树，什么是二叉排序树，二叉排序树的算法思想，如何使用并正确使用二叉排序树。学会构建二叉排序树，学会最简单且实用的操作（如：二叉排序树的建立，遍历）并进一步具备更深一层次的插入，删除等操作以此来认识二叉排序树，认识数据结构这门课程。当然主要关键还是要学会一门思想，学会另外一种考虑问题的方法，进一步巩固语言和编程方面的应用技能。参考文献1严蔚敏,吴伟民.数据

23、结构.北京:清华大学出版社,2007.42Decoder编著.C/C+程序设计.北京：中国铁道出版社，20023 H.M.Deitel，Paul James Deitel著.薛万鹏译.C/C+程序设计大全.北京：机械工业出版社.19974Michael J.Young著.Mastering Visual C+6.0 Sybex Inc.19995杨进才，沈显君，刘蓉编.C/C+语言程序设计教程.清华大学出版社，20066 刘振安，刘燕君，孙忱C/C+语言课程设计.机械工业出版社，20077Al Strevens,Clayton Walnum著.林丽闽等译.标准C/C+宝典.北京：电子工业出版社

24、.20018Brian Overland著.董梁等译.C/C+语言命令译解（第二版）.北京：机械工业出版社，20029 李廉治,姜文清,郭福顺.数据结构M.大连.大连理工大学出版社,1989年.10 许卓群,张乃孝,杨冬青,唐世渭.数据结构M.北京.高等教育出版社,1988年.11 陈文博,严蔚敏.数据结构M.北京.机械工业出版社,1990,87-100.12 严蔚敏,吴伟民.数据结构M.第二版.北京.清华大学出版社,1992.附录二叉排序树的应用源代码：#include #include typedef struct btreeint data;struct btree *left;stru

25、ct btree *right; BTR,*PBTR;typedef struct BTRStPBTR ptree;struct BTRSt *link;Stack,*PStack; PBTR Bitree=NULL;void creat_btree(int *a,int size)int i;PBTR pre,pre2; for(i=0;idata=ai; Bitree-left=NULL; Bitree-right=NULL; continue; else pre = Bitree; while(1) if(aipre-data) if(pre-right=NULL) pre2=(PBTR

26、)malloc(sizeof(BTR); if(pre2=NULL) printf(Malloc fail/n); break; else pre2-data=ai;pre2-left=NULL; pre2-right=NULL; pre-right=pre2; break; else pre=pre-right; else if(pre-left=NULL) pre2=(PBTR)malloc(sizeof(BTR); if(pre2=NULL) printf(Malloc fail/n); break; else pre2-data=ai;pre2-left=NULL;pre2-right

27、=NULL;pre-left=pre2; break; else pre=pre-left; void midorder(PBTR p)if(p!=NULL) midorder(p-left); printf(%4d,p-data);midorder(p-right); int btreedepth(PBTR head)int h,hl,hr;PBTR p;p=head; if(p=NULL) h=0; else hl=btreedepth(p-left); hr=btreedepth(p-right); if(hlhr) h=hl+1; else h=hr+1; return h; /*主函数 main()作测试用*/#define N 12int main() int h;int aN=1,45,89,13,24,56,39,78,79,69,20,44; printf(非递归建立建立二叉树./n); creat_btree(a,N); printf(/n非递归建立建立二叉树后中序遍历就是按照由小到大排序); printf(/n中序遍历: ); midorder(Bitree); printf(/n二叉树的深度是：/n); printf(%4d/n,btreedepth(Bitree); getchar(); 15 / 15文档可自由编辑打印