第7章搜索
一、复习要点
本章讨论了搜索方法和简单的性能分析方法，包括适用于静态搜索表的顺序搜索和折半搜索及代表动态搜索表的二叉搜索树和AVL树。可以使用扩充的二叉搜索树描述顺序搜索和折半搜索，从而推导出估算搜索效率的公式。静态搜索表在整个程序的运行期间结构不会变化，其搜索效率随着表中对象的个数n不断增长。动态搜索表因各个对象的输入顺序不同，得到的搜索表的形态不同，典型的是二叉搜索树。在具有n个对象的二叉搜索树中，搜索效率最高的是高度最低的二叉搜索树。为确保二叉搜索树始终保持搜索效率最高，必须在输入新的对象时判断二叉搜索树是否“失去平衡”，并进行适当的平衡旋转，使二叉搜索树的高度降到最低。这就是AVL树。在AVL树的讨论中，4种平衡旋转，选择参加平衡旋转的3个结点是关键，必须加以注意。
本章复习的要点是： 1、基本知识点
理解理解搜索的概念，理解静态搜索表结构，掌握静态搜索表的顺序搜索和折半搜索算法及其性能分析方法。掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法，掌握AVL树的构造、插入、删除时的调整方法及其性能分析，重点是AVL树的定义、平衡化旋转、AVL树的插入和删除、AVL树的高度。
2、算法设计
? 用有序链表表示集合时的求集合的并、交、差的算法 ? 并查集中的构造函数、求根及合并算法
? 并查集中根据树的高度和根据树中结点个数进行合并的算法 ? 设置监视哨的顺序搜索算法和不设监视哨的顺序搜索算法 ? 有序顺序表的顺序搜索算法
? 有序顺序表的折半搜索的递归算法和非递归算法 ? 二叉搜索树的搜索、插入和删除算法
? 计算AVL树中指定结点高度的递归算法及利用此算法计算结点平衡因子的算法
二、难点和重点
3、基本搜索方法
? 对一般表的顺序搜索算法(包括有监视哨和没有监视哨) ? 对有序顺序表的顺序搜索算法，包括递归和非递归算法 ? 用判定树(即扩充二叉搜索树)描述有序顺序表的顺序搜索，以及平均搜索长度(成功
与不成功)的计算。
? 对有序顺序表的折半搜索算法、包括递归和非递归算法 ? 用判定树(即扩充二叉搜索树)描述有序顺序表的折半搜索，以及平均搜索长度(成功
与不成功)的计算。 4、二叉搜索树
? 动态搜索树与静态搜索树的特性
? 二叉搜索树的定义、二叉搜索树上的递归和非递归搜索算法 ? 二叉搜索树搜索时的平均搜索长度(成功与不成功)的计算 ? 二叉搜索树的插入与删除算法
136
? AVL树结点上的平衡因子、AVL树的平衡旋转方法 ? 高度为h的AVL树上的最少结点个数与最多结点个数 ? AVL树的搜索方法、插入与删除方法(不要求算法)
三、教材中习题的解析
7-8 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 【解答】
509 154 677
553 897 017 275
094 170 503 512 612 765 908
114145ASLsucc??Ci?(1?2*2?3*4?4*7)?
14i?1141415 1159'ASL?C?(3*1?4*14)??unsucci 15i?01515
7-9 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?
(1) 搜索失败;
(2) 搜索成功, 且表中只有一个关键码等于给定值k的对象;
(3) 搜索成功, 且表中有若干个关键码等于给定值k的对象, 要求一次搜索找出所有对象。
【解答】
(1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。
(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。
(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。
前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。
7-10 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。 【解答】
137
current
10 20 30 40 50 60 head
相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。
template
ListNode
if ( key < current ) { p = head; q = current; } else { p = current; q = head; }
while ( p != q && p->data < key ) p = p->link; if ( p->data == key ) { current = p; return p; } else { current = head; return NULL; } }
//循链搜索其值等于key的结点 //找到, 返回结点地址 //未找到, 返回空指针
//确定检测范围, 用p, q指示
7-11 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head, p, key)，检索具有关键码key的结点，并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。 【解答】
p
∧ 10 20 30 50 60 70 ∧ head 40
template
DblListNode
DblListNode
if ( key < p->data ) { while ( q != NULL && q->data > key ) q = q-> lLink; } else { while ( q != NULL && q->data < key ) q = q-> rLink; } if ( q != NULL && q->data == key ) { p = q; return p; } else return NULL; }
//反向搜索 //正向搜索 //搜索成功
如果指针p处于第i个结点(i = 1, 2, ?, n)，它左边有i-1个结点，右边有n-i个结点。
找到左边第i-1号结点比较2次，找到第i-2号结点比较3次，?，找到第1号结点比较i次，一般地，找到左边第k个结点比较i-k+1次(k = 1, 2, ?, i-1)。找到右边第i+1号结点比较2次，找到第i+2号结点比较3次，?，找到第n号结点比较n-i+1次，一般地，找到右边第k个结点比较k-i+1次(k = i+1, i+2, ?, n)。因此，当指针处于第i个结点时的搜索成功的平均数据比较次数为 nn?3i2?i?i*n?i?1??n*(n?3)2?(k?i?1)?n???i?i?i*n?n??? 1?(i?k?1)?22n??k?i?1?k?1?
一般地，搜索成功的平均数据比较次数为 1n?n?3i2?i?i*n?n2?3n?1??ASLsucc????ni?1?2?n????3n138
如果指针p处于第i个结点(i = 1, 2, ?, n)，它左边有i个不成功的位置，右边有n-i+1个不成功的位置。
?? ?i?1n(i?k)??(k?i?1)??(n?1)???n*(n?3)?i2?i?i*n?1?
?k?0k?i??2??(n?1)一般地，搜索不成功的平均数据比较次数为
ASL?1n?n*(n?3)22?2n?7n?6unsucc(n?1)2??i?0?2?i?i?i*n?1???n?1
7-12 在一棵表示有序集S的二叉搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S = S1 ? S2 ? S3。若对于任意的a ? S1, b ? S2, c ? S3， 是否总有a ? b ? c？为什么？ 【解答】
答案是否定的。举个反例：看下图粗线所示的路径
45 25 65 15 35 50 70
30 40 S1 = { 15 }, S2 = { 25, 30, 35, 45 }, S3 = { 40, 50, 65, 70 } c = 40 ? S3，b = 45 ? S2，b ? c 不成立。
7-13 请给出下列操作序列运算的结果：Union(1, 2), Union(3, 4), Union(3, 5), Union(1, 7), Union(3, 6), Union(8, 9), Union(1, 8), Union(3, 10), Union(3, 11), Union(3, 12), Union(3, 13), Union(14, 15), Union(16, 17), Union(14, 16), Union(1, 3), Union(1, 14)，要求
(1) 以任意方式执行Union； (2) 根据树的高度执行Union； (3) 根据树中结点个数执行Union。 【解答】
(1) 对于union(i, j)，以i作为j的双亲
1 2 7 8 3 14 9 4 5 6 10 11 12 13 15 16 0
(2) 按i和j为根的树的高度实现union(i, j)，高度大者为高度小者的双亲；
7
139
1
2 8 9 4 5 6 3 10 11 12 13 14 15 16 0 (3) 按i和j为根的树的结点个数实现union(i, j)，结点个数大者为结点个数小者的双亲。
4 5 6 10 3 11 12 13 2 1 7 8 9 14 15 16 0
7-14 有n个结点的二叉搜索树具有多少种不同形态? 【解答】
1n n?1C2n
7-15 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。 【解答】 46 46 46 46 46 46
25 78 25 78 25 78 25 78 空树 加46 25 加78 加25
62 12 62 12 37 62 加62 加12 加37
46 46
25 78 25 78
12 37 62 12 37 62 70 29 70 加29 加70
7-16 设有一个标识符序列{else, public, return, template}，p1=0.05, p2=0.2, p3=0.1, p4=0.05, q0=0.2, q1=0.1, q2=0.2, q3=0.05, q4=0.05，计算W[i][j]、C[i][j]和R[i][j]，构造最优二叉搜索树。 【解答】 将标识符序列简化为 { e, p, r, t }，并将各个搜索概率值化整，有
e p r t p1 = p2 = 4 p3 = 2 p4 = 1
1
q0 = 4 q1 = q2 = 4 q3 = 1 q4 = 1
140
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第7章在线全文阅读。
相关推荐：