当前位置：文档之家 › 第9章 查找_1

第9章 查找_1

  • 格式：ppt
  • 大小：853.00 KB
  • 文档页数：46

下载文档原格式

  / 46

合集下载

数据结构第九章--查找-习题及答案

数据结构第九章--查找-习题及答案

第九章查找一、选择题1•若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为()。

A ．(n-1)/2B.n/2C.(n+1)/2D.n 2. 下面关于二分查找的叙述正确的是()A. 表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只 能以顺序方式存储3. 用二分(对半)查找表的元素的速度比用顺序法() A. 必然快B.必然慢C.相等D.不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度()A.3.1B.4C.2.5D.55．当采用分块查找时，数据的组织方式为()A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同6. 二叉查找树的查找效率与二叉树的((1))有关,在((2))时其查找效率最低(1) ：A.高度B.结点的多少C.树型D.结点的位置(2) :A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。

7. 对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败,它们的平均查找长度是((1)),对于查找成功,他们的平均查找长度是((2))供选择的答案:A.相同的B.不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A ．(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90) C. (100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1，则应作()型调整以使其平衡。

第章查找A

第章查找A
• 折半查找在查找成功时关键字比较次数 不超过树的深度,即: log2n + 1
假设 n=2h-1 并且查找概率相等
则
ASLbs

1 n
n i1
Ci

1 n

h j1
j

2
j1



n
n
1
log
2
(n

1)

1
在n>50时，可得近似结果
ASLbs log2(n 1) 1
若此关键字能识别若干记录，则称
之谓“次关键字”。
查找（搜索 、 Search)
所谓查找，就是在数据集合中寻找满足某种条 件的数据对象。
查找的结果通常有两种可能： 查找成功，即找到满足条件的数据对象。这 时，作为结果，可报告该对象在结构中的位置， 还可进一步给出该对象中的具体信息。 查找不成功，或搜索失败。作为结果，也应 报告一些信息，如失败标志、失败位置等。
• 分块有序原则：第二个子表的所有记录的关键字均 大于第一个字表中的最大关键字，……，依此类推。
索引顺序表的查找过程：
1）由索引确定记录所在块（子表）； 2）在顺序表的某个块内进行顺序查找。
可见， 索引顺序查找的过程也是一个
“缩小区间”的查找过程。
注意：索引可以根据查找表的特点来构造。
因为索引表中的 索引项是按关键字有 序排列的，因此可用顺序查找，也可用 折半查找；而块（子表）中的记录是任 意排列的，只能用顺序查找的方法。
for (i=ST.length; ST.elem[i].key!=key; --i);
// 从后往前找
return i ;

第九章 查找

第九章 查找

} // Search_Seq

例：在顺序查找表中查找key=8的关键字 ST.elem
0 8 1 100 2 10 3 0 4 8 i 5 1 6 3 7 7
查找成功 i=4
9.1.1 顺序表的查找性能分析

等概率下查找成功的平均查找长度：Pi=1/n；Ci=n-i+1，
1 ASLSS n
(n i 1)
9.1.2 有序表的查找的性能分析
•判定树：用二叉树描述折半查找过程，树中每个结点表示一个 记录，结点值为该记录在表中的位臵，结点所在的层次表示查找 该值需要进行的比较次数。则有如下的表：
位臵 0 1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
} // Search_Seq

例：在顺序查找表中查找key=8的关键字 ST.elem
0 8 1 100 2 10 3 0 4 8 5 1 6 3 i 7 7
9.1.1 顺序表的查找

