Featured image of post 第六章 查找 - 《数据结构导论》笔记
书籍

第六章 查找 - 《数据结构导论》笔记

目录

概要

分析查找运算的时间性能可以将“查找成功时的平均查找长度”作为评价查找算法时间性能的度量。

静态查找表

书中主要讨论查找操作在不同存储结构下的实现。

顺序表上的查找

静态查找表最简单的实现方法是以顺序表作为存储结构。

用C语言表示如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

const int maxSize = 20;
typedef struct
{
	int key;
} tableEle;
typedef struct
{
	tableEle data[maxSize+1];
	int lastEleIndex; // 最后一个数据元素的下标
} sequenceTable;

data[0]用于设置“岗哨”，不存储数据元素，以便简化查找运算的实现。

在以上存储结构上实现顺序查找Sequential Search操作的步骤如下：

  • 从表的最后一个数据元素位置开始，从后往前依次将各个位置的数据元素和给定值比较。
  • 如果相等，则查找成功，返回该下标位置作为结果。
  • 如果查找到第一个元素，仍然与给定值不等，则查找不成功。

算法如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 返回0表示查找失败。
int searchSequenceTable(sequenceTable table, int key)
{
	table.data[0].key = key;
	i = table.lastEleIndex;
	while (table.data[i].key != key) {
		i--;
	}
	return i;
}

该算法巧妙利用data[0]存储待查找的key，从而免去了每次查找都要检测表是否查找完毕，保证了while循环一定会终止，起到了岗哨的作用，这一改进对一次查找所花费的平均时间减少一半。

因此对于分析查找运算的时间性能，通常用“数据元素的值与给定值的比较次数”作为衡量查找算法的好坏依据，其中的比较次数称为查找长度。

例如：

  • 若待查找值在顺序表的第n个位置上，则查找长度为1。
  • 而待查找值在顺序表的第1个位置上，查找长度为n。

那么可以将查找成功时的平均查找长度记为ASL，作为评价查找算法时间性能的度量。

公式为：

$ASL=\displaystyle \sum^{n}_{i=1}P_iC_i$

  • $P_i$：查找第i个元素的概率，即给定值与顺序表中第i个元素值相等的概率，且$\displaystyle \sum^{n}_{i=1}P_i=1$。
  • $C_i$：表示在找到第i个元素时，顺序表中值与给定值已进行比较的个数。

假设顺序表为(b1, b2, b3)，查找b1，b2，b3的概率分别为0.2、0.2、0.6，则顺序查找法的平均查找长度为：

$(0.2\times3)+(0.2\times2)+(0.6\times1)=1.6$，即平均需要1.6次与给定值的比较才能找到待查找元素。

由于多种因素的影响，$P_i$的值是难以确定的，通常假设$P_i$概率相等，即对所有i，有$P_i=\frac{1}{n}$，并在此假设下确定查找算法的平均查找长度，因此得到顺序查找算法的平均查找长度为： $$ASL=\displaystyle \sum^{n}_{i=1}\frac{1}{n}\times(n-i+1)=\frac{n+1}{2}$$

有序表上的查找

二分查找

有序表：顺序表中的数据元素按照值的大小顺序排列。

思想：在有序表中，用给定值和表中间位置的值进行比较，确定值所在的区间，然后逐步缩小查找区间，重复这个过程直到找到或者确认找不到为止，简单点说就是每找一次，区间缩小为原来的二分之一，因此得名二分查找。

例如《幸运52》节目中的“看商品猜价格（13:40）”环节里，可以很好地应用二分查找的思想猜价格。

例如有一个有序表：(10, 13, 17, 20, 30, 55, 68, 89, 95)，需要找17的值，以下是过程：

  1. 确定搜索区间，low为1，即10的位置，high为9，即95的位置，区间就是[1, 9]。
  2. 取区间的中间位置，$(1+9)\div2=5$，也就是30，发现大了，往左重新确定搜索区间。
  3. 接下来要搜索的区间是[1, 4]。
  4. 取中间位置，$(1+4)\div2=2.5$，向下取整，为2，也就是13，发现小了，往右重新确定搜索区间。
  5. 接下来要搜索的区间是[3, 4]。
  6. 取中间位置，$(3+4)\div2=3.5$，为3，也就是17，成功找到。

