靜态查找表：順序查找、折半查找、分塊查找

引言：

       除去各種線性和非線性的資料結構外，還有一種在實際應用中大量使用的資料結構——查找表。查找表是由同一類型的資料元素構成的集合。

       對查找表經常進行的操作有：1、查找某個"特定的"資料元素是否在查找表中；2、檢索某個"特定的"資料元素的各種屬性；3、在查找表中插入一個資料元素；4、從查找表中删去某個資料元素。對查找表隻作前兩種統稱為"查找"的操作，則稱此類查找表為靜态查找表。若在查找過程中同時插入查找表中不存在的資料元素，或者從查找表中删除已存在的某個資料元素，則稱此類表為動态查找表。

基礎知識：

[cpp]  view plain copy print ?

1. 關鍵字類型和資料元素類型統一說明如下：    
2. 典型的關鍵字類型說明可以是：    
3. typedef float KeyType;      //實型    
4. typedef int    KeyType;            //整型    
5. typedef char KeyType;            //字元串型    
6. 資料元素類型定義為：    
7. typedef struct {    
8.          KeyType   key;               //關鍵字域    
9.          ........                               //其他域    
10. }SElmType;    
11. 對兩個關鍵字的比較約定如下的宏定義：    
12. //對數值型關鍵字    
13. #define EQ(a, b)    ((a) == (b))    
14. #define LT(a, b)     ((a) < (b))    
15. #define LQ(a, b)     ((a) > (b))    
16.  //對字元串型關鍵字    
17. #define EQ(a, b)    (!strcmp((a), (b)))    
18. #define LT(a, b)     (strcmp((a), (b)) < 0)    
19. #define LQ(a, b)     (strcmp((a), (b)) > 0)   

具體分析：

1、順序查找。

       順序查找：從表中最後一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若直至第一個記錄，其關鍵字和給定值比較都不相等，則表明表中沒有所查記錄，查找不成功。

       性能分析：我們知道當讨論一個程式的性能時一般從3個角度：時間複雜度、空間複雜度、和算法的其他性能。由于在查找過程中，通常隻是需要一個固定大小的輔助空間來做比較，是以空間複雜度是一定的。而時間複雜度卻是可變的：其關鍵字和給定值進行過比較的記錄個數的平均值。

      适用範圍：順序查找一般适用于查找資料比較少的情況下。

      優點：

      1、算法實作簡單且适應面廣

      2、對表的結構無任何要求，無論記錄是否按關鍵字有序排列。

      3、即适用于順序表又适用于單連結清單。

     缺點：

     1、平均查找長度較大，特别是當n很大時，查找效率較低。

     2、速度慢，平均查找長度為 (n + 1) / 2，時間複雜度為 O(n) 

[cpp]  view plain copy print ?

1. typedef int ElementType;    
2. #define EQ(a, b)  ((a) == (b))    
3. int sequential(int Array[], ElementType key, int n)    
4. {    
5.     int index;    
6.     for(index = 0; index < n; index++){    
7.         if(EQ(Array[index], key))       
8.             return index + 1;    
9.     }    
10.     return -1;    
11. }    

2、折半查找。

       折半查找：折半查找又稱二分查找，先确定待查記錄所在的範圍（區間），然後逐漸縮小範圍直到找到或找不到該記錄為止。

       适用範圍：對于規模較大的有序表查找，效率較高。适合很少改動但經常查找的表。

        優點：

       1、折半查找的效率比順序查找要高。

       2、折半查找的時間複雜度為log2(n)

       3、折半查找的平均查找長度為log2(n+1) - 1

       缺點：

       1、折半查找隻适用于有序表

       2、折半查找限于順序存儲結構，對線性連結清單無法有效地進行折半查找     

        關鍵字key與表中某一進制素array[i]比較，有3中情況：

        1. key == array[i]， 查找成功

        2.key > array[i], 待查找元素可能的範圍是array[i]之前

        3.key < array[i], 待查找元素可能的範圍是array[i]之後

[cpp]  view plain copy print ?

1. typedef int ElementType;    
2. #define EQ(a, b)  ((a) == (b))    
3. #define LT(a, b)  ((a) < (b))    
4. #define LQ(a, b)  ((a) <= (b))    
5. int Search_Bin(ElementType Array[], int num, int length)    
6. {    
7.     int index_low, index_mid, index_high;    
8.     index_low = 1;    
9.     index_high = length;    
10.     while(index_low <= index_high){    
11.         index_mid = (index_low + index_high) / 2;       
12.         if(EQ(num, Array[index_mid]))    
13.             return index_mid + 1;    
14.         else if (LT(num, Array[index_mid]))    
15.             index_high = index_mid - 1;    
16.         else    
17.             index_low = index_mid + 1;    
18.     }    
19.     return -1;    
20. }    

3、分塊查找。

       分塊查找：分塊查找又稱索引順序查找，它是順序查找的一種改進方法。将n個資料元素“按塊有序”劃分為m塊（m<=n）。每一塊中的資料元素不必有序，但塊與塊之間必須“按塊有序”，即第1快中的任一進制素的關鍵字都必須小于第2塊中任一進制素的關鍵字；而第2塊中任一進制素又都小于第3塊中的任一進制素，……    

        操作步驟：

       1、先選取各快中的最大關鍵字構成一個索引表

       2、查找分兩部分：先對索引表進行二分查找或順序查找，以确定待查記錄在哪一塊中；然後在已确定的快中用順序法進行查找。

      優點：在表中插入或删除一個記錄時，隻要找到該記錄所在塊，就在該塊中進行插入或删除運算（因快内無序，是以不需要大量移動記錄）。

      缺點：增加了一個輔助數組的存儲空間和将初始表分塊排序的運算。

      性能：介于順序查找和二分查找之間。

[cpp]  view plain copy print ?

1. #define MAX 3    
2. #define MAXSIZE 18    
3. typedef int ElemType;    
4. typedef struct IndexItem{    
5.     ElemType index;    
6.     int start;    
7.     int length;    
8. }IndexItem;    
9. IndexItem indexlist[MAX];    
10. ElemType MainList[MAXSIZE] = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53};    
11. int sequential(IndexItem indexlist[], ElemType key)    
12. {    
13.     int index;    
14.     if(indexlist[0].index >= key) return 1;    
15.     for(index = 1; index <= MAX; index++){    
16.         if((indexlist[index-1].index < key)&&(indexlist[index].index >= key))     
17.                 return index+1;    
18.     }    
19.     return 0;    
20. }    
21. int mainsequential(ElemType MainList[], int index, ElemType key)    
22. {    
23.     int i, num=0;    
24.     for(i = 0; i < index-1; i++){    
25.         num += indexlist[i].length;     
26.     }    
27.     for(i = num; i < num+indexlist[index-1].length; i++){    
28.         if(MainList[i] == key) return i+1;      
29.     }    
30.     return -1;    
31. }    

除上面介紹的3種查找方法，還有針對有序表的斐波那契查找和插值查找以及靜态樹表的查找。