一.基本概念
1.查找：在数据集合中寻找满足条件的数据元素
2.查找表：用于查找的数据结合称之为查找表
3.静态查找表(Static Search Table)：只作查找操作的查找表。
主要操作
查询某个“特定的”数据元素是否在查找表中。
检索某个“特定的”数据元素和各种属性。
4.动态查找表(Dynamic Search Table)： 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
主要操作
查找时插入不存在的数据元素。
查找时删除已存在的数据元素。
5.主关键字：唯一标识数据元素
6.次关键字：可以标识若干个数据元素
7.平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度，则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为
式中，n是查找表的长度；Pi是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即P i = 1 / n ；C i是找到第i个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。
二.线性表的查找
1.顺序查找
（1）代码
/*有哨兵顺序查找*/
int Sequential_Search(int *a, int n, int key){
int i;
a[0] = key; //设置a[0]为关键字，称之为“哨兵”
i = n; //循环从数组尾部开始
while(a[i] != key){
i--;
}
return i; //返回0则说明查找失败
}
这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。
上述顺序表查找时间复杂度是O( n )。
1.查找成功：ASL：（n+1）/2
2.查找失败：ASL：n+1（长度为n，要查到哨兵才停）
（2） 无论是有序数组还是无序数组，顺序查找的平均查找长度都是（n+1）/2 。
（3）查找概率相等时，ASL相同；查找概率不等时，如果从前向后查找，则按查找
概率由大到小排列的有序表其ASL要比无序表ASL小。
2.折半查找
（1）折半查找(Binary Search)技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序)，线性表必须采用顺序存储。
折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
（2）代码
int Binary_Search(SeqList L, ElemType key){
int low = 0, high = L.length - 1, mid;
while(low <= high){
mid = (low + hight)/2; //取中间位置
if(L.elem[mid] == key){
return mid; //查找成功返回所在位置
}else if(L.elem[mid] > key){
high = mid - 1; //从前半部分继续查找
}else{
low = mid + 1; //从后半部分继续查找
}
}
return -1; //查找失败，返回-1
}
（3） 每次将待查记录所在区间缩小一半，比顺序查找效率高,时间复杂度O(log2 n)
3.分块查找（块间有序，块内无序）
（1） 分块有序，即分成若干子表，要求每个子表中的数值都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。
（上面是每个子表的最大值，下面是每个子表的起始地址）
（2）分块查找过程：对索引表使用折半查找法（因为索引表是有序表）；
确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；
（3）查找效率：ASL=Lb+Lw
Lb为对索引表查找的ASL，Lw为对块内查找的ASL
三.树形表的查找
1.二叉排序树
（1）定义：二叉排序树(也称二叉查找树)或者是一棵空树，或者是具有下列特性的二叉树:
若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵二叉排序树。
第二个图不是排序二叉树
（2）查找
- 若查找的关键字等于根结点，成功。
- 否则若小于根结点，查其左子树。
- 若大于根结点，查其右子树
在左右子树上的操作类似
BiTree *BST_Search(BiTree t, int v){
while (t!=NULL){
if (t.data>v){
t=t.rchild;//往左子树查找
}else if (t.data < v){
t = t.rchild;//往右子树查找
}else{
return t;
}
}
return t;
}
（3）插入
若二叉排序树为空，则插入结点应为根结点。否则，继续在其左、右子树上查找
- 树中已有，不再插入
- 树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子（插入的元素一定在叶结点上）
/*
当二叉排序树T中不存在关键字等于key的数据元素时
插入key并返回TRUE，否则返回FALSE
*/
bool InsertBST(BiTree *T, int key){
BiTree p, s;
if(!SearchBST(*T, key, NULL, &p)){
//查找不成功
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if(!p){
*T = s; //插入s为新的根节点
}else if(key < p->data){
p->lchild = s; //插入s为左孩子
}else{
p->rchild = s; //插入s为右孩子
}
return TRUE;
}else{
return FALSE; //树种已有关键字相同的结点，不再插入
}
}
（4）二叉排序树的生成
有了二叉排序树的插入代码，我们要实现二叉排序树的构建就非常容易了，举个例子：
int i;
int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
BiTree T = NULL;
for(i = 0; i<10; i++){
InsertBST(&T, a[i]);
}
（5）删除
- 删除叶结点：只需将其双亲结点指向它的指针清零，再释放它即可。
- 被删结点缺右子树：可以拿它的左子女结点顶替它的位置，再释放它。
- 被删结点缺左子树：可以拿它的右子女结点顶替它的位置，再释放它。
- 被删结点左、右子树都存在：可以在它（该节点）的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。 （删除他的直接前驱或直接后继，用中序遍历可以得到直接前驱或直接后继）
（层数*个数再相加）
时间复杂度：
（因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。）
四.平衡二叉树
（1）定义：
平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。
它是一种高度平衡的二叉排序树。它要么是一棵空树， 要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF
注：任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；
对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。
（2）平衡二叉树的插入
以48为节点的这个树是不平衡的（左子树高度为0，右子树高度为2），需要调整
（包括那个根节点）
为RL类型
将最小的48放左边，最大的76放右边，则中间的52就为根节点，连接起来
以52为节点的这个树是不平衡的（左子树为1，右子树为3），需要调整
将52,76,81单独拎出来，为RR型，将其调整
需要将剩下的48,70,92进行调整（按照平衡二叉树的特性）
接下来将15插入其中
以18为节点的这个树是不平衡的（左子树为2，右子树为0），需要调整
为LR型
完全调整过后的
五.B树
1.引入：硬盘的访问次数与树高呈正相关，尽量减少树高
2.定义：B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m 表示。
最多有五个分叉，为五阶B树（五叉树）
包含数据的节点为内部节点（蓝色的节点） ，失败节点无任何数据只代表失败
3.B树的特性
（多路指的是除根节点以外的节点）5阶B树的最少分支为5/2=2.5，向上取整为3
4.查找
（跟二叉排序树查找很像）16先于17比较，小于17，进入左子树，再与6,13进行比较（一般用顺序查找），16大于13，进入13的右子树，然后找到16
找不到28，28进入失败节点
5.插入
（1）无溢出
（2）有溢出
节点中最多的元素个数为2，上溢出
（3）溢出导致父节点溢出
一直分裂，直到不溢出为止
（4）溢出导致根节点溢出
六.哈希表
1.定义：哈希也叫散列，因而哈希表也叫散列表。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数。采用散列函数将记录存储在一块连续的存储空间中，这块连续的存储空间称为哈希表。所得的存储地址称为哈希地址。
平均查找长度与结点个数无关
2.哈希常见的构造方法
（1）直接定址法
（2）除留余数法
最常用的构造哈希函数方法。哈希函数为：
H(key) = key mod p
其中mod为取余运算，p<m，m为哈希表表长。
此方法不仅可以对关键字直接取模，也可以在折叠、平方取中之后再取模。
（3） 数字分析
处理关键字位数比较多、数字出现频率不高的情况，通过抽取关键字的一部分进行操作，计算哈希存储位置。
假设在记录员工的生日，如20000618。若直接把年月日作为哈希地址，空间浪费很大，若是将月日作为哈希地址，则既能减少空间浪费又能降低哈希冲突的可能性。
（4）平方取中
当无法确定关键字中哪几位分布较均匀时，可以求关键字的平方值，然后取平方值的中间几位作为散列地址。
（5）随机数法
适用于关键字位数很多，而且关键字每一位上数字分布大致均匀的情况。将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后去这几部分的叠加和舍去进位后作为散列地址。
假设关键字1472580369，表长为3。可将关键字分成4部分，147|258|036|9，147+258+036+9=450，取450为散列地址。
3.哈希冲突
4. 开放定址法
（1）线性探测法
29%11=7 （29+1）%11=8 （3+1）%11=4
22%11=0 （22+1）%11=1 （3+2）%11=5
8%11=8 （8+1）%11=9 （3+3）%11=6
3%11=3
如果冲突了，就让i再加1
（2）二次探测法
5.哈希表的查找
（1）线性探测法
线性探测法计算ASL的方法：标清楚元素移动了几次，数量*移动的次数相加再除以总的元素个数
（2）链地址法
第一数列代表次数为1，与数量相乘再相加，其他列亦如此