查找-線性表的查找-順序查找

　　順序查找(Sequential Search)

　　在表的組織方式中線性表是最簡單的一種順序查找是一種最簡單的查找方法

　　順序查找的基本思想

　　基本思想是從表的一端開始順序掃描線性表依次將掃描到的結點關鍵宇和給定值K相比較若當前掃描到的結點關鍵字與

　　K相等則查找成功;若掃描結束後仍未找到關鍵字等於K的結點則查找失敗

　　順序查找的存儲結構要求

　　順序查找方法既適用於線性表的順序存儲結構也適用於線性表的鏈式存儲結構(使用單鏈表作存儲結構時掃描必須從第一個

　　結點開始)

　　基於順序結構的順序查找算法

　　()類型說明

　　typedef struct{

　　KeyType key;

　　InfoType otherinfo; //此類型依賴於應用

　　}NodeType;

　　typedef NodeType SeqList[n+]; //號單元用作哨兵

　　()具體算法

　　int SeqSearch(Seqlist RKeyType K)

　　{ //在順序表R[n]中順序查找關鍵字為K的結點

　　//成功時返回找到的結點位置失敗時返回

　　int i;

　　R[]key=K; //設置哨兵

　　for(i=n;R[i]key!=K;i); //從表後往前找

　　return i; //若i為表示查找失敗否則R[i]是要找的結點

　　} //SeqSearch

　　注意

　　監視哨設在高端的順序查找【參見練習】

　　()算法分析

　　① 算法中監視哨R[]的作用

　　為了在for循環中省去判定防止下標越界的條件i≥從而節省比較的時間

　　②成功時的順序查找的平均查找長度

　　

　　在等概率情況下p i =/n(≤i≤n)故成功的平均查找長度為

　　(n+…++)/n=(n+)/

　　即查找成功時的平均比較次數約為表長的一半

　　若K值不在表中則須進行n+次比較之後才能確定查找失敗

　　③表中各結點的查找概率並不相等的ASL

　　【例】在由全校學生的病歷檔案組成的線性表中體弱多病同學的病歷的查找概率必然高於健康同學的病歷由於上式的ASL sq

　　在p n ≥p n ≥…≥p ≥p 時達到最小值

　　若事先知道表中各結點的查找概率不相等和它們的分布情況則應將表中結點按查找概率由小到大地存放以便提高順序查找的效率

　　為了提高查找效率對算法SeqSearch做如下修改每當查找成功就將找到的結點和其後繼(若存在)結點交換這樣使得查

　　找概率大的結點在查找過程中不斷往後移便於在以後的查找中減少比較次數

　　④順序查找的優點

　　算法簡單且對表的結構無任何要求無論是用向量還是用鏈表來存放結點也無論結點之間是否按關鍵字有序它都同樣適用

　　⑤順序查找的缺點

　　查找效率低因此當n較大時不宜采用順序查找

From:http://tw.wingwit.com/Article/program/sjjg/201311/23867.html