1、定義

順序查找又叫線性查找，是最基本的查找技術(shù)。

2、基本思想

? ? 　從表的一端開始（第一個(gè)或最后一個(gè)記錄），順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵宇和給定值K相比較。若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗。

3、存儲(chǔ)結(jié)構(gòu)

　　順序查找方法既適用于線性表的順序存儲(chǔ)結(jié)構(gòu)，也適用于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（使用單鏈表作存儲(chǔ)結(jié)構(gòu)時(shí)，掃描必須從第一個(gè)結(jié)點(diǎn)開始）。

????????注意：單鏈表為什么從第一個(gè)掃描，而不是最后一個(gè)，這與其存儲(chǔ)結(jié)構(gòu)有關(guān)，單鏈表名字即表示第一個(gè)第一個(gè)結(jié)點(diǎn)的地址，而不是最后一個(gè)結(jié)點(diǎn)的地址。

4、順序查找算法

（1）類型說(shuō)明

typedef struct{KeyType key；InfoType otherinfo； //此類型依賴于應(yīng)用}NodeType；typedef NodeType SeqList[n+1]； //0號(hào)單元用作哨兵

（2）具體算法

/*順序查找，參數(shù)說(shuō)明：a——數(shù)組；n——要查找的數(shù)組個(gè)數(shù)；key——要查找的關(guān)鍵字 */ int SeqSearch(int *a,int n,int key) //這里是指針引用 { int i； for(i=1；i<=n;i++){//缺陷：每次循環(huán)都需要對(duì)i是否越界，即是否小于等于n做判斷if(a[i]=key)return i;}return 0； }

上述操作中，每次循環(huán)都需要對(duì)i是否越界，即是否小于等于n做判斷，我們可以設(shè)置一個(gè)哨兵，不需要每次i與n作比較，改進(jìn)方案如下：

/*有哨兵的順序查找*/ int SeqSearch(int *a,int n,int key) //這里是指針引用 { int i； a[0]=key;/*設(shè)置a[0]為關(guān)鍵字值，我們稱之為“哨兵”，當(dāng)然也可以設(shè)置最后一個(gè)元素為“哨兵”*/int n;/*循環(huán)從數(shù)組尾部開始*/while(a[i]!=key){i--;}return i； /*返回0說(shuō)明查找失敗*/}

當(dāng)然參數(shù)也可以如下設(shè)置，把元素個(gè)數(shù)放在數(shù)據(jù)結(jié)構(gòu)體中定義：

int SeqSearch(Seqlist R，KeyType K) { //在順序表R[1..n]中順序查找關(guān)鍵字為K的結(jié)點(diǎn)，//成功時(shí)返回找到的結(jié)點(diǎn)位置，失敗時(shí)返回0int i；R[0].key=K； //設(shè)置哨兵for(i=n；R[i].key!=K;i--)； //從表后往前找return i； //若i為0，表示查找失敗，否則R[i]是要找的結(jié)點(diǎn) }

3、算法分析

① ?算法中監(jiān)視哨R[0]的作用

????為了在for循環(huán)中省去判定防止下標(biāo)越界的條件i≥1，從而節(jié)省比較的時(shí)間。

② 成功時(shí)的順序查找的平均查找長(zhǎng)度：

? ? ??

????在等概率情況下，pi=1/n(1≤i≤n)，故成功的平均查找長(zhǎng)度為

? ? ? ? (n+…+2+1)/n=(n+1)/2

????即查找成功時(shí)的平均比較次數(shù)約為表長(zhǎng)的一半。

????若K值不在表中，則須進(jìn)行n+1次比較之后才能確定查找失敗。

③ 表中各結(jié)點(diǎn)的查找概率并不相等的ASL

【例】在由全校學(xué)生的病歷檔案組成的線性表中，體弱多病同學(xué)的病歷的查找概率必然高于健康同學(xué)的病歷，由于上式的ASLsq在pn≥pn-1≥…≥p2≥p1時(shí)達(dá)到最小值。

????若事先知道表中各結(jié)點(diǎn)的查找概率不相等和它們的分布情況，則應(yīng)將表中結(jié)點(diǎn)按查找概率由小到大地存放，以便提高順序查找的效率。

????為了提高查找效率，對(duì)算法SeqSearch做如下修改：每當(dāng)查找成功，就將找到的結(jié)點(diǎn)和其后繼(若存在)結(jié)點(diǎn)交換。這樣，使得查找概率大的結(jié)點(diǎn)在查找過(guò)程中不斷往后移，便于在以后的查找中減少比較次數(shù)。

④ 順序查找的優(yōu)點(diǎn)

????算法簡(jiǎn)單，且對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論是用向量還是用鏈表來(lái)存放結(jié)點(diǎn)，也無(wú)論結(jié)點(diǎn)之間是否按關(guān)鍵字有序，它都同樣適用。

⑤ 順序查找的缺點(diǎn)

????查找效率低，因此，當(dāng)n較大時(shí)不宜采用順序查找。

⑥ ?適用情況

????對(duì)那些查找少而又經(jīng)常需要改動(dòng)的線性表，可采用鏈表作存儲(chǔ)結(jié)構(gòu)，進(jìn)行順序查找。

轉(zhuǎn)載于:https://www.cnblogs.com/yedushusheng/p/5524175.html

總結(jié)

以上是生活随笔為你收集整理的顺序查找(Sequential Search)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。