靜態(tài)查找
順序查找 折半查找 散列查找動(dòng)態(tài)查找
二叉排序樹 散列查找ASL(平均查找長(zhǎng)度) - 衡量查找算法效率的主要指標(biāo)
ASL=ΣPiCi;(1...n)
P為查找第i個(gè)元素的概率臂聋，Ci為查找到第i個(gè)元素所需的比較次數(shù)
順序查找（線性查找）
注意：線性鏈表只能進(jìn)行順序查找寞埠；
typedef struct {
ElemType *data;
int TableLength;
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
ST.data[0]=key;//哨兵 0號(hào)單元留空用來(lái)存哨兵
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;
對(duì)于有序表的順序查找
ASL(suc)= (n+1)/2;
ASL(fal)=Qi * (Lj-1)=((n+1)/2 + n) /（n+1）;(j為第j個(gè)失敗結(jié)點(diǎn))
化簡(jiǎn)得 =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é)點(diǎn)數(shù) * 層數(shù)的和）/總結(jié)點(diǎn)數(shù)
ASL（失斈灰佟）為（所有失敗的節(jié)點(diǎn) * 層數(shù)的和）/n+1蓝丙；（這里失敗的節(jié)點(diǎn)指的是樹中2*N0+N1）;
如圖：
圖中所有方形節(jié)點(diǎn)即為失敗節(jié)點(diǎn)；
分塊查找（索引順序查找）
將表分塊望拖，塊內(nèi)可無(wú)序渺尘，塊間有序
塊間即索引表
ASL=Li+Ls;(Li索引查找，Ls塊內(nèi)查找)
長(zhǎng)度為n的表分為b塊说敏，每塊有s個(gè)記錄鸥跟；即（b=s/n）
Li=(b+1)/2;(b=s/n)
Ls=(s+1)/2
ASL=(s2+2s+n)/2s;
實(shí)際上對(duì)索引及塊內(nèi)記錄的查找都為順序查找，若為折半查找改為logn即可盔沫；
B樹及B+樹
其實(shí)對(duì)于B樹医咨，比較重要的幾點(diǎn)：
B樹的特性
對(duì)于一個(gè)m階B樹
1）每個(gè)結(jié)點(diǎn)最多m顆子樹,（即至多含有m-1個(gè)關(guān)鍵字）
2）根節(jié)點(diǎn)不是終端節(jié)點(diǎn)時(shí)，則至少有兩個(gè)子樹
3）除根節(jié)點(diǎn)外所有的非葉節(jié)點(diǎn)架诞，至少有ceil（m/2）顆子樹拟淮，（即至少含有ceil（m/2）-1個(gè)關(guān)鍵字）
4）結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)n（ceil(m/2)-1<=n<=m-1）
5）所有的葉結(jié)點(diǎn)出現(xiàn)在同一層上，且不帶信息
所有結(jié)點(diǎn)的平衡因子均為0的多路查找樹谴忧。
B樹的高度(n為關(guān)鍵字個(gè)數(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)整很泊，分裂方式很重要，我從中體會(huì)出的一點(diǎn)就是不管是增結(jié)點(diǎn)還是刪除結(jié)點(diǎn)俏蛮，首先判斷關(guān)鍵字容量是否符合撑蚌，符合就結(jié)束，不符合搏屑，就要分裂争涌，分裂的情況中比較復(fù)雜的就是要和它的父結(jié)點(diǎn)發(fā)生變動(dòng)的，像加個(gè)結(jié)點(diǎn)辣恋，有一個(gè)原則就是關(guān)鍵字超過(guò)上限了（m/2(向上取整)-1）就要分裂完全分開亮垫，兩個(gè)的分成一個(gè)，多出來(lái)的上升為父結(jié)點(diǎn)伟骨，父結(jié)點(diǎn)關(guān)鍵字溢出則繼續(xù)分裂上升從而最終結(jié)果就是這顆B樹 長(zhǎng)高了饮潦！ 對(duì)于刪除比較復(fù)雜的也是要從父結(jié)點(diǎn)借關(guān)鍵字的情況，（這個(gè)前提當(dāng)然是在兄弟不夠借的情況下）
B+樹
這里只寫與B樹不同的地方携狭，
3）結(jié)點(diǎn)的子樹個(gè)數(shù)與關(guān)鍵字個(gè)數(shù)相同
4）所有葉結(jié)點(diǎn)包含全部的關(guān)鍵字按順序排列继蜡，相鄰結(jié)點(diǎn)同樣也按順序排列且互相鏈接起來(lái)
5）所有的分支結(jié)點(diǎn)中僅包含它的各個(gè)子結(jié)點(diǎn)中關(guān)鍵字最大的值及指向其子節(jié)點(diǎn)的指針
B+樹種葉結(jié)點(diǎn)包含信息，所有非葉結(jié)點(diǎn)僅起到索引的作用 ，通常有兩個(gè)頭指針稀并，一個(gè)只想最小的關(guān)鍵字仅颇，便于進(jìn)行鏈?zhǔn)降捻樞虿檎遥硪粋€(gè)是根節(jié)點(diǎn)碘举，便于進(jìn)行多路查詢忘瓦。
Hash表
關(guān)于散列表比較重要的一塊就是處理沖突的方法以及平均查找長(zhǎng)度ASL
- 構(gòu)造散列函數(shù)得到構(gòu)造散列表
1）直接頂?shù)刂贩?br> H（key）=a * k+b；
適合關(guān)鍵字分布基本連續(xù)引颈，若分配不連續(xù)將造成空間浪費(fèi)
2）除留余數(shù)法
散列表的長(zhǎng)度為m耕皮，選一個(gè)不大于但接近m的質(zhì)數(shù)p；
H（key）=key%p蝙场；
3）數(shù)字分析法
4）平方取中法
5）折疊法
一般構(gòu)造函數(shù)題目中會(huì)直接給出凌停，這塊并不難
Hi=（H（key）+di）%m； - 處理沖突的辦法
開放定地址發(fā)
1）線性探測(cè)
即沖突發(fā)生時(shí)李丰，順序查看表中下一個(gè)單元直到不沖突為止苦锨；
2）平方探測(cè)法（又稱二次探測(cè)）
即di=12，-12趴泌，22舟舒，-22，.....,k2嗜憔，-k2秃励，k<=m/2;m必須為4k+3的質(zhì)數(shù)
3）再散列法（雙散列法）
di=Hash2(key);
即兩個(gè)散列函數(shù)
4）偽隨機(jī)序列
拉鏈法
將散列在同一地址的關(guān)鍵字用線性鏈表連接起來(lái) - 散列查找性能分析
散列表的裝填因子 α=表中記錄長(zhǎng)度n/散列表長(zhǎng)度m；
散列表的平均查找長(zhǎng)度依賴于散列表的裝填因子吉捶，而不直接依賴于n或m夺鲜。
查找成功的時(shí)的平均查找長(zhǎng)度正常計(jì)算
查找失敗時(shí)的平均查找長(zhǎng)度為直到查找到第一個(gè)空結(jié)點(diǎn)為止，做經(jīng)過(guò)的查找次數(shù)呐舔；
例如：拉鏈法為找到每一個(gè)同義詞線性鏈的最后一個(gè)空結(jié)點(diǎn)币励；
散列表中為直到找到第一個(gè)表中元素為空的時(shí)候做經(jīng)過(guò)的查找次數(shù)；
