数据结构实验报告三-BST.doc

－ PAGE 1 － 实验3 BST 需求分析 输入的形式和输入值的范围： 建表的输入： 第一次输入一个正整数N，代表接下来要输入的结点值的个数。 以后输入N个整数，分别代表N个结点的值，中间用空格隔开。 输入格式为：“34 76 45 18 26 54 92 65”。 查询的输入： 输入一个整数，代表需要在表中查询的值。 不对非法输入做处理，即假设输入都是合法的。 输出的形式： 对于需要查询的值： 如果存在于表中，则输出“查找成功”，并输出比较次数； 如果不存在于表中，则输出“查找不成功，已插入到表中”。 程序所能达到的功能： 该程序可以构建一个动态查找表。 可以对用户输入的数据进行查询，输出查询结果和查询过程中的比较次数；对于表中不存在的数据，还可以动态插入。 测试数据： 请输入数据个数：8 34 76 45 18 26 54 92 65 45 查找成功，比较次数为3 34 查找成功，比较次数为1 100 查找不成功，已插入到表中 26 查找成功，比较次数为3 100 查找成功，比较次数为4 概要设计 抽象数据类型的定义： 对于一个具有插入和查询功能的动态查询表，我们需要其插入和检索的时间效率更高，因此选择使用二叉查找树（BST）来实现这个动态查询表。 查询表中的数据类型作为BST的结点，所以需要定义一个结点类来实现数据及其关系的存储。 结点类的ADT如下： 数据类型：整形 基本操作： int val() //返回结点的数值 inline Node* left()const //获取左结点 inline Node* right()const //获取右结点 void setLeft(Node* it) //设置左结点 void setRight(Node* it) //设置右结点 BST的ADT如下： 数据对象：Node类型 数据关系：二叉树 基本操作： bool insert(const int it) //插入元素 bool find(int it) //查找元素 算法的基本思想： 建表 对于输入的数据，从根结点开始与其数值进行比较。 如果数值小于结点的值则与该结点的左子结点值比较，反之与该结点的右子结点值比较，反复进行上述比较，直到需要比较的下一结点是一个空结点，将此数据的结点类型赋给此空结点。即完成一次插入工作。 对于所有输入数据，反复进行上述插入操作，直到所有数据都插入树中，则此BST的构建工作完成。 查询 对于需要查询的数据，采取与插入操作相同的比较操作。每一次比较后都将“比较次数”加一。当比较到具有同样值的元素时，返回找到，如果所有元素比较完毕仍然没有相同的结果，返回没有找到，并且使用插入操作将该值插入到表中。 详细设计 实现概要设计中定义的所有数据类型： 用整形存储用户的输入，并将相应数据存入Node类。 class Node //结点类 { private: int data; //数据 Node* lc; //指向左子结点的指针 Node* rc; //指向右子结点的指针 public: Node(){lc=rc=NULL;} //空结点 Node(int it){data=it;lc=NULL;rc=NULL;} //值不为空的结点 int val(){return data;} //返回值 inline Node* left()const{return lc;} //返回左子结点 inline Node* right()const{return rc;} //返回右子结点 void setLeft(Node* it){lc=it;} //设置左子结点 void setRight(Node* it){rc=it;} //设置右子结点 }; 用链式结构（二叉链表）实现二叉树，该二叉链表的结点类型为Node类。 class BST { private: Node* root; //根结点 public: