扫码获取更多资源

●静态查找表的类型定义

静态查找表的抽象数据类型定义如下：

静态查找表可以用顺序表或线性链表表示，本节中只讨论它在顺存储结构模块中的 实现，读者可以自己完成在线性链表模块中实现的情况。设静态查找表釆用顺序存储结构， 其类型定义如下：

顺序表的查找

以顺序表表示的静态查找表可以采用顺序查找(Sequential Search)技术，这是一种最基 本、最简单的查找方法。

算法设计

从顺序表的一端向另一端逐个将关键字与给定值进行比较：如果相等，则查找成功，返 回该记录在表中位置；如果未找到与给定值相等的关键字，则查找失败，返回0。

索引顺序表的查找

以索引顺序表表示的静态查找表，可以采用分块查找(Blocking Search)技术，这是一种 对顺序查找改进的方法，也称索引顺序查找技术。

算法设计

按照表内记录的某种属性把表分成n(n>l)个块(子表)，并建立一个相应的“索引表”, 索引表中的每个元素对应一个块，其中包括该块内最大的关键字值和块中第一个记录的位 置；且后一个块中所有记录的关键字值都应该比前一个块中所有记录的关键字值大，而在 一个块内关键字值的大小可以无序。由于查找表分块有序，则索引表为有序表。索引表的 类型定义如下：

联系我们：