静态查找表：顺序查找、折半查找、分块查找

引言：

       除去各种线性和非线性的数据结构外，还有一种在实际应用中大量使用的数据结构——查找表。查找表是由同一类型的数据元素构成的集合。

       对查找表经常进行的操作有：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种查找方法，还有针对有序表的斐波那契查找和插值查找以及静态树表的查找。