静态查找表(Static Search Table): 只作查找操作的查找表
散列查找：直接查到储存的位置
数据[12,67,56,16,25,37,22,29,15,47,48,34]， key的数组
int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
1. 创建一个同样长度的数组，遍历数据， 通过散列F(key)求得储存位置, 添加item
散列F(key)求得储存位置，会产生冲突，需要解决冲突
创建一个同样长度的数组
Status InitHashTable(HashTable *H)
{
int i;
//① 设置H.count初始值; 并且开辟m个空间
m = HASHSIZE;
H->count=m;
H->elem=(int*)malloc(m*sizeof(int));
//② 为H.elem[i] 动态数组中的数据置空(-32768)
for(i=0;i < m;i++)
H->elem[i]=NULLKEY;
return OK;
}
遍历插入数据key
void InsertHash(HashTable *H,int key)
{
//① 求散列地址
int addr =Hash(key);
//② 如果不为空，则冲突
while(H->elem[addr] !=NULLKEY)
{
//开放定址法的线性探测 解决散列冲突
addr = (addr+1) %m;
}
//③ 直到有空位后插入关键字
H->elem[addr] = key;
}
散列函数
int Hash(int key)
{
//除留余数法
return key %m;
}
2. 查找数据时 key -> F(key) -> 储存位置 -> 通过散列后数组（1步骤得到）获得key, 进行比较 ，相等存在， 不相等不存在
Status SearchHash(HashTableH,intkey,int*addr)
{
//① 求散列地址
*addr = Hash(key);
//② 如果不为空，则冲突
while(H.elem[*addr] != key)
{
//③ 开放定址法的线性探测
*addr = (*addr+1) %m;
//④H.elem[*addr] 等于初始值或者循环有回到了原点.则表示关键字不存在;
if(H.elem[*addr] ==NULLKEY|| *addr ==Hash(key))
//则说明关键字不存在
return UNSUCCESS;
}
return SUCCESS;
}
散列函数：简单 均匀
1. 直接定址法 ： f(key) = a * key + b (a,b为常数);
2. 数字分析法
3. 平⽅取中法： 1234 * 1234 = 1522756 ，取中间的3位
4. 折叠法：将关键字从左到右分割成位数相等的⼏部分(注意最后⼀部分位数不够可以稍微短些); 然后将⼏部分叠加求和,并按散列表表⻓,取后⼏位作为散列地址
5. 除留余数法： f ( key ) = key % p ( p <= m )，用的比较多
散列冲突解决方法
1.开放定址法就是⼀旦发⽣了冲突,就去寻找下⼀个空的散列地址.只有散列表⾜够⼤,空的散列地址总能找到,并将记录存⼊
f ( key ) = ( f ( key ) + di ) % m ; ( di= 1,2,3,……,m-1)
2.链地址法
将所有的关键字为同义词的记录存储在⼀个单链表中,我们称为这种同义词⼦表. 在散列表中只存储所有同义词⼦表的头指针(头地址). 冲突的数据特别多可以使用红黑树进行储存
1. 顺序查找 + 哨兵 （不用判断边界）
int Sequential_Search2(int *a,int n,int key){
int i;
//设置a[0]为关键字值,称为'哨兵'
a[0] = key;
//循环从数组尾部开始
i = n;
while(a[i] != key) {
i--;
}
//返回0,则说明查找失败
return i;
}
查找数据是有序的
2.折半查找：在有序表中,取中间记录作为⽐较对象,若给定值与中间记录的关键字相等则查找成功; 若给定值⼩于中间的记录关键字,则在中间记录的左半区继续查找; 若给定的值⼤于中间记录的关键字,则在中间记录的右半区继续查找; 不断重复以上的过程,直到查找成功,或所以查找区域⽆记录,查找失败
3. 插值查找
4.斐波拉契查找
有序查找总结
int Interpolation_Search(int *a,int n,int key){
int low, high, mid;
low =1;
high = n;
while(low <= high) {
//插值
mid = low+ (high-low)*(key-a[low])/(a[high]-a[low]);
if(key < a[mid]) {
//若key比a[mid]插值小,则将最高下标调整到插值下标小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid]插值 大,则将最低下标调整到插值下标大一位;
low = mid+1;
} else
//若相等则说明mid即为查找到的位置;
return mid;
}
return 0;
}
动态查找(Dynamic Search Table): 在查找过程中同时插⼊查找表中不存在的数据元素,
或者从查找表中删除已经存在的某个数据元素; 显然动态查找表的操作就是2个动作
1. 查找时插⼊数据元素;
2. 查找时删除数据元素
二叉排序树实现
结点左子树 < 结点 < 结点右子树
考虑极端二叉排序树
使用AVL树（搜索）和红黑树（删除或插入）
各种树的代码演示网站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
