图内容回顾 图 Dijkstra算法 最短路径 Floyd算法 拓扑排序 邻接矩阵 有向图的应用 DAG图 关键路径 邻 接 表 存储结构 十字链表 邻接多重表 图 应用 深度优先搜索 遍 历 广度优先搜索 图的连通分量 （利用DFS） 无向图的应用 Prim算法 图的生成树 最小生成树 Kruskal算法

第7章 查找 7.1 查找的基本概念 7.2 静态查找表 7.3动态查找表 7.4 哈希表

7.1 查找的基本概念 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 是一种数据结构 7.1 查找的基本概念 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询(Searching)特定元素是否在表中。 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） ——只查找，不改变集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志 ) ——可以唯一标识一个记录的关键字 例如“学号” ——识别若干记录的关键字 例如“女”

讨论： （1）查找的过程是怎样的？ （2）对查找表常用的操作有哪些？ （3) 有哪些查找方法？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。 “特定的”=关键字 （2）对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。 （3) 有哪些查找方法？ 查找方法取决于表中数据的排列方式; 例如查字典 针对静态查找表和动态查找表的查找方法也有所不同。

（4）如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：average search length）。 统计意义上的数学期望值 物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高。

7.2 静态查找表 针对静态查找表的查找算法主要有： 一、顺序查找（线性查找） 二、折半查找（二分或对分查找） 三、分块查找（索引顺序查找）

