如何进行查找? 查找的方法取决于查找表的结构 由于查找表中的数据元素之间不存在明显的组 织规律,因此不便于查找。 为了提高查找的效率,需要在查找表中的 元素之间人为地附加某种确定的关系,换句 话说,用另外一种结构来表示查找表
如何进行查找？ 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组 织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的 元素之间人为地 附加某种确定的关系，换句 话说， 用另外一种结构来表示查找表
查找方法评价 查找速度 占用存储空间多 算法本身复杂程度 平均查找长度 ASL(Average Search Length) 为确定记录在表中的位置,需和给定值进行比 较的关键字的个数的期望值叫査找算法的 对含有n个记录的表,ASL=∑pC 其中:P为查找表中第计个元素的概率∑P1=1 c为找到表中第i个元素所需比较次数
查找方法评价 • 查找速度 • 占用存储空间多少 • 算法本身复杂程度 • 平均查找长度ASL(Average Search Length)： 为确定记录在表中的位置，需和给定值进行比 较的关键字的个数的期望值叫查找算法的~ 为找到表中第 个元素所需比较次数 其中： 为查找表中第 个元素的概率， 对含有 个记录的表， c i p i p n ASL p c i n i i i n i i i 1 1 1
静查找表 抽象数据类型静态查找表的定义: ADT StaticSearchTable i 数据对象D:D是具有相同特性的 数据元素的集合。每 个数据元素含有类型 相同的关键字,可唯 标识数据元素。 数据关系R:数据元素同属一个集合
抽象数据类型静态查找表的定义: ADT StaticSearchTable { D是具有相同特性的 数据元素的集合。每 个数据元素含有类型 相同的关键字，可唯 一标识数据元素。 数据关系R：数据元素同属一个集合。 静 态 查 找 表 数据对象D:
基本操作P: Create(&ST,n);/构造一个含n个数据 元素的静态查找表ST Destroy( &st); ∥销毁表ST。 Search(ST,key);查找ST中其关键字等 于kval的数据元素。 Traverse(sT, visito) ∥按某种次序对 ST的每个元素调用函数 s0一次且仅一次, 3 ADT StaticSearchTable
Create(&ST, n); //构造一个含 n 个数据 元素的静态查找表ST。 Destroy(&ST); //销毁表ST。 Search(ST, key); //查找 ST 中其关键字等 于kval 的数据元素。 Traverse(ST, Visit()); //按某种次序对 ST的每个元素调用函数 Visit()一次且仅一次， } ADT StaticSearchTable 基本操作 P：
顺序表的查找 以顺序表表示静态查找表,则 Search函数可 用顺序查找来实现。其顺序存储结构如下: typedef struct i ElemType *elem;∥数据元素存储空间基址,建表时 按实际长度分配,0号单元留空 int length;∥表的长度 3 SSTable;
§顺序表的查找 typedef struct { ElemType *elem; // 数据元素存储空间基址，建表时 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable; 以顺序表表示静态查找表，则Search函数可 用顺序查找来实现。其顺序存储结构如下：