第9章查找(上课用)讲述.ppt

数 据 结 构 主讲人： 张立震 E-mail: system0@ 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 第9章 查找 查找的概念 静态查找表 二叉排序树 平衡二叉树（不讲） 哈希表 本章主要内容 查找(Search)的概念 查找表: 是由同一类型的数据元素(或记录)组成的 数据集合。 在查找表中一般有四个操作： (1) 查询某个“特定”的数据元素是否在查找表中 (2) 检索某个“特定”的数据元素的各种属性 (3) 在查找表中插入一个元素 (4) 在查找表中删除一个元素 查找表的分类： 静态查找表 动态查找表 关键字：数据元素中某个数据项的值，用以标识一个数据元素（或记录）。 主关键字：可唯一地标识一个数据元素的关键字。 使用基于主关键字的查找，查找结果应是唯一的！ 查找：就是在数据集合中寻找一个关键字等于某个给定值的数据元素（记录）。 查找的结果通常有两种可能： 查找成功 给出记录信息或记录所在的位置信息。 查找不成功 作为结果，给出“空记录”或“空指针” 表示查找失败。 为 在上图中，如果我们查找主关键字“代码”的主关键字为“sh601398”的记录时就可以得到第二条唯一一个记录。如果查找次关键字“涨跌额”为“-0.11”的记录时，可以得到两条记录。 平均查找长度ASL(Average Search Length) 衡量一个查找算法的时间效率的标准是：在查找过程中关键字的平均比较次数或平均读写磁盘次数。 设查找第 i 个元素的概率为 pi，查找到第 i 个元素所需比较次数为 ci，则查找成功的平均查找长度: 以上讨论的是“基本上每次查找都成功”，若查找不成功的情况不可忽略，则应是查找成功的平均长度与查找不成功的平均长度之和。 以后主要讨论在查找成功下的ASL(哈希表除外)。 此外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题。 9.1 静态查找表 静态查找表有不同的表示方法，不同的表示方法中查找方法也不同。可分为： 顺序查找表 有序查找表 静态树表的查找（不讲解） 索引查找表 9.1.1 顺序表的查找 (Sequential Search) 所谓顺序查找，又称线性查找，主要用于在 线性结构中进行查找。 其顺序存储结构如下： typedef struct { // 元素类型定义 KeyType key; // 元素的关键字 InfoType data; // 元素的其他数据 } ElemType; typedef struct { // 顺序表类型定义 ElemType *elem; // 存储空间的基址，建表时0号单元留用 int length; // 表的长度 } SSTable; SSTable tb; 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 比较次数=5 比较次数： 查找第 n 个元素：1 查找第n-1个元素：2 ………. 查找第 1 个元素： n 查找第 i 个元素： n+1-i 查找失败： n+1 查找过程：从表的一端开始逐个进行记录的关键字和 给定值的比较。 例如： 顺序查找算法 (p217 算法9.1) int Search_Seq(SSTable ST, KeyType key){ //顺序查找的算法，0号元素为监视哨。 int i = ST.length; ST.elem[0].key = key; // “哨兵” for (