动态查找类模板的设计与实现

成 绩 评 定 表学生姓名 * 班级学号 *专 业 通信工程 课程设计题目 动态查找类模板的设计与实现评语组长签字：成绩日期 20 年 月 日课程设计任务书学 院 信息科学与工程 专 业 通信工程学生姓名 * 班级学号课程设计题目 动态查找类模板的设计与实现实践教学要求与任务实现以二叉排序树为代表的动态查找表类模板，数据元素可以是 char ,int,float 等多种数据类型，包括以下功能：（1） 采用二叉链表存储结构实现二叉排序树的存储；（2） 实现二叉排序树的建树；（3） 实现二叉排序树结点的插入；（4） 实现二叉排序树结点的删除；（5） 实现二叉排序树结点的查找；（6） 将上述功能作为类的成员函数实现，编写主函数测试上述查找功能。工作计划与进度安排第 17 周：分析题目，查阅课题相关资料，进行类设计、算法设计；第 18 周：程序的设计、调试与实现；第 19 周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师：201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘 要二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；动态查找表类模板实现二叉排序树的建树，结点插入，结点删除和结点的查找的功能，并采用二叉链表存储结构实现二叉排序树的存储，采用 Visual C+ 6.0 的控制台工程和 MFC 工程分别实现二叉排序树的各种算法。关键词： 动态查找表；类模板；建树；结点插入；结点删除；结点查找；二叉链表；MFC 工程目 录1 需求分析 .12 算法基本原理 .13 类设计 .23.1 类的概述 .23.2 类的接口设计 .33.3 类的实现 .44 基于控制台的应用程序 .124.1 主函数设计 .124.2 运行结果及分析 .155 基于 MFC 的应用程序 .165.1 图形界面设计 .165.2 程序代码设计 .175.3 运行结果及分析 .21结论 .24参考文献 .2511 需求分析用户需要对存储在闪存中的数据进行插入和删除等操作，为了快速响应用户的这些操作 以及保证每次操作完后剩下的数据记录仍为二叉排序数，对每项操作都需要有一个安全高效的算法。查找到原文件中已经存有该用户数据记录，则接下来不需要任何操作。而如 果需要进行插入时，采用在二叉排序树算法需要添加该记录并修改新记录父结点指向它的指 针。所以当新记录要插入的位置和其要修改的指针不在一个扇区时，就一共需要擦除两个扇 区。但因为在插入之前都会首先在其父节点所在的扇区中去寻找空闲存储区。所以大部分情 况下该操作都只需要擦除一个扇区。：如果在原文件中查找不到要删除的用户数据记录，则接下来不需要任何操作。 而如果查找到并且是 2，3，4 的情况，采用在二叉排序树算法需要释放该记录所占用的存储 空间并修改该记录父结点指向它的指针。需要修改的扇区数与插入一样，但因为插入的时候 都优先选择它们在一个扇区，所以大部分情况下该算法都只需要擦除一个扇区。在 5 的情况 下，则需要将被删除记录除了二叉排序树结点左右指针以外的其他值用 S 的值替代，还要放 S 所占用的存储空间并修改 S 的父结点指向它的指针共三处地方。所以在坏的情况下要 擦除三个扇区，但后两处大部分情况下都在一个扇区中，可以减少一些工作量。在上节已经对该查找算法进行了详细的分析，这里就不再重复了。而采用顺序存储的线性表，每次都需要在整个文件所包含的所有扇区进行搜索，它的查找长度与整个 文件所能存储的用户数据记录条数成正比。当文件比较大时，进行线性查找将是非常耗时的。 而对于用户的每一项操作，都要必须先使用查找算法进行查找对应的用户数据记录，所以本 文使用基于二叉排序数的查找算法，无疑在整体性能上具有非常大的优势。2 算法基本原理二叉排序树定义：二叉排序树是这样的树，结点左边的值都小于结点的值，结点右边的值都大于结点的值，所以按照二叉树的中序遍历的话，得到的的将是按顺序排列的值。2二叉排序树的主要操作：1）：建立二叉树用插入函数依次插入用户输入的序列，最后再中序遍历并输出显示2）：插入插入的操作非常简单，从根结点开始，如果插入值大于根节点值，则向右遍历，如果小于根节点值，则想左遍历，知道遇到一个叶子结点为止。按插入值大于叶子则将插入值作为叶子结点的右孩子，否则左孩子。中间过程中如果遇到跟插入值相等的，则插入失败。3）：删除关于有三种情况需要不同对待。如果是叶子结点，那么直接删除就行（注意相关的孩子指针要变成 NULL） 。如果要删除的结点只有左孩子或者右孩子，这样也好办，我们只需要把相应的孩子赋值给待删除结点的双亲结点的孩子指针即可，孙子升级当儿子。如果要删除的结点既有左孩子，又有右孩子，那么情况就稍微有点麻烦，在这里我们可以采取两种策略来实现，第一种是“前驱不动，移动右孩子法” ，第二种是“右孩子不动，移动前驱法” 。4）：遍历遍历采用递归方法，遍历的实现就很简单了。5）：清除在清除树的所有结点的时候，采取了递归思想，判断左孩子是否为空，如果不空则清空做孩子；再判断右孩子是否为空，不为空则清空右孩子；只有当结点左右孩子结点都为空的时候，才释放该结点的空间。6）：查找查找要利用二叉排序树的自身优点来进行，每次根据与结点的比较结果选择再继续跟左孩子比较还是跟右孩子比较33 类设计3.1 类的概述类模板就是设计一种类的框架，可以适用不同的数据类型，只是一种类的抽象，因此，利用类模板可以针对不同的数据类型定义出具有共性的一组类。从上面的过程分析可以看到，本设计中包含的主要函数 bool insert(),bool erase1(),bool erase2(),void clear(),Node*find(),void traverse(),Node*build(),void dispiay(),3.2 类的接口设计#include /预处理命令using namespace std;/使用命名空间 stdtemplate/声明类模板class BSTrees/定义一个类public:BSTrees();构造函数BSTrees();析构函数public:struct Node/二叉链表存储Type e;/关键字Node* leftChild;/用指针存放左孩子Node* rightChild;/指针存放右孩子Node()Node(Type _e)/存放关键字4e = _e;leftChild= NULL;/左孩子为空rightChild = NULL;/右孩子为空;public:/公有成员函数bool insert(Type e);/插入bool erase1(Type e);/删除voidclear();/清空bool isEmpty();/判断是否为空int getLength();/求长度Node* find(Type e);/查找Node* getRoot();/求根结点Node* getParent(Node* p);/求双亲void traverse(Node* ptr);/遍历Node* build(Node* m_root,int number);/建立void display(void);/显示void show(Node* m_root);/显示private:voidclears(Node* /清空private:/私有成员函数Node* m_root;int m_Length;3.3 类的实现template BSTrees:BSTrees()/构造函数coutnumber;/插入数字while(number!=-1)/while循环语句m_root=build(m_root,number);cinnumber; template typename BSTrees: Node* BSTrees:build(Node* m_root,int number)/建立一棵二叉树Node *p; p=new Node;p-e=number;p-leftChild =p-rightChild=NULL;/左孩子与右孩子为空if(m_root=NULL)return p;/返回elseif(p-e e)/结点小于根结点m_root-leftChild=build(m_root-leftChild,number);/成为根结点的左孩子elsem_root-rightChild=build(m_root-rightChild,numbe