数据结构

顺序表与线性链表都可以表示静态查找表。两者的实现静态查找表相似，这里以顺序表为例。 顺序查找就是从表中最后一个记录开始，逐个进行记录关键字与给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，反之失败。 对于顺序查询有一种技巧可以优化效率。 查找之前先将key赋值给elem[0]，搜索从后向前搜索，这样可以免去每次循环都要检查整个表是否搜索完毕，这样时间可以减少一半。当然监视哨也可以放在表尾。

无序表可以使用顺序查找，有序表除此以外还可以使用折半查找。 折半查找就是先确定待查记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到记录为止。 折半查找的效率比顺序查找高，但折半查找只使用于有序表，且限于顺序储存结构(对线性链表无法有效地进行查找)。 斐波那契查找是根据斐波那契序列的特点对表进行切割，在表中找到一个关键字比某一斐波那契数小1，将这个关键字作为割点将数组分为两半，过程与折半查找类似。 斐波那契查找的平均性能比折半查找好，但最坏情况下性能却比折半查找差。还有一个优点就是分割时只需进行加减运算。 插值查找是根据给定值key来确定进行比较的关键字的查找方式。这种插值查找只使用于关键字均匀分布的表，在这种情况下，对表长较大的顺序表，其平均性能比折半查找好。

上一节对有序表的查找性能都是在“等概率”的前提下进行的，即当各记录的查找概率相等时，按折半查找性能最优。 那对于不同概率的查询如何找到最优的查询方法。需要一个概念PH值即带权平均查找次数。 称取PH值最小的二叉树为静态最优查找树。 由于构造静态最优查找树花费的时间代价较高，因此这里退而求其次我们研究次优二叉树， 构造次优二叉树的方法是每次取△p的最小值为根节点构建树表