简介
写这一节，其实一开始我是拒绝的，因为我感觉在本科的时候没怎么学呀！不过后来想了想，“Duang！”一下，发现我错了, 查找在数据库上有辣么重要的应用，还是写出来吧！不写完，总感觉《数据结构》总结的不是很完整！
另外话说，我当时去哪玩去了？是骗小女生去了？不应该呀，我这么善良的宝宝~
好了，收！
这节呢，就讨论一下8种常用的查找算法，部分有代码实现，一起来看看吧！ 相关代码已经托管到Github上了~我是代码，快点我
基础知识：
查找分类
- 静态查找和动态查找（动态查找对查找表有删除和插入操作）
- 无序查找和有序查找（要求查找数列是否必须有序）
平均查找长度（Average Search Length，ASL）计算方法：ASL = （Pi*Ci的和）
8大查找算法
静态查找
1：顺序查找
顺序查找对查找表无要求，查找过程依次遍历数组元素，进行对比后返回~
2：二分查找
二分查找，要求数组必须有序，通过不断的折半查找所需元素，最多比较次数（(log2n)向下取整+1） 具体实现，有递归和非递归2种形式，下面是非递归的形式！
源代码如下：
int binarySearch(vector<int> &v,int m)
{
int mid=0;
int low=0;
int hight=v.size()-1;
while(low<=hight)
{
mid=(low+hight)/2;
if(v[mid]==m)break;
if(v[mid]<m)
low=mid+1;
else
hight=mid-1;
}
if(v[mid]==m)
{
print(v,m,true);
return m;
}
else
{
print(v,m,false);
return -1;
}
}
3：斐波那契查找
斐波那契查找利用黄金分割的原理，遵照数据的非均匀分布的现象！
使用有2个条件要求
- 数组大小要是某一个斐波那契数
- 数组要是有序数组
int initfb(vector<int> &v,int m)
{
int s=0;
int f=1;
int i=0;
v.push_back(s);
while(i++<m)
{
f=f+s;
s=f-s;
v.push_back(f);
}
cout<<"创建斐波那契序列："<<endl;
for(vector<int>::iterator it=v.begin();it!=v.end();it++)
cout<<*it<<" ";
cout<<endl;
return 0;
}
int fbSearch(vector<int> &v,int m)
{
vector<int> fb;
initfb(fb,10);
int mid=0;
int low=0;
int hight=v.size()-1;
int i=4;
v.pop_back();v.pop_back();
while(low<=hight)
{
mid=low+fb[i];
if(v[mid]==m)break;
if(v[mid]<m)
{
low=mid+1;
i-=2;
}
else
{
hight=mid-1;
i--;
}
}
if(v[mid]==m)
{
print(v,m,true);
return m;
}
else
{
print(v,m,false);
return -1;
}
}
4：索引顺序表查找
索引顺序表查找是对顺序查找和二分查找的结合，通过索引-数组的关系来维护，要求部分有序，即数组内部无序，数组之间有序！
算法步骤如下：
- 选取各块中的最大关键字组成索引表；
- 对索引表进行二分查找或顺序查找，确定在哪个块中；
- 在已确定的块中用顺序法进行查找。
动态查找
5：二叉排序树(BST)
也叫二叉查找树，左小、右大！
二叉排序树定义：
- 左子树：不为空，则小于根结点的值
- 右子树：不为空，则大于根结点的值
- 左右孩子分别为二叉排序树
二叉搜索树的操作：（利用树的递归定义的性质）
查找： 如果值大于根节点，着查找右孩子，否则查找左孩子，递归下去。
插入： 先查找，如果值大于返回结点，则插入右孩子，否则插入左孩子。
删除： 右孩子为NULL，直接赋值左孩子；左孩子为NULL，直接赋值右孩子；均不为NULL，找到左孩子的最大右孩子，置换，重接终端结点
6：平衡二叉树（AVL树）
定义：
平衡因子BF只能取 -1，0，1 即AVL树上任何结点的左右子树的深度之差不能超过1
平衡二叉树的方法：
- 单向右旋
- 单项左旋
- 双向旋转 先左后右，转化为1
- 双向旋转 先右后左，转化为2
7：B-树与B+树
B-树：（m阶）
- 每个结点最多m棵子树；
- 根节点不是叶结点，至少有2棵子树
- 除根外，所有非终端结点至少m/2向上取整棵子树
- 结点结构（n,a1,k1,a2,k2,a3,k3,…,kn,an）
- 所有叶子结点在同一层上
B-树的分裂：（母爱无私，兄弟奉献）（并不太懂）
B+树（这对文件系统而变种的B-树）
- n棵子树的结点含有n个关键字；（B-树是N+1）
- 所有叶子结点包含全部关键字，及指向关键字的指针，并且按照关键字大小顺序连接（B-树叶子结点只包含部分，且不相连）
- 非终端结点是索引，包含子树中最大（小）的关键字（B-树非终端结点，比子树的最大（小）值要大（小））
8：哈希表
哈希表，散列，哈希地址，
冲突：将不同的关键字映射到同一Hash地址。冲突只能尽可能地减少，而不能完全避免
6种常用Hash算法：
- 直接定址法 H=key 或者 H=a*key+b
- 数字分析法 分析关键字的基，并选择冲突次数较少的基
- 平方取中法 取关键字平方后的中间几位
- 折叠法 关键字的基大致分布均匀，取几部分关键字的叠加和
- 除留余数法 H=key % p
- 伪随机数法
4种常用冲突解决方法：
- 开放地址法 Hi=(H+d) % m (d 取值 线性探测，平方探测，伪随机数探测)
- 再hash法 Hi=H(H)
- 链地址法 (比较常用的Hash冲突解决方法)
- 公共溢出区 填入策略不定
### 总结
这一节写的比较简单，只是介绍了相关的基础概念，很多代码都没有实现，以后回过来看的时候要记得补充呀！(^_^)
### 参考文献