实验六 查找/检索一 实验任务1）静态查找方法的实现2）动态查找方法的实现二 实验目的1）掌握典型的查找方法（折半查找、二叉树查找）。2）了解各种查找方法的适用范围和效率。三 实验原理1 查找表表（Table）是由同一种类型数据元素（记录）构成的集合。表的抽象数据类型定义如下：ADT Table数据对象：具有同种数据类型的数据元素的集合； 数据关系：数据元素之间无特定的次序关系，同属一个集合； 基本操作： CreateTable (&L)操作结果：创建一个空表L。TableEmpty( L )初始条件：表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。 TableInsert(&L, newItem)初始条件：表L已存在，newItem为给定元素。操作结果：在表L中插入一个新数据元素newItem。 TableDelete(&L, searchKey)初始条件：表L已存在，searchKey为给定元素。操作结果：在表L中删除一个关键字值等于searchKey 的数据元素。 TableSearch( L, searchKey)初始条件：表L已存在，searchKey为给定元素。操作结果：在表中查找一个关键字值等于searchKey 的数据元素。 TableTraverse( L, visit( )初始条件：表L已存在，visit( )是对元素操作的应用函数。操作结果：按某种次序对L中元素调用函数visit( )一次且仅一次。一旦visit( )失败，则操作失败。 ADT Table若对表只作“查找”的操作，则称此类表为静态查找表(Static Search Table)。若在查找过程中同时插入表中不存在的数据元素，或者在表中删除已存在的某个数据元素，则称此类表为动态查找表(Dynamic Search Table)。2静态查找（1）顺序查找顺序查找(Sequential Search)的方法是：从表的一端开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若找遍了表中所有记录，也未找到关键字与给定值相等的记录，则查找不成功。（2）折半查找折半查找（Binary Serach）的查找过程是：首先将给定的值key与有序表中间位置的记录的关键字相比较，若两者相等，则查找成功，否则根据比较结果确定下次查找范围是在中间记录的前半部分还是后半部分，然后在新的查找范围内进行同样操作，如此重复迭代，直到查找成功或失败。折半查找优点是比较次数少，查找速度快，尤其当表的规模较大（n值较大）时，它的查找效率较高。但是，折半查找只适用于有序表，且限于顺序存储结构（对线性链表无法进行折半查找）。因此，在查找之前必须将顺序表按关键字的大小排序。3动态查找（1）二叉查找树二叉查找树（Binary Search Tree）又称二叉排序树（Binary Sort Tree），是这样一棵二叉树，它或为空，或者每个结点中包含一个关键字，并满足如下条件：（1）若它的左子树存在，则左子树上所有结点的关键字值均小于根结点。（2）若它的右子树存在，则右子树上所有结点的关键字值均大于根结点。（3）它的左、右子树也是一棵二叉查找树。二叉查找树结构兼有顺序存储结构和链式存储结构的最佳特性，是实现动态查找的最佳选择。（2）二叉查找树的建立从空树出发，经过一系列的插入操作之后，可以构建一棵二叉查找树。若在二叉查找树上插入一个元素，具体操作如下：将一个新结点插入到一棵空二叉查找树中非常容易实现，只需将root指针指向新结点即可。如果树不空，则必须将插入结点的关键字值与根结点的关键字值比较。如果新插入结点的关键字值较小，则插入结点必须插入到该根结点的左子树中；如果较大，则插入结点必须插入到该根结点的右子树中。新插入结点一定是一个新添加的叶子结点，并且是在查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。（3）二叉查找树的查找为了查找给定的目标，首先将它与树根结点的关键字进行比较。如果相等，则完成查找，否则将依据给定的关键字值和根结点的关键字之间的大小关系，分别转向左子树或右子树继续查找，直到查找成功或命中一棵空子树。四 实验设备、仪器、工具与资料 微机、VC五 实验内容（1）实验任务1：静态查找设计一个程序，演示顺序查找、折半查找方法，要求采用菜单的形式进行选择。（2）实验任务2：动态查找设计一个程序，实现二叉查找树的建立、查找、删除结点等操作。（3）实验任务3：散列表查找（选做）针对你所在的班级的同学姓名设计一个散列表，使得平均查找长度不超过2，并完成相应的建表和查表程序。要求：散列函数采用质数除余法，冲突采用拉链法解决。六 实验步骤（1）实验预习1）预习本实验原理中静态查找和动态查找的实现原理。2）分析掌握教材168171页中的算法6-16-2，为完成实验任务1做好准备。3）分析掌握教材177184页中的算法6-56-8，为完成实验任务1做好准备。（2）实验步骤1）问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件是什么。2）系统的结构设计。按照以数据结构为中心的原则划分模块。最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。3）详细设计。详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF 、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。4）编码。在详细设计的基础上，对详细设计的结果进一步求精，用C语言表示出来。5）在VC环境下调试程序。七 实验报告要求实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：1）需求分析及规格说明：问题描述，求解的问题是什么。2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互关系。3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调用关系。4）调试报告。5）本实验任务1、2的程序清单及运行结果。八 思考题1）针对实验任务1中折半查找，如何求解其平均查找长度？2）在散列表查找中，已知平均查找长度和散列表存储的纪录数，如何求出散列表的长度？