数据结构实验报告三-bst

《数据结构实验报告三-bst》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验3BST1．需求分析（1）输入的形式和输入值的范围：建表的输入：第一次输入一个正整数N，代表接下来要输入的结点值的个数。以后输入N个整数，分别代表N个结点的值，中间用空格隔开。输入格式为：“3476451826549265”。查询的输入：输入一个整数，代表需要在表中查询的值。不对非法输入做处理，即假设输入都是合法的。（2）输出的形式：对于需要查询的值：如果存在于表中，则输出“查找成功”，并输出比较次数；如果不存在于表中，则输出“查找不成功，已插入到表中”。（3）程序所能达到的功能：该程序可以构建一个

2、动态查找表。可以对用户输入的数据进行查询，输出查询结果和查询过程中的比较次数；对于表中不存在的数据，还可以动态插入。（4）测试数据：请输入数据个数：8347645182654926545查找成功，比较次数为334查找成功，比较次数为1100查找不成功，已插入到表中26查找成功，比较次数为3100查找成功，比较次数为4－6－1．概要设计（1）抽象数据类型的定义：对于一个具有插入和查询功能的动态查询表，我们需要其插入和检索的时间效率更高，因此选择使用二叉查找树（BST）来实现这个动态查询表。查询表中的数据类

3、型作为BST的结点，所以需要定义一个结点类来实现数据及其关系的存储。结点类的ADT如下：数据类型：整形基本操作：intval()//返回结点的数值inlineNode*left()const//获取左结点inlineNode*right()const//获取右结点voidsetLeft(Node*it)//设置左结点voidsetRight(Node*it)//设置右结点BST的ADT如下：数据对象：Node类型数据关系：二叉树基本操作：boolinsert(constint&it)//插入元素bool

4、find(int&it)//查找元素（2）算法的基本思想：1、建表对于输入的数据，从根结点开始与其数值进行比较。如果数值小于结点的值则与该结点的左子结点值比较，反之与该结点的右子结点值比较，反复进行上述比较，直到需要比较的下一结点是一个空结点，将此数据的结点类型赋给此空结点。即完成一次插入工作。对于所有输入数据，反复进行上述插入操作，直到所有数据都插入树中，则此BST的构建工作完成。2、查询对于需要查询的数据，采取与插入操作相同的比较操作。每一次比较后都将“比较次数”加一。当比较到具有同样值的元素时，返

5、回找到，如果所有元素比较完毕仍然没有相同的结果，返回没有找到，并且使用插入操作将该值插入到表中。－6－1．详细设计（1）实现概要设计中定义的所有数据类型：1、用整形存储用户的输入，并将相应数据存入Node类。classNode//结点类{private:intdata;//数据Node*lc;//指向左子结点的指针Node*rc;//指向右子结点的指针public:Node(){lc=rc=NULL;}//空结点Node(intit){data=it;lc=NULL;rc=NULL;}//值不为空的结点

6、intval(){returndata;}//返回值inlineNode*left()const{returnlc;}//返回左子结点inlineNode*right()const{returnrc;}//返回右子结点voidsetLeft(Node*it){lc=it;}//设置左子结点voidsetRight(Node*it){rc=it;}//设置右子结点};2、用链式结构（二叉链表）实现二叉树，该二叉链表的结点类型为Node类。classBST{private:Node*root;//根结点pu

7、blic:BST(){root=NULL;}//构造函数boolinsert(constint&it)//插入方法{if(root==NULL)root=newNode(it);//根结点为空时else{Node*subroot=root;Node*tem=root;while(subroot!=NULL)//根结点不为空时{tem=subroot;if(itval()){subroot=subroot->left();}else{subroot=subroot->right();}

8、}subroot=newNode(it);－6－if(itval()){tem->setLeft(subroot);}else{tem->setRight(subroot);}}returntrue;}boolfind(int&it)//查找方法{Node*subroot=root;intcount=0;while(subroot!=NULL)//当结点不为空时继续比较{if(itval()){subroot