Day 11-12：查找
目录
概念
方法
折半查找
前提
算法思路
分块查找
算法思路
哈希表
概念
构造哈希函数的方法
保留除数法
处理冲突的方法
开放地址法（二次探查法）
链地址法（重要）
哈希表的实现
结构体的创建
哈希表的创建
哈希元素插入
哈希元素查找
概念
记录表L=(R1 R2……Rn)，其中Ri(l≤i≤n)为记录，对给定的某个值k，在表L中确定key=k的记录的过程，称为查找。
表L中存在一个记录Ri的key=k，记为Ri.key=k，则查找成功，返回该记录在表L中的序号i(或Ri 的地址)，否则(查找失败)返回0(或空地址Null)。
方法
顺序查找、折半查找、分块查找、Hash表。
折半查找
前提
仅仅适用于有序的顺表。
算法思路
首先将给定值key与表中中间位置的元素（mid的指向元素）比较。mid=low+high/2（向下取整）
若key与中间元素相等，则查找成功，返回该元素的存储位置，即mid；
若key与中间元素不相等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。（至于是前半部分还是后半部分要看key与mid所指向元素的大小关系）
a.若给定值key大于中间元素则所查找的元素只可能在后半部分。此时让low=mid+1；
b.若给定值key小于中间元素则所查找的元素只可能在前半部分。此时让high=mid-1；
举例：查找key = 20
分块查找
算法思路
-
需要把数据分成N多小块，块与块之间不能有数据重复的交集。
-
给每一块创建对象单独存储到数组当中。
-
查找数据的时候，先在数组查，当前数据属于哪一块。
-
再到这一块中顺序查找。
哈希表
概念
对给定的k，不经任何比较便能获取所需的记录，其查找的时间复杂度为常数级O(C)。在建立记录表的时候，确定记录的key与其存储地址之间的关系f，即：
使key与记录的存放地址H相对应。
这个关系f就是所谓的Hash函数（或称散列函数、杂凑函数），记为H(key)。
构造哈希函数的方法
保留除数法
概念：设Hash表空间长度为m，选取一个不大于m的最大质数p。
H(key) = key % p
冲突：表中某地址j∈[0，m-1]中己存放有记录，而另一个记录的H(key)值也为 j。
表的装填因子α：α=n/m，其中m为表长，n为表中记录个数。一般α在0.7～0.8之间，使表保持一定的空闲余量，以减少冲突和聚积现象。比如：有70%的数据要存，选择一个数组长度为100%的数组来存。
质数的选取：不大于m的最大质数。
处理冲突的方法
在地址j的前面或后面找一个空闲单元存放冲突的记录，或将相冲突的诸记录拉成链表。
开放地址法（二次探查法）
当发生冲突时，在H(key)的前后找一个空闲单元来存放冲突的记录，即在H(key)的基础上获取下一地址：
Hi=(H(key)+di)%m
其中m为表长，%运算是保证Hi落在[0，m-l]区间。
di为地址增量。di的取法有多种：
（1）di=1，2，3，……(m-1)——称为线性探查法；
（2）d = 1^2, -1^2, 2^2, -2^2, 3^2,……
举例
设记录的key集合k={23，34，14，38，46，16，68，15，07，31，26}，记录数n=11。
令装填因子α=0.75，取表长m= n/α =15。 用“保留余数法”选取Hash函数（p=13）： H(key)=key%13
16 % 13 == 68 % 13
46 % 13 == 7 % 13
链地址法（重要）
发生冲突时，将各冲突记录链在一起，即同义词的记录存于同一链表。
设H(key)取值范围（值域）为[0，m-l]， 建立头指针向量HP[m]， HP[i]（0≤i≤m-l）初值为空。
哈希表的实现
结构体的创建
#define M 15//表长
typedef int datatype;
/*1.创建链表结构体*/
typedef struct node
{
datatype key;
datatype value;
struct node* next;
}listnode,*linknode;
/*创建链表数组，存放链表的头节点*/
typedef struct
{
listnode data[M];
}hash,*linkhash;哈希表的创建
/*哈希表创建*/
linkhash hash_create()
{
linkhash HT;
if (HT = malloc(sizeof(hash)) == NULL)
{
printf("create failed!\n");
return NULL;
}
memset(HT, 0, sizeof(hash));
return HT;
}哈希元素插入
/*哈希元素插入*/
/*整体逻辑：1.求余数 2.判断是否冲突（原来有值）*/
int hash_insert(linkhash HT, datatype value)
/*注意：结构体数组上仅存放了指向第一个数的指针*/
{
linknode p,q;
if (HT == NULL)
return -1;
/*1.创建一个链表存放插入值：指针p*/
if ((p = malloc(sizeof(listnode)) == NULL)
return -1;
p->key = value % P;
p->value = value;
p->next = NULL;
/*2.找到数组上对应的位置，判断是否为冲突元素？否则就是空元素（？），指针q*/
q = &(HT->data[value % P]);
/*移动q指针，目标：越大越放在后面*/
while (q->next != NULL && q->next->value < p->value)
{
q = q->next;
}
/*3.插入元素并要注意链表插入规则，以在16和68之间为例*/
p->next = q->next;
q->next = p;
return 0;
}哈希元素查找
/*哈希查找*/
linknode hash_search(linkhash HT, datatype value)
{
if (HT == NULL)
return -1;
linknode p;
p = &HT->data[value % P];
while (p->next && p->next->value != value)
{
p = p->next;
}
if (p->next == NULL)
return NULL;
else
return p->next;
}