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

《动态查找类模板的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、成绩评定表学生姓名************班级学号**************专业通信工程课程设计题目动态查找类模板的设计与实现评语组长签字：成绩日期20年月日课程设计任务书学院信息科学与工程专业通信工程学生姓名***班级学号课程设计题目动态查找类模板的设计与实现实践教学要求与任务实现以二叉排序树为代表的动态查找表类模板，数据元素可以是char,int,float等多种数据类型，包括以下功能：（1）采用二叉链表存储结构实现二叉排序树的存储；（2）实现二叉排序树的建树；（3）实现二叉排序树结点的插入；（4）实现二叉排序树结点的删除；（5）实现二叉排序树结点的查找；（6）将上述功能作为类的成员

2、函数实现，编写主函数测试上述查找功能。工作计划与进度安排第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日摘要二叉排序树（BinarySortTree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；动态查找表类模板实现二叉排序树的建树，结点插入，结点删除和结

3、点的查找的功能，并采用二叉链表存储结构实现二叉排序树的存储，采用VisualC++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参考文献251需求分析用户需要对存储在闪存中的数据进行插入和删除等操作，为了快速响应用户的这些操作以及保

4、证每次操作完后剩下的数据记录仍为二叉排序数，对每项操作都需要有一个安全高效的算法。查找到原文件中已经存有该用户数据记录，则接下来不需要任何操作。而如果需要进行插入时，采用在二叉排序树算法需要添加该记录并修改新记录父结点指向它的指针。所以当新记录要插入的位置和其要修改的指针不在一个扇区时，就一共需要擦除两个扇区。但因为在插入之前都会首先在其父节点所在的扇区中去寻找空闲存储区。所以大部分情况下该操作都只需要擦除一个扇区。：如果在原文件中查找不到要删除的用户数据记录，则接下来不需要任何操作。而如果查找到并且是2，3，4的情况，采用在二叉排序树算法需要释放该记录所占用的存储空间并修改该记录父结点指

5、向它的指针。需要修改的扇区数与插入一样，但因为插入的时候都优先选择它们在一个扇区，所以大部分情况下该算法都只需要擦除一个扇区。在5的情况下，则需要将被删除记录除了二叉排序树结点左右指针以外的其他值用S的值替代，还要放S所占用的存储空间并修改S的父结点指向它的指针共三处地方。所以在坏的情况下要擦除三个扇区，但后两处大部分情况下都在一个扇区中，可以减少一些工作量。在上节已经对该查找算法进行了详细的分析，这里就不再重复了。而采用顺序存储的线性表，每次都需要在整个文件所包含的所有扇区进行搜索，它的查找长度与整个文件所能存储的用户数据记录条数成正比。当文件比较大时，进行线性查找将是非常耗时的。而对于

6、用户的每一项操作，都要必须先使用查找算法进行查找对应的用户数据记录，所以本文使用基于二叉排序数的查找算法，无疑在整体性能上具有非常大的优势。2算法基本原理二叉排序树定义：二叉排序树是这样的树，结点左边的值都小于结点的值，结点右边的值都大于结点的值，所以按照二叉树的中序遍历的话，得到的的将是按顺序排列的值。二叉排序树的主要操作：V1）：建立二叉树用插入函数依次插入用户输入的序列，最后再中序遍历并输出显示2）：插入插入的操作非常简单，从根结点开始，如果插入值大于根节点值，则向右遍历，如果小于根节点值，则想左遍历，知道遇到一个叶子结点为止。按插入值大于叶子则将插入值作为叶子结点的右孩子，否则左孩

7、子。中间过程中如果遇到跟插入值相等的，则插入失败。3）：删除关于有三种情况需要不同对待。<1>如果是叶子结点，那么直接删除就行（注意相关的孩子指针要变成NULL）。<2>如果要删除的结点只有左孩子或者右孩子，这样也好办，我们只需要把相应的孩子赋值给待删除结点的双亲结点的孩子指针即可，孙子升级当儿子。<3>如果要删除的结点既有左孩子，又有右孩子，那么情况就稍微有点麻烦，在这里我们可以采取两种策略来实现，第一种是“前驱不动，