[理学]数据结构 - 查找.ppt

Chapter 8Search 中序：CL C …QL Q SL S P PR F 中序：CL C …QL Q SL S PR F 3) ?p 左、右子树均非空： F P C PR CL Q QL S SL F C PR CL Q QL S SL 用 ?p 的直接前驱取代 ?p F C PR CL Q QL S SL 用 ?p 的直接后继取代 ?p 若 ?p 的左子树无右子树， 用 ?p 的左子树取代 ?p。 中序遍历：CL C P PR F 中序遍历：CL C PR F F P C PR CL F C PR CL F P C PR CL Q QL S SL F C PR CL Q QL S SL 中序：CL C …QL Q SL S P PR F 中序：CL C …QL Q SL S PR F 1、查找的基本概念 2、静态查找表及查找算法 3、动态查找表及查找算法 教 学 内 容 存储结构 非线性结构（树、图） 逻辑结构 数据结构 线性结构 顺序结构 链式结构 基本操作 插入操作 删除操作 修改操作 查找操作 排序操作 回顾 集合 查找表：由同一类型的数据元素构成的集合。 对查找表经常进行的操作： 1、查询某个“特定的”数据元素是否在查找表中； 2、查询某个“特定的”数据元素的各种属性； 3、在查找表中插入一个数据元素； 4、删除查找表中的某个数据元素。 8.1 查找的基本概念 静态查找表：仅作“查询”（检索）操作的查找表。 动态查找表：作“插入”和“删除”操作的查找表。 关键字(key)：数据元素中某个数据项的值，用它 可以标示（识别）一个数据元素。 主关键字：可以惟一地标示一个数据元素的关键字。 次关键字：可标示若干个数据元素的关键字。 主关键字 次关键字 用集合表示查找表：数据元素之间的关系不作限定 查询时无规律可循，只能对集合中的元素一一加以 辨认。 用其它结构表示查找表 （对查找表的元素人为 地附加上某种关系） 问题：如何进行查找？ 查找方法取决于查找表的结构。 有序表：字典 索引表：电话号码表 树 表 效率低 效率高 8.2 静态查找表 静态查找表的存储结构 顺 序 表 线性链表 …… 存储结构不同，实现查找操作的方法则不同。 顺序查找 typedef struct { ElemType * elem; int length; // 表长度 } SSTable; 静态查找表的顺序存储结构 8.2.1 顺序表的查找（顺序查找） 顺序查找：从表的一端开始，逐个进行记录的关 键字和给定值的比较。 查找过程： 0 1 2 3 4 5 6 7 8 9 10 11 找64 5 37 19 21 13 56 64 92 88 80 75 64 优点：算法简单，适应面广。 缺点：平均查找长度大。 顺序查找 else return 0 ; 算法描述： int Search_Seq(SSTable ST, KeyType key) { 找60 ST.elem[0].key = key ; ; 0 1 2 3 4 5 6 7 8 9 10 11 5 37 19 21 13 56 64 92 88 80 75 当 ST.length = 1000 时，此改进能使进行 一次查找所需的平均 时间几乎减少一半。 60 监视哨 for (i = ST.length ; ST.elem[i].key != key ; - - i ) if (i = 0) break ; if (i 0) return i ; } 查找方法评价： 时间复杂度；空间复杂度；算法本身复杂程度。 因为查找算法的基本操作为：将记录的关键字同给定值比较。 平均查找长度 ASL (Average Search Leng