数据结构实验三：BST动态查找表

《数据结构实验三：BST动态查找表》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HUNANUNIVERSITYBST实现动态查找表课程实习报告题学生姓名:学生学号:专业班级：指导老师：李晓鸿完成日期：20151121一、需求分析1、程序任务：本程序是利用二义查找树（BST）來实现；二义树使用链式结构（二义链表）实现,本程序要实现BST的构建，查找BST树中元索中两个功能。2、输入形式：输入整数n//BST的节点个数no输入n个数，其取值范围为（（），216）,对非法输入做处理。3、输出形式：若查找成功整数m（次数）//返回成功和查找时比较的次数若杳找不成功幣数m（次数）//返回不成功和杳找时比较的次数若输入错误“输入了无效的元素”4、测试数据：①•正

2、常的输入10//BST的节点个数501327865100594318//10个数据输入：50输出：查找成功，查找次数1输入:1输出：查找成功，查找次数6输入：3输出：查找成功，查找次数4输入：100输出：査找成功，查找次数5输入:19输出：杏找失败②.只有左子树的情况10〃BST的节点个数10011235439554827893//I0个数据输入：1输出：查找成功，查找次数1输入：12输岀：杏找成功，杏找次数6输入：35查找成功，查找次数4输入：95输出：查找成功，查找次数5输入:19输出：查找失败③.错误的节点数输入-2//BST的节点个数输出：错谋的结点数输入④.错误

3、的结点值的输入(字母)10//BST的结点个数lq23456789〃10个数据输出：无效的结点输入③.错误的结点值的输入(负数)10//BST的结点个数1-223456789〃10个数据输出：无效的结点输入二叉树中任意结点的值大于左节点的值，小于右节点的值，满足BST树的性质，所以用BST树來实现。二.概要设计1・抽象数据类型二叉树中任意结点的值人于左节点的值，小于右节点的值，满足BST树的性质，同时本题在建树时需要大量的插入操作，运用链式结构比较方便，所以用链式结构的二叉树来满足BST树的构建。2.ADT①.二叉树的ADT：数据对象D：D是BinNode类的数据元索的集

4、合数据关系R：若D为空集，则称为空树。否则：(1)在D中存在唯一的称为根的数据元素root；(2)当n>l时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵了集本身又是一棵符合本定义的树，称为根root的子树。基本操作：boolInitBST(BST*b)//初始化二叉树boolInitBSTNode(BSTNode*&n)〃初始化节点boolclearBST(BSTNode*&n)//销毁BST②结点的ADT数据对象：包含结点的值，同时包含结点的左右指针数据关系：每个结点都有各自的值若结点左右指针为空，则该节点称为叶子结点基本操作：〃结点的

5、初始化BinNodePtr(){lc=rc=NULL}BinNodePtr(Eleme,BinNodePtr*l=NULL;BinNodePtr*r=NULL){it=e;lc=l;rc=r;}〃判断是否是叶了结点boolisleafQ{return(lc==NULL)&&(rc==NULL)};3•算法的基本思想构建BST树：输入节点数后，依次输入每个结点的值，将第一个结点作为根结点，插入一个数，这个数与根节点先比较，若小于则再与根结点的左了树相比较，若大于则与根节点的右子树相比较。比较时，若小于根结点且根结点的左子树为空，则这个数为根结点左子树的值，若小于根结点乂大于

6、根结点的左子树，则运用指针将根结点的左指针指向这个值得地址，这个值地址的指针再指向原来根结点左子树；大于的情况同理。査找：设置一个计数器，每杏找一次则加一。从根节点开始，在BST屮检索值Ko如果根节点存储的值为K,则检索结束。如果不是，必须检索数的更深的一层。BST的效率在于只需检索两棵子树Z-。如果K小于根节点的值，则只需检索左子树；若果K结点大于根结点的值，则检索右子树。这个过程一直持续到K被知道或者遇到一个叶子结点为止。如果叶子结点仍没有发现K,那么K就不在BST屮。3•程序的流程程序由三个模块组成：输入模块：输入结点数冃初始数据，构建二叉查找树查找模块：判断需要查

7、找的值是否在该BST中输出模块：输出查找成功与否，并输出比较的次数三、详细设计1・物理数据类型动态查找表的数据为小数或整数，用float类型保存。树的ADT具体实现//初始化二叉树boolInitBST(BST*b){b->root=NULL;returntrue;}〃销毁BSTboolclearBST(BSTNode*&n){if(n)returnfalse;if(n->lchild)clearBST(n->lchild);讦(n->rchild)clearBST(n->rchild);free(n);returntrue;