查找
查找表是由同一类型的数据元素构成的集合。由于集合中数据元素的各种属性之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。 查找主要分为以下几个板块：
- 静态查找
无序查找（顺序查） 有序查找（折半查找） 概率不等查找（次优二叉树） 索引顺序表（分块查找）
- 动态查找
二叉树顺序平衡查找 B+树，B-树 key树
- Hash
Hash（哈希查找）
查找操作的性能分析
衡量一个算法的好坏的度量有三条：时间复杂度，空间复杂度，算法的其他性能，对于查找算法来说，通常以“其关键字和给定值进行比较的关键字和定值进行比较的记录个数的平均值”作为衡量算法好坏的依据。
为确定在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功的平均查找长度（Average Search Length）。
折半查找
以有序表表示静态查找表时，可以用折半查找实现。折半查找先确定待查记录所在的区间，然后逐步缩小范围直到找到或找不到该记录为止。每次选择区间的中点进行查找，若待查找元素大于中点则变换区间为中点到上界，若小于中点则变换区间为下界到中点，若中点是待查找元素则返回中点下标。在算法的实现当中需要三个指针，分别是low，hight，mid，分别代表待查找区间的下界上界和中点，下面是折半查找的说明：
#include <stdio.h>
int main(){
int mid,low,hight,Search[10] = {12,23,28,34,45,66,71,83,86,94},search,postion;
search = 86;
low = 0;
hight = 9;
while(low <= hight){
mid = (low + hight) / 2;
if(Search[mid] == search)
{
postion = mid;
break;
}
else if(Search[mid] > search){
hight = mid - 1;
} else
low = mid + 1;
}
printf("%d",postion);
return 0;
}
二叉排序树
二叉排序树（Binary Sort Tree）具有以下性质
- 若他的左子树不为空，则左子树上所有的结点的值均小于它根结点的值。
- 若它的右子树不为空，则右子树上所有的结点的值均大于它根结点的值。
- 它的左右子树也分别为二叉排序树。
二叉排序树又称查找树，当二叉排序树不为空时，首先将给定值和根节点的关键字进行比较，若相等，则查找成功，否则将依据给定值和关键字之间的大小关系，分别在左子树或右子树上继续进行查找。通常，可取二叉链表作为二叉排序树的存储结构，下面说明二叉排序树的结构：
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lChild, *rChlid; //左右子树域
}BiTNode, *BiTree;
数据结构当然和二叉树相同。
二叉排序树的插入
二叉排序树是一种动态树表。树的结构通常不是一次生成的，而是在查找的过程中，当树不存在关键字等于给定值的结点时再插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子。 下面是二叉排序树的插入说明：
int SearchBST(BiTree T,int key,BiTree m,BiTree *p){
if(!T){ //查找失败
*p = m;
return 0;
}
else if (key == T->data){ //找到key
*p = T;
return 1;
}
else if(key < T->data){
return SearchBST(T->lChild,key,T,p);
}
else {
return SearchBST(T->rChlid,key,T,p);
}
}
二叉排序树的插入
先调用查找操作将要插入的关键字进行比较 如果在原有的二叉树中没有要插入的二叉树，则将关键字与查找的结点p的值进行比较（就是查找的最后一个查找结点） 若p为空，则插入关键字赋值给该结点，若小于节点p的值则插入到p的子树否则插入到右子树。 下面说明二叉排序树的插入操作：
int InsertBST(BiTree *T,int key){
BiTree p,s;
if(!SearchBST(*T,key,NULL,&p)){ //没找到key
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lChild = s->rChlid = NULL; //新结点初始化
if(!p)
*T = s; //插入s为新的根节点
else if(key < p->data)
p->lChild = s; //插入s为左孩子
else
p->rChlid = s; //插入s为右孩子
return 1;
} else
return 0;
}
有着对二叉树数据结构的基本了解，相信很容易能够理解而上面的内容，其中对于参数表中的BiTree *T 以及 *T,key,NULL,&p做一点解释，其中BiTree是二叉树结构体指针，它指向的是一个个二叉树的结点，但对于我们的插入查找操作来说我们需要对整个二叉排序树进行操作，所以需要的的是一个指向结点的指针，所以参数中的&p,参数表中*T都是是指向二叉树结构体指针的指针.
二叉排序树的删除
对于二叉排序树不仅仅是插入，和查找，当我们想在找到目标元素时，想要删除该数据，就需要删除的操作，相对来说删除的操作很难，二叉排序树的删除操作分为三种情况：
- 删除结点的左右子树都为空，直接对它的双亲结点进行操作，删除该节点即可。
- 删除结点的左或右子树为空，删除该节点，并把它的左或右子接到双亲结点的左右子树上（替代原本要删除的结点）。
- 删除结点的左或右子树都不为空，删除该结点，以它的直接前驱或者直接后继取代该结点，并把该结点的直接前驱或直接后继结点删除，什么是直接前驱或者直接后继：就是该结点左子树的最右结点（最大结点），该结点右子树的最左结点（最小结点）。 下面说明二叉排序树的的删除： ``` /** *从二叉排序树中删除结点p。并重接他的左/右子树
-
@return */ int Delete(BiTree *p){ BiTree q,s;
if((p)->rChlid == NULL){ //右子树为空，重接他的左子树 q = *p; *p = (p)->lChild; free(q); } else if((p)->lChild == NULL){ //左子树为空，重接他的右子树 q = *p; *p = (p)->rChlid; free(q);
}else{ //左右子树都部位空 q = p; s = (p)->lChild; while(s->rChlid){ //找到左子树的最右子树 q = s; s = s->rChlid; }(*p)->data = s->data; //s指向被删除结点的直接前驱（将被删除结点的值改为直接前驱结点的值） if(q != p) //删除直接前驱结点 q->rChlid = s->lChild; //重接q的右子树 else q->lChild = s->lChild; //重接q的左子树 free(s); } }
/**
- 二叉排序树的删除
- 当二叉排序树中存在关键字等于key的数据元素时，删除该数据元素并返回True
- @return / int DeleteBST(BiTree *T,int key){ if(!T) //不存在关键字等于key的元素 return 0; else{ if(key == (T)->data) return Delete(T); else if (key < (T)->data) return DeleteBST(&(T)->lChild,key); else return DeleteBST(&(T)->rChlid,key); } } ``` 功能的实现分为两个部分，先实现删除单个结点的函数，在实现在二叉排序树中的删除。这里使用的是用直接前驱结点覆盖删除节点。
平衡二叉树
平衡二叉树（Blanced Binary Tree），它或者是一颗空树，或者满足以下性质：它的左右子树都是平衡二叉树，且左子树和右子树的深度之差不超过1。它是建立在查找二叉树上的，但相对于查找二叉树它的平均查找长度更小。 下面说明平衡二叉树的存储结构：
typedef struct BiTNode
{
int data;
int bf;
struct BiTNode* lchild, *rchild;
}BiTNode, *BiTree;
相对于查找二叉树而言多了一个bf，代表该结点在树中的深度。
平衡二叉树的插入
平衡二叉树主要算法就是插入算法，它的插入和删除和二叉查找树并没有区别，在构建平衡二叉树时，每插入一个结点,都要检查是否破坏了树的平衡。调整树的平衡就是平衡二叉树的实现过程，平衡二叉树分为四个情况：对结点进行右旋转，左旋转，双旋转（左平衡/右平衡）。其中需要一些宏定义表示平衡因子，bool值；
#define LH +1
#define EH 0
#define RH -1
#define TRUE 1
#define FALSE 0;
下面是平衡二叉树插入的说明：
//左旋转
void L_Rotate(BiTree *T)
{
BiTree R = (*T)->rchild;
(*T)->rchild = R->lchild;
R->lchild = *T;
*T = R;
return;
}
//右旋转
void R_Rotate(BiTree *T)
{
BiTree L = (*T)->lchild;
(*T)->lchild = L->rchild;
L->rchild = *T;
*T = L;
return;
}
#define LH +1
#define EH 0
#define RH -1
//T 的左边高，不平衡，使其平衡，右旋转，右旋转前先检查L->bf，
//如果为RH，L要先进行左旋转，使T->lchild->bf和T->bf一致
void LeftBalance(BiTree* T)
{
BiTree L,Lr;
L = (*T)->lchild;
Lr = L->rchild;
switch (L->bf)
{
case LH:
L->bf = (*T)->bf = EH;
R_Rotate(T);
break;
case RH:
switch (Lr->bf)
{
case LH:
L->bf = EH;
(*T)->bf = RH;
break;
case EH:
L->bf = (*T)->bf = EH;
break;
case RH:
L->bf = LH;
(*T)->bf = EH;
break;
}
Lr->bf = EH;
L_Rotate(&L);
R_Rotate(T);
break;
}
}
//T 的右边高，不平衡，使其平衡，左旋转，左旋转前先检查R->bf,
//如果为LH，R要先进行右旋转，使T->rchild->bf和T->bf一致
void RightBalance(BiTree* T)
{
BiTree R,Rl;
R = (*T)->rchild;
Rl = R->lchild;
switch(R->bf)
{
case RH:
R->bf = (*T)->bf = EH;
L_Rotate(T);
break;
case LH:
switch(R->bf)
{
case LH:
R->bf = RH;
(*T)->bf = EH;
break;
case EH:
R->bf = (*T)->bf = EH;
break;
case RH:
R->bf = EH;
(*T)->bf = LH;
break;
}
Rl->bf = EH;
R_Rotate(&R);
L_Rotate(T);
break;
}
}
//往平衡二叉树上插入结点
int InsertAVL(BiTree* T,int data,bool *taller)
{
if(*T == NULL) //找到插入位置
{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->bf = EH;
(*T)->rchild = (*T)->lchild = NULL;
(*T)->data = data;
*taller = true;
}
else
{
if(data == (*T)->data) //树中有相同的结点数据直接返回
{
*taller = false;
return false;
}
if(data < (*T)->data) //往左子树搜索进行插入
{
if(!InsertAVL(&(*T)->lchild,data,taller)) //树中有相同的结点
{
*taller = false;
return false;
}
if (*taller)
{
switch ((*T)->bf) //T插入结点后，检测平衡因子，根据情况，做相应的修改和旋转
{
case LH:
LeftBalance(T); //插入后左边不平衡了，让其左平衡
*taller = false;
break;
case EH:
(*T)->bf = LH;
*taller = true;
break;
case RH:
(*T)->bf = EH;
*taller = false;
break;
}
}
}
else //往右子树搜索进行插入
{
if(!Insert(&(*T)->rchild),data,taller) //树中有相同的结点
{
*taller = false;
return false;
}
if (*taller) //插入到右子树中且长高了
{
switch ((*T)->bf) //T插入结点后，检测平衡因子，根据情况，做相应的修改和旋转
{
case LH:
(*T)->bf = EH;
*taller = false;
break;
case EH:
(*T)->bf = RH;
*taller = true;
break;
case RH:
R_Balance(T); //插入后右边不平衡了，让其右平衡
*taller = false;
break;
}
}
}
}
return true;
}
哈希表（Hash Table）
哈希表也称为散列表，理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，对应关系使每个关键字和结构中唯一的存储位置相对应.这样在查找过程中可以把时间复杂度降到n极大地提升了查找的效率。 哈希函数是一个映像，因此哈希函数的设定很灵活，只要任何关键字由此所得的哈希值都落在表长允许的范围之内即可。 对不同的关键字可能得到同一哈希地址，这个现象称为哈希冲突，具有相同函数值的关键字对该哈希函数来说称为同义词，因此在构建哈希函数是不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。 综上所述，可如下描述哈希表：根据设定的哈希函数H（key）的处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这个表便成为哈希表，这一映像过程称为哈希造表，或散列，所得存储位置称哈希地址，或散列地址。
哈希函数的构造方法
若对于关键字集合中的任何以个关键字，经过哈希函数映射到地址集合中的任何一个地址概率是相等的，则称此类哈希函数为均匀的哈希函数。（是关键字经过哈希函数得到一个随机的地址，使得关键字的地址均匀分布，减少哈希冲突） 常用的构造哈希函数的方法：
- 直接定址法 取关键字或关键字的线性函数为哈希地址，例如：H（key） = key或H（key） = a*key + b.这样的哈希函数地址集合和关键字集合大小一直，也不会发生冲突。但实际上使用这种哈希函数的情况很小。
- 数字分析法 如果关键字有一定规律例如电话号码，前三位都是代表运营商，中间这四位表示电话归属地最后四位才是电话号，因此同一地区同一运营商的电话我们可以选择电话号的后四位构建哈希函数。数字分析法适合关键字位数比较大，且事先知道关键字。
- 平方取中法 取关键平方后的中间几位为哈希地址，这是一种较为常用的构造哈希函数的方法。
- 折叠法 将关键字分割为位数相同的及部分，然后去这几部分的叠加和做为哈希地址。关键字位数很多，且关键字中每一位上的数字分布大致均匀时，可以采用折叠法得到哈希地址。例如图书后的图书编号（ISBN）
- 除留余数法 取关键字某个不大于哈希表长m的数p除后所得余数为哈希地址。即：H（key） = key MOD p，p <= m，这是一种最常用的构造哈希函数的方法。
- 随机数法 选择一个随机函数，取关尖子的随机函数作为他的哈希地址，即：H（key） = Random（key），Random为随机函数，通常当关键字长度不等时采用此构造哈希函数。
处理冲突的方法
均匀的哈希函数可以减少冲突，但不能避免冲突，因而如何处理哈希冲突也是哈希造表必不可少的另一方面。
- 开放定址法
Hi = (H(key) + di) MOD m,i = 1,2,3,4,….k,(k <= m - 1)，其中H（key）为哈希函数；m为哈希函数表长；di为增量序列，可有下列三种取法：
（1）di = 1，2，3，4……m - 1，称线性探测再散列。 （2）di = 1^2,-1^2,2^2,-2^2,3^2…..,k^2(k <= m/2)称为二次探测再散列。 （3）di = 伪随机数序列，称伪随机探测再散列。
- 再哈希法 Hi = RHi（key），i = 1，2，3…..k。RHi均是不同的哈希函数，在同义词产生地址冲突时计算另一个哈希函数地址直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算时间。
- 链地址法 将所有关键字为同义词的记录存储在同一线性链表中。，我们称这种单链表为同义词子表，散列表中存储同义词子表的头指针。
- 公共溢出法 即设立两个表：基础表和溢出表。将所有关键字通过哈希函数计算出相应的地址。然后将未发生冲突的关键字放入相应的基础表中，一旦发生冲突，就将其依次放入溢出表中即可。在查找时，先用给定值通过哈希函数计算出相应的散列地址后，首先 首先与基本表的相应位置进行比较，如果不相等，再到溢出表中顺序查找。
