数据结构与算法－静态查找表

顺序查找

顺序表的结构定义如下：

// 静态表的表长
const int Maxsize = 20;

typedef struct {
    // 关键字
    KeyType key;
}TableElm;

typedef struct {
    TableElm elm[Maxsize +1];
    // 最后一个元素的下标
    int n;
}SqTable

静态查找表中数组的第0个单元，用于设置“岗哨”，以便简化查找运算的实现，数据存放在数组的第1到第n个单元中，第n+1到最后一个单元为备用区。

顺序查找算法描述如下：

int SearchSqTable(SqTable T, KeyType key){
    T.elem[0].key = key;
    int i = T.n;
    while (T[i].key != key){
        i--;
    };
    return i;
}

本算法的精炒之处在于在查找之前对T.elem[0]赋以待查的key，这样，算法中免去了每次查找表都要检测表是否查找完毕，并保证while循环一定会终止，elem[0]起到了岗哨的作用，因此，不必将i>0写入循环条件，从而简化循环条件。

顺序查找的优点是简单，对表无要求，缺点是比较次数多。

顺序查找成功时平均查找长度 ASL = (n+1)/2，查找失败时ASL = n +1。

二分查找

如果顺序表中的数据元素是按照键值大小的顺序排列的，查找运算可以用效率更高的二分查找实现。

二分查找的查找过程为每次用给定值与处在表中间位置的数据元素的键值进行比较，确定给定值的所在区间，然后逐步缩小查找区间，重复这个过程直到找到或确认找不到该元素为止。

用给定值key与处在中间位置的数据元素T.elm[mid]的键值T.elm[mid].key进行比较，可根据三种比较结果区分三种情况：

1. key = T.elm[mid].key ，查找成功，T.elm[mid]即为待查元素。

2. key < T.elm[mid].key，说明若待查元素在表中，则一定排在T.elm[mid]之前。

3. key > T.elm[mid].key，说明若待查元素在表中，则一定排在T.elm[mid]之后。

二分查找示意图：

二分查找的算法如下：

int SearchBin(SqTable T,KeyType key){
    int low, high;
    low = 1, high = T.n;
    while(low<=high){
        int mid = (low+high)/2;
        if(key == T.elm[mid].key){
            return mid;
        }else if(key <T.elm[mid].key){
            high = mid -1;
        }else{
            low = mid +1;
        }
    }
}

二分查找算法每进行一次键值与给定值的比较，查找区间的长度至少减少为原来的二分之一，由此我们可以得出以下结论：

二分查找的时间性能比顺序查找好，但是相比顺序查找，二分查找要求表元素是排好序的，当采用的存储结构不是顺序表，或者顺序表中的元素未按键值的次序递增或递减排列时，则不能进行二分查找。

索引顺序查找

索引顺序表是结合了顺序查找和二分查找的优点构造的一种带索引的存储结构，索引顺序表由两部分组成：一个索引表和一个顺序表。其中顺序表的组织形式与普通的顺序表完全相同，而索引表在组织形式上本身也是一个顺序表。

索引表通过索引将顺序表分割为若干块，让顺序表呈现出“按块有序”的性质，所谓“按块有序”是指顺序表中的数据元素被划分为一些子表，并且对其中任意两个相邻的子表来说，排在后面的子表中的任一数据元素的键值大于排在前面子表中的所有数据元素的键值。

查找步骤：

1. 先建立最大或最小关键字表。

将每块中最大或最小关键字及指示块首记录在表中位置的指针依次存入一张表中，此表称为索引表，将索引表按键值进行排序。

2. 查找索引表，以确定所查元素所在的块号。

将查找关键字k与索引表中每一元素（即各块中最大关键字）进行比较，以确定所查元素所在块号。

3. 在相应块中按顺序查找关键字为k的记录。

算法分析

总结

静态查找表的上述三种不同实现各有优缺点。其中，顺序查找效率最低但限制最少；二分查找效率最高，但限制最强；而分块查找则介于上述二者之间，在实际应用中应根据需要加以选择。