一、顺序查找（ Linear search，又称线性查找 ） 顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。 对顺序结构如何线性查找？ 对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”； 对非线性树结构如何顺序查找?可借助各种遍历操作！ （1）顺序表的存储结构： typedef struct { ElemType *elem; //表基址，0号单元留空。表容量为全部元素 int length; //表长，即表中数据元素个数 }SSTable;

技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），目的在于免去查找过程中每一步都要检测整个表是否查找完毕，这样可以加快执行速度。 （2）算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），目的在于免去查找过程中每一步都要检测整个表是否查找完毕，这样可以加快执行速度。 例： 若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！ 例 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 i i i i i 监视哨

顺序查找算法描述: int Search_Seq( SSTable ST , KeyType key ){ ST.elem[0].key =key; //设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n>1000时，查找时间将减少一半。 for( i=ST.length; ST.elem[ i ].key!=key; - - i ); return i; //若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。 } // Search_Seq

——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回 i=0。 讨论① 查不到怎么办？ ——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回 i=0。 讨论② 查找效率怎样计算？——用平均查找长度ASL衡量。 讨论③ 如何计算ASL？ 0 1 2 3 4 5 6 7 8 9 10 11 分析： 查找第n个元素所需的比较次数为1； 查找第n-1个元素所需的比较次数为2； 查找第i个元素所需的比较次数为n+1-i； …… 查找第1个元素所需的比较次数为n； 5 13 19 21 37 56 64 75 80 88 92 未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1 总计全部比较次数为：1＋2＋…＋n = (1+n)n/2 若求某一个元素的平均查找次数，还应当除以n（等概率）， 即： ASL＝（1＋n）/2 ，时间效率为 O(n) 这是查找成功的情况

二、折半查找（又称二分查找或对分查找） 讨论④ 顺序查找的特点： 优点：算法简单，且对顺序结构或链表结构均适用。 讨论④ 顺序查找的特点： 优点：算法简单，且对顺序结构或链表结构均适用。 缺点： ASL 太长，时间效率太低。 如何改进？ 二、折半查找（又称二分查找或对分查找） 先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。 对顺序表结构如何编程实现折半查找算法？ ——见下页之例 对单链表结构如何折半查找？ ——无法实现！因全部元素的定位只能从头指针head开始 对非线性(树)结构如何折半查找？ ——可借助二叉排序树来查找（属动态查找表形式）。

已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和70的数据元素。 已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和70的数据元素。 折半查找举例： Low指向待查元素所在区间的下界 mid指向待查元素所在区间的中间位置 high指向待查元素所在区间的上界 解：① 先设定3个辅助标志: low,high,mid， 显然有：mid= (low+high)/2 ② 运算步骤： (1) low =1,high =11 ,mid =6 ，待查范围是 [1,11]； (2) 若 ST.elem[mid].key < key，说明 key[ mid+1,high] ， 则令：low =mid+1;重算 mid＝ (low+high)/2；. (3) 若 ST.elem[mid].key > key，说明key[low ,mid-1]， 则令：high =mid–1;重算 mid ； (4)若 ST.elem[ mid ].key = key，说明查找成功，元素序号=mid; 结束条件： （1）查找成功 ： ST.elem[mid].key = key （2）查找不成功 ：high≤low（意即区间长度小于0）

折半查找算法描述： int Search_Bin(SSTable ST,KeyType key){ low=1;high=ST.length; while( low<=high){ mid=(low+high)/2; if (EQ(key,ST.elem[mid].key)) return mid; else if (LT(key,ST.elem[mid].key)) high=mid -1; else low=mid +1 ; } return 0; }//Search_Bin;

折半查找的效率（ASL） 分析法1： 推导过程 1次比较就查找成功的元素有1个（20），即中间值； 1 2 3 4 5 6 7 8 9 10 11 分析法1： 5 13 19 21 37 56 64 75 80 88 92 1次比较就查找成功的元素有1个（20），即中间值； 2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处； 3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处… 4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处… …… 则第m次比较时查找成功的元素会有（2m-1）个； 为方便起见，假设表中全部n个元素＝ 2m-1个，此时就不讨论第m次比较后还有剩余元素的情况了。 推导过程

折半查找效率分析法2 查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。 11 8 5 2 10 7 4 1 9 3 6 判定树： 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92

找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。 比较的关键字个数：为该结点在判定树上的层次数。 查找成功时比较的关键字个数最多不超过树的深度 d : d =  log2 n  + 1 若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。 查找不成功的过程 就是：走了一条从根结点到外部结点的路径。 6 3 9 1 4 2 5 7 8 10 11

查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 三、分块查找（索引顺序表的查找） 查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 查找表：用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针 算法描述

采用折半查找方法或顺序查找方法在索引表中找到块 用顺序查找方法在主表对应块中找到记录 22 采用折半查找方法或顺序查找方法在索引表中找到块 用顺序查找方法在主表对应块中找到记录 12 13 8 9 20 33 42 44 索引表 38 24 22 1 块中最大key 44 48 7 38 24 块第一个元素在查找表中的位置 86 13 48 60 58 (有序) 74 49 86 53 查找表 (只描述了关键字部分) (块间有序，块内无序)

静态查找表：查找方法比较 顺序查找 折半查找 分块查找 ASL 最大 最小 两者之间 表结构 有序表、无序表 有序表 分块有序表 存储结构 顺序存储结构 线性链表

7.3 动态查找表 二叉排序树 平衡二叉树

1. 定义--或是一棵空树；或者是具有如下性质的非空二叉树： 一、二叉排序树 1. 定义--或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点的值均小于根的值； （2）右子树的所有结点的值均大于根的值； （3）它的左右子树也分别为二叉排序树。 练：下列2种图形中，哪个不是二叉排序树 ？ （a） （b） 讨论：对(a)中序遍历后的结果是什么？ 递增有序序列

2. 二叉排序树的插入和查找操作 在插入之前，先使用搜索算法在树中检查要插入元素是否已经存在。 2. 二叉排序树的插入和查找操作 在插入之前，先使用搜索算法在树中检查要插入元素是否已经存在。 搜索成功: 树中已有这个元素，不再插入。 搜索不成功: 把新元素加到搜索停止的地方。 新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。 二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。

2. 二叉排序树的插入和查找操作 每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶结点插入。 二叉搜索树的搜索 插入新结点88 每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶结点插入。 注：折半查找长度为n的表的判定树是惟一的，而含有n个结点的二叉树却不惟一。即若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！

例：输入待查找的关键字序列=（45，24，53，45，12，24，90） 2. 二叉排序树的插入和查找操作 例：输入待查找的关键字序列=（45，24，53，45，12，24，90） 查找成功，返回 查找成功，返回 则生成二叉排序树的过程为： 45 24 53 12 90 如果待查找的关键字序列输入顺序为： （24，53， 45，45，12，24，90）， 查找成功，返回 查找成功，返回 24 则生成的二叉排序树形态不同： 12 53 90 45

3、二叉排序树(性能分析) 最好情况：即：与折半查找中的判定树相同 （形态均衡） 最坏情况：即插入的n个元素从一开始就有序。（单支树） 75 56 19 64 5 37 21 80 13 88 92 3、二叉排序树(性能分析) 最好情况：即：与折半查找中的判定树相同 （形态均衡） 此时树深为：log 2n  +1 ；ASL=log 2(n+1) –1 ；与折半查找情况相同。 其时间复杂性为O(log2n) 最坏情况：即插入的n个元素从一开始就有序。（单支树） 此时树深为n ; ASL= (n+1)/2 ; 与顺序查找情况相同。 其时间复杂性为O(n) 80 88 92 64 75 21 19 13 56 37 5

平衡二叉树 4、二叉排序树(特性) 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列（通过中序遍历） 插入新记录时，只需改变一个结点的指针，相当于在有序序列中插入一个记录而不需要移动其它记录 二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构,它是动态查找表的一种适宜表示。 但当插入记录的次序不当时(如升序或降序)，则二叉排序树深度很深(11)，增加了查找的时间 问题：如何提高二叉排序树的查找效率？ 尽量让二叉树的形状均衡 80 88 92 64 75 21 19 13 56 37 5 平衡二叉树

二、 AVL树（平衡二叉树） 1、 AVL树的定义 高度不平衡的二叉搜索树 高度平衡的二叉搜索树

结点的平衡因子 (BF--Balance Factor): 任一结点的左子树的高度减去右子树的高度所得的高度差称为该结点的平衡因子BF 。 根据AVL树的定义，任一结点的平衡因子只能取 -1，0 和 1。 如果一个结点的平衡因子的绝对值大于1，则这棵二叉排序树就失去了平衡，不再是AVL树。 如果一棵二叉排序树是高度平衡的，它就成为 AVL树。如果它有 n 个结点，其高度可保持在O(log2n)，平均查找长度也可保持在O(log2n)。

小结 1 查找的基本概念 查找表、查 找、查找成功、查找不成功、静态查找、关键字、主关键字、次关键字、平均查找长度ASL 2 静态查找表 顺序查找（线性查找） 折半查找（二分或对分查找） 分块查找（索引顺序查找） 3 动态查找表 二叉排序树 平衡二叉树

作业 已知如下所示长度为12的表 (Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec) (1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度ASL; (2)若对表中元素先进行排序构成有序表,求其在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度;