第六章：查找

1.查找的基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程。

查找的结果 查找成功和查找失败

查找表：用于查找的数据集合，由同一种数据类型(或记录)的组成，可以是一个数组或链表等数据类型

操作

查询某个特定的数据元素是否在查找表中
检索满足条件的某个特定的数据元素的各种属性
在查找表中插入一个数据元素
从查找表中删除一个数据元素

如果只有前连个操作的查找表称为：静态查找表，有上面四个操作的称为：动态查找表

关键字：数据元素中唯一标识该元素的某个数据项的值,使用基于关键字的查找,查找结果应该是唯一的

平均查找长度：查找时，关键字比较次数的平均值ASL

Pi：编号为i的数据元素的查找概率，我们一般假设每个元素的查找概率是相同的，那么n个元素的查找概率就是 1/n ，Ci：编号为i的元素的查找长度（注意这个公式代表的是查找成功的查找长度）

2.顺序查找

顺序查找：又称线性查找,主要用于在 线性表 中进行查找

其中这个线性表又分为有序和无序的，他们的查找方式不同。例如下图：我们给每一个人加上一个序号，这个序号就是关键字

2.1无序线性表

然后我们现在要查找7号人，我们则需要依次遍历整个线性表，才可以说此表中没有7号；即

对无序线性表进行顺序查找,查找失败时要遍历整个线性表

代码实现：

结构体是我们需要查找的查找表，查找函数中的ST.elem[0]=key，我们称为哨兵，它的作用下面讲：

首先我们查找是从后往前查找的，如果我们找到了关键字，那么返回下标，注意我们那个哨兵的值是key，所以这个循环一定会查找到，但是如果是匹配到最后一个元素，他返回值是0，0代表哨兵的位置，那么我们就可以判断查找失败，所以加这个哨兵其实就是相当于查找函数中可以少写一个判断。

这里每个元素的查找长度为n-i+1，每个元素的查找概率Pi=1/n，则它的平均查找长度为：

ASL失败=n+1

2.2有序线性表

我们要查找3号人，我从开始比较，最后在第三个位置找到，我们可以发现如果要查找的元素在查找表中，那么它的查找方式和无序表方式相同。那么如果我们如果查找4号人，我们从头开始比较，直到比较到5号后，还不相等，那么我们就不需要继续进行判断了，即

对关键字有序线性表进行顺序查找，查找失败时不一定要遍历整个线性表

这里查找成功的查找长度和上面的无序表一样，为了找查找失败的查找长度我们需要学习判定树

2.2判定树

判定树：描述查找过程的二叉排序树

例如有序线性表：（10，20，30，40，50），我们首先讲该有序表构造成一颗二叉排序树如下图：

二叉排序树：所有左子树值都比根节点小，所有右子树值都比根节点大

下面我们标出，每个结点之间查找失败的元素范围

我们称这些橘黄色的矩形范围内的结点为：失败结点

例如我们利用上面的二叉排序树查找值为30的结点，首先10!=20，根据二叉排序的特点我们继续查找右子树，然后20!=30，继续查找右子树，30==30查找成功；如果我们查找值为25的结点，首先10!=25，20!=25，30<25，所以我们要比较30的左子树，则查找失败。查找失败一定会走到对于的失败节点，并且我们发现对于顺序查找失败节点的层数减一就是比较次数

ASL失败=n/2 + n/(n+1) 这里我们看的是一个区间的失败结点的平均查找长度，整个数据元素我们是没法计算的，因为有无穷个元素

3.折半查找

上面我们讲的是顺序查找，即依次进行查找，比如我们查找6号元素，就如图所示6号元素比较靠后，那么我们查找的效率就比较慢，我们如果不是从第一个位置依次向后进行查找，而是从后往前或者从后半段进行查找，那么效率相比会高一点。

折半查找：又称二分查找，仅适用于有序的顺序表

算法思想

首先将给定值key与表中中间位置元素的关键字比较
若相等，则返回该元素的位置
若不等，则在前半部分或者是后半部分进行查找
重复该过程，直到找到查找的元素为止；或查找失败。(递归)

查找序列升序时

若key小于中间元素,则查找前半部分

若key大于中间元素,则查找后半部分

这里我们就可以看出为啥这里要求是顺序表；如果是链表，我们想找中间元素位置则需要遍历整个链表，而对于顺序表来说我们只需要除以2就可以找到中间元素的下标了

代码实现：

三个初始变量分别代表：我们查找部分的第一个元素下标，最后一个元素的下标和中间元素的下标

