靜態(tài)查找表(Static Search Table):?只作查找操作的查找表
散列查找：直接查到儲(chǔ)存的位置
數(shù)據(jù)[12,67,56,16,25,37,22,29,15,47,48,34]， key的數(shù)組
int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
1. 創(chuàng)建一個(gè)同樣長度的數(shù)組，遍歷數(shù)據(jù)， 通過散列F(key)求得儲(chǔ)存位置, 添加item
散列F(key)求得儲(chǔ)存位置，會(huì)產(chǎn)生沖突，需要解決沖突
創(chuàng)建一個(gè)同樣長度的數(shù)組
Status InitHashTable(HashTable *H)
{
? ? int?i;
? ? //① 設(shè)置H.count初始值; 并且開辟m個(gè)空間
? ? m = HASHSIZE;
? ? H->count=m;
? ? H->elem=(int*)malloc(m*sizeof(int));
? ? //② 為H.elem[i] 動(dòng)態(tài)數(shù)組中的數(shù)據(jù)置空(-32768)
? ? for(i=0;i < m;i++)
? ? ? ? H->elem[i]=NULLKEY;
? ? return?OK;
}
遍歷插入數(shù)據(jù)key
void?InsertHash(HashTable *H,int?key)
{
? ? //① 求散列地址
? ? int?addr =Hash(key);
? ? //② 如果不為空，則沖突
? ? while(H->elem[addr] !=NULLKEY)
? ? {
? ? ? ? //開放定址法的線性探測 解決散列沖突
? ? ? ? addr = (addr+1) %m;
? ? }
? ? //③ 直到有空位后插入關(guān)鍵字
? ? H->elem[addr] = key;
}
散列函數(shù)
int?Hash(int?key)
{
? ? //除留余數(shù)法
? ? return?key %m;
}
2. 查找數(shù)據(jù)時(shí) key ->?F(key) ->?儲(chǔ)存位置 -> 通過散列后數(shù)組（1步驟得到）獲得key, 進(jìn)行比較 ，相等存在， 不相等不存在
Status SearchHash(HashTableH,intkey,int*addr)
{
? ? //① 求散列地址
? ? *addr = Hash(key);
? ? //② 如果不為空，則沖突
? ? while(H.elem[*addr] != key)
? ? {
? ? ? ? //③ 開放定址法的線性探測
? ? ? ? *addr = (*addr+1) %m;
? ? ? ? //④H.elem[*addr] 等于初始值或者循環(huán)有回到了原點(diǎn).則表示關(guān)鍵字不存在;
? ? ? ? if(H.elem[*addr] ==NULLKEY|| *addr ==Hash(key))
? ? ? ? ? ? //則說明關(guān)鍵字不存在
? ? ? ? ? ? return?UNSUCCESS;
? ? }
? ? return SUCCESS;
}
散列函數(shù)：簡單 均勻
1.?直接定址法 ：?f(key) = a * key + b (a,b為常數(shù));
2.?數(shù)字分析法
3.?平?取中法：?1234 * 1234 = 1522756 ?，取中間的3位
4.?折疊法：將關(guān)鍵字從左到右分割成位數(shù)相等的?部分(注意最后?部分位數(shù)不夠可以稍微短些);?然后將?部分疊加求和,并按散列表表?,取后?位作為散列地址
5.?除留余數(shù)法：?f ( key ) = key % p ( p <= m )，用的比較多
散列沖突解決方法
1.開放定址法就是?旦發(fā)?了沖突,就去尋找下?個(gè)空的散列地址.只有散列表?夠?,空的散列地址總能找到,并將記錄存?
f ( key ) = ( f ( key ) + di?) % m ; ( di= 1,2,3,……,m-1)
2.鏈地址法
將所有的關(guān)鍵字為同義詞的記錄存儲(chǔ)在?個(gè)單鏈表中,我們稱為這種同義詞?表.?在散列表中只存儲(chǔ)所有同義詞?表的頭指針(頭地址). 沖突的數(shù)據(jù)特別多可以使用紅黑樹進(jìn)行儲(chǔ)存
1.?順序查找 ?+ 哨兵 （不用判斷邊界）
int Sequential_Search2(int *a,int n,int key){
? ? int?i;
? ? //設(shè)置a[0]為關(guān)鍵字值,稱為'哨兵'
? ? a[0] = key;
? ? //循環(huán)從數(shù)組尾部開始
? ? i = n;
? ? while(a[i] != key) {
? ? ? ? i--;
? ? }
? ? //返回0,則說明查找失敗
? ? return?i;
}
查找數(shù)據(jù)是有序的
2.折半查找：在有序表中,取中間記錄作為?較對(duì)象,若給定值與中間記錄的關(guān)鍵字相等則查找成功; 若給定值?于中間的記錄關(guān)鍵字,則在中間記錄的左半?yún)^(qū)繼續(xù)查找; 若給定的值?于中間記錄的關(guān)鍵字,則在中間記錄的右半?yún)^(qū)繼續(xù)查找; 不斷重復(fù)以上的過程,直到查找成功,或所以查找區(qū)域?記錄,查找失敗
3.?插值查找
4.斐波拉契查找
有序查找總結(jié)
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]插值小,則將最高下標(biāo)調(diào)整到插值下標(biāo)小一位;
? ? ? ? ? ? high = mid-1;
? ? ? ? }else?if(key > a[mid]){
? ? ? ? ? ? //若key比a[mid]插值 大,則將最低下標(biāo)調(diào)整到插值下標(biāo)大一位;
? ? ? ? ? ? low = mid+1;
? ? ? ? }?else
? ? ? ? ? ? //若相等則說明mid即為查找到的位置;
? ? ? ? ? ? return?mid;
? ? }
? ? return?0;
}
動(dòng)態(tài)查找(Dynamic Search Table):?在查找過程中同時(shí)插?查找表中不存在的數(shù)據(jù)元素,?
或者從查找表中刪除已經(jīng)存在的某個(gè)數(shù)據(jù)元素;?顯然動(dòng)態(tài)查找表的操作就是2個(gè)動(dòng)作
1.?查找時(shí)插?數(shù)據(jù)元素;
2.?查找時(shí)刪除數(shù)據(jù)元素
二叉排序樹實(shí)現(xiàn)
結(jié)點(diǎn)左子樹 < 結(jié)點(diǎn) < 結(jié)點(diǎn)右子樹
考慮極端二叉排序樹
使用AVL樹（搜索）和紅黑樹（刪除或插入）
各種樹的代碼演示網(wǎng)站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
