靜態(tài)查找
順序查找 折半查找 散列查找動態(tài)查找
二叉排序樹 散列查找ASL(平均查找長度) - 衡量查找算法效率的主要指標(biāo)
ASL=ΣPiCi;(1...n)
P為查找第i個元素的概率，Ci為查找到第i個元素所需的比較次數(shù)
順序查找（線性查找）
注意：線性鏈表只能進(jìn)行順序查找；
typedef struct {
ElemType *data;
int TableLength;
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
ST.data[0]=key;//哨兵 0號單元留空用來存哨兵
for(int i=ST.TableLength;ST.data[i]!-key;--i){
return i;
}
}
所以，
ASL(suc)=ΣPi * (n-i+1); (1...n)
ASL(fal)=ΣPi * (n+1); (1...n)
若查找概率相等為1/n;（Pi(suc）=1/n;Pi(fal)=1/n+1;）
ASL(suc)=(n+1)/2;
ASL(fal)=n+1;
對于有序表的順序查找
ASL(suc)= (n+1)/2;
ASL(fal)=Qi * (Lj-1)=((n+1)/2 + n) /（n+1）;(j為第j個失敗結(jié)點)
化簡得 =n/2+n/(n+1);
折半查找
要求：僅適用于有序順序表
int Binary_Search(SeqList L,ElemType kay){
int low=0,high=L.TbaleLen-1,mid;
while(low<high){
mid=(low+high)/2;
if(L.data[mid]==key)
return mid;
else if(L.data[mid]<key)
high=mid-1;
else
low=mid+1;
}
return -1;
}
ASL=log(n+1)向上取整
可畫二叉排序樹進(jìn)行判斷 ，一般求ASL（成功）準(zhǔn)確的為（每層的節(jié)點數(shù) * 層數(shù)的和）/總結(jié)點數(shù)
ASL（失?。椋ㄋ惺〉墓?jié)點 * 層數(shù)的和）/n+1；（這里失敗的節(jié)點指的是樹中2*N0+N1）;
如圖：
圖中所有方形節(jié)點即為失敗節(jié)點；
分塊查找（索引順序查找）
將表分塊，塊內(nèi)可無序，塊間有序
塊間即索引表
ASL=Li+Ls;(Li索引查找，Ls塊內(nèi)查找)
長度為n的表分為b塊，每塊有s個記錄；即（b=s/n）
Li=(b+1)/2;(b=s/n)
Ls=(s+1)/2
ASL=(s2+2s+n)/2s;
實際上對索引及塊內(nèi)記錄的查找都為順序查找，若為折半查找改為logn即可；
B樹及B+樹
其實對于B樹，比較重要的幾點：
B樹的特性
對于一個m階B樹
1）每個結(jié)點最多m顆子樹,（即至多含有m-1個關(guān)鍵字）
2）根節(jié)點不是終端節(jié)點時，則至少有兩個子樹
3）除根節(jié)點外所有的非葉節(jié)點，至少有ceil（m/2）顆子樹，（即至少含有ceil（m/2）-1個關(guān)鍵字）
4）結(jié)點中關(guān)鍵字個數(shù)n（ceil(m/2)-1<=n<=m-1）
5）所有的葉結(jié)點出現(xiàn)在同一層上，且不帶信息
所有結(jié)點的平衡因子均為0的多路查找樹。
B樹的高度(n為關(guān)鍵字個數(shù))
n<=m^h-1;即 h>=logm(n+1);
n+1>=2(ceil(m/2))^(h-1);即h<=logceil(m/2)(n+1)/2 + 1;
B樹上數(shù)據(jù)元素的增刪調(diào)整，分裂方式很重要，我從中體會出的一點就是不管是增結(jié)點還是刪除結(jié)點，首先判斷關(guān)鍵字容量是否符合，符合就結(jié)束，不符合，就要分裂，分裂的情況中比較復(fù)雜的就是要和它的父結(jié)點發(fā)生變動的，像加個結(jié)點，有一個原則就是關(guān)鍵字超過上限了（m/2(向上取整)-1）就要分裂完全分開，兩個的分成一個，多出來的上升為父結(jié)點，父結(jié)點關(guān)鍵字溢出則繼續(xù)分裂上升從而最終結(jié)果就是這顆B樹 長高了！ 對于刪除比較復(fù)雜的也是要從父結(jié)點借關(guān)鍵字的情況，（這個前提當(dāng)然是在兄弟不夠借的情況下）
B+樹
這里只寫與B樹不同的地方，
3）結(jié)點的子樹個數(shù)與關(guān)鍵字個數(shù)相同
4）所有葉結(jié)點包含全部的關(guān)鍵字按順序排列，相鄰結(jié)點同樣也按順序排列且互相鏈接起來
5）所有的分支結(jié)點中僅包含它的各個子結(jié)點中關(guān)鍵字最大的值及指向其子節(jié)點的指針
B+樹種葉結(jié)點包含信息，所有非葉結(jié)點僅起到索引的作用 ，通常有兩個頭指針，一個只想最小的關(guān)鍵字，便于進(jìn)行鏈?zhǔn)降捻樞虿檎?，另一個是根節(jié)點，便于進(jìn)行多路查詢。
Hash表
關(guān)于散列表比較重要的一塊就是處理沖突的方法以及平均查找長度ASL
- 構(gòu)造散列函數(shù)得到構(gòu)造散列表
1）直接頂?shù)刂贩?br> H（key）=a * k+b；
適合關(guān)鍵字分布基本連續(xù)，若分配不連續(xù)將造成空間浪費
2）除留余數(shù)法
散列表的長度為m，選一個不大于但接近m的質(zhì)數(shù)p；
H（key）=key%p；
3）數(shù)字分析法
4）平方取中法
5）折疊法
一般構(gòu)造函數(shù)題目中會直接給出，這塊并不難
Hi=（H（key）+di）%m； - 處理沖突的辦法
開放定地址發(fā)
1）線性探測
即沖突發(fā)生時，順序查看表中下一個單元直到不沖突為止；
2）平方探測法（又稱二次探測）
即di=12，-12，22，-22，.....,k2，-k2，k<=m/2;m必須為4k+3的質(zhì)數(shù)
3）再散列法（雙散列法）
di=Hash2(key);
即兩個散列函數(shù)
4）偽隨機序列
拉鏈法
將散列在同一地址的關(guān)鍵字用線性鏈表連接起來 - 散列查找性能分析
散列表的裝填因子 α=表中記錄長度n/散列表長度m；
散列表的平均查找長度依賴于散列表的裝填因子，而不直接依賴于n或m。
查找成功的時的平均查找長度正常計算
查找失敗時的平均查找長度為直到查找到第一個空結(jié)點為止，做經(jīng)過的查找次數(shù)；
例如：拉鏈法為找到每一個同義詞線性鏈的最后一個空結(jié)點；
散列表中為直到找到第一個表中元素為空的時候做經(jīng)過的查找次數(shù)；