我们使用一个循环语句来执行这个折半查找过程，注意这里是low<=high，其中(low+high)/2，肯定会出现小数，而我赋值给一个整数，相当于取下界了，然后当前mid只需的关键字的值和我们要查找的相等则直接返回mid即可，如果大于我们要查找的关键字的值，此时我们要查找左边部分，所以令high=mid-1；如果小于我们要查找的关键字的值，我们要查找右边部分，所以令low=mid+1；如果循环结束还没查找到，则返回-1

折半查找的判定树

我们可以看出折半查找的二叉树的层数是比较少的，而层数代表比较的次数直接相关

ASL(成功)=Log2(n+1) -1 （判定树是满二叉树）

对于上图ASL(成功)=(1*1+2*2+3*4+4*4)/11=3，对于上图ASL(失败)，我们没有给出失败的例子，所以直接按照失败结点为单位进行计算ASL(失败)=(4*3+8*4)/12=11/3，这里一共有12个失败结点，第4层有4个失败结点，所以是4*(4-1)，第5层有8个失败结点所以是8*(5-1)

折半查找的时间复杂度为O(log2n) （以2为底，n的对数）

总结：顺序查找适用于顺序存储和链式存储，序列有序无序皆可。折半查找只适用于顺序存储，且要求序列一定有序

4.分块查找

分块查找我们将要查找的序列分成块，然后每一个块有一个名字，我查找的俺块进行查找，每一个块的名字是这块元素中值最大的那个。我们在查找的时候首先可以比较该元素和块的名称的大小，如果比该块大的话，找下一块，小或等于的话可以进入块进行比较。

分块查找：又称索引顺序查找，它吸取了顺序查找和折半查找各自的有点，既有动态结构，又适于快速查找。

如何分块 ？

将查找表分为若干子块。块内的元素可以无序，但块间是有序的，即对于所有块有第 i 块的最大关键字小于第 i+1 块的所有记录的关键字。
建立索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

即：块内无序块间有序

如何查找？

1、在索引表中确定待查记录所在的块,可以顺序查找或折半查找索引表

2、在块内进行顺序查找

比如我们要查找53这个元素，首先查找在哪一块，这里我们可以使用顺序查找也可以使用折半查找，加入我们使用顺序查找，此时查找到下标为3的这个索引表位置的时候因为 53<65，所以我们进入块内查找，此时只能使用顺序查找，接着我们查找到53元素。

平均查找长度

5.B树

B树 又称多路平衡查找树，B树中所有结点的孩子结点数的最大值称为B树的阶。

一棵m阶B树或为空树，或为满足如下特性的m叉树：

1)树中每个结点至多有m棵子树(即至多含有m-1个关键字)
2)若根结点不是终端结点，则至少有两棵子树
3)除根结点外的所有非叶结点至少有m/2 取上界棵子树(即m/2-1取上界-1个关键字)
4)非叶结点的结构
5)所有的叶子结点都出现在同一层次上，并不带任何信息

n是结点关键字的个数：m/2-1<n<m-1

Ki(i=1,2,...,n)为结点的关键字，k1<k2<....<kn

Pi(i=1,2,...,n)为子树根结点的指针，Pi-1所指子树的关键字均小于Ki,Pi所指子树的关键字均大于Ki，

观察上面的B树可以发现其实B树是由二叉排序树更改来的，这样的排序结果方便我们查找

这里需要注意，上边的B树的叶子结点都在第四次上，最后一层的结点有的地方作为虚拟的结点，有的则作为实际的一层存在

n个关键字，阶数为m，高度为h的B树，它对这个高度h有什么要求？

首先我们求h最小值，h何时最小？当B树每一个结点关键字的个数达到最大，即

解释：每个结点关键字个数达到最大，第一层有1个结点，第二层有m个结点，第三层有m^2个结点……每一个结点最多有m-1个关键字，所以乘以m-1，最后化简n<=m^h -1，移项化简即可得到h和n得关系

然后我们求h最大值，h何时最小？当B树每个结点关键字的个数达到最小，即

首先根节点至少有一个关键字，那么他有两个子树，而且这两个子树的每一个节点至少有m/2 -1个关键字，而且每个结点至少有m/2个子树，同理可以计算出第三层有多少个子树和关键字…..最后得到最后一层2(m/2)^(h-1)<=n+1，最终化简得到：，这个式子不需要记忆，一般都是给出要给一个例子，手动计算即可。

5.1查找

在B树中找结点（磁盘）
在节点中找关键字（内存）

5.2插入

1.定位

查找插入该关键字的位置，即最底层中的某个非叶子结点；规定一定是插入在最底层的某个非叶子结点内

2.插入

若插入后，不破会m阶二叉树的定义，即插入后结点关键字个数在属于区间[m/2 -1,m-1]，则直接插入

