【2019-2020年整理】数据结构--第八章-查找

SearchDSTable(DT, key); InsertDSTable(&DT, e);
DeleteDSTable(&T, key); TraverseDSTable(DT, Visit());
}ADT DynamicSearchTable
InitDSTable(&DT); 操作结果：
构造一个空的动态查找表DT。
return mid; // 找到待查元素
else if ( key < ST.elem[mid].key )
high = mid - 1; // 继续在前半区间进行查找
else low = mid + 1; // 继续在后半区间进行查找
}
return 0;
// 顺序表中不存在待查元素
} // Search_Bin
操作结果：若 ST 中存在其关键字等于
key 的数据元素，则函数值 为该元素的值或在表中的位 置，否则为“空”。
Traverse(ST, Visit());
初始条件：静态查找表ST存在，Visit
是对元素操作的应用函数；
操作结果：按某种次序对ST的每个元
素调用函数Visit()一次且仅 一次，一旦Visit()失败，则 操作失败。
例如: key=64 的查找过程如下：
ST.elem
ST.length
0513192137566475808892
0 1 2 3 4 5 6 7 8 9 10 11
low
low high
high
mid mid mid
low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2
Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3

n=0
n=1
n=2
空树
最大深度为 0 最大深度为 1 最大深度为 2
n=4
n=7
最大深度为 3
最大深度为 4
三、 B - 树
1．定义
2．查找过程
1．B-树的定义
B-树是一种 平衡 的 多路 查找 树：
root 50
15
71 84
38
20 26 43
56 62 78 89 96
在 m 阶的B-树上，每个非终端结点可能 含有：
low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2。
分析折半查找的平均查找长度
先看一个具体的情况，假设：n=11
i 1 2 3 4 5 6 7 8 9 10 11 Ci 3 4 2 3 4 1 3 4 2 3 4
判定树
3
6 9
1
4
7
10
2
5
8
11
一般情况下，表长为 n 的折半查找 的判定树的深度和含有 n 个结点的完全 二叉树的深度相同。
何谓查找表 ？
查找表是由同一类型的数据元素( 或记录)构成的集合。
由于“集合”中的数据元素之间存在着 松散的关系，因此查找表是一种应用灵 便的结构。
对查找表经常进行的操作:
• 1）查询某个“特定的”数据元素是否 在查找表中；
• 2）检索某个“特定的”数据元素的各 种属性；
• 3）在查找表中插入一个数据元素； • 4）从查找表中删去某个数据元素。
• 根据动态查找表的定义，“插入”操 作在查找不成功时才进行;
• 若二叉排序树为空树，则新插入的 结点为新的根结点；否则，新插入 的结点必为一个新的叶子结点，其 插入位置由查找过程得到。

low
mid
high
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92
查找第i个元素： n+1-i
查找失败：
n+1
iii 比较次数=5
顺序查找方法的ASL
n
对含 n个 有记录的 AS表 L ， pici i1
设表中每个元 概素 率的 相 pi查 等 1n找
n
则AS L
i1
pici
1 n i ni1
1n(n1) n2
n1 2
7.2.2 折半查找
1. 折半查找的基本思想 折半查找要求查找表用顺序存储结构存放且各数 据元素按关键字有序（升序或降序）排列，也就是说 折半查找只适用于对有序顺序表进行查找。
查找——也叫检索，是根据给定的某个值，在表中确定一 个关键字等于给定值的记录或数据元素
关键字——是数据元素中某个数据项的值，它可以标识一 个数据元素
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度ASL(Average Search Length)：为确定记 录在表中的位置，需和给定值进行比较的关键字的个 数的期望值叫查找算法的~
7.2 静态查找
正如本章第一节所述：静态查找是指在静态查找 表上进行的查找操作，在查找表中查找满足条件的数 据元素的存储位置或各种属性。本节将讨论以线性结 构表示的静态查找表及相应的查找算法。
7.2.1 顺序查找
1. 顺序查找的基本思想

邻接表表示时：无向图的任意顶点的度=顶点所对应边结点链表中结点个数；
有向图的任意顶点的度=邻接表中顶点所对应边链表中结点个数+逆邻接表中顶点所对应边链表中结点个数；
4、课本P3928.3题
【解答】
n个顶点的无向连通图至少有n-1条边，n个பைடு நூலகம்点的无向强连通图至少有n(n-1)/2条边；n个顶点的有向连通图至少有n条边，n个顶点的有向强连通图至少有n(n-1)条边。
上面不正确的是（A）。
A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)
5、下列说法不正确的是（C）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B．遍历的基本算法有两种：深度遍历和广度遍历
C．图的深度遍历不适用于有向图
D．图的深度遍历是一个递归过程
三、填空题
1、判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图_。
注: 答案并不唯一
2、课本P3928.1题
【解答】
（1）不是强连通图
（2）简单路径如：D->B->C->F
（3）略
（4）邻接表见图，其他略
3、课本P3928.2题
【解答】
（1）邻接矩阵表示：无向图的边数为
矩阵中非零元素的个数/2;有向图的边数为矩阵中非零元素的个数。
邻接表表示时：无向图的边数为邻接表中边结点的个数/2；有向图的边数为邻接表中边结点的个数。
(2)(3)略
12、课本P3958.24题
【解答】
A->B : 10
A->B->D: 15
A->B->D->C : 17
A->B->D->E : 17