数据结构导论【六】之 查找表

接上一篇：数据结构导论【五】之 图

一、基本概念

查找表 – 由同一类型的数据元素(或记录)构成的集合。
关键字(键) – 用来标识数据元素的数据项称为关键字，简称键；其值称为键值。
主关键字 – 可唯一标识各个数据元素的关键字。
查找 – 根据给定的某个k值，在查找表寻找一个其键值等于k的数据元素。
静态查找表 – 进行的是引用型运算
动态查找表 – 进行的是加工型运算。

二、静态查找表的实现

const int maxsize = 20; // 静态查找表的表长
typedef struct {
	TableElem elem[maxsize + 1]; // 一维数组，0号单元留空
	int n; // 最后一个元素的下标，也即表长
} SqTable;

typedef struct {
	keyType key; // 关键字域
	... // 其他域
} TableElem;
1
2
3
4
5
6
7
8
9
10

1.顺序表上的查找 – 顺序查找

a.过程

从表中最后一个记录开始顺序进行查找，若当前记录的关键字等于给定值，则查找成功；否则，继续查上一记录…；若直至第一个记录尚未找到需要的记录，则查找失败。

b.算法

方法一：使用一种设计技巧：设立岗哨

int SearchSqtable(Sqtable T, KeyType key) {
	// 在顺序表R中顺序查找其关键字等于key的元素。
	// 若找到，则函数值为该元素在表中的位置，否则为0.
	T.elem[0].key = key;
	i = T.n;
	while(T.elem[i].key != key) i--;
	return i;
}
1
2
3
4
5
6
7
8

c.算法分析

成功查找：ASL = (n + 1) / 2
不成功查找：ASL = n + 1

---

顺序查找优点：简单，对表无要求；
顺序查找缺点：比较次数多。

---

2.有序表上的查找 – 二分查找

a.二分查找思想

二分查找的前提条件：顺序方式存储、且元素按关键字有序。

---

二分查找的逻辑步骤：
每次找中项，中项是的话，则找到；
中项不是的话，根据此中项的关键字与给定关键字的关系，决定在表的前或后半部继续找。

关键点：可使下次查找范围缩小一半。

---

b.二分查找过程

表头指针low = 1，表尾指针high = n。
1.求中间点：mid = (low + high) / 2; // 结果向下取整，抛弃小数部分
{item[1], …, item[mid - 1], item[mid], item[mid + 1], …, item[n]}
2.给定关键字k与中项记录关键字比较
①K < item[mid].key，则所查记录落在表的前半部；继续在前半部找，此时low不变，high = mid - 1
②K = item[mid].key，则查找成功，中项即是，结束；
③K > item[mid].key，则所查记录落在表的后半部；继续在后半部找，此时low = mid + 1，high不变
3.若low <= high，则转(1)，否则查找不成功。

c.二分查找算法