总结规律：

  • 二分查找的查找长度不超过⌊log2n⌋-1。
  • 二分查找的平均查找长度为：$ASL_b = \frac{n+1}{n}log_2(n + 1) - 1$。
    • 当n较大时可得：$ASL_b \approx log_2(n + 1) - 1$。
    • 因此二分查找算法的时间复杂度为O(logn)。

散列表

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

本文中键值是指一个东西，键值和值是两个东西。例如拿数组来说，键值是指下标，值就是下标指向的值。

  • 散列函数：数据元素的键值和存储位置之间建立的对应关系，也称为哈希（hash）函数。
  • 散列值：经过散列函数处理以后的值，也称哈希值、哈希码。
  • 散列：指用键值通过散列函数来获取存储位置的映射过程。
    • 散列地址：指其中的存储位置。
  • 散列表（Hash Table）：通过散列进行存储的方式，即这种存储结构。
  • 冲突：也称哈希冲突，设有散列函数H，键值key有k1、k2，k1≠k2，冲突是指$H(k1)=H(k2)$。
    • 即不同的键值散列到了同一个存储位置上。
    • 这种情况在实际应用中经常出现，只能尽可能减少而不能完全避免。

因此使用散列技术时需要考虑两个问题：

  1. 如何构造均匀的散列函数？
  2. 用什么方法有效地解决冲突？

散列法

数字分析法

数字分析法（Digit Analysis Method），大概说一下它的思想：

  1. 将键值经过转换成数字。
    • 例：abc转换成了301482。
  2. 再将数字进行分析，取出这些数字或者这些数字中的一部分。
    • 例：将这些数字拆成单独的一个个数字，3，0，1，4，8，2。
  3. 将这些数字通过某种方式组织成一个值，这个值就是散列值。
    • 例：把这些数字加起来，得到18。

除留余数法

是一种简单有效且最常用的方法。

它的基本思想是：

  1. 将键值转换成非负整数。
  2. 将该整数除以n（一般是散列表的长度），并取余数，这个余数就是散列值。
    • 例如：整数37，n是10，37除以10，得到商3和余数7。
    • 这个过程在C语言中可以用%进行运算。

在书中的表示是：$H(key) = key {\quad} mod {\quad} p(p{\leq}n)$

  • mod是指取余运算。
  • p是指除数（正整数）。

该方法对p的选取比较关键，通常选n为小于散列表长度的素数。

素数是指除了1和自身，再没有其他正整数能够整除它。

  • 例如2、3、5、7、11都是素数。

如果p选的不合适的情况下，容易发生冲突，会遇到以下的问题：

  • 遇到奇数键值，散列值总是得到奇数。
  • 遇到偶数键值，散列值总是得到偶数。

平方取中法

平方取中法（Square-Then-Choose Method）是一种简单的伪随机数生成算法。

它的基本思想是：

  1. 先将某个种子值进行平方运算。
  2. 再从中间选取若干位作为新的种子值。
  3. 重复以上过程直到得到想要的随机数。

而用在散列函数中，因为计算简单，也是一种较为常用的方法。

一般步骤如下：

  1. 将键值转换为一个初始种子值x0，x0是数字。
  2. 对x0进行平方运算，得到x1。
  3. 从x1的中间取出若干位作为值，这个值就是散列值。

基数转换法

…

散列冲突解决

冲突解决的核心思想：给冲突的键值找一个空闲的散列地址，如果仍然冲突，重复这个过程，直到不发生冲突为止。

那么接下来就是介绍都有哪种方式去找一个空闲的散列地址。

线性探测法

设H(key)=d，d是散列值，散列表容量为m，那么线性探测法找一个空闲的散列地址遵循以下的规律：

  • d+1。
  • d+2。
  • d+3。
  • …。
  • m-1。
  • 0。
  • 1。
  • 2。
  • …。
  • d-1。

举个例子，有长度13（即m=13）的散列表，存储地址的下标有0-12，采用除留余数法进行散列，表中已有16、30、54的元素，分别位于下标为3、4、2的存储空间。