适用场合：以顺序表表示静态查找表，表内元素无序。
思想：从表中最后一条记录起，逐个比较记录关键字与给定值， 若相等查找成功；反之，直至与第一条记录不等，查找不成功 int Search_Seq( SSTable ST, KeyType key ) { ST.elem[0]. key = key;//哨兵 for ( i = ST.length ; ! EQ(ST.elem[i]. key, key ) ; - - i ); return i;
比较次数 0 3 4 2 3 4 1 3 4 2 3 4
查找的定义和术语(2)
“特定的”数据元素 关键字(Key):数据元素中某个数据项的值，用以标识一个 数据元素 主关键字(Primary Key):可以唯一标识一个记录的关键 字 次关键字(Secondary Key):用以识别若干记录的关键 字 查找(Searching):根据给定值，在查找表中确定一个其关 键字等于给定值的数据元素或记录. 查找成功(Searching Success)：若存在这一记录，给 出该记录信息或指示该记录在表中的位臵 查找不成功(Searching Failed)：若查找表中不存在这 一记录，给出“空记录”或“空指针”。

数据结构教案第9章 查找

数据结构教案第9章 查找

●性能分析 定义：为了确定记录在查找表中的位置，需和给定值进行比 较的关键字个数的期望值称为查找算法在查找成功时的平均查找 长度。
ASL = ∑ Pi C i
i =1
n
其中：Pi为查找表中第i个记录的概率；Ci为找到第i个记 录的比较次数； 查找成功的平均查找长度：
1 n n +1 ASL = ∑ (n − i + 1) = 2 n i =1
索引表 最大关键字 起始地址
22 48 86 1 7 13
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
9．2动态查找表 特点：表结构本身是在查找过程中动态生 成的，即对于给定值key，若表中存在其关键 字等于key的记录，则查找成功返回；否则插 入关键字等于key的记录。
10 10 9 15 9 17 17 15
a
16
作业：(P55)9.9, 9. 33
9．3哈希表 9．3．1什么是哈希表 哈希函数：在记录的关键字和它的存储位置之间建立 一个确定的对应关系f，使每个关键字和结构中一个 唯一的存储位置相对应，称对应关系f为哈希(Hash) 函数。 哈希表：按哈希函数建立的表称为哈希表。
void Delete(BiTree &p){ if(!p->rchild) { q=p; p=p->lchild; free(q); } else if(!p->lchild) { q=p; p=p->rchild; free(q); } else{ q=p; s=p->lchild; while(s->rchild) {q=s; s=s->rchild;} p->data=s->data; if(q!=p) q->rchild=s->lchild; \*q！=p正常情况 else q->lchile= s->lchild; \* q=p意外者，p的左子树的根没有右子树 free(s); }\\else }

大学数据结构课件--第9章 查找

大学数据结构课件--第9章 查找
——这种既查找又插入的过程称为动态查找。
二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态 查找表的一种适宜表示。
注：若数据元素的输入顺序不同，则得到的二叉排序树形态 也不同！
17
二、二叉树的插入和删除操作
1、二叉排序树的插入和查找操作
例：输入待查找的关键字序列=（45，24，53，12，90）
折半查找举例：
已知如下11个元素的有序表：
（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21和85的数据元素。
Low指向待查元 素所在区间的下 界
mid指向待查元素所在 high指向待查元素所
区间的中间位置
在区间的上界
8
9.1.2 折半查找（又称二分查找或对分查找）
balance。这样，可以得到AVL树的其它性质：
❖ 任一结点的平衡因子只能取：-1、0 或 1；如果树中任 意一个结点的平衡因子的绝对值大于1，则这棵二叉树 就失去平衡，不再是AVL树；
24
三、平衡二叉树
例：判断下列二叉树是否AVL树？
-1
1
-1
0
0
1
0
(a) 平衡树
2
-1
0
0
1
0
(b) 不是平衡树
（1）p为叶子结点，只需修改p双亲f的指针f->lchild=NULL或 f->rchild=NULL
（2）P只有左子树或右子树 ❖ P只有左子树，用P的左孩子代替P ❖ P只有右子树，用P的右孩子代替P
（3）P左、右子树均非空 （P左子树的根C的右子树分支找到S，S的右子树为空） ❖ P的左子树成为双亲f的左子树，P的右子树成为S的右子树 ❖ S的左子树成为S的双亲Q的右子树，用S取代p； 若C无右子树，用C取代p

数据结构(C语言版)9-12章练习 答案 清华大学出版社

数据结构(C语言版)9-12章练习 答案 清华大学出版社

数据结构（C语言版）9-12章练习答案清华大学出版社9-12章数据结构作业答案第九章查找选择题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A)个链表。

这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意（2） A．0至17 B. 1至17 C. 0至16 D. 1至16判断题1．Hash表的平均查找长度与处理冲突的方法无关。