int SearchBin(SqTable T, KeyType key) {
	// 在有序表R中二分查找其关键字等于K的数据元素；若找到，则返回改元素在表中的位置，否则返回0
	int low, high;
	low = 1;
	high = T.n;
	while (low <= high) {
		mid = (low + high) / 2;
		if (key == T.elem[mid].key) {
			return mid;
		} else if (key < T.elem[mid].key) {
			hight = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

d.例：（在下列有序顺序表中查找 K = 18）

e.算法分析

查找成功时：比较次数最多为 log₂n 向下取整 + 1；
查找失败时：比较次数最多也为 log₂n 向下取整 + 1；

二分查找算法每进行一次键值与给定值的比较，查找区间的长度至少减小为原来二分之一，『二分查找』由此得名。由此易推算出二分查找的查找长度不超过log₂n 向下取整 + 1。

二分查找的平均查找长度为：

当n较大时可得：

---

由此可见，二分查找的时间性能比顺序查找好。而相比顺序查找而言，二分查找要求表元素是排好序的。当采用的存储结构不是顺序表，或者顺序表中元素未按键值的次序（递增或递减）排列时，则不能进行二分查找。

---

3.索引顺序表的查找 – 分块查找

a.查找过程

1. 先建立最大（或小）关键字表 – 索引表（有序）
   即将每块中最大（或最小）关键字及指示块首记录在表中位置的指针依次存入一张表中，此表称为索引表；
2. 查找索引表，以确定所查元素所在块号；
   将查找关键字k与索引表中每一元素（即各块中最大关键字）进行比较，以确定所查元素所在块号；
3. 在相应块中按顺序查找关键字为k的记录。

---

b.例

c.算法分析

分块查找的平均长度等于俩阶段各自的查找长度之和。若每块含S个元素，且第一阶段采用顺序查找，则在等概率假定下，分块查找的平均查找长度为

其中，n为顺序表中的数据元素数目。当s取$\sqrt{n}$时，ASL_bs达到最小值$\sqrt{n+1}$。

静态查找表的上述三种不同实现各有优缺点。
其中：
顺序查找效率最低，但限制最少。
二分查找效率最高，但限制最强。
而分块查找则介于上述二者之间。
在实际应用中应根据需要加以选择。

---

三、动态查找表（二叉排序树）

表结构是在查找过程中动态生成的；对于给定值k，若表中存在其关键字等于k的记录，则查找成功返回，否则在表中插入关键字等于k的记录。

1.二叉排序树

一颗二叉排序树（Binary Sort Tree）(又称二叉查找树)或者是一颗空二叉树，或者是具有下列性质的二叉树；
①若它的左子树不空，则左子树上所有结点的键值均小于它的根结点键值；
②若它的右子树不空，则右子树上所有结点的键值均大于它的根结点键值；
③根的左、右子树也分别为二叉排序树。

---

性质：
中序遍历一颗二叉排序树所得的结点访问序列是键值的递增序列。

---

2.二叉排序树上的查找

a.过程

当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功；否则根据给定值与根结点关键字间的大小关系，分别在左子树或右子树上继续进行查找。

---

b.二叉排序树查找算法

注：
1.二叉排序树，对每个结点，均有：
左子树上的所有结点键值都比根的小；
右子树上的所有结点键值都比根的大。
2.构造二叉排序树的同时也对序列排序了。

BinTree SearchBST(BinTree bst, KeyType key) {
	// 在根指针bst所指的二叉排序树上递归地查找键值等于key的结点。若成功，则返回指向该结点的指针，否则返回空指针
	// 不成功时返回NULL作为标记
	if (bst == NULL) {
		return NULL;
	} else if (key == bst -> key) { // 成功时返回结点地址
		return bst;
	} else if (key < bst -> key) { // 继续在左子树中查找
		return SearchBST(bst -> lchild, key);
	} else { // 继续在右子树中查找
		return SearchBST(bst -> rchild, key); 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

PS：由上面的查找过程可知：在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根结点到待查结点的路径；若查找不成功，则是从根节点出发走了一条从根到某个叶子的路径。因此与二分查找类似，关键字比较的次数不超过二叉树的深度。

c.二叉排序树的插入和生成

对序列R={k1, k2, …, kn}, k1 ~ kn均为关键字值，则按下列原则可构造二叉排序树：
1.令k1为根；
2.若k1 < k2,则令k2为k1的右孩，否则为左孩；
3.k3,k4,…kn递归重复（2）

---

例题：查找键值序列为{50, 48，24, 55, 53, 50, 90},则生成的二叉排序树如图6-6所示。

---

二叉排序树的查找分析：
二叉排序树上的平均查找长度是介于O(n)和O(log₂n)之间的，其查找效率与树的形态有关。

假设5个元素的查找概率相等均为$\frac{1}{5}$
则图6-7 a的平均查找长度为ASL(a) = $\frac{1+2+2+3+3}{5}$ = $\frac{11}{5}$

需要在二叉排序树的动态变化过程中随时调整其形态，使之保持『平衡』。二叉排序树的平均查找长度 ASL <= 1 + log₂n。

---

四、散列表（哈希表）

散列函数（哈希函数） – 设记录表A，长为n，ai(1 <= i <= n)为表中某一元素，ki为其关键字，则关键字ki和元素ai在表中的地址之间有一函数关系，
即： Addr(ai) = H(Ki)

ai在表中地址。
散列函数：关键字与元素地址的函数

为了使数据元素的存储位置和键值之间建立某种联系，以减少比较次数，可以用散列技术实现动态查找表。

散列地址 – 由散列函数决定数据元素的存储位置，该位置称为散列地址。

---

散列查找：

散列表 – 通过散列法建立的表称为散列表。

冲突：
k1 != k2 但H(k1) = H(k2)的现象称为冲突。
即：不同的关键字映射到同一存储单元。
并称k1和k2是同义词。


散列法主要工作：
1.选择一个好的散列函数
2.解决冲突


PS：函数计算简便，运算速度快
随机性好，地址尽可能均匀分布
冲突小

1.常用散列法

a.数字分析法

b.除留余数法

散列函数：取关键字被某个不大于散列表长m的数p除后所得余数作为散列地址。
即：H(key) = key mod p (p <= n)


方法关键 – 如何取p？
结论:
①p不取偶数
②p不取关键字字符基的n倍
③一般选p为质数且最接近表长m的质数

---

c.平方取中法

平方取中法以键值平方的中间几位作为散列地址。这一方法计算简单，是一种较常用的构造散列函数的方法，通常在选定散列函数时不一定能知道键值的分布情况。取其中哪几位也不一定合适，而一个数平方的中间几位与这个数的每一位都有关，所得散列地址比较均匀。

---

d.基数转换法

2.处理冲突的几种方法

①链地址法

用『链地址法』处理冲突
思想 ： 将散列地址相同记录存储在同一单链表中（称同义词表），同时按散列地址设立一个表头指针向量。

---

链地址是对每一个同义词都建一个单链表来解决冲突，其组织方式如下：
设选定的散列函数为H，H的值域（即散列地址的范围）为 0 ~(n - 1)。设置一个『指针向量』Pointer HP[n],
其中的每个指针HP[i]指向一个单链表，该单链表用于存储所有散列地址为i的数据元素。每一个这样的单链表称为一个同义词子表。

例如，若选定的散列函数为H(key) = key mod 13,已存入键值为26、41、25、05、07、15、12、49、51、31、62的散列表，如图6-10所示。

---

②线性探测法

用『线性探测法』处理冲突构造散列表
思想： 计算出的散列地址已被占用，则按顺序找"下一个"空位。
过程： 设有散列表HT(向量)，对给定记录R，其关键字k，对应哈希地址H(k) => j

要点：
①HT[j]空，则R填入；
②HT[j].key = k，则输出；
③否则，按顺序一步步找『下一个』空位，将R填入。

例：已知一组关键字为（13， 41， 15， 44， 06， 68， 25，12，38，64，19，49），按散列函数H(key) = key mod 13 和 线性探测法 处理冲突构造散列表。

---

散列法的优缺点：
优点：直接由关键字通过哈希函数计算出哈希地址，查找效率高；
缺点：常发生冲突，影响查找效率。

---

③二次探测法：

二次探测法的基本思想：生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下空间从而减少堆积。按照二次探测法，键值key的散列地址序列为d₀=H(key);

di = (d₀ + i) mod m；

其中，m 为散列表的表长， i = 1², -1², 2³,…,± k²(k <= m / 2)。

例题：
如图 6-9 所示长度为13的散列表中，用二次探测法插入键值为29的元素。

分析:当发生冲突时，应用二次探测法，得到下一个地址d1 = (3 + 1²) mod 13 = 4仍冲突，则再求下一个地址d₂ = (3 - 1²) mod 13 = 2仍冲突，直到散列地址为d₃ = (3 + 2²) mod 13 = 7时其位置上没有元素，即元素填入散列表中序号为7的位置。

二次探测法的缺点是不易探测到整个散列表的所有空间，也就是说，上述后继散列地址可能难以包括散列表的所有存储位置。

---

④多重散列法

此法要求设立多个散列函数Hi， i = 1， …, k。当给定值 key 与散列表中的某个键值是相对于某个散列函数式的同义词而发生冲突时，继续计算这个给定值key在下一个散列函数H_i+1下的散列地址，直到不再产生冲突为止。这种方法的优点是不易产生 『堆积』 ，缺点是计算量较大

---

⑤公共溢出区法

按这种方法，散列表由俩个一维数组组成。一个称为基本表，它实际上就是上面所说的散列表，另一个称为溢出表。插入首先在基本表上进行，假如发生冲突，则将同义词存入溢出表。这样，基本表不可能发生『堆积』。

---

⑥总结

常用散列法：数字分析法、除留余数法、平方取中法、基数转换法。

散列表解决冲突的方法：线性探测法、二次探测法、链地址法、多重散列法、公共溢出区法。

---

五.小结

熟练掌握顺序表和有序表的查找方法和算法。

掌握二叉排序树的定义、构建方法和查找方法；

什么是散列方法、什么是冲突？

熟练掌握散列表的构造和查找及冲突的处理；

按定义计算各种查找方法在等概率情况下查找成功的平均查找长度。

---

---

---

下一篇：数据结构导论【七】之 排序