靜態查找是指在靜態查找表上進行的查找操作，查找滿足條件的資料元素的存盤位置或各種屬性。它具有以下三種查找方式：
一、順序查找
1、順序查找，顧名思義就是在查找程序中按順序依次用查找條件中給定的值與查找表中資料元素的關鍵字值進行比較，若某個記錄的值與給定值相等，則查找成功，回傳該記錄值的存盤位置；反之，若直到最后一個記錄值的關鍵字值與給定值均不相等，則查找失敗，回傳查找失敗標志。
2、查找表的存盤結構是線性表（順序表或鏈表）。
3、順序表的型別定義：
#define MAX_NUM 100 //用于定義表的長度
typedef struct elemtype{
keytype key;
……
}RecordType[MaxSize];
資料元素個數為n(n<MAX_NUM)；分別存放在陣列的下標變數a[1]~a[n]中。
4、假設我們有多個關鍵字，我們只選取一個我們需要比較的關鍵字的值，把它們放入陣列r中，這時陣列有n個元素，假設要查找的關鍵字的記錄是k，下面我們給出順序查找的完整演算法：
int SeqSearch(RecordType r,int n, Keytype k){
/*回傳關鍵字值等于k的資料元素在表r中的位置，n為表中元素的個數*/
i=n;
r[0].key=k;/*監視哨*/
while (r[i].key!=k){
i--;
}
if(i>0){
return (i); /*查找成功*/
}else{
return (-1); /*查找失敗*/
}
}
二、折半查找
1、折半查找只適用對有序順序表進行查找。
2、每進行一次折半查找，要么查找成功，結束查找；要么將查找范圍縮小一半，如此重復，直到查找成功或查找范圍縮小為空即查找失敗為止。因此折半查找需要的時間相對較少，效率高。
3、折半查找又稱二分查找。是對有序的順序表進行的高效查找方法。有序表的對應向量R中最多可錄入12個結點的關鍵字。每個關鍵字為1000以內的正整數，且用半角逗號分隔。
4、折半查找演算法的描述如下所示：
int BinSearch(RecordType r,int n, Keytype k){
/*在有序表r中折半查找關鍵字值等于k的資料元素*/
int low,high,mid;/* low是指起始點；high是指最高點；mid是指low加high的和除以2的值；*/
low=1; high=n;/*設定初始查找范圍的低、高端指標*/
while (low <= high){
mid=(low+high)/2; /*取表的中間位置*/
if(k==r[mid].key){
return (mid); /*查找成功*/
}else{
if(k< r[mid].key){
high=mid-1; /*在左子表中查找*/
}else{
low=mid+1; /*在右子表中查找*/
}
}
}
return (-1); /*查找失敗*/
}
5、二分查找演算法平均查找長度為log2n，比較次數少，查找速度快。它適用于那種一經建立就很少改動，而又經常需要查找的順序表。
三、分塊檢索
1、分塊查找（Blocking Search）又稱索引順序查找。它是一種性能介于順序查找和二分查找之間的查找方法。
2、查找表存盤結構：查找表由“分塊有序”的線性表和“有序的”索引表組成。
（1）“分塊有序”的線性表：線性表R被均分為若干塊，每一塊中的關鍵字不一定有序，但前一塊中的最大關鍵字必須小于后一塊中的最小關鍵字，即表示“分塊有序”的。
（2）“有序的”索引表：抽取各塊中的最大關鍵字及其起始位置和長度構成一個索引表ID中，
3、分塊查找時首先查找索引表。索引表是有序表，可采用二分查找或順序查找，以確定待查的結點在哪一塊。然后在已確定的塊中進行順序查找。
4、索引表中的資料元素由兩個域構成，key域為被索引的若干個資料元素中關鍵字的最大值，link域為被索引的若干個資料元素中第一個資料元素的位置編號。
四、靜態查找方法比較
1、ASL（Average Search Length），即平均查找長度： 順序查找最大，折半查找最小，分塊查找在兩者（順序查找和折半查找）之間。
2、適用的表結構：順序查找是有序表、無序表都可以（即對表無要求），折半查找是有序表，分塊查找是分塊有序表。
3、存盤結構：順序查找是順序存盤結構和線性鏈表，折半查找是順序存盤結構，分塊查找是順序存盤結構和線性鏈表。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/48288.html
標籤：非技術區