线性表的查找顺序查找，折半查找，分块查找，哈希表的建立、查找、冲突处理

江南才子

1.顺序查找
表内元素之间无序
数据元素类型定义：

typedef struct {
KeyType key;//关键字域
......//其他域
}ElemType;

顺序表结构类型定义：

typedef struct {//顺序表结构类型定义
ElemType *R;//表基址
int length;//表长
}SSTable;//Sequential Search Table
SSTable ST;//定义顺序表ST

顺序查找代码

int Search_Seq(SSTable ST, KeyType key)
{//若成功返回其位置信息，否则返回0
for (int i = 1; i <= ST.length;i++)
if (ST.R[i].key == key) return i;
return 0;
}

改进：把关键字key存入表头（“哨兵”）从后往前逐个比较，可免去每一步都要进行检查和比较两个步骤，加快速度

int Search_Seq(SSTable ST, KeyType key)
{//若成功返回其位置信息，否则返回0
ST.R[0].key = key;
int i;
for ( i = ST.length; ST.R[i].key != key; i--);//这个“；”很重要
return 0;
}

顺序：优点：算法简单，不同存储结构都适用；缺点：效率低
2.折半查找：每次将待查记录所在区间缩小一半
low=1,high=n,mid=(low+high)/2
key<mid:high=mid-1;
key>mid:low=mid+1;
key==mid,找到；
high<low ,结束
算法：(非递归)

int Search_Bin(SSTable ST, KeyType key)
{
int low = 1,high=ST.length;//设置初始区间
while (low<=high)
{
int mid = (low + high) / 2;
if (ST.R[mid].key == key)return mid;//找到待查元素
else if (key < ST.R[mid].key)//缩小查找空间
high = mid - 1;//继续在前半区查找
else
low = mid + 1;//继续在后半区查找
}//while
return 0;//没找到
}//Search_Bin

算法：(递归)

int Search_Bin(SSTable ST, KeyType key, int low, int high)
{
if (low>high)return 0;//找不到，返回0
int mid = (low + high) / 2;
if (key == ST.R[mid].key)return mid;
else if (key < ST.R[mid].key)
Search_Bin(ST, key, low, mid-1);//递归，在前半区找
else
Search_Bin(ST, key, mid+1, high);//递归，在后半区找
}

折半查找：优点：效率比顺序高；缺点：只适合有序表，且限于顺序存储结构
3.分块查找（索引顺序表的查找）
（1）将表分成几块，且表或者有序，或者分块有序（块间有序，块内无序）
若i<j，则第j块中的关键字均大于第i块中的最大关键字
（2）建立“索引表”（每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序）。
查找过程：先确定待查记录所在块（顺序查找或折半查找），再在块内查找（顺序查找）
4.哈希表：记录的存储位置与关键字之间存在对应关系
对应关系--hash函数     loc(i)=H(keyi )
散列方法（杂凑法）：
选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；
查找时，有同一个函数对给定值K计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。
（三种查找方式完整代码：线性表的三种查找方法：顺序查找、折半查找、分块查找（算法实现）_wx601562e1506ae的技术博客_51CTO博客)
哈希函数构造方法：
除留余数法：Hash(Key)=key mod p(p是一个整数)
取p技巧：设表长为m，取P<=m且为质数
冲突处理方法：
链地址法：相同散列地址的记录链成一个单链表，m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。
建立散列表步骤
step1：取数据元素的关键字Key，计算其散列函数值（地址）。若该地址对应链表空，将元素插入链表；否则step2解决冲突；
step2：根据选择的冲突处理方法，计算关键值K的下一个存储地址，若该地址对应链表不为空，则利用链表的前插法或后插法将该元素插入此链表
（哈希表完整代码，哈希表的建立与查找，用链地址法处理冲突，用除留余数法构造哈希函数_wx601562e1506ae的技术博客_51CTO博客）