數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)小記6之查找1
平均查找長度：
對于含有n個記錄的表，查找成功的平均查找長度（ASL）為：
? ? ? ? ?n
ASL=∑ PiCi
? ? ? ? i=1
其中Pi為第i個查找表中記錄的概率，且∑ pi=1；
Ci為找到表中其關(guān)鍵字與給定值相等的第i個記錄時，和給定值已進行比較的關(guān)鍵字個數(shù)，隨查找過程不同而不同。
由于查找的基本運算是關(guān)鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能
順序查找
（1）過程為：從表的一端開始，依次將記錄的關(guān)鍵字和給定值進行比較，若某個記錄的關(guān)鍵字和給定值相等，在查找成功；反之，若掃描整個表后，仍未找到關(guān)鍵字和給定值相等的記錄，則查找失敗。
（2）順序查找方法既適用于線性表的順序存儲結(jié)構(gòu)，又適用于線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)
（3）實現(xiàn)算法：以順序表作為存儲結(jié)構(gòu)
數(shù)據(jù)元素類型定義：
typedef struct
{
KeyType key;//關(guān)鍵字域
InfoType otherinfo;//其他S域
}ElemType;
typedef struct
{ElemType *R;//存儲空間基地址
int length; //當(dāng)前長度
}SSTable;
【算法描述】
int Search_Seq(SSTable ST, KeyType key)
{for(i=ST.length;i>=1;--i)
? ? if(ST.R[i].key==key)? ? return i; //從后往前找，找到了就返回位置的下標(biāo)
?return? 0;//沒有查找成功返回0
}
以上這個算法每一步都要檢測整個表是否查找完畢，即每一步都要檢測是否i>=1，改進這個程序的方法是增加監(jiān)視哨先對ST.R[0]的關(guān)鍵字賦值key(key為徐璈查找的關(guān)鍵字，ST.R[0]這個位置不用于存儲，因為數(shù)據(jù)從末尾開始遍歷，到ST.R[1]結(jié)束，所以ST.R[0]可以用于存儲“哨兵”）
添加“哨兵”后的實現(xiàn)算法：
int Search_Seq(SSTable ST, KeyType key)
{ST.R[0].key=key;
for(i=ST.length;ST.R[i]!=key;--i)
? ?return i;?//從后往前找，找到了就返回位置
}
【算法分析】
時間復(fù)雜度為O(n);
? ? ? ? ? ? ? n
ASL=1/n∑i=(n+1)/2;
? ? ? ? ? ? ? i=1
順序查找的優(yōu)點是：算法簡單，對表結(jié)構(gòu)無任何要求。
缺點：平均查找長度較大，查找效率較低，所以當(dāng)n很大時，不宜采取順序查找。
2.折半查找（二分查找）
折半查找是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序結(jié)構(gòu)且表中元素按關(guān)鍵字有序排列。
查找過程為：從表的中間記錄開始，如果給定值和中間記錄的關(guān)鍵字相等，則查找成功；如果給定值大于或者小于中間記錄開始，則在表中大于或小于中間記錄的那一半中查找，這樣重復(fù)操作，直到查找成功，或者在某一步中查找區(qū)間為空，則代表查找失敗。
【算法描述】
用low和high來表示當(dāng)前查找區(qū)間的下界和上界，mid為區(qū)間的中心位置。
int Search_Bin(SSTable ST, KeyType key)
{
low=1;high=ST.length;//查找區(qū)間的初值
while(low<=high)
//循環(huán)執(zhí)行的條件是low<=high而不是low<high,因為當(dāng)low=high時，查找區(qū)間還有最后一個結(jié)點，還要進一步比較
{
mid=(low+high)/2;
if(key==ST.R[mid].key) return mid;//此時中間位置的元素恰為待查的元素
else if(key<ST.R[mid].key)? high=mid-1;//在前一個表中查找
else low=mid+1;
}
return 0;//表中不存在待查元素
}
【算法分析】
折半查找過程可用二叉樹來表示，
? ? ? ? ? ? ? ? ? ? ?h
ASL=（1/n）∑ j*2^(j-1)=(n+1)/nlog2(n+1)-1
? ? ? ? ? ? ? ? ? ? ?j=1
當(dāng)n較大時有以下近似結(jié)果：ASL=log2(n+1)-1;
?折半查找的時間復(fù)雜度為O(log2n),比較次數(shù)較少，查找的效率高，但是對表的要求高，只能用于順序存儲的有序表。折半查找不適用于數(shù)據(jù)元素經(jīng)常變動的線性表。
分塊查找：又叫索引順序查找，這是一種性能介于順序查找和折半查找之間的一種查找方法，在此查找法中需要建立一個“索引表”，索引表中含有最大關(guān)鍵字和起始地址，便于查找，若線性表既要快速查找又要經(jīng)常動態(tài)變化，則可采用分塊查找。
