计算机数据结构第九章查找讲述.ppt

第九章 查找 9.1 静态查找表 静态查找表的定义： ADT StaticSearchTable { 数据对象D: D是具有相同特性的数据元素的集合。各 个数据元素均含有类型相同，可唯一标识 数据元素的关键字。 数据关系R: 数据元素同属一个集合。 基本操作P: Create(ST, n) 操作结果：构造一个含 n 个数据元素的静态查找表ST。 Destroy(ST) 初始条件：静态查找表 ST 存在。 操作结果：表 ST 被销毁。 Search( ST, key ) 初始条件：静态查找表 ST 存在，key为和关键字 类型相同的给定值。 操作结果：若ST中存在其关键字等于 key 的数据 元素，则函数值为该元素的值或它在 表中的位置，否则函数值为空。 Traverse( ST, Visit() ) 初始条件：静态查找表 ST 存在，Visit 是对元素 操作的应用函数。 操作结果：按某种次序对ST的每个元素调用函数 Visit 一次且仅一次。一旦Visit 失败， 则操作失败。 9.1.1 顺序表的查找 9.1.2 有序表的查找 若顺序表中所有记录的关键字满足下列关系: ST.elem[i].key ≤ ST.elem[i+1].key i = 1, 2, …, n-1 则称其为有序顺序表，简称有序表。 折半查找判定树 折半查找判定树：折半查找过程可用二叉树描述 有序顺序表：a1，a2，a3，a4，a5，a6，a7，a8 折半查找判定树 查找失败 查找失败 折半查找判定树 折半查找判定树 9.1.4 索引顺序表的查找 —— 分块查找 第一步：建立索引表： 第二步：分块查找 9.2 动态查找表 动态查找表的特点 动态查找表的定义： ADT DynamicSearchTable { 数据对象D: D是具有相同特性的数据元素的集合。各 个数据元素均含有类型相同，可唯一标识 数据元素的关键字。 数据关系R: 数据元素同属一个集合。 基本操作P: InitDSTable( DT ) 操作结果：构造一个空的动态查找表 DT。 DestroyDSTable( DT ) 初始条件：动态查找表 DT 存在。 操作结果：动态查找表 DT 被销毁。 SearchDSTable( DT, key ) 初始条件：动态查找表 DT 存在，key为和关键字 类型相同的给定值。 操作结果：若DT中存在其关键字等于key 的数据 元素，则函数值为该元素的值或它在 表中的位置，否则函数值为空。 InsertDSTable( DT, e ) 初始条件：动态查找表DT 存在，e 为待插入的数 据元素。 操作结果：若DT 中不存在其关键字等于 e.key 的 数据元素，则插入 e 到 DT。 DeleteDSTable( DT, key ) 初始条件：动态查找表 DT 存在，key为和关键字 类型相同的给定值。 操作结果：若DT 中存在其关键字等于key 的数据 元素，则删除之。 Traverse( DT, Visit() ) 初始条件：动态查找表 DT 存在，Visit 是对结点 操作的应用