数据结构 第七章（查找算法）

写在前面：

1. 本系列笔记主要以《数据结构（C语言版）》为参考（本章部分图片来源于王道），结合下方视频教程对数据结构的相关知识点进行梳理。所有代码块使用的都是C语言，如有错误欢迎指出。
2. 视频链接：第01周a--前言_哔哩哔哩_bilibili

一、查找的基本概念

1、查找表

（1）查找表是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。

（2）对查找表经常进行的操作：

①查询某个“特定的”数据元素是否在查找表中。

②检索某个“特定的”数据元素的各种属性。

③在查找表中插入一个数据元素。

④删除查找表中的某个数据元素。

2、关键字

（1）关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。

（2）若一个关键字可以唯一地标识一个记录，则称此关键字为主关键字（对不同的记录，其主关键字均不同）；反之，称用以识别若干记录的关键字为次关键字。

3、查找

        查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功，此时查找的结果可给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。

4、动态查找表和静态查找表

        若在查找的同时对表执行修改操作（如插入和删除），则称相应的表为动态查找表，否则称之为静态查找表。

5、平均查找长度

（1）为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度ASL（关键字的平均比较次数）。

（2）对于含有n个记录的表，查找成功时的平均查找长度为，其中为查找表中第i个记录的概率，为找到表中其关键字与给定值相等的第i个记录时和给定值已进行过比较的关键字个数。

二、线性表的查找

1、顺序查找

（1）顺序查找的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等则查找成功，若查找整个表后仍未找到关键字和给定值相等的记录则查找失败。

（2）以顺序表作为存储结构时实现的顺序查找算法：

①顺序表及数据元素类型的定义：

typedef int KeyType;
typedef int InfoType;
typedef struct
{
	KeyType key;        //关键字域
	InfoType otherinfo; //其它域
}ElemType;
 
typedef struct
{
	ElemType* R;   //存储空间基地址
	int length;    //当前长度
}SSTable;

②在第二章中也有查找算法的具体实现，但是在当时的算法中每一步都要检测整个表是否查找完毕，也就是需要让循环变量i和顺序表的长度进行比较。为了改善算法的运行效率，可以闲置数组R的0号元素不用于存储，进入查找算法后把需要查找的值赋给0号元素，然后从顺序表的最后一个元素开始，逐个元素与0号元素比较，查找到目标元素后当即结束查找并返回元素的下标，当目标元素不在顺序表中时，查找算法遍历所有元素后最终会访问0号元素，这时必定会结束查找并返回0，代表要查找的元素不在顺序表中，如此，可以免去查找过程中每一步都要检测整个表是否查找完毕，不过需要牺牲一个元素的存储空间。

③算法具体实现：

int Search_Seq(SSTable ST, KeyType key)    //顺序查找
{
	ST.R[0].key = key;      //监视哨
	int i;
	for (i = ST.length; ST.R[i].key != key; i--);   //从后往前查找
	return i;
}

（3）顺序查找的优缺点：

①优点：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构（链式结构不用设置监视哨），无论记录是否按关键字有序均可应用。

②缺点：平均查找长度较大，查找效率较低，对于元素不在表中或者目标位置与开始查找位置相距较远的情况比较不友好。

（4）提高查找效率的办法：

①当记录的查找概率不相等时（比如某个人的知名度高，公示信息经常被其他人查找），可按查找概率的高低存储，查找概率越高，比较次数越少。

②如果记录的查找概率无法测定时（比如通讯录中的一部分电话号码需要经常拨打，一部分基本不拨打，一段时间后过去某个常拨打的电话可能也基本不拨打），可按查找概率动态调整记录顺序，这需要在每个记录中设一个访问频度域，始终保持记录按非递增有序的次序排列（以访问频度排序），或者每次查找后均将刚查到的记录直接移至表头。

2、折半查找

（1）折半查找也称二分查找，它是一种效率较高的查找方法，但是折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。在下面及后续的讨论中，均假设有序表是有序递增的。

（2）折半查找的查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等则查找成功，如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。

（3）折半查找每一次查找都使查找范围缩小一半，与顺序查找相比，显著地提高了查找效率。

（4）折半查找过程可用二叉树来描述，树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。把当前查找区间的中间位置作为根，把左子表和右子表分别作为根的左子树和右子树，由此得到的二叉树称为折半查找的决策树。

①折半查找法在查找成功时进行比较的关键字个数最多不超过树的深度，而决策树的形态只与表记录个数n相关，与关键字的取值无关，具有n个结点的决策树的深度为，所以对于长度为n的有序表，折半查找法在查找成功时和给定值进行比较的关键字个数至多为。

②在决策树中所有结点的空指针域上加一个指向一个方形结点的指针，并且称这些方形结点为决策树的外部结点（与之相对，称那些圆形结点为内部结点），那么折半查找时查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数，因此折半查找在查找不成功时和给定值进行比较的关键字个数最多也不超过。

（5）算法具体实现：

①非递归实现：

int Search_Bin(SSTable ST, KeyType key)    //折半查找的非递归算法
{
	int left = 1;            //最左端
	int right = ST.length;   //最右端
	while (left <= right)     //查找区间不为空（左指针不大于右指针）
	{
		int mid = (left + right) / 2;
		if (key == ST.R[mid].key)   //查找成功
			return mid;
		else if (key < ST.R[mid].key)   //目标值在当前位置左侧，右指针左移
			right = mid - 1;
		else                            //目标值在当前位置右侧，左指针右移
			left = mid + 1;
	}
	return 0;  //查找区间为空，说明欲查找的值不在表中，返回0
}

②递归实现：

int Search_Bin(SSTable ST, KeyType key, int low, int high)  //折半查找的递归算法
{
	
	if (low > high)
		return 0;  //查找区间为空，说明欲查找的值不在表中，返回0
	int mid = (low + high) / 2;
	if (key == ST.R[mid].key)
		return mid;
	else if (key < ST.R[mid].key)
		return Search_Bin(ST, key, low, mid - 1);
	else
		return Search_Bin(ST, key, mid + 1, high);
}

（6）折半查找的优缺点：

①优点：比较次数少，查找效率高，该算法的时间复杂度为。

②缺点：对表结构要求高，只能用于顺序存储的有序表，所以该算法不太适用于数据元素经常变动的线性表（因为要经常排序）。

3、分块查找

（1）分块查找又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的查找方法。在此查找方法中，除表本身以外，尚需建立一个“索引表”。表本身可分为若干个子表（子表中记录数不宜过少），对每个子表（或称块）建立一个索引项（存储在索引表中），其中包括两项内容——关键字项（其值为该子表内的最大关键字）和指针项（指示该子表的第一个记录在表中的位置）。

（2）索引表按关键字有序，则表有序或者分块有序（块内无序、块间有序）。所谓“分块有序”指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，依次类推。

（3）由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找或折半查找，而块中的记录是任意排列的，则在块中只能用顺序查找。

（4）设表中有n个记录均匀分成b块，每块有s个记录。

（5）分块查找的优缺点：

①优点：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

②缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。