补充资料：查找表

查找表
search table

Chozhoo匕一00查找表(s earch table)同一类型的数据元素(或记录)构成的集合。由于集合中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。表是记录的集合，记录中可包含有处理过程中反复使用的“控制”信息字段，这种字段称为关键字。查找过程是将关键字中信息与某一值(一给定值或者某一文件当前记录的关键字信息等)比较，直到匹配成功或者整张表查完为止。若对查找表只作查找的操作，则称此类查找表为静态查找表。若在查找过程中同时插人查找表中不存在的数据元素，或从查找表中删除已存在的某个数据元素，则称此类表为动态查找表。静态查找表常用的查找方法有顺序表的查找、归并查找、有序表的查找等。动态查找表常用的查找方法有二叉排序树的查找、B一树和B+树的查找、数字查找树的查找和直接查找等。 顺序表的查找从表的起始位置(或某一指定位置)开始，向下依次地将各记录关键字与当前文件记录关键字比较进行查找。这种查找方法简单，易于编写程序，但查找速度慢。 归并查找也是一种顺序查找，查找是对一张表和一个文件进行的，要求表和文件的记录均已按关键字递增排序(或递减排序)。归并查找的过程如下:先对文件第一个记录的关键字与表的第一项的关键字进行比较，若匹配未成功，继续对表中下一项进行查找，直到一个相等的或较大的关键字的表项被找到。若较大，表明表中无此当前文件记录关键字值，继续对文件下一记录重复上述动作。如果相等，对记录进行处理，而后考察下一个文件记录。显然，此时不必从表端开始，只需从前一查找的终止位置继续下去即可。当表和文件都已排序时，归并查找是最快的方法口对于信息量大的表，该方法不需要把表全部放人内存中，可以从外存储器中分块调人，因此，归并技术特别有效。 有序表的查找又称折半查找，查找过程是以处于表区间中间位置记录的关键字和给定值比较。若相等，则查找成功。若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值，或者查找区间的大小小于零时(表明查找不成功)为止。在有n个元素的有序表中查找任一元素时，最多只做Llog。司+1次比较。在对于表中的项只作比较不作其他运算的查找算法中，折半查找方法是最优的。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。