例如同样是上图B树，我们插入结点13：

若插入后，关键字数量大于m-1，则对插入后的结点进行分裂操作

分裂：插入后的结点中间位置(m/2)关键字并入父结点中，中间结点左侧结点留在原先的结点中，右侧结点放入新的节点中，若并入父节点后，父结点关键字数量超出范围，继续向上分裂，直到符合要求为止

例如同样是上图B树，我们插入结点19：

插入之后我们发现此时不满足，B树的定义了，所以我们要进行向上分裂操作，即将中间位置的结点并入父结点当中，然后左侧的19留在原来的结点当中，右侧的21我要加入到新的结点当中如下图：

此时我们发现分裂后任然不符合B树的定义，同样也要进行分裂操作：

然而分裂完成后，任然不符合B树定义，我们继续分裂，接着符合B树的定义：

5.3删除

删除操作我们要分情况进行讨论，把所有的结点分为非终端结点和终端结点：

对于终端节点的删除操作：

1. 直接删除：若被删除关键字所在结点关键字总数>m/2 -1，表明删除后仍满足B树定义可以直接删除
1. 兄弟够借：若被删除关键字所在结点关键字总数=m/2 -1（关键字的最小值），且与此结点邻近的兄弟结点的关键字个数≥m/2,则需要从兄弟结点借一个关键字，此过程需要调整该结点、双亲结点和兄弟结点的关键字

同样上图的B树，我们删除结点24：

此时我需要从兄弟节点中借一个关键字，假设我们从左兄弟借一个结点，首先我们从这两个兄弟结点中夹着的双亲结点23，放到我们删除24位置，然后我们将左兄弟结点中最大的那个放到刚才的23结点的位置上

3)兄弟不够借：若被删除关键字所在结点关键字总数=m/2 -1,且与此结点邻近的兄弟结点的关键字个数=m/2-1，则删除关键字，并与一个不够借的兄弟结点和双亲结点中两兄弟子树中间的关键字合并。合并后若双亲结点因减少一个结点导致不符合定义,则继续执行2、3步骤

如下图的B树，我们删除结点30

我们可以发现30这个结点的两侧的兄弟结点都不够借，所以我们要与一个不够借的兄弟结点和双亲结点中两兄弟子树中间的关键字合并。

对于非终端节点的删除操作：

1)若小于k的子树中关键字个数>m/2 -1,则找出k的前驱值k‘,并用k’来取代k,再递归地删除k即可。

2)若大于k的子树中关键字个数>m/2 -1，则找出k的后继值k‘，并用k’来取代k，再递归地删除k即可。
3)若前后两子树关键字个数均为m/2 -1，则直接两个子结点合并，然后删除k即可。

首先进行合并

然后再进行删除

6.B+树

B+树

一棵m阶B+树满足如下特性:

1)每个分支结点最多有m棵子树(子结点)
2)若根结点不是终端结点，则至少有两棵子树
3)除根结点外的所有非叶结点至少有m/2棵子树，子树和关键字个数相等
4)所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻结点按大小顺序连接起来
5)所有分支结点 (可视为索引的索引) 中仅包含他的各个子结点(下一级索引块)中关键字的最大值及指向其子结点的指针

B+树 vs B+树

1)在B+树中，具有n个关键字的结点值含有n棵子树，即每个关键字对应一棵子树；在B树中，具有n个关键字的结点含有n+1棵子树
2)在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树关键字的指针，不含有该关键字对应记录的存储地址
3)在B+树中，叶结点包含全部关键字即在非叶结点中出现的关键字也会出现在叶结点中；在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的

6.1查找

在B+树种，和B树不同的是，我们有两种查找方式，我们可以从树的根节点进行多路查找，也可以从树的最后一层进行顺序查找。

注意：在B+树中查找时，无论查找成功还是失败一定是查找大叶节点当中的值为止。

7.散列

7.1散列表

我们上面学习的顺序、折半、分块或者B树查找都是基于比较进行查找的，与下面我们讲的散列查找不同。首先我们讲一个小例子：

如上面的查找，如果我们使用平常的比较进行查找按照顺序依次进行查找。但是如果我们知道红色就是1号，黄色就是2号…..那我们如果将这种特性进行映射其实就相当于我们的散列。

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数

也就是通过这个函数传入一个关键字值，他就能返回此关键字对应的地址；但是我们需要注意的是这里的地址并不局限于只是地址，它还可以是数组的下标或索引的，只要能代表关键字即可。

例如：我们有一个数组，此时我们假设Hash(key)=key%3；此时我们用散列出的下标代表关键字的位置：6%3=0，所以对应的下标为0

散列表：根据关键字而直接进行访问的数据结构。他建立了关键字与存储地址之间的一种直接映射关系

那么既然它的查找效率更高，为什么没有得到推广呢?

因为这个方法存在冲突的问题，如上面我们通过取余3来找关键字存储的下标，假设我们现在还要存储关键字3，那么3%3=0；而0我们已经存储了6，这就冲突了。

冲突：散列函数可能会把多个不同的关键字映射到同一地址下的情况

这样的冲突其实是不可避免的，所以我们接下来的学习中主要是设计散列函数如何减小这种冲突发生的可能性，以及就算发生了冲突怎么样让其不影响我们的查找。

7.2散列函数

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数；（Hash(key)=Addr）

散列函数构造要求：

1)散列函数的定义域必须包含全部需要存储的关键字,而值域的范围则依赖于散列表的大小或地址范围。
2)散列函数计算出来的地址应该能等概率均匀分布在整个地址空间中,从而减少冲突的发生。
3)散列函数应尽量简单,能够在较短时间内计算出任一关键字对应的散列地址。

直接定值法： 直接取关键字的某个线性函数值为散列地址。 Hash(key)=a*key+b (其中a,b为常数)

特点：方法简单，不会产生冲突，若关键字分布不连续，则会浪费空间。

除留取余法： Hash(key)=key%p；p的取法：假定散列表表长为m,取一个不大于m但最接近或等于m的质数p

特点：选好p是关键，可以减少冲突的可能。

数字分析法： 适用于关键字已知的集合,若更换关键字则需要重新构造散列函数

如上图有8个关键字的二进制位，我们可以看到每个二进制数的前8为都是一样的，而后四位各不相同，所以如果我们将这后四位当作各个关键字的散列地址的计算的话，这样的方法就是数字分析法。

平方取中法： 这种方法取关键字的平方值的中间几位数作为散列地址

例如：512的平方是271441，假如我们选择7144作为该关键字的散列地址，那么这种方法就叫平方取中法。

特点：适用于关键字的每位取值不均匀或均小于散列地址所需要的位数。

折叠法： 将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址。

例如：5121252 可以分成521+125+2=648

特点：适用于关键字的位数多?而且关键字中的每位上数字分布大致均匀

7.3冲突处理

我们可以为产生冲突的关键字寻找下一个空的Hash地址；

上面的过程叫：开放地址法，我们还有一种方法叫拉链法。

开放定址法：是指可存放新表项的空闲地址既向它的同义词表项开放,又向它的非同义词表项开放。

如何计算增量序列?

线性探查法：容易产生堆积现象，堆积现象会大大降低查找效率
平方探测法
再散列法
伪随机序列法

在开放定址法中不能随便删除某个元素

拉链法：是指把所有同义词存放在一个线性链表中,这个线性链表由地址唯一标识,即散列表中每个单元存放该链表头指针。

拉链法适用于经常进行插入和删除的情况

查找步骤：初始化:Addr=Hash(key)

①检测查找表中地址为Addr的位置上是否有记录，若无记录，则返回查找失败；若有记录，则比较它与key值，若相等则返回成功，否则执行步骤②

②用给定的处理冲突方法计算“下一散列地址”，把Addr置为此地址，转入步骤①

例如我们在拉链法中查找28这个关键字，首先通过Hash(key)找到它的头指针地址，然后遍历这个头指针指向的单链表，一次比较即可。如果在开放定址法中，直接通过Hash(key)找到它的下标即可，如果下标对应的无记录，说明查找失败。28的Hash(key)为1，然后下标为1的值不是28，然后用给定的处理冲突方法计算“下一散列地址”，把Addr置为此地址，继续查找。

查找效率

散列表的平均查找长度依赖于散列表的填装因子

8.字符串模式匹配

8.1串

若两个串长度相等且每个对应位置的字符都相等时,称这两个串是相等的

子串 串中任意个连续的字符组成的子序列称为该串的子串,包含子串的串为主串

通常称字符在序列中的序号为该字符在串中的位置。子串在主创中的位置是以子串的第一个字符在主串的位置来表示的

我们用子串的第一个字符在主串的位置来表示字串的位置；例如：S2='World' 位置为7

8.2串的存储结构

1、定长顺序存储

# define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

2、堆分配存储

typedef struct{
    char *ch;
    int lenght;
}HString;

使用malloc()/free 进行申请和释放空间

3、块链存储表示

8.3串的基本操作

最小操作子集

8.4模式匹配

StrString(&Sub,S,pos,len) 子串截取 StrCompare(S,T) 字串比较

不依赖模式匹配的上面的两个函数（这里假设是定长的字符串，下标为0的地方不存储字符）