(错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。

（错）3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

（错）填空题1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .算法应用题1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。

要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

数据结构教程李春葆课后答案 查找

第9章 查找教材中练习题及参考答案1. 设有5个数据do 、for 、if 、repeat 、while ，它们排在一个有序表中，其查找概率分别是p 1=0.2，p 2=0.15，p 3=0.1，p 4=0.03，p 5=0.01。

而查找它们之间不存在数据的概率分别为q 0=0.2，q 1=0.15，q 2=0.1，q 3=0.03，q 4=0.02，q 5=0.01，该有序表如下：（1）试画出对该有序表分别采用顺序查找和折半查找时的判定树。

（2）分别计算顺序查找的查找成功和不成功的平均查找长度。

（3）分别计算折半查找的查找成功和不成功的平均查找长度。

答：（1）对该有序表分别采用顺序查找和折半查找时的判定树分别如图9.2和9.3所示。

（2）对于顺序查找，成功查找到第i 个元素需要i 次比较，不成功查找需要比较的次数为对应外部结点的层次减1：ASL 成功=(1p 1+2p 2+3p 3+4p 4+5p 5)=0.97。

ASL 不成功=(1q 0+2q 1+3q 2+4q 3+5q 4+5q 5)=1.07。

（3）对于折半查找，成功查找需要比较的次数为对应内部结点的层次，不成功查找需要比较的次数为对应外部结点的层次减1：ASL 成功=(1p 3+2(p 1+p 4)+3(p 2+p 5))=1.04。

ASL 不成功=(2q 0 q 5图9.3 有序表上折半查找的判定树2. 对于A [0..10]有序表，在等概率的情况下，求采用折半查找法时成功和不成功的平均查找长度。

对于有序表（12，18，24，35，47，50，62，83，90，115，134），当用折半查找法查找 90时，需进行多少次查找可确定成功；查找47时需进行多少次查找可确定成功；查找100时，需进行多少次查找才能确定不成功。

答：对于A [0..10]有序表构造的判定树如图9.4（a ）所示。

因此有：ASL 成功=1144342211⨯+⨯+⨯+⨯=3ASL 不成功=124834⨯+⨯=3.67 对于题中给定的有序表构造的判定树如图9.4（b ）所示。

第9章查找习题

第九章查找习题一、判断题1.折半查找法可以用于按值有序的线性链表的查找。

2.对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。

3.任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。

4.中序遍历二叉排序树的结点就可以得到排好序的结点序列。

5.哈希表存储的基本思想是由关键码的值决定数据的存储地址。

6.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。

7.装载因子是散列法的一个重要参数，它反映散列表的装满程度。

8.采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。

二、选择题1.采用顺序查找方法查找长度为n的线性表，平均查找长度为A.nB.n/2C.(n+1)/2D.(n-1)/22.对线性表采用折半查找法，该线性表必须A.采用顺序存储结构B.采用链式存储结构C.采用顺序存储结构，且元素按值有序D.采用链式存储结构，且元素按值有序3.在按值有序的线性表(5,8,11,12,15,20,32,41,57)中采用折半查找法查找20需要进行多少次元素间的比较A.3B.4C.5D.64.按逐点插入法建立对应于序列(54,28,16,34,73,62,95,60,26,43)的二叉排序树后，查找62要进行多少次比较。

A.2次B.3次C.5次D.6次5.散列法存储的基本思想是根据哪个来决定存储地址。

A.散列表空间B.元素的序号C.装载因子D.关键码值6.散列法存储的冲突指的是A.两个元素具有相同的序号B.两个元素的关键码值不同，而非码属性相同C.不同关键码值对应相同的存储地址D. 装载因子过大7.哈希地址空间为m，k为关键字，散列地址H(k)=k MOD p。

为了减少发生冲突的频率，一般取p为A.小于m的最大奇数B.小于m的最大合数C.小于m的最大素数D.大于m的最小素数8.在10阶B-树中根结点所包含的关键码．．．个数最多为_______，最少为________。

数据结构第9章作业 查找答案

第9章 查找答案一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 9 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m-1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)二、单项选择题（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

(完整word版)数据结构第九章查找

第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。

A. k B。

k+l C. k(k+l）／2 D. l+k （k+l)/22．下述命题( )是不成立的。

A。

m阶B-树中的每一个结点的子树个数都小于或等于mB。

m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C。

m阶B-树中的每一个结点的子树高度都相等D。

m阶B—树具有k个子树的非叶子结点含有(k-l）个关键字3．如果要求一个基本线性表既能较快地查找，又能适应动态变化的要求，可以采用( ）查找方法.A。

分块 B. 顺序 C. 二分 D.散列4．设有100个元素，用折半查找法进行查找时，最大比较次数是( ),最小比较次数是( ）.A。

7，1 B.6，l C.5，1 D. 8，15．散列表长m=15，散列表函数H(key）=key％13。

表中已有4个结点：addr（18)=5；addr(32）=6; addr(59)=7；addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。

A. 8 B。

3 C. 5 D。

46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。

A。

15 B. 27 C。

25 D。

307．散列函数有一个共同性质，即函数值应当以( )取其值域的每个值。

A.同等概率B。

最大概率C。

最小概率D。

平均概率8．设散列地址空间为O.。

m—1，k为关键字，假定散列函数为h(k)=k％p，为了减少冲突，一般应取p为( )。

A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9．当向一棵m阶的B-树做插入操作时，若使一个结点中的关键字个数等于( )，则必须分裂成两个结点。

A。

m B。

m-l C.m+l D。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

5
一、顺序查找（ Linear search，又称线性查找 ）
顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直 接的办法。 见下页之例或教材P216 对顺序结构如何线性查找？ 对单链表结构如何线性查找？ 从头指针始 “顺藤摸瓜” 对非线性树结构如何顺序查找? 借助各种遍历操作！ （1）顺序表的机内存储结构： typedef struct { ElemType *elem; //表基址，0号单元留空。表容量为全部元素 int length; //表长，即表中数据元素个数 }SSTable;

j 1
（详细推导过程见教材P221的附录1）
课堂练习1（多选题）：使用折半查找算法时，要求被查文件：
Ａ．采用链式存贮结构 Ｃ．采用顺序存贮结构
√
Ｂ．记录的长度≤12 Ｄ．记录按关键字递增有序
√
15
再用查找二叉树/判定树来分析ASL(参见教材P220） 以（a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11）为例： a6
静态查找 ——只查找，不改变集合内的数据元素。
动态查找 ——既查找，又改变（增减）集合内的数据元素。 关键字 ——记录中某个数据项的值，可用来识别一个记录
( 预先确定的记录的某种标志 )
主关键字 ——可以唯一标识一个记录的关键字 次关键字 ——识别若干记录的关键字
例如“学号”
例如“女”
2
讨论：
讨论1：查找的过程是怎样的？
d = log2 n + 1 • 查找不成功的过程就是：走了一条从根结点到外部结点的路径。
16
–算法评价
• 判定树：描述查找过程的二叉树 • 有n个结点的判定树的深度k=log2n+1 • 折半查找法在查找过程中进行的比较次数最多不超过其 判定树的深度 • 折半查找的ASL
设有序表长n 2k 1, k log 2 ( n 1)， 则描述折半查找的判定树是深度为k的满二叉树, 即 设表中每个记录的查找概率相等pi
特点：块间有序，块内无序
18
分块查找过程举例：
索引表
块内最大关键字 各块起始地址
22 12 13 8 9 22 1 48 7 86 13
特点：块间有序，块内无序 查找：块间折半，块内线性
20 33 42 44 38 24 48 60 58 74 49 86 53
第1块
查找步骤分两步进行：
第2块
第3块
Average Search Length
统计意义上的 其中： 数学期望值 n是文件记录个数； Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; Ci是找到第i个记录时所经历的比较次数。 物理意义：假设每一元素被查找的概率相同，则查找每一元 素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高
全部比较总次数为1×20＋2×21＋3×22＋4×23…＋m×2m—1 ＝ m j 1
j2
j 1
14
请注意：ASL的含义是“平均每个数据的查找时间”，而前式 是n个数据查找时间的总和，所以： m 1 n 1 j 1 ASL j2 log2 ( n 1) 1 log2 n n n
mid 3 4 19 21
high 5 6 37 56
7 64
8 75
9 80
10 88
11 92
low mid high
11
找70
例 1 5 2 13 3 19 4 21 5 37 6 56 7 64 8 75 9 80 10 88 11 92 high 11 92
low 1 2 5 13
3 19
4
9.2 静态查找表
针对静态线性查找）
二、折半查找（二分或对分查找） 三、分块查找（索引顺序查找） 四、静态树表的查找
静态查找表的定义 （抽象数据类型） 参见教材P216 ADT StaticSearchTable { 数据对象D: 数据关系R： 基本操作P： } ADT StaticSearchTable
ASL=(1*1+2*2+4*3+4*4)/11=3
13
讨论1：若关键字不在表中，怎样得知并及时停止查找？
——典型标志是：当查找范围的上界≤下界时停止查找。high<low
讨论2：如何计算二分查找的时间效率（ASL）？
推 导 过 程
经1次比较就查找成功的元素有1个（20），即中间值； 经2次比较就查找成功的元素有2个（21），即1/4处和3/4处； 3次比较就查找成功的元素有4个（22），即1/8，3/8， 5/8，7/8处 4次比较就查找成功的元素有8个（23），即1/16处，3/16处…… …… 则第m次比较时查找成功的元素应该有（2m-1）个。 注：为方便起见，假设表中全部n个元素刚好是 2m-1个，此时暂 不讨论第m次比较后还有剩余元素的情况。
4 21
5 37
mid 6 7 56 64 low
8 75
9 80
10 88
1 5
2 13
3 19
4 21
5 37
6 56
7 64
mid high 8 9 10 11 75 80 88 92
low mid high 1 5 2 13 3 19 4 21 5 37 6 56 7 64 8 75 9 80 10 88 11 92
讨论3：有哪些查找方法？
查找方法取决于表中数据的排列方式;
例如查字典
针对静态查找表和动态查找表的查找方法也有所不同。
3
讨论4：如何评估查找方法的优劣？
明确：查找的过程就是将给定的K值与文件中各记录的 关键字项进行比较的过程。所以用比较次数的平均值来 评估算法的优劣。称为平均查找长度ASL。
ASL=∑ Pi. Ci
① 对索引表使用折半查找法（因为索引表是有序表）； ② 确定了待查关键字所在的子表后，在子表内采用顺序 查找法（因为各子表内部是无序表）；
19
查找效率ASL分析： ASL=Lb+Lw
n
1 n
1 n 1 k n 1 则：ASL pi ci ci j 2 j 1 log 2 (n 1) 1 log 2 ( n 1) 1 n i 1 n j 1 n i 1
17
讨论：对顺序查找除了折半改进法外，还有无其他改进算法？
有，例如分块查找法。
low high mid
12
1 5
2 13
3 19
4 21
5 37
6 56
7 64
8 75
9 80
10 88
11 92
high low 1 5 2 13 3 19 4 21 5 37 6 56 6 3 1 2 4 5 7 8 9 10 11 7 64 8 75 9 80 10 88 11 92
判定树：
9
折半查找举例： 已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和85的数据元素。
Low指向待查元素 所在区间的下界 mid指向待查元素所在 区间的中间位置 high指向待查元素所 在区间的上界
解：① 先设定3个辅助标志: low,high,mid， 显然有：mid= (low+high)/2 ② 运算步骤：
给定一个值K，在含有n个记录的文件中进行搜索，寻找 一个关键字值等于K的记录，如找到则输出该记录，否则输 出查找不成功的信息。
讨论2：对查找表常用的操作有哪些？
查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。
―特定的”=关键 查询某个“特定的”数据元素是否在表中； 字
三、分块查找（索引顺序查找）
思路：先让数据分块有序，即分成若干子表，要求 每个子表中的数据元素值都比后一块中的数值小 （但子表内部未必有序）。 然后将各子表中的最大关键字构成一个索引表，表 中还要包含每个子表的起始地址（即头指针）。
例：
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
6
（2）算法的实现：
技巧：把待查关键字key存入表头或表尾（俗称“哨兵”）， 这样可以加快执行速度。
例： 若将待查找的特定值key存入顺序表的首部（如0号单
元），并从后向前逐个比较,就不必担心“查不到”。
int Search_Seq( SSTable ST , KeyType key ){
ST.elem[0].key =key; //在顺序表ST中，查找关键字与key相同的元素；
a3
a1 a2 a4 a5
a9
a7 a10 a8 a11
判定树由表中元素个数决 定，且n个元素表的折半 查找判定树是唯一的。
• 找到有序表中任一记录的过程就是：走了一条从根结点到与该记 录对应结点的路径。 • 比较的关键字个数为：该结点在判定树上的层次数。
• 查找成功时比较的关键字个数最多不超过树的深度 d :
二、折半查找（又称二分查找或对分查找）
这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将key 与正中元素相比，若key小，则缩小至右半部内查找；再取其中 值比较，每次缩小1/2的范围，直到查找成功或失败为止。 对顺序表结构如何编程实现折半查找算法？ ——见下页之例，或见教材（P219） 对单链表结构如何折半查找？ ——无法实现！因全部元素的定位只能从头指针head开始 对非线性(树)结构如何折半查找？ ——可借助二叉排序树来查找（属动态查找表形式）。
第 9章
查找
9.1 基本概念
9.2 静态查找表