第1次 第2次 第3次 第4次 10 10 10 10 ∞ 60 50 50 30 30 30 30 100 100 90 60 {V1，V2} {V1，V2，V4} {V1，V2，V4，V3} {V1，V2，V4， V3，V5} V1到各顶点的最短路径是： V1→V2：（V1，V2） V1→V4：（V1，V4） V1→V3：（V1，V4，V3） V1→V5：（V1，V4，V3，V5）
第8章 查找 8．1 基本概念
一、各种数据的逻辑结构 数据 线性表 树 图 查找表 二、查找表
1．定义：查找表是一种以集合为逻辑结构，以查找为核心运算的数据结构。
例：一个平面表格，当各条记录可以任意排列时，就成为查找表。 2．关键字：由一个或多个数据项组成，可标识若干条记录； 主键：由一个或多个数据项组成，能唯一标识一条记录。
3．查找：在查找表中寻找关键字值等于给定值的记录，若找到，则返回记录号；否则，则查找失败。
4．静态查找表和动态查找表
静态查找表：只做建表、查找操作；
动态查找表：做建表、查找、插入、删除操作。
8．2 静态查找表
◆ 静态查找表的存储结构：
顺序表、有序表、索引顺序表 一、顺序表上的查找 1． 顺序表的类型定义
typedef struct
逻辑结构 线性结构 树型结构 图状结构 集合 特点 数据元素之间存在着一对一的逻辑关系。 数据元素之间存在着一对多的逻辑关系。 数据元素之间存在着多对多的逻辑关系。 数据元素之间不存在任何关系。 21
{ int key; 类型 data; ... } ELEMENT; typedef struct
{ ELEMENT r[maxsize]; int len; } SSTABLE;
2． 在顺序表上实现查找运算，采用“顺序查找法”
对顺序表从后往前依次查找关键字值等于给定值k的记录，若找到，则返回记录的序号。 3． 查找长度：
记录的键值与给定值的比较次数，称为查找长度。它用来衡量查找算法的时间性能。 ① 查找成功的平均查找长度 ASL=
n?1 （n为记录条数） 2② 查找不成功的平均查找长度为：n 二、有序表上的查找
1． 查找表中各元素之间无任何逻辑关系，但各元素的键值存在次序关系。 2． 有序表：各元素按关键字值升序（或降序）排列的顺序表。 3． 在有序表上实现查找运算，采用“二分查找法”
每次将查找区间中间位置上的记录键值与给定值k作比较，若不等则缩小查找区间，直到查找成功，或查找区间长度为0。
例：在有序表（5，12，30，45，70，73，80，85，89，100，103，109）查找关键字值为85的记录，则二分查找法的过程为：
5，12，30，45，70，73，80，85，89，100，103，109 1 2 3 4 5 6 7 8 9 10 11 12 第1次查找：low=1，high=12，则mid=6 第2次查找：low=7，high=12，则mid=9 第3次查找：low=7，high=8，则mid=7
第4次查找：low=8，high=8，则mid=8（8号记录的关键字值为85，查找成功。） 三、索引顺序表上的查找 1． 索引顺序表由两部分组成：
一个顺序表和一个索引表，且满足： ① 顺序表的记录键值“按块有序”。
② 对于顺序表的每一块，索引表有相应的一个“索引项”，每个索引项含两大域：块起
22
始位置和块内最大键值。
2．在索引顺序表上实现查找运算，采用“分块查找法”
① 确定待查键值所在的块。（索引表） ② 在块内查找待查的键值。（顺序表） ◆ 小结：三种查找法的比较： 查找效率 限制 顺序查找 最低 最少
8．3 动态查找表
静态查找表（顺序表、有序表、索引顺序表） 查找表
动态查找表（二叉排序树、散列表） 一、二叉排序树
对二叉树进行中根遍历，若得到的结点键值的序列是逐渐递增的有序序列，则称为二叉排序树。
特点：任一结点的键值大于其左子树上所有结点的键值，小于其右子树上所有结点的键值。
二、二叉排序树的生成
① 生成二叉排序树的过程就是一个反复插入结点的过程，且保证插入结点后仍为一棵二叉排序树。
② 含有n个结点的二叉排序树的形态不唯一，但中根遍历的结果是唯一的。 三、二叉排序树的查找
对二叉排序树查找，若查找成功，则返回指向该结点的指针，否则返回null。 四、二叉排序树的删除
从二叉排序树删除一个结点后，要保证仍为一棵二叉排序树。 设待删结点为P： P为叶子结点
P只有一棵非空子树：以P的非空子树的根结点取代P
P有两棵非空子树：以P的左孩子A取代P，并将P的右子树插入到A的右子树中。
23
二分查找 最高 最多 分块查找 居中 居中 20 20 P A 12 15 24 A 11 12 24 16 14 11 14 13 13 16 24