9.3.1 动态查找表的类型定义 　　动态查找表的抽象数据类型定义如下： ADT DynamicSearchTable { 　数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同 　　　　　　　的关键字，可唯一标识数据元素。 　数据关系R：数据元素同属一个集合。 　基本操作P： 　　InitDSTable(&DT); 　　　操作结果：构造一个空的动态查找表 DT。 　　DestroyDSTable(&DT); 　　　初始条件：动态查找表DT存在； 　　　操作结果：销毁动态查找表 DT。 　　SearchDSTable(DT, kval); 　　　初始条件：动态查找表DT存在，kval 为和关键字类型相同的给定值； 　　　操作结果：若DT中存在其关键字等于 kval 的数据元素，则函数 　　　　　　　　值为该元素的值或在表中的位置，否则为"空"。 　　InsertDSTable(&DT, e); 　　　初始条件：动态查找表DT存在，e 为待插入的数据元素； 　　　操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e 到DT。 　　DeleteDSTable(&T, kval); 　　　初始条件：动态查找表DT存在，kval 为和关键字类型相同的给定值； 　　　操作结果：若DT中存在其关键字等于 kval 的数据元素，则删除之。 　　TraverseDSTable(DT, Visit()); 　　　初始条件：动态查找表DT存在，Visit 是对结点操作的应用函数； 　　　操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次。 　　　　　　　　一旦 visit() 失败，则操作失败。 } ADT DynamicSearchTable 　　可见，动态查找表的特点是，在查找过程中尚需进行"插入"或"删除"的操作。因此，表示动态查找表的结构应不仅便于查找，还应便于插入和删除。