408数据结构-查找的基本概念，顺序查找 自学知识点整理

（感觉第七章似乎比第六章还难，不过既然学了，就要有始有终才好）

查找的基本概念

1. 查找：在数据集合中寻找满足某种条件的数据元素的过程称为 查找 。查找的结果一般分为两种：一是 查找成功 ，即在数据集合中找到了满足条件的数据元素；二是 查找失败 。
2. 查找表（查找结构）：用于查找的数据集合称为 查找表 ，它由同一类型的数据元素（或记录）组成。对查找表的常见操作有：①查询符合条件的数据元素；②插入、删除数据元素。
3. 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找的结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地表示一名学生。
4. 平均查找长度（$ASL$, $AverageSearchLength$）：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为：$$ASL=\sum _{i=1}^n{P}_i{C}_i$$
   式中，$n$是查找表的长度；$P_i$是查找第$i$个数据元素的概率，一般认为每个数据元素的查找概率相等，即$P_i=1/n$；$C_i$是找到第$i$个数据元素所需进行的比较次数。
   评价一个查找算法的效率时，通常考虑查找成功/查找失败两种情况的$ASL$，$ASL$的数量级反应了查找算法的时间复杂度，因此$ASL$是衡量查找算法效率的最主要的指标。

对查找表的常见操作

①查找符合条件的数据元素；
②插入、删除某个元素。
若一个查找表的操作只涉及操作①，无须动态地修改查找表，则此类查找表称为静态查找表。设计相应的算法和数据结构时只需要关注查找速度即可。
与此对应，需要动态地插入或删除的查找表则称为动态查找表。除了查找速度，也要关注插/删操作是否方便实现。
适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有二叉排序树的查找、散列查找等。

二叉排序树⭐
左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字，左右子树又各是一棵二叉排序树，这样的二叉树被称为二叉排序树。（之后的博客会写）

顺序查找

顺序查找 又称 线性查找 ，通常用于线性表（顺序表/链表）。
对于顺序表，可通过数组下标递增来扫描每个元素；对于链表，可通过指针$next$来依次扫描每个元素。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找。

1. 一般线性表的顺序查找

作为一种最直观的查找方法，其基本思想为：①从线性表的一端开始，逐个检查关键字是否满足给定的条件；②若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；③若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

typedef struct {//查找表的数据结构（顺序表）
	ElemType* elem;//动态数组基址
	int TableLen;//表的长度
}SSTable;

inline int Search_Seq(SSTable ST, ElemType key) {
	ST.elem[0] = key;//“哨兵”
	int i = ST.TableLen;
	for (; ST.elem[i] != key; --i);//从后往前找
	return i;//若查找成功，则返回元素下标；若查找失败，则返回0
}

上述算法中，将$ST.elem[0]$称为 哨兵 ，引入它的目的是使得$Searc{h}_{S}eq$内的循环不必判断数组是否会越界。算法从尾部开始查找，若找到$ST.elem[i]==key$，则返回$i$值，查找成功。否则一定在查找到$ST.elem[0]==key$时跳出循环，此时返回的是$0$，查找失败。引入“哨兵”的目的是避免很多不必要的判断语句，提高程序效率。

完整代码可看我的Github：传送门

2. 有序线性表的顺序查找

若在查找之前就已知表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低查找失败的平均查找长度。假设表$L$是按关键字从小到大排序的，查找的顺序是从前往后，待查找元素的关键字是$key$，当查找到第$i$个元素时，发现第$i$个元素的关键字小于$key$，但第$i+1$个元素的关键字大于$key$，这时就可返回查找失败的信息，因为第$i$个元素之后的元素的关键字均大于$key$，所以表中不存在关键字为$key$的元素。

(图片来自王道考研408数据结构2025)

如图，可以用一棵判定树来描述有序线性表的查找过程。树中的圆形结点表示有序线性表中存在的元素；矩形结点称为 失败节点 （若有$n$个结点，则相应地有$n+1$个查找失败结点），它描述的是那些不在表中的数据值的集合。若查找到矩形结点，则说明查找失败。失败的man

在有序线性表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于其父结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下为：$$AS{L}_{不成功}=\sum _{j=1}^n{q}_i\left(l_j-1\right)=\frac{1+2+\cdots +n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$$
式中，$q_j$是到达第$j$个失败结点的概率，在相等查找概率的情形下，它为$1/(n+1)$；$l_j$是第$j$个失败结点所在的层数。当$n=6$时，$AS{L}_{不成功}=6/2+6/7\approx 3.86$，比一般的顺序查找好一些。
一个成功结点的查找长度则等于其自身所在层数。

需要注意的是，有序线性表的顺序查找和后面的折半查找的思想是不一样的，且有序线性表的顺序查找中的线性表可以是链式存储结构，而折半查找中的线性表只能是顺序存储结构。

实际上，无论如何优化，顺序查找的时间复杂度均是$O(n)$。

本小节的重点考察内容是查找判定树的画法，以及如何根据查找判定树计算$ASL$。
以上。