HUNANUNIVERSITY课程实习报告题目:BST实现动态查找表学生姓名:学生学号:专业班级:指导老师:李晓鸿完成日期:20151121一、需求分析1、程序任务:本程序是利用二叉查找树(BST)来实现;二叉树使用链式结构(二叉链表)实现,本程序要实现BST的构建,查找BST树中元素中两个功能。2、输入形式:输入整数n//BST的节点个数n。输入n个数,其取值范围为(0,216),对非法输入做处理。3、输出形式:若查找成功整数m(次数)//返回成功和查找时比较的次数若查找不成功整数m(次数)//返回不成功和查找时比较的次数若输入错误“输入了无效的元素”4、测试数据:①.正常的输入10//BST的节点个数501327865100594318//10个数据输入:50输出:查找成功,查找次数1输入:1输出:查找成功,查找次数6输入:3输出:查找成功,查找次数4输入:100输出:查找成功,查找次数5输入:19输出:查找失败②.只有左子树的情况10//BST的节点个数10011235439554827893//10个数据输入:1输出:查找成功,查找次数1输入:12输出:查找成功,查找次数6输入:35输出:查找成功,查找次数4输入:95输出:查找成功,查找次数5输入:19输出:查找失败③.错误的节点数输入-2//BST的节点个数输出:错误的结点数输入④.错误的结点值的输入(字母)10//BST的结点个数1q23456789//10个数据输出:无效的结点输入⑤.错误的结点值的输入(负数)10//BST的结点个数1-223456789//10个数据输出:无效的结点输入二叉树中任意结点的值大于左节点的值,小于右节点的值,满足BST树的性质,所以用BST树来实现。二.概要设计1.抽象数据类型二叉树中任意结点的值大于左节点的值,小于右节点的值,满足BST树的性质,同时本题在建树时需要大量的插入操作,运用链式结构比较方便,所以用链式结构的二叉树来满足BST树的构建。2.ADT①.二叉树的ADT:数据对象D:D是BinNode类的数据元素的集合数据关系R:若D为空集,则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root;(2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。基本操作:boolInitBST(BST*b)//初始化二叉树boolInitBSTNode(BSTNode*&n)//初始化节点boolclearBST(BSTNode*&n)//销毁BST②结点的ADT数据对象:包含结点的值,同时包含结点的左右指针数据关系:每个结点都有各自的值若结点左右指针为空,则该节点称为叶子结点基本操作://结点的初始化BinNodePtr(){lc=rc=NULL}BinNodePtr(Eleme,BinNodePtr*l=NULL;BinNodePtr*r=NULL){it=e;lc=l;rc=r;}//判断是否是叶子结点boolisleaf(){return(lc==NULL)&&(rc==NULL)};3.算法的基本思想构建BST树:输入节点数后,依次输入每个结点的值,将第一个结点作为根结点,插入一个数,这个数与根节点先比较,若小于则再与根结点的左子树相比较,若大于则与根节点的右子树相比较。比较时,若小于根结点且根结点的左子树为空,则这个数为根结点左子树的值,若小于根结点又大于根结点的左子树,则运用指针将根结点的左指针指向这个值得地址,这个值地址的指针再指向原来根结点左子树;大于的情况同理。查找:设置一个计数器,每查找一次则加一。从根节点开始,在BST中检索值K。如果根节点存储的值为K,则检索结束。如果不是,必须检索数的更深的一层。BST的效率在于只需检索两棵子树之一。如果K小于根节点的值,则只需检索左子树;若果K结点大于根结点的值,则检索右子树。这个过程一直持续到K被知道或者遇到一个叶子结点为止。如果叶子结点仍没有发现K,那么K就不在BST中。4.程序的流程程序由三个模块组成:输入模块:输入结点数目初始数据,构建二叉查找树查找模块:判断需要查找的值是否在该BST中输出模块:输出查找成功与否,并输出比较的次数三、详细设计1.物理数据类型动态查找表的数据为小数或整数,用float类型保存。树的ADT具体实现//初始化二叉树boolInitBST(BST*b){b-root=NULL;returntrue;}//销毁BSTboolclearBST(BSTNode*&n){if(n)returnfalse;if(n-lchild)clearBST(n-lchild);if(n-rchild)clearBST(n-rchild);free(n);returntrue;}//初始化节点boolInitBSTNode(BSTNode*&n){n=(BSTNode*)malloc(sizeof(BSTNode));n-lchild=NULL;n-rchild=NULL;returntrue;}结点的ADT具体实现BinNodePtr(){lc=rc=NULL}//结点的初始化BinNodePtr(Eleme,BinNodePtr*l=NULL;BinNodePtr*r=NULL){it=e;lc=l;rc=r;}//判断是否是叶子结点boolisleaf()2.算法的具体步骤①.结点输入操作:先输入结点数,在输入每个结点的值,通过循环调用insert函数将每个结点进行插入coutBST结点数目:endl;cinn;for(inti=0;in;i++){cinp[i];if(p[i]=0){cout无效的结点输入endl;system(pause);return;}insert(&b,p[i]);}②.头结点的建立:对于第一个调用insert函数插入的值,作为头结点建立二叉树if(b-root==NULL){b-root=n;returntrue;}④.之后结点的插入:插入一个数,这个数与根结点先比较,若小于则再与根结点的左子树相比较,若大于则与根节点的右子树相比较。比较时,若小于根结点且根结点的左子树为空,则这个数为根结点左子树的值,若小于根结点又大于根结点的左子树,则运用指针将根结点的左指针指向这个值得地址,这个值地址的指针再指向原来根结点左子树;大于的情况同理。while(1)//循环比较{if(em-data)//小于根节点则插入左子树{if(m-lchild==NULL){m-lchild=n;//给左孩子赋值returntrue;}if(m-lchild!=NULL&&em-lchild-data){n-lchild=m-lchild;m-lchild=n;returntrue;}elsem=m-lchild;continue;}else//大于根节点则插入右子树{if(m-rchild==NULL){m-rchild=n;//给右孩子赋值returntrue;}if(m-rchild!=NULL&&em-rchild-data){n-rchild=m-rchild;m-rchild=n;returntrue;}elsem=m-rchild;continue;}}⑤.完整的insert插入操作:插入元素e时,先判断该二叉树是否为空,若为空,将e作为该二叉树的根节点。否则,从根节点开始,比较e与节点n的大小。如果e的值更小,判断n的左子树是否为空,若为空,将e作为节点n的左孩子并返回e,否则比较e与n左孩子的值,依此循环下去;如果e的值更大,判断n的右子树是否为空,若为空,将e作为节点n的右孩子并返回e,否则比较e与n右孩子的值,依此循环下去。boolinsert(BST*b,ElemTypee)//把结点插入BST{BSTNode*n,*m;InitBSTNode(n);n-data=e;if(b-root==NULL){b-root=n;returntrue;}m=b-root;while(1)//循环比较{if(em-data)//小于根节点则插入左子树{if(m-lchild==NULL){m-lchild=n;//给左孩子赋值returntrue;}if(m-lchild!=NULL&&em-lchild-data){n-lchild=m-lchild;m-lchild=n;returntrue;}elsem=m-lchild;continue;}else//大于根节点则插入右子树{if(m-rchild==NULL){m-rchild=n;//给右孩子赋值returntrue;}if(m-rchild!=NULL&&em-rchild-data){n-rchild=m-rchild;m-rchild=n;returntrue;}elsem=m-rchild;continue;}}}②find查找操作,查找元素时,从根节点开始,比较e与节点x的大小,若相等,返回true;如果e比节点x的值小,判断x的左子树是否为空,若为空,返回false,不为空则比较e与x左孩子的值,依次循环下去;如果e比节点x的值大,判断x的右子树是否为空,若为空,返回false,不为空则比较e与x右孩子的值,依次循环下去。boolfind(BST*b,ElemTypee)//查询元素e,记录比较的次数查询成功返回true,否则返回false{intcount=0;BSTNode*x=b-root;while(1)//循环比较{count++;//设置计数器if(ex-data)//小于根节点则在左子树中查找{if(x-lchild==NULL){cout查找失败,查找次数:countendl;returnfalse;//左子树为空则查找失败}x=x-lchild;//继续与左孩子的值比较continue;}if(ex-data)//大于根节点则在右子树中查找{if(x-rchild==NULL){cout查找失败,查找次数:countendl;returnfalse;//右子树为空则查找失败}x=x-rchild;//继续与右孩子的值比较continue;}if(e==x-data){cout查找成功,查找次数:countendl;//coutcount;returntrue;}}}3.算法的时空分析查找元素需要的比较次数由树的深度决定查找,最好时间复杂度O(logN),最坏时间复杂度O(N)(只有左子树或右子树的情况)。4.输入和输出的格式输入BST结点数BST结点数目://等待输入coutBST结点数:endl;cinn;输入BST结点数据BST节点数据://等待输入for(inti=0;in;i++){cinp[i];if(p[i]=0){cout无效的结点输入endl;system(pause);return;}输入要查找的数据cout输入要查找的数据(输入-1结束查找)endl;cinm;若BST结点数目输入错误:输出“无效的结点数目输入”if(n=0){cout无效的结点数目输入endl;system(pause);return;}若BST节点数据输入错误:输出“无效的结点输入”if(p[i]=0){cout无效的结点输入endl;system(pause);return;}若查找成功输出查找次数://输出次数if(e==x-data){cout查找成功,查找次数:countendl;returntrue;}查找失败,查找次数://输出次数if(x-rchild==NULL){cout查找失败,查找次数:countendl;returnfalse;//右