2009/12/29 9.0一些定义-查找 9.0一些定义-类型定义 。查找 typedef struct ·定义：根据给定的某个值，在查找表中确定一 KeyType key;关键字域 个其关健字等于给定值的记录或数据元素。 其它域 }ElemType; 若查找表中存在这样一个记录，则称查找 是成功的，此时查找结果为给出整个记录的信 根据具体的关键字类型，定义用于比较的、带参的宏 息，或指示该记录在查找表中的位置： #define EQ(a,b)... #define LT(a,b).… 否则称查找不成功，此时查找结果可给出 #define LQ(a,b)... 一个空记录或空指针。 7103 图 8/10 圄 戴帽时像D:具有相同特性的嫩元素的桌合。 9.1静态查找表 数关暴R:元素同属 一个桌合。 盖本操作P: Create(&ST,n) ▣抽象数据类型定义 操作结果：构造一个含个数拥元素的牌态查找表ST. Destroy(&ST) 。9.1.1顺序查找 初始条件，静态查找表ST存在 ,9.1.2有序表的查找 操作结果：轴服表ST. Search(ST,key) ·折半查控 初始条件静志查找表ST存在，key为和关幢字类型相同的始定值。 ,望波拉奥查找、播值查找 操作结果，若ST中存在其关能李等于key的数婚元来，则图数值为该 元素的值或在妻中的位置，否则为空” ■9.1.3整态树表的查找 Traverse(ST,Visit()) 。9.1.4索引顺序表的查找（分块查找】 初始条件静达查找表ST存在，Vs北是对元求作的应用西 操作结果：按某种洗序对5T的每个元家调用函数Vst)一次且仅一 次。一且Vst)失收，则操作失收 9110g 10/103 9.1.1顺序查找(1) 9.1.1顺序查找(2) 。查找表纳构：以顺序表或线性链表表示 ·对顺序麦的顺序查找 。基本思想：从一增开始向另一增，逐个进行记录的关健字 typedef struct( 和给定值的比较，若某个记录的关键字和给定值比校相等， ElemType*elem;数据元素存情空间蓬址 则查找成功：反之，若直至另一嘴，其关健字和给定值比 int length; 表长度 较都不等，则表明表中没有所查记录，查找不成功。 )SSTable; 查找成功示例： (34,44,4312,53,55,73,6477,kcy=64 查找不成功示例： 34,44,43,12,53,55,73,64,77,key=88 1y103 12/103 图 22009/12/29 2 9.0 一些定义-查找  查找  定义：根据给定的某个值，在查找表中确定一 个其关键字等于给定值的记录或数据元素 7/103 。 若查找表中存在这样一个记录，则称查找 是成功的，此时查找结果为给出整个记录的信 息，或指示该记录在查找表中的位置； 否则称查找不成功，此时查找结果可给出 一个空记录或空指针。 9.0 一些定义-类型定义 typedef struct { KeyType key; //关键字域 …… //其它域 8/103 } ElemType; 根据具体的关键字类型, 定义用于比较的、带参的宏 #define EQ(a, b) … #define LT(a, b) … #define LQ(a, b) … 9.1 静态查找表  抽象数据类型定义  9.1.1 顺序查找 912 有序表的查找 9/103  9.1.2 有序表的查找  折半查找  斐波拉契查找、插值查找  9.1.3 静态树表的查找  9.1.4 索引顺序表的查找(分块查找) ADT StaticSearchTable{ 数据对象D:具有相同特性的数据元素的集合。 数据关系R:数据元素同属一个集合。 基本操作P: Create(&ST, n) 操作结果：构造一个含n个数据元素的静态查找表ST. Destroy(&ST) 初始条件：静态查找表ST存在. 操作结果：销毁表ST. 10/103 Search(ST, key) 初始条件：静态查找表ST存在，key为和关键字类型相同的给定值. 操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该 元素的值或在表中的位置，否则为“空”. Traverse(ST,Visit()) 初始条件：静态查找表ST存在,Visit是对元素操作的应用函数. 操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一 次。一旦Visit()失败，则操作失败. } ADT StaticSearchTable 9.1.1 顺序查找(1)  查找表结构：以顺序表或线性链表表示  基本思想：从一端开始向另一端，逐个进行记录的关键字 和给定值的比较，若某个记录的关键字和给定值比较相等， 11/103 则查找成功；反之，若直至另一端，其关键字和给定值比 较都不等，则表明表中没有所查记录，查找不成功。 查找成功示例： (34, 44, 43, 12, 53, 55,73, 64, 77)，key = 64 查找不成功示例： (34, 44, 43, 12, 53, 55,73, 64, 77)，key = 88 9.1.1 顺序查找(2)  对顺序表的顺序查找 typedef struct{ ElemType *elem; //数据元素存储空间基址 12/103 int length; //表长度 }SSTable;