[计算机软件及应用]第8章 查找.ppt

100
865
10
Data Structure
第八章查找
7/26/2018
1
学习目标
理解“查找表”的结构特点以及各种表示方法的适用性;
熟练掌握以顺序表或有序表表示静态查找表时的查找方法;
熟练掌握二叉查找树的构造和查找方法;
理解二叉平衡树的构造过程;
熟练掌握哈希表的构造方法,深刻理解哈希表与其它结构的表的实质性的差别;
掌握描述查找过程的判定树的构造方法,以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
7/26/2018
2
重点和难点
重点:理解查找表的结构特点及其各种表示方法的特点和适用场合。
知识点
顺序表、有序表、索引顺序表
二叉查找树、二叉平衡树
哈希表
7/26/2018
3
基本概念
查找表
由一些具有相同可辨认特性的数据元素(或记录)构成的集合。
该集合中的数据元素用于查找。
对查找表经常进行的操作有:
查询某个“特定的”数据元素是否在表中;
检索某个“特定的”数据元素的各种属性;
在查找表中插入一个数据元素;
从查找表中删除某个数据元素。
静态查找表
只对查找表进行如下两种操作
查询某个“特定的”数据元素是否在表中;
检索某个“特定的”数据元素的各种属性;
7/26/2018
4
静态查找
对静态查找表进行的查找操作。
动态查找表
若在对查找表进行查找的过程中,同时需要随时插入当前查找表中不存在的数据元素,或者从当前的查找表中删除已存在的某个数据元素,则称此类查找表为动态查找表。
动态查找
对动态查找表进行的查找操作。
关键字
是数据元素(或记录)中某个数据项的值,可以标识一个数据元素(或记录)。
7/26/2018
5
主关键字
可以唯一地标识一个元素的关键字。
对不同的元素,其主关键字均不同。
次关键字
用以识别若干元素的关键字。
查找
根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素的过程。
若表中存在这样的一个元素,则称查找是成功的;
若表中不存在这样的元素,则称查找不成功。
7/26/2018
6
查找方法评价
查找速度;
占用存储空间多少;
算法本身复杂程度;
平均查找长度ASL:查找过程中先后和给定值进行比较的关键字 个数的期望值。
7/26/2018
7
静态查找表
抽象数据类型静态查找表的定义
ADT StaticSearchTable {
数据对象:D是具有相同特性的数据元素的集合。每个数据元素含有类 型相同的关键字,可唯一标识数据元素。
数据关系:D中所有数据元素同属一个集合。
基本操作:
CreateTable(&ST, n); 操作结果:构造一个含 n 个数据元素的静态查找表 ST。
DestroyTable(&ST); 初始条件:静态查找表 ST 存在; 操作结果:销毁查找表 ST。
7/26/2018
8
Search(ST, kval);初始条件:静态查找表 ST 存在,kval 为和查找表中元素的关键字 类型相同的给定值;操作结果:若ST中存在其关键字等于 kval 的数据元素,则函数值 为该元素的值或在表中的位置,否则为“空”。
Traverse(ST, visit());初始条件:静态查找表 ST 存在,visit 是对元素操作的应用函数;操作结果:按某种次序对ST的每个元素调用函数 visit() 一次且仅 一次,一旦 visit() 失败,则操作失败。
} ADT StaticSearchTable
7/26/2018
9
顺序表的查找
适用情况
查找表用顺序存储结构存放。
查找过程
从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较;
若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录;
反之,若直至第一个记录,其关键字和给定值比较都不相等,则表明表中没有所查记录,查找不成功。
7/26/2018
10