山东大学《数据结构》实验指导06查找或检索.docx

实验六查找/检索
一实验任务
1)静态查找方法的实现
2)动态查找方法的实现二实验目的
1)掌握典型的查找方法(折半查找、二叉树查找)。
2) 了解各种查找方法的适用范围和效率。
三实验原理
1 .查找表
表(Table)是由同一种类型数据元素(记录)构成的集合。表的抽象数据 类型定义如下：
ADT Table{数据对象：具有同种数据类型的数据元素的集合；
数据关系：数据元素之间无特定的次序关系，同属一个集合；基本操作：
CreateTable (&L)操作结果：创立一个空表L。
TableEmpty( L)初始条件：表L已存在。
操作结果：假设L为空表，那么返回TRUE,否那么返回FALSE。
TableInsert(&L, newltem)初始条件：表L已存在，newltem为给定元素。
操作结果：在表L中插入一个新数据元素newltem。
TableDelete(&L, search Key)初始条件：表L已存痘，searchKey为给定元素。
操作结果:在表L中删除一个关键字值等于searchKey的数据元素。
TableSearch( L, searchKey)初始条件：表L已存在，searchKey为给定元素。
操作结果：在表中查找一个关键字值等于searchKey的数据元素。
TableTraverse( L, visit())初始条件：表L已存在，visit()是对元素操作的应用函数。
操作结果：按某种次序对L中元素调用函数visit。一次且仅一次。一 旦visit。失败，那么操作失败。
} ADT Table
假设对表只作''查找〃的操作，那么称此类表为静态查找表(Static Search Table)o 假设在查找过程中同时插入表中不存在的数据元素，或者在表中删除已存在的某个 数据元素，那么称此类表为动态查找表(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）分析掌握教材168~171页中的算法6-1~6-2,为完成实验任务1做好准备。
3）分析掌握教材177~184页中的算法6-5~6-8,为完成实验任务1做好准 备。
（2）实验步骤
1）问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件 是什么。
2）系统的结构设计。按照以数据结构为中心的原那么划分模块。最后写出每 个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示那么更加清晰，这样便完成了系统结构设计。
3）详细设计。详细设计的目的是对子程序（过程或函数）的进一步求精。 用IF、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的 目的是防止陷入细节。
4）编码。在详细设计的基础上，对详细设计的结果进一步求精，用C语言 表示出来。
5）在VC环境下调试程序。
七实验报告要求
实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：
1）需求分析及规格说明：问题描述，求解的问题是什么。
2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互 关系。
3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调 用关系。
4）调试报告。
5）本实验任务1、2的程序清单及运行结果。
八思考题
1）针对实验任务1中折半查找，如何求解其平均查找长度？
2）在散列表查找中，平均查找长度和散列表存储的纪录数，如何求出散列 表的长度？