北京理工大学数据结构查找课件剖析.ppt

2000年1月25日 北京理工大学 / 第9章 查 找 查找表：由同一类型的数据元素（或记录）构成的集合。 查找表的基本操作1) 查询某个“特定的”数据元素是否在表中 2) 检索某个“特定的”数据元素的各种属性 3) 插入一个数据元素 4) 删去某个数据元素 静态查找表：只作查询和检索操作的查找表。 动态查找表：在查找过程中同时作插入或删除操作的查找表。 第9章 查 找 关键字：能标识一个数据元素（或记录）的数据项。 主关键字：能唯一地标识一个记录的关键字。 次关键字：用以识别若干记录的关键字。 第9章 查 找 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的记录，则称查找成功，查找结果为该记录在查找表中的位置；否则称为查找不成功，查找结果为0或NULL。 第9章 查 找 查找方法评价 查找算法的基本操作：比较 平均查找长度ASL ( Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字个数的期望值。 平均查找长度： ASL = ?PiCi Pi：查找第 i 个记录的概率，且?Pi=1 ； Ci：查找第 i 个记录所需的比较次数。 第9章 查 找 关键字类型定义 typedef float KeyType; 实型 typedef int KeyType; 整型 typedef char* KeyType; 字符串型 数据元素类型定义 typedef struct { KeyType key; 关键字域 …… 其他域 } ElemType; 第9章 查 找 对数值型关键字 #define EQ(a,b) ((a) = = (b)) #define LT(a,b) ((a) (b)) #define LQ(a,b) ((a) = (b)) 对字符串型关键字 #define EQ(a,b) (!strcmp((a),(b))) #define LT(a,b) (strcmp((a),(b)) 0) #define LQ(a,b) (strcmp((a),(b)) = 0) 第9章 查 找 静态查找 在指定的表中查找某一个“特定”的数据元素是否存在，检索某一个“特定”数据元素的各种属性。 动态查找 在查找的过程中同时插入表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。 第9章 查 找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 §9.1 静态查找表 静态查找表 无序表的查找：顺序查找 有序表的查找：折半查找 索引顺序表的查找：分块查找 §9.1 静态查找表 查找表——用线性表表示 L1=(45,61,12,3,37,24,90,53,98,78） 用顺序表表示静态查找表 用线性链表表示静态查找表 查找方法：顺序查找 §9.1 静态查找表-顺序表查找 顺序表类型定义 typedef struct { ElemType *elem; // 0号单元留空 int length; } SSTable; §9.1 静态查找表 int Search_Seq ( SSTable ST, KeyType key ) { ST.elem[0].key = key; // “哨兵” for ( i=ST.length; !EQ(key, ST.elem[i].Key; --i )； return i; // 若表中不存在待查元素, i=0 } §9.1 静态查找表 例1：在下表中查找 key = 8 的结点。 §9.1 静态查找表 顺序查找的特点： 无排序要求； 存储结构：顺序、链式； 平均查找长度ASLSS=(n+1)/2； §9.1 静态查找表-有序表查找 查找表：用有序表表示 查找方法：折半查找（二分查找） 查找过程：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。 例：有原始查找表 {45, 61, 12, 3, 37, 24, 90, 53, 98, 78} 为进行折半查找，需要先进行排序： L=(3, 12, 24, 37, 45, 53, 61, 78, 90, 98) §9.1 静态查找表-有序表查找 例：查找 Key=24 的记录。 §9.1 静态查找表-有序表查找 int Search_Bin ( SSTab