基本查找方法

1、基本查找方法數(shù) 據(jù) 結 構查找1.1 順序查找順序查找(Sequential search)也稱為線性查找，是采用線性表作為數(shù)據(jù)的存儲結構，對數(shù)據(jù)在表中存放的先后次序沒有任何要求。順序查找是最簡單的查找方法，它的基本思想是：查找從線性表的一端開始，順序將各單元的關鍵字與給定值k進行比較，直至找到與k相等的關鍵字，則查找成功，返回該單元的位置序號；如果進行到表的另一端，仍未找到與k相等的關鍵字，則查找不成功，返回0作為查找失敗的信息。查找順序查找的線性表定義如下：#define MAXITEM 100 /*最多項數(shù)*/struct element keytype key; Elemtype da

2、ta;typedef struct sqlistMAXITEM; 這里keytype和ElemType可以是任何相應的數(shù)據(jù)類型，如int、float或char等，在算法中我們規(guī)定它們缺省是int類型。 查找順序查找算法int sequsearch (sqlist r, int k, n) /*n為線性表r中元素個數(shù)*/ i=1 while (ri.key!=k & in) i=0; return(i); 查找順序查找算法分析此函數(shù)的主要運算時間是用于循環(huán)語句逐單元進行比較判斷ri.key是否等于k，因此順序查找的速度較慢，最壞的情況查找成功需比較n次，最好的情況是比較1次，如果對每個關鍵字進行

3、查找的概率相等，則查找成功所需的平均比較次數(shù)為(n+1)/2，而查找失敗則需比較(n+1)次，時間復雜度為O（n）。順序查找的優(yōu)點是算法簡單、適應面廣，且不要求表中數(shù)據(jù)有序。缺點是平均查找長度較大，特別是當n較大時，查找效率較低，不宜采用。查找1.2 二分查找二分查找(Birary search)也稱為折半查找，它的查找速度比順序查找快，但它要求數(shù)據(jù)在線性表中按查找的關鍵字域有序排列。設n個數(shù)據(jù)存放于數(shù)組r中，且已經(jīng)過排序，按由小到大遞增的順序排列。采用二分查找，首先用要查找的給定值k與表正中間元素的關鍵值相比較，此元素的下標 。查找比較結果有三種可能： 如果rm.keyk，說明如果存在欲查找

4、的元素，該元素一定在數(shù)組的前半部分，查找范圍縮小了一半，修改查找范圍的的上界high=m-1，繼續(xù)對數(shù)組的前半部分進行二分查找； 如果rm.keyk，說明如果存在欲查找的元素，該元素一定在數(shù)組的后半部分，查找范圍縮小了一半，修改查找范圍的的下界low=m+1，繼續(xù)對數(shù)組的后半部分進行二分查找； 如果rm.key=k，查找成功，m所指的記錄就是查找到的數(shù)據(jù)。查找重復上述過程，查找范圍每次縮小1/2，當范圍不斷縮小，出現(xiàn)查找范圍的下界大于上界時，則查找失敗，確定關鍵字為key的記錄不存在。二分查找是一種效率較高的算法，最好的情況是第一次比較即找到所查元素，即使一次比較沒有找到，也把進一步查找的范圍

5、了縮小一半。與此類似，每比較一次均使查找范圍減半，故最壞的情況所需比較次數(shù)為O(logn)，對于較大的n顯然較順序查找速度快得多。查找二分查找算法int binsearch(sqlist r,int k,n) int i,low=1,high=n,m,find=0;/*low和high分別表示查找范圍的起始單元下標和終止單元下標，find為查找成功的標志變量*/ while (low=high & !find) m=(low+high)/2; if(krm.key)查找二分查找算法續(xù) low=m+1; else i=m; find=1; if (!find) i=0; return(i); 查

6、找1.3 分塊查找分塊查找又稱為索引順序查找，是順序查找方法的另一種改進，其性能介于順序查找和二分查找之間。分塊查找把線性表分成若干塊，每一塊中的元素存儲順序是任意的，但塊與塊之間必須按關鍵字大小有序排列，即前一塊中的最大關鍵字值小于后一塊中的最小關鍵字值。還需要建立一個索引表，索引表中的一項對應于線性表中的一塊，索引項由鍵域和鏈域組成，鍵域存放相應塊的最大關鍵字，鏈域存放指向本塊第一個結點和最末一個結點的指針。索引表按關鍵字值的遞增順序排列。查找分塊查找的算法分兩步進行，首先確所查找的結點屬于哪一塊，即在索引表中查找其所在的塊，然后在塊內查找待查的數(shù)據(jù)。由于索引表是遞增有序的，可采用二分查找

7、，而塊內元素是無序的，只能采用順序查找。如果塊內元素個數(shù)較少，則不會對執(zhí)行速度有太大的影響。例如線性表中關鍵字為:9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82其索引如圖8.1所示。查找圖8.1 線性表與索引表查找索引表的定義struct indexterm keytype key; int low,high;typedef struct indexterm indexMAXITEM; 這里的keytype可以是任何相應的數(shù)據(jù)類型，如int、float、或char等，在算法中，我們規(guī)定keytype缺省是int類型。查找分塊查找算法int blksearch (sqlist r,index idx,int k,bn) /*bn為塊的個數(shù)*/ int i,high=bn,low=1,mid,j,find=0; while (low=high& !find) /*二分查找索引表*/ mid=(low+high)/2; if(kidxmid.key) low=mid+1;查找分塊查找算法續(xù) else find=1; if(find=1) i=idxmid.low; j=id