BST实现动态查找表.doc

《BST实现动态查找表.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、HUNANUNIVERSITY课程实习报告题目：BST实现动态查找表学生姓名学生学号专业班级计算机科学与技术指导老师李晓鸿完成日期一、需求分析1、程序任务：本程序是利用二叉查找树（BST）来实现；二叉树使用链式结构（二叉链表）实现；本程序要实现BST的构建，查找两个功能。2、输入形式：整数n//BST的节点个数n//n个数据数据x//查找此数据3、输出形式：查找成功整数m（次数）//返回成功和查找时比较的次数或：查找不成功整数m（次数）//返回不成功和查找时比较的次数4、测试数据：输入：8//BST的节点个数34,76,45,18,26,54,92,65//8个数据输入：45//查找45输出

2、：查找成功3//返回成功和查找时比较的次数输入：34//查找34输出：查找成功1//返回成功和查找时比较的次数输入：100//查找100输出：查找不成功3//返回成功和查找时比较的次数二、概要设计抽象数据类型以正整数储存用户输入节点个数，浮点小数存储用户输入的数据。要实现动态查找表，二叉查找树BST的效率很高，因此用BST实现，二叉查找树定义如下：ADTBST{数据对象：D＝{具有相同特性的一组数据元素}数据关系：若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集Tl、Tr，其中每一棵子集本身又是一棵符

3、合本定义的树，称为根root的子树。(3)对于任意结点，设其值为K，则该结点左子树中任意一个结点的值都小于K，右子树中任意一个结点的值都大于等于K。基本操作：InitBST(BST&)//初始化二叉树InitBSTNode(BSTNode*)//初始化结点clearBST(BSTNode*)//销毁二叉树结构insert(BST&,Elem&)//插入结点find(BST&,Elem&,intcount)//查找结点,记录查找次数}ADTBST算法的基本思想根据题目要求，用二叉查找树实现动态查找表。首先将输入的元素插入BST中。判断输入要查找的元素是否在BST中，递归比较要查找的元素与当前元

4、素的值的大小，若小于当前值，则查找其左子树；若大于，则查找其右子树。设置一个计数器，每查找一次则加一。如果找到，则输出位置和查找次数。程序的流程程序由三个模块组成：（1）输入模块：输入结点数目初始数据，构建二叉查找树（2）查找模块：判断需要查找的值是否在该BST中（3）输出模块：输出查找成功与否，并输出比较的次数三、详细设计算法的具体步骤插入元素e时，先判断该二叉树是否为空，若为空，将e作为该二叉树的根节点。否则，从根节点开始，比较e与节点n的大小。如果e的值更小，判断n的左子树是否为空，若为空，将e作为节点n的左孩子并返回e，否则比较e与n左孩子的值，依此循环下去；如果e的值更大，判断n的

5、右子树是否为空，若为空，将e作为节点n的右孩子并返回e，否则比较e与n右孩子的值，依此循环下去。查找元素时，从根节点开始，比较e与节点x的大小，若相等，返回true；如果e比节点x的值小，判断x的左子树是否为空，若为空，返回false，不为空则比较e与x左孩子的值，依次循环下去；如果e比节点x的值大，判断x的右子树是否为空，若为空，返回false，不为空则比较e与x右孩子的值，依次循环下去。物理数据类型动态查找表的数据为小数或整数，用float类型保存。typedeffloatElemType;为了提高空间利用率，用链表来实现BST，由于BST是二叉树，每个节点有左右两个节点，所以用二叉链表

6、实现。typedefstructBSTNode{ElemTypedata;structBSTNode*lchild,*rchild;}BSTNode;typedefstructBST{BSTnode*root;}BST;基本操作：boolInitBST(BST&b)//初始化二叉树{b.root=NULL;returnture;}boolInitBSTNode(BSTNode*&n)//初始化节点{n=(BSTNode*)malloc(sizeof(BSTnode));(*n).lchild=NULL;(*n).rchild=NULL;returnture;}boolclearBST(BST

7、Node*&n)//销毁BST{if(n)returnfalse;if((*n).lchild)clearBST((*n).lchild);if((*N).rchild)clearBST((*n).rchild);free(n);returnture;}boolinsert(BST&b,ElemTypee)//把结点插入BST{BSTNode*n,*m;InitBSTNode(n);(*n).data=e;i