【概述】

順序查找是最基本的查找技術(shù)之一，其基本思想是：從數(shù)據(jù)結(jié)構(gòu)線形表的一端開(kāi)始，順序掃描，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值 k 相比較，若相等則表示查找成功；若掃描結(jié)束仍沒(méi)有找到關(guān)鍵字等于?k 的結(jié)點(diǎn)，表示查找失敗。

【復(fù)雜度分析】

對(duì)于 n 個(gè)記錄的順序表，查找第 i 個(gè)記錄時(shí)，需要進(jìn)行 n-i+1 次關(guān)鍵碼的比較。

在查找成功時(shí)，有：

設(shè)每個(gè)記錄的查找概率相等，則有：

故：

而當(dāng)查找不成功時(shí)，需要 n+1 次比較。

所以，順序查找的時(shí)間復(fù)雜度為 O(n)。

【源程序】

1.順序表

int SequenceSearch(int a[], int value, int n){int i;for(i=0; i<n; i++)if(a[i]==value)return i;return -1; }

2.單鏈表

int SequenceSearch(Node<int> *first,int k){Node *p=first->next;int cnt=1;while(p!=NULL&&p->data!=k){p=p->next;cnt++;}if(p->data==k)return cnt;return 0; }

總結(jié)

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

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