文档介绍：第8章查找表
11/10/2017
1
计算机教研室
基本概念
查找表是由同一类型的数据元素(或记录)构成的集合。
由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。
对查找表经常进行的操作:
1)查询某个“特定的”数据元素是否在查找表中;
2)检索某个“特定的”数据元素的各种属性;
3)在查找表中插入一个数据元素;
4)从查找表中删去某个数据元素。
11/10/2017
2
计算机教研室
查找表可分为两类
静态查找表
仅作查询和检索操作的查找表。
动态查找表
有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;或者,从查找表中删除其“查询”结果为“在查找表中”的数据元素。
11/10/2017
3
计算机教研室
关键字是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)。
若此关键字可以识别唯一的一个记录,则称之谓“主关键字”。若此关键字能识别若干记录,则称之谓“次关键字”。
查找根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。
若查找表中存在这样一个记录,则称“查找成功”。查找结果给出整个记录的信息,或指示该记录在查找表中的位置;
否则称“查找不成功”。查找结果给出“空记录”或“空指针”。
11/10/2017
4
计算机教研室
如何进行查找?
查找的方法取决于查找表的结构。
由于查找表中的数据元素之间不存在明显的组织规律,因此不便于查找。
为了提高查找的效率, 需要在查找表中的元素之间人为地附加某种确定的关系,换句话说, 用另外一种结构来表示查找表
静态查找表
动态查找树表
哈希表
11/10/2017
5
计算机教研室
静态查找表
抽象数据类型
ADT StaticSearchTable {
数据对象D:
D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字,可唯一标识数据元素
数据关系R:
数据元素同属一个集合。
基本操作 P:
Create(&ST, n);
Destroy(&ST);
Search(ST, key);
Traverse(ST, Visit());
} ADT StaticSearchTable
11/10/2017
6
计算机教研室
静态查找表的存储
静态查找表基本上不采用插入和删除操作,因此通常以顺序存储结构的线形表或有序表存储
假设静态查找表的顺序存储结构为
typedef struct {
ElemType *elem;
// 数据元素存储空间基址,建表时按实际
// 长度分配,0号单元留空
int length; // 表的长度
} SSTable;
数据元素类型的定义为:
typedef struct {
keyType key; // 关键字域
……// 其它属性域
} ElemType
11/10/2017
7
计算机教研室
顺序查找表
以顺序表或线性链表表示静态查找表
回顾顺序表的查找过程:
int LocateElem_Sq( SqList L, ElemType e)
{
// 在顺序线性表 L 中查找第 1 个值与 e 相等的数据元素,
// 若找到,则返回其在 L 中的位序,否则返回 0
i = 1; // i 的初值为第 1 个元素的位序
p = ; // p 的初值为第 1 个元素的存储位置
while (i <= && *p++ != e ) ++i; // 依次进行判定
if (i <= ) return i; // 找到满足判定的数据元素为第 i 个元素
else return 0; // 该线性表中不存在满足判定的数据元素
} // LocateElem_Sq
11/10/2017
8
计算机教研室
以顺序表或线性链表表示静态查找表
假设给定值 e=64,
要求 [k] = e, 问: k = ?
21
37
88
19
92
05
64
56
80
75
13
0 1 2 3 4 5 6 7 8 9 10 11
k
k
11/10/2017
9
计算机教研室
设置“哨兵”
i
i
60
i
key=64
key=60
i
64
11/10/2017
10
计算机教研室