文档介绍：第九章查找
查找的概念
静态查找表
动态查找表
哈希表
查找表是由同一类型的数据元素(或记录)构成的集合,由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的数据结构。对查找表的操作:
查询某个“特定的”数据元素是否在查找表中;
检索某个“特定的”数据元素的各种属性;
在查找表中插入一个数据元素;
从查找表中删去某个数据元素
查找的概念
静态查找表
仅作查询和检索操作的查找表。
动态查找表
在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。
查找表的分类:
关键字
是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)。若此关键字可以识别唯一的一个记录,则称之谓“主关键字”。若此关键字能识别若干记录,则称之谓“次关键字”。
根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录)。
若查找表中存在这样一个记录,则称“查找成功”,查找结果:给出整个记录的信息,或指示该记录在查找表中的位置;
否则称“查找不成功”,查找结果:给出
“空记录”或“空指针”。
查找
如何进行查找?
查找的方法取决于查找表的结构。
由于查找表中的数据元素之间不存在明显的组织规律,因此不便于查找。
为了提高查找的效率, 需要在查找表中的元素之间人为地附加某种确定的关系,换句话说, 用另外一种结构来表示查找表。
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度ASL(Average Search Length):为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值叫查找算法的~
抽象数据类型静态查找表的定义:
ADT StaticSearchTable {
D是具有相同特性的
数据元素的集合。每个数据元素含有类型相同的关键字,可唯一标识数据元素。
数据关系R:数据元素同属一个集合。
静态查找表
数据对象D:
Create(&ST, n); //构造一个含 n 个数据元素的静态查找表ST。
Destroy(&ST); //销毁表ST。
Search(ST, key); //查找 ST 中其关键字等于kval 的数据元素。
Traverse(ST, Visit()); //按某种次序对 ST的每个元素调用函数 Visit()一次且仅一次,
} ADT StaticSearchTable
基本操作 P:
顺序表的查找
typedef struct {
ElemType *elem; // 数据元素存储空间基址,建表时
按实际长度分配,0号单元留空
int length; // 表的长度
} SSTable;
以顺序表表示静态查找表,则Search函数可
用顺序查找来实现。其顺序存储结构如下: