1 查找的基本概念
2 顺序查找法
3 分块查找法
4 折半查找法
5 B树及其基本操作、B+树的基本概念
B树的基本概念
一棵度为m的B树称为m阶B树，是一棵平衡的m路查找树，其定义是：
一棵m阶B树，或者是空树，或者是满足以下性质的m叉树：
(1)根结点或者是叶子结点，或者至少有两棵子树，至多有m棵子树；
(2)除根结点外，所有非叶子结点至少有⌈m/2⌉棵子树，至多有m棵子树；
(3)所有叶子结点都在树的同一层上。
(4)每个结点应包含如下信息：
其中n是结点中关键字的个数，且⌈m/2⌉-1≤n≤m-1，n+1为子树的棵树。
是关键字，且
，即递增。
为指向孩子结点的指针，且
所指向的子树中所有结点的关键字都小于
，
所指向的子树中的所有结点的关键字都大于
；
#define M 5 //根据实际需要定义B树的阶数
typedef struct BTNode {
int keyNum;//结点中关键字的个数
struct BTnode *parent;//指向父结点的指针
int key[M + 1];//关键字数组，key[0]未用
struct BTNode *ptr[M + 1];//子树指针向量
} BTNode;
B树的查找
类似二叉排序树的查找，所不同的是 B 树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功;否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码，查找失败。即在 B 树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。
int BT_seartch(BTNode *T, int K, BTNode *p) {
//查找关键字K，查找成功返回在结点中的位置及结点指针p；否则返回0及最后一个结点指针
BTNode *q;
p = q = T;
while (q != NULL) {
p = q;
q->key[0] = K;//设置查找哨兵
for (int i = q->keyNum; K < q->key[i]; i--) {
if (i > 0 && q->key[i] == K) {
return i;
}
q = q->ptr[i];
}
}
return 0;
}
B树的插入
B树的生成也是从空树起，逐个插入关键字。
插入时不是每插入一个关键字就添加一个叶子结点，而是首先在最低层的某个叶子结点中添加一个关键字，然后有可能“分裂”。
(1)插入思想
①在B树种查找关键字K，若找到，表明关键字已存在，返回；否则，K的查找操作失败于某个叶子结点，转②
②将K插入到该叶子结点中，插入时，若
※叶子结点的关键字数<m-1，则直接插入；
※叶子结点的关键字数=m-1，将结点“分裂”
(2)分裂方法
设待分裂结点p包含信息为：，从其中间位置分为两个结点：
。并将中间关键字
插入到p的父结点中，以分裂后的两个结点作为中间关键字
的两个子结点。
当把中间关键字插入到p的父结点后，父结点可能也不满足m阶B树的要求，则必须对父结点进行分裂，一直进行下去，直到没有父结点或分裂后的父结点满足要求。
当根结点分裂时，因没有父结点，则建立一个新的根，B树增高一层。
一棵三阶 B 树(2-3 树)，(b) 插入 30 之后; (c) 、(d) 插入 26 之后;(e)~(g) 插入 85 之 后; (h)~(j) 插入 7 之后变化如下图：
B树的删除
如果想要在 B 树上删除一个关键字，首先需要找到这个关键字所在的结点，从中删去这个关键字。若 N 不是叶子结点，设 K 是 N 中的第 i 个关键字，则将指针 所指子树中的最大关键字(或最小关键字)K’放在(K)的位置，然后删除 K’，而 K’一定在叶子结点上。
从叶子结点中删除一个关键字的情况是：
(1)若结点N中的关键字个数>⌈m/2⌉-1，在结点中直接删除关键字K。
(2)若结点N中的关键字个数=⌈m/2⌉-1，若兄弟结点关键字个数>⌈m/2⌉-1，则将兄弟结点的最大(或最小)关键字上移到父结点中，再把父结点中下移一个到结点N。
下图为删除65借用兄弟结点示例：
(3)若结点N的兄弟结点关键字数也=⌈m/2⌉-1，兄弟不可借。则删除关键字K，再将N、兄弟结点、父结点的某个关键字合并为一个结点，若因此使父结点不符合要求，继续合并。
下图演示了删除50(兄弟可借)和删除37(兄弟不可借且父结点兄弟也不可借)的删除过程：
在实际的文件系统中，基本上不使用B树，而是使用B树的一种变体，称为m阶树。
它与B树的主要不同是叶子结点中存储记录，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。
一棵 m 阶的 B+树和 m 阶的 B 树的差异在于:
(1)若一个结点有 n 棵子树，则必含有n个关键字；
(2)所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接。
(3)所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。
与B树相比，B+树不仅可以从根结点开始按关键字随机查找，而且可以从最小关键字起，按叶子结点的链接顺序进行顺序查找。在B+树上进行随机查找、插入、删除的过程基本上和B树类似。
在B+树进行随机查找时，若非叶子结点的关键字等于给定的K值，并不终止，而是继续向下直到叶子结点(只有叶子结点才存储记录)。
6 哈希(散列)表
哈希表的基本概念
基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。
哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。
哈希查找(又叫散列查找)：利用哈希函数进行查找的过程叫哈希查找。
冲突：对于不同的关键字，哈希值相同的现象叫冲突。
同义词：具有相同函数值的两个不同的关键字，称为该哈希函数的同义词。
设计散列表的方法
设计一个散列表应包括：
①散列表的空间范围，即确定散列函数的值域。
②构造合适的散列函数，使得对于所有可能的元素，函数值均在散列表的地址空间范围内，且出现冲突的可能尽量小。
③处理冲突的方法。
1.直接定址法
取关键字或关键字的某个线性函数作哈希地址，即H(key) = key 或 H(key) = a * key + b。
特点：直接定址法所得地址集合与关键字集合大小相等，不会发生重复，但实际中很少使用。
2.数字分析法
假设关键字集合中的每个关键字都是由 s 位数字组成(k1, k2, ..., kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。
此法仅适合于:能预先估计出全体关键字的每一位上各种数字出现的频度。
3.平方取中法
若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过“平方”扩大差别，同时平方值的中间几位受到整个关键字中各位的影响。
此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。
4.折叠法
若关键字的位数特别多，则可将其分割成几部分，然后取它们的叠加和为散列地址。可有:移位叠加和间界叠加两种处理方法。
(1)移位法:将各部分的最后一位对齐相加。
(2)间界叠加法:从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。此方法适合于:关键字的数字位数特别多。
5.除留余数法
H(key) = key % p p≤m (表长)
即取关键码除以 p 的余数作为散列地址。使用除留余数法，选取合适的 p 很重要，若散列表表长为 m，则要求 p≤m，且接近 m 或等于 m。p 一般选取质数，也可以是不包含小于 20 质因子的合数。
6.随机数法
H(key) = Random(key)，其中，Random 为伪随机函数。
通常，此方法用于对长度不等的关键字构造散列函数。实际造表时，采用何种构造散列函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。
冲突处理的方法
冲突处理：出现冲突时，为冲突元素找到另一个存储位置。
1.开放定址法
基本方法：当冲突发生时，形成某个探测序列，按此序列逐个探测散列表中的其它地址，直到找到给定的关键字或一个空地址为止，将发生冲突的记录放到该地址中。
①线性探测法
将散列表T看成循环向量。设初次发生冲突的地址是h，则依次探测T[h+1]、T[h+2]...，直到T[m-1]时又循环到表头，再次探测T[0],T[1]...。
计算公式是：
其中Hash(key)是哈希函数，m是散列表长度，是第i次探测时的增量序列。
设散列表长为 7，记录关键字组为:15, 14, 28, 26, 56, 23，散列函数:H(key)=key MOD 7，冲突处理采用线性探测法。
H(15) = 15 % 7 = 1
H(14) = 14 % 7 = 0
H(28) = 28 % 7 = 0 冲突
又冲突
H(26) = 26 % 7 = 5
H(56) = 56 % 7 = 0 冲突
又冲突
又冲突
H(23) = 23 % 7 = 2 冲突
又冲突
查找成功的平均查找长度 ASLsucc 是指查找到表中已有表项的平均探查次数。
查找不成功的平均查找长度 ASLunsucc 是指在表中查找不到待查的表项，但找到插入位置的平均探查次数。
查找成功：(1 + 1 + 3 + 1 + 4 + 3) / 6 = 13/6
查找不成功：(7 + 6 + 5 + 4 + 3 + 2 + 1) / 7 = 4
线性探测法的特点
优点：只要散列表未满，总能找到一个不冲突的散列地址。
缺点：每个产生冲突的记录被散列到离冲突最近的空地址上，从而又增加了更多的冲突机会(称为冲突的“聚集”)。
②二次探测法
增长序列为:
上面例题采用二次探测法进行冲突处理
H(15) = 15 % 7 = 1
H(14) = 14 % 7 = 0
H(28) = 28 % 7 = 0 冲突
又冲突
又冲突
二次探测法的特点
优点：探测序列跳跃式地散列到整个表中，不易产生冲突的聚集现象。
缺点：不能保证探测到散列表的所有地址
③伪随机探测法
增长序列使用一个伪随机函数来产生一个落在闭区间[1,m-1]的随机序列。
2.再哈希法
构造若干个哈希函数，当发生冲突时，利用不同的哈希函数再计算下一个新哈希地址，直到不发生冲突为止。
优点：不易产生冲突的聚集现象。
缺点：计算时间增加。
3.链地址法
方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放链表的头指针。哈希值相同的元素插入时可以在表头或表尾插入。
优点:不易产生冲突的“聚集”;删除记录也很简单。
例: 已知一组关键字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) ，哈希函数为:H(key)=key % 13，用链地址法处理冲突 。
查找成功：(61 + 42 + 31 + 41) / 12
查找不成功：(71 + 22 + 33 + 51) / 13
4.建立公共溢出区
方法：在基本散列表外，另外设立一个溢出表保存与基本表中记录冲突的所有记录。
设散列表长为 m，设立基本散列表 hashtable[m]，每个分量保存一个记录;溢出表overtable[m]，一旦某个记录的散列地址发生冲突，都填入溢出表中。
已知一组关键字(15, 4, 18, 7, 37, 47) ，散列表长度为 7 ，哈希函数为:H(key)=key % 7，用建立公共溢出区法处理冲突。
得到的基本表和溢出表如下:
哈希查找过程及分析
7 字符串模式匹配
串的基本概念:串是零个或多个字符组成的有限序列。一般为:S=“c1c2c3...cn”其 中，s 是串名;将一个串中若干个相连字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。
串的模式匹配:子串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。模式匹配成功是指在主串 S 中能够找到模式串 T，否则，称模式串 T 在主串 S 中不存在。(注意算法描述都是从 1 开始，c 语言设计是从 0 开始)
KMP算法
例:设有串 s=“abacabab” ，t=“abab” 。则第一次匹配过程如图所示。
定义 next[j]函数为:
例:若模式串 P 为’ abaabc’，由定义可得 next 函数值(从头尾比较相等的串)
j = 1 next[1] = 0
j = 2 a next[2] = 1
j = 3 ab next[3] = 1
j = 4 aba next[4] = 2
j = 5 abaa next[5] = 2
j = 6 abaab next[6] = 3
在求得了 next[j]值之后，KMP 算法的思想是:
主串 S = 'a c a b a a b a a b c a c a a b c'
模式串 P = 'a b a a b c'