此时插入一个键值为29的元素，散列函数求出散列地址为3，即下标为3，而下标为3已经被占用了，采用线性探测法进行冲突解决，过程如下：

  • 进行第一次找空闲空间，d+1，即3+1，找到了下标为4的空间，发现仍然被占用。
  • 继续第二次找空间空间，d+2，即3+2，找到了下标为5的空间，是空闲的，那就将29放到这个空间里。

线性探测法：当键值冲突时，将得到的散列值按照顺序依次往后寻找空闲的空间，直到散列值下标的前一个空间为止。

可以看出寻找空闲散列地址的计算过程（书上称为生成后继散列地址）还是很简单的。

但是，存在一个问题：以键值16和29为例，它们并不相同（书上称为不是同义词）却发生了冲突。

这种非同义词之间对同一个散列地址的争夺现象称为堆积。

因为某个键值冲突而被安排到一个空闲空间，而本该被分配到这个空闲空间的键值出现时，又因为被占用，而需要重新寻找空闲空间。

这个方法实际上非常容易出现堆积现象，意味着插入时间复杂度非常高，特别是在散列表快满了的时候。

二次探测法

思想：生成的后续散列地址不是连续的，而是跳跃式的，目的是减少堆积问题。

二次探测法找一个空闲的散列地址遵循以下的计算方式： $$d_0 = H(key)$$ $$d_i = (d_0 \pm i){\quad}mod{\quad}m$$ 其中i的规律是：

  • $i = 1^2$
  • $i = -1^2$
  • $i = 2^2$
  • $i = -2^2$
  • $i = 3^2$
  • $i = -3^2$
  • …
  • $i = {\pm}k^2(k \leq\frac{m}{2})$

举个例子，有长度11（即m=11）的散列表，存储地址的下标有0-10，采用除留余数法进行散列，序列为：（20，38，16，27，5，23，56，29），建立出对应的散列表以及计算出等概率的情况下查找成功的平均查找长度。

以下是过程：

  • 20取余，得到下标9。
    • 查找长度为1，经过1次散列函数才找到。
  • 38取余，得到下标5。
  • 16取余，得到下标5，发生冲突。
    • 寻找第一次空闲空间：$(5 + 1^2){\quad}\%{\quad}11$，得到下标6，空间空闲可用（以下可用时不再赘述）。
    • 查找长度为2，经过2次散列函数才找到（以下同理不再赘述）。
  • 27取余，得到下标5，发生冲突。
    • 寻找第一次空闲空间：$(5 + 1^2){\quad}\%{\quad}11$，得到下标6，空间被（16）占用。
    • 第二次空闲空间：$(5 - 1^2){\quad}\%{\quad}11$，得到下标4。
  • 5取余，得到下标5，发生冲突。
    • 寻找第一次空闲空间：$(5 + 1^2){\quad}\%{\quad}11$，得到下标6，空间被（16）占用。
    • 第二次空闲空间：$(5 - 1^2){\quad}\%{\quad}11$，得到下标4，空间被（27）占用。
    • 第三次空闲空间：$(5 + 2^2){\quad}\%{\quad}11$，得到下标9，空间被（20）占用。
    • 第四次空闲空间：$(5 - 2^2){\quad}\%{\quad}11$，得到下标1。
  • 23取余，得到下标1，发生冲突。
    • 寻找第一次空闲空间：$(5 + 1^2){\quad}\%{\quad}11$，得到下标2。
  • 56取余，得到下标1，发生冲突。
    • 寻找第一次空闲空间：$(5 + 1^2){\quad}\%{\quad}11$，得到下标2，空间被（23）占用。
    • 第二次空闲空间：$(5 - 1^2){\quad}\%{\quad}11$，得到下标0。
  • 29取余，得到下标7。

得出序列：

下标 0 1 2 3 4 5 6 7 8 9 10
序列 56 5 23 27 38 16 29 20
查找长度 1 1 2 3 5 2 3 1

等概率情况下查找成功的平均查找长度为：$ASL=\frac{1+1+2+3+5+2+3+1}{11}=\frac{18}{11}$。

链地址法

多重散列法

© 2023 - 2024 GHJayce
Built with Hugo
主题 Stack 由 Jimmy 设计