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

1、1 基本概念基本概念 静态查找表静态查找表 动态查找表动态查找表 哈希表哈希表第第9章章 查找查找2基本概念基本概念若表中存在特定元素，称查找成功，应输出该记录或位置；若表中存在特定元素，称查找成功，应输出该记录或位置；否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查找表 查 找查找成功查找不成功静态查找动态查找关键字主关键字次关键字由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。查询查询(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改变集合内的数据元素。只查找，不改变集合内的数据元

2、素。既查找，又改变（增减）集合内的数据元素。既查找，又改变（增减）集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字识别若干记录的关键字识别若干记录的关键字3明确：明确：查找的过程就是将给定的查找的过程就是将给定的K K值与文件中各记录的关键字项进行比值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找平均查找长度长度（ASLASL：average search lengthaverage sea

3、rch length）。）。其中：其中： n n是记录个数；是记录个数； P Pi i是查找第是查找第i i个记录的查找概率（通常取等概率个记录的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ; C Ci i是找到第是找到第i i个记录时所经历的比较次数。个记录时所经历的比较次数。物理意义：物理意义：假设每一元素被查找的概率相同，则查找每一元素所需假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为的比较次数之总和再取平均，即为ASLASL。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。 如何评估查找方法的优劣？1iini

4、ASLPC基本概念基本概念4针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有： 一、顺序查找（线性查找）一、顺序查找（线性查找）二、折半查找（二分或对分查找）二、折半查找（二分或对分查找）三、静态树表的查找三、静态树表的查找四、分块查找（索引顺序查找）四、分块查找（索引顺序查找）9.1 静态查找表静态查找表5（1）顺序表的机内存储结构：顺序表的机内存储结构：typedef struct ElemType *elem; /表基址，表基址，0 0号单元留空。表容量为全部元素号单元留空。表容量为全部元素 int length; /表长，即表中数据元素个数表长，即表中数据元素个数SSTa

5、ble;Linear search，又称线性查找，又称线性查找，即用逐一比较的办法顺即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。序查找关键字，这显然是最直接的办法。 9.1.1 顺序查找顺序查找6（2）算法的实现：算法的实现：技巧：技巧：把待查关键字把待查关键字keykey存入表头或表尾（俗称存入表头或表尾（俗称“哨兵哨兵”），）， 若将待查找的特定值若将待查找的特定值keykey存入存入顺序表的顺序表的首部首部（如（如0 0号单元），则号单元），则顺序查找的实现方案为：顺序查找的实现方案为：从后向前从后向前逐个比较！逐个比较！int Search_Seq( SSTable ST

6、, KeyType key ) ST.elem0.key =key; /设立哨兵，可免去查找过程中每一步都要检设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当测是否查找完毕。当n1000n1000时，查找时间将减少一半。时，查找时间将减少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /从后往前找从后往前找 return i; /若到达若到达0 0号单元才结束循环，说明不成功，返回号单元才结束循环，说明不成功，返回0 0值值(i=0)(i=0)。成功。成功时则返回找到的元素位置时则返回找到的元素位置i i。 / Search_Se

7、q/不要用不要用for(i=n; i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+)for(i=1; i=n; i+)9.1.1 顺序查找顺序查找7说明说明 查找效率怎样计算？查找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。说明说明 如何计算如何计算ASL？查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n；总计全部比较次数为：总计全部比较次数为：12n = (1+n)n/2这是查找成功的情况这是查

8、找成功的情况若求某一个元素的平均查找次数，还应当除以若求某一个元素的平均查找次数，还应当除以n，即：即： ASL（1n）/2 ，时间效率为，时间效率为 O(n)优点：优点：算法简单，且对顺序结构或链表结构均适用。算法简单，且对顺序结构或链表结构均适用。缺点：缺点： ASL 太长，时间效率太低。太长，时间效率太低。说明说明 顺序查找的特点：顺序查找的特点：8先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与与正中元素相比，若比正中元素相比，若比keykey小，则缩小至右半部内查找；再取其中值小，则缩小至右半部内查找；再取其中值比

9、较，每次缩小比较，每次缩小1/21/2的范围，直到查找成功或失败为止。的范围，直到查找成功或失败为止。折半查找举例：折半查找举例：LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下11个元素的个元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为请查找关键字为21和和85的数据元素。的数据元素。9.1.2 折半查找折半查找（又称二分查找或对分查找又称二分查找或对分查找）9

10、 运算步骤运算步骤： （1） low =1,high =11 ,mid =6 ，待查范围是，待查范围是 1,11； （2）若）若 ST.elemmid.key key，说明，说明key low ,mid-1， 则令：则令：high =mid1;重算重算 mid ； （4）若）若 ST.elem mid .key = key，说明查找成功，元素序号，说明查找成功，元素序号=mid; 结束条件：结束条件： （1）查找成功）查找成功 ： ST.elemmid.key = key （2）查找不成功）查找不成功 ： highlow （意即区间长度小于（意即区间长度小于0）解：解： 先设定先设定3个辅助标

11、志个辅助标志: low,high,midlow,high,mid，显然有：显然有：mid= (low+high)/2 9.1.2 折半查找折半查找（又称二分查找或对分查找又称二分查找或对分查找）10查找查找21:（05 13 19 21 37 56 64 75 80 88 92）lowhighmidlowhighmidlowhighmid 查找结果：查找成功，查找结果：查找成功，21所在位置是所在位置是49.1.2 折半查找折半查找（又称二分查找或对分查找又称二分查找或对分查找）11查找查找85:（05 13 19 21 37 56 64 75 80 88 92）lowhighmidlowhi

12、ghlow highmidlowhighmid查找结果：查找失败查找结果：查找失败9.1.2 折半查找折半查找（又称二分查找或对分查找）（又称二分查找或对分查找）12折半查找算法折半查找算法int Search_Bin(SSTable ST,KeyType key) low=1; high=ST.length; while(lowlchild=NULLf-lchild=NULL或或 f-rchild=NULLf-rchild=NULL20SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)删除18634

13、218158634215821中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP删除12634218121513634218151322F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2: 2: S的左子树成为的左子树成为S的双亲的双亲Q的右子树，的右子树， 用用S取代取代p；若若C无右子树，用无右子树，用C取代取代p F FC CCLS SSLQLPPRQ法法1: 1: P的左子树成为的左子树成为f的左子树，的左子树， P的右子树成为的右子树成为S的右子树的右子树

14、例：请从下面的二叉排序树中删除结点例：请从下面的二叉排序树中删除结点P P。S SSL231036241812156342181215删除104362181215问题：问题：如何提高二叉排序树的查找效率？如何提高二叉排序树的查找效率？尽量让二叉树的形状均衡尽量让二叉树的形状均衡口诀：用左子树最大的结点代替P； 或 用右子树最小的结点代替P24平衡二叉树又称平衡二叉树又称AVL树，它是具有如下性质的二叉树：树，它是具有如下性质的二叉树：为了方便起见，给每个结点附加一个为了方便起见，给每个结点附加一个数字数字，给出，给出该结点左该结点左子树与右子树的高度差子树与右子树的高度差。这个数字称为结点的。

15、这个数字称为结点的平衡因子平衡因子balance。这样，可以得到这样，可以得到AVL树的其它性质：树的其它性质：左、右子树是平衡二叉树；左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值所有结点的左、右子树深度之差的绝对值 1 1v任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1-1、0 0 或或 1 1；如果树中任；如果树中任意一个结点的平衡因子的绝对值大于意一个结点的平衡因子的绝对值大于1 1，则这棵二叉树，则这棵二叉树就失去平衡，不再是就失去平衡，不再是AVLAVL树；树；三、平衡二叉树三、平衡二叉树25(a) (a) 平衡树平衡树 (b) (b) 不是平衡树不是平衡树

16、例：例：判断下列二叉树是否判断下列二叉树是否AVL树？树？0001 11 1-1-10001-1三、平衡二叉树三、平衡二叉树26如果在一棵如果在一棵AVL树中插入一个新结点，就有可能造成失衡，树中插入一个新结点，就有可能造成失衡，此时必须此时必须重新调整树的结构重新调整树的结构，使之恢复平衡。我们称调整，使之恢复平衡。我们称调整平衡过程为平衡过程为平衡旋转平衡旋转。平衡旋转可以归纳为四类：平衡旋转可以归纳为四类：v RR平衡旋转平衡旋转v LL平衡旋转平衡旋转v LR平衡旋转平衡旋转v RL平衡旋转平衡旋转三、平衡二叉树三、平衡二叉树27若在A的左子树的左子树上插入结点，使A的平衡因子从1增加

17、至2，需要进行一次顺时针旋转。(以B为旋转轴）若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需进行一次逆时针旋转。(以B为旋转轴）（2）LL平衡旋转（1）RR平衡旋转三、平衡二叉树三、平衡二叉树28若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）（4）RL平衡旋转若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）（3）LR平衡旋转这种调整规则可以保证二叉排序树的次序不变三、平衡二叉树三、平衡二叉树290 013130 03

18、7370 02424例：例：请将下面序列构成一棵平衡二叉排序树：请将下面序列构成一棵平衡二叉排序树： （ 1313，2424，3737，9090，5353）0 013130 03737-1-113130 02424-1-124241313需要需要RR平衡旋转平衡旋转(绕绕B逆转逆转,B为根）为根）0 09090-1-12424-1-137370 053531 190903737需要需要RL平衡旋转平衡旋转(绕绕C先顺后逆）先顺后逆）0 037370 090900 053530 037370 090900 05353三、平衡二叉树三、平衡二叉树30B-树是一种 平衡平衡 的 多路多路 查找查找

19、树： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96一棵4阶B-树1781501152718432026432382566228996FFFFFFFFFFFFFFF四、四、B-B-树和树和B+B+树树31平衡树的特性平衡树的特性树中每个结点最多含有树中每个结点最多含有 m 棵子树棵子树; ;根结点或为叶子结点，或至少含有两棵子树根结点或为叶子结点，或至少含有两棵子树;其余所有非叶子结点均至少含有其余所有非叶子结点均至少含有 m/2 棵棵子树；子树；树中所有叶子结点均不带信息，且在树中的同一层次上树中所有叶子结点均不带信息，且在树中的同一层次上;每个非终

20、端结点可能含有：每个非终端结点可能含有： n 个个关键字关键字 Ki（1 in） nm n 个个指向记录的指针指向记录的指针 Di（1in） n+1 个个指向子树的指针指向子树的指针 Ai（0in）;多叉树的特性多叉树的特性非叶结点中的非叶结点中的多个关键字多个关键字均均自小至大自小至大有序排列，即：有序排列，即：K1 K2 Kn;且且 Ai-1 所指子树上所有关键字均所指子树上所有关键字均小于小于Ki;Ai 所指子树上所有关键字均所指子树上所有关键字均大于大于Ki; ;查找树的特性查找树的特性 一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:（n,A0,K1,A1,K2Kn,An）32

21、从根结点出发，沿指针搜索结点搜索结点和在结点内进行在结点内进行顺序（或折半）查找查找 两个过程交叉进行。若查找不成功查找不成功，则需要插入关键值需要插入关键值。在B-树中插入一个关键值k，不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键值。并且要使插入的结点中的关键值个数m1，否则将涉及到结点的分裂问题。3 3、B-B-树的插入树的插入2 2、B-B-树的查找树的查找331）插入后，该结点的关键字个数插入后，该结点的关键字个数nm，不修改指针不修改指针; ; 2）插入后，该结点的关键字个数插入后，该结点的关键字个数 n=m，则，则需进行需进行“结点分结点分裂裂”，令，

22、令 s = m/2 ， 在原结点中保留在原结点中保留A0，K1， Ks-1，As-1）；）； 建新结点建新结点（As，Ks+1， ，Kn，An）；）； 将（将（Ks，p）插入双亲结点）插入双亲结点；-分裂后提升3）若双亲为空，则若双亲为空，则建新的根结点建新的根结点。3 3、B-B-树的插入树的插入34例如例如:下列为下列为 3 阶阶B-树，分别插入树，分别插入60、90、30。5020 408060 80 60 80 90906050 8020906030 50 804080 30 503 3、B-B-树的插入树的插入35 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，

23、结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点借调关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的合并 。4 4、B-B-树的删除树的删除36例：请在下面的3阶B-树上依次删除关键字12、50（或100）、37 。53 9053 90454524243 123 123737505010010061 7061 7053 9053 90454524243 33737505010010061 7061 7061 9061 90454524243 3373753531001007070删除12删除5053 7053 70454524243 3

24、3737505090906161删除100从邻近兄弟结点中取一个放到双亲中，从双亲中取一个下移到被删除结点中。3770 9070 90454524243 33737616110010061 9061 90454524243 3373753531001007070删除539090454524243 3373710010061 7061 70从双亲结点中取一个与其邻近兄弟合并389090454524243 3373710010061 7061 70909045453 243 2410010061 7061 7045 9045 903 243 2410010061 7061 70删除3739前面介绍

25、的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是希望不经过任何比较，一次便能得到所查记录。哈希表哈希表它既是一种查找方法，它既是一种查找方法，又是一种存储方法又是一种存储方法40一、哈希表的概念一、哈希表的概念二、哈希函数的构造方法二、哈希函数的构造方法三、冲突处理方法三、冲突处理方法四、哈希表的查找及分析四、哈希表的查找及分析9.4 哈希查找表哈希查找表41哈希表：哈希表：即散列即散列(Hash)存储结构。存储结构。 散列法存储的基本思想：散列法存储的基本思想：建立关键字与其存储位置的建立关键字与其存储位置的对应关系，对

26、应关系， 或者说，由关键字的值决定数据的存储地址。或者说，由关键字的值决定数据的存储地址。 例例1 1：若将学生信息按如下方式存入计算机，如：若将学生信息按如下方式存入计算机，如：将将20010118102200101181020101的所有信息存入的所有信息存入V01V01单元；单元；将将20010118102200101181020202的所有信息存入的所有信息存入V02V02单元；单元；将将20010118102200101181023131的所有信息存入的所有信息存入V31V31单元。单元。欲查找学号为欲查找学号为20010118102200101181021616的信息，便可直接访问

27、的信息，便可直接访问V16V16单元单元优点：优点：查找速度极快（查找速度极快（ (1)(1)）, ,查找效率与元素个数查找效率与元素个数n n无关！无关！9.4 哈希查找表哈希查找表42解：解：根据散列函数根据散列函数H H（k k）k k ，可知元素，可知元素1414应当存入地址为应当存入地址为 1414的单元，元素的单元，元素2323应当存入地址为应当存入地址为2323的单元，的单元， 对应散列存储表（哈希表）如下：对应散列存储表（哈希表）如下：地址地址9111423242539内容内：有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地

28、址H（k）k，请画出存储结构图。 注：H（k）k称为散列函数）9.4 哈希查找表哈希查找表43讨论：如何进行散列查找？ 根据存储时用到的散列函数根据存储时用到的散列函数H(k)H(k)表达式，即可查到结果！表达式，即可查到结果！ 例如，查找例如，查找key=9,key=9,则访问则访问H(9)=9H(9)=9号地址，若内容为号地址，若内容为9 9则成则成 功；若查不到，应当设法返回一个特殊值，例如空指针或功；若查不到，应当设法返回一个特殊值，例如空指针或 空记录。空记录。 缺点：空间效率低！9.4 哈希查找表哈希查找表44选取某个函数，该函数按关键字计算元素的存储选取某个函数，该函数按关键字计

29、算元素的存储位置，并按此存放；位置，并按此存放；查找时，由同一个函数查找时，由同一个函数对给对给定值定值k k计算地址，将计算地址，将k k与地址单元中元素关键字进与地址单元中元素关键字进行比较，确定查找是否成功。行比较，确定查找是否成功。通常关键字的集合比哈希地址集合大得多，因而通常关键字的集合比哈希地址集合大得多，因而经过哈希函数变换后，经过哈希函数变换后，可能将不同的关键字映射可能将不同的关键字映射到同一个哈希地址上到同一个哈希地址上，这种现象称为，这种现象称为冲突冲突。哈希方法哈希方法哈希函数哈希函数 哈希表哈希表 冲冲 突突哈希方法中使用的转换函数称为哈希方法中使用的转换函数称为哈希

30、函数哈希函数按上述思想构造的表称为按上述思想构造的表称为哈希表哈希表哈希表的若干术语哈希表的若干术语45有有6个元素的关键码分别为：（个元素的关键码分别为：（14，23，39，9，25，11）。）。选取关键码与元素位置间的函数为选取关键码与元素位置间的函数为H(k)=k mod 7，地址编地址编号从号从0-6。通过哈希函数对6个元素建立哈希表：253923914H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4 0 1 2 3 4 5 6冲突现象举例冲突现象举例46所以，所以，哈希方法必须解决以下两个问题哈希方法必须解决以下两个问题：1）构造好的哈希函数 （a a）所

31、选函数尽可能简单，以便提高转换速度；）所选函数尽可能简单，以便提高转换速度； （b b）所选函数对关键码计算出的地址，应在哈希地址集）所选函数对关键码计算出的地址，应在哈希地址集 中致均匀分布，以减少空间浪费。中致均匀分布，以减少空间浪费。2）制定一个好的解决冲突的方案 查找时，如果从哈希函数计算出的地址中查不到关键查找时，如果从哈希函数计算出的地址中查不到关键 码，则应当依据解决冲突的规则，有规律地查询其它相码，则应当依据解决冲突的规则，有规律地查询其它相 关单元。关单元。在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。47常用的哈

32、希函数构造方法有：常用的哈希函数构造方法有：1.1. 直接定址法直接定址法 2.2. 除留余数法除留余数法 3.3. 乘余取整法乘余取整法4.4. 数字分析法数字分析法 5.5. 平方取中法平方取中法 6.6. 折叠法折叠法 7.7. 随机数法随机数法 要求一：要求一：n n个数据原仅占用个数据原仅占用n n个地址，个地址，虽然散列查找是以空间换时间，但仍虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。希望散列的地址空间尽量小。要求二：要求二：无论用什么方法存储，目无论用什么方法存储，目的都是尽量均匀地存放元素，以避免的都是尽量均匀地存放元素，以避免冲突。冲突。二、哈希函数的构造方法

33、哈希函数的构造方法48Hash(key) = akey + b ( (a、b为常数为常数) )优点：优点：以关键码以关键码keykey的某个线性函数值为哈希地址，的某个线性函数值为哈希地址，不会产生冲突不会产生冲突. .缺点：缺点：要占用连续地址空间，空间效率低。要占用连续地址空间，空间效率低。 例：例：关键码集合为关键码集合为100，300，500，700，800，900， 选取哈希函数为选取哈希函数为Hash(key)=key/100， 则存储结构（哈希表）如下：则存储结构（哈希表）如下：0 1 2 3 4 5 6 7 8 99008007005003001001 1、直接定址法、直接定址

34、法49Hash(key)=key mod p (p (p是一个整数是一个整数) )特点：特点：以关键码除以以关键码除以p的余数作为哈希地址。的余数作为哈希地址。关键：关键：如何选取合适的如何选取合适的p？技巧：技巧：若设计的哈希表长为若设计的哈希表长为m，则一般取，则一般取pm且为且为质数质数 2、除留余数法50Hash(key)= B*( A*key mod 1 ) ( (A、B均为常数，且均为常数，且0A 724+518+69 = 724+518+69 =13111311法法1 1：移位法移位法 将各部分的最后一位对齐相加。将各部分的最后一位对齐相加。法法2 2：间界叠加法间界叠加法从一端

35、向另一端沿分割界来回折叠后，从一端向另一端沿分割界来回折叠后， 最后一位对齐相加。最后一位对齐相加。 6、折叠法54Hash(key) = random ( key ) (random (random为伪随机函数为伪随机函数) )适用于：适用于：关键字长度不等的情况。造表和查找都很方便。关键字长度不等的情况。造表和查找都很方便。 执行速度（即计算哈希函数所需时间）；执行速度（即计算哈希函数所需时间）； 关键字的长度；关键字的长度； 哈希表的大小；哈希表的大小； 关键字的分布情况；关键字的分布情况； 查找频率。查找频率。小结：构造哈希函数的原则：7、随机数法55三、冲突处理方法冲突处理方法56设

36、计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 具体实现：Hi=(Hash(key)+di) mod m ( 1i m )其中： Hash(key)为哈希函数 m为哈希表长度 di 为增量序列 1，2，m-1，且di=i 1.线性探测法1 1、开放定址法（开地址法）、开放定址法（开地址法）57例：关键码集为关键码集为 47，7，29，11，16，92，22，8，3，哈希表表，哈希表表长为长为m=m=11；哈希函数为；哈希函数为Hash(key)=key mod 11；拟用；拟用处处理冲突。建哈希表如下：理冲突。建哈希表如下：解释：解释：

37、47、7均是由哈希函数得到的没有冲突的哈希地址；均是由哈希函数得到的没有冲突的哈希地址；0 1 2 3 4 5 6 7 8 9 10 Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：，哈希地址有冲突，需寻找下一个空的哈希地址：由由H1=(Hash(29)+1) mod 11=8，哈希地址哈希地址8为空，因此将为空，因此将29存入。存入。另外，另外，22、8、3同样在哈希地址上有冲突，也是由同样在哈希地址上有冲突，也是由H1找到空找到空 的哈希地址的。的哈希地址的。 平均查找长度ASL=(1+2 +1 +1 +1 +4 +1 +2 +2)/9=1.6747729111692228

38、3 11、16、92均是由哈希函数得到的没有冲突的哈希地址；均是由哈希函数得到的没有冲突的哈希地址；58基本思想：基本思想：将具有相同哈希地址的记录链成一个单链表，将具有相同哈希地址的记录链成一个单链表，m个个 哈希地址就设哈希地址就设m个单链表个单链表，然后用一个数组将，然后用一个数组将m个个 单链表的表头指针存储起来，形成一个动态的结构。单链表的表头指针存储起来，形成一个动态的结构。 设设 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函数为：的哈希函数为：Hash(key)=key mod 11，用用处理冲突，则建表如处理冲突，则建表如右图

39、所示。右图所示。 例：例：注：注：有冲突的元素可以插有冲突的元素可以插在表尾在表尾, ,也可以插在表头也可以插在表头平均查找长度ASL=(1*8 +2 *4)/12=1.334730 1 2 3 4 5 6 7 8 9107291116922285037892 2、链地址法、链地址法( (拉链法）拉链法）591 1、采用顺序查找方法查找长度为、采用顺序查找方法查找长度为n n的线性表时的线性表时, ,每个元素的平均每个元素的平均 查找长度为查找长度为 。 （A A）n n （B B）n/2n/2（C C）(n+1)/2(n+1)/2（D D）(n-1)/2(n-1)/22 2、对线性表进行二分

40、查找时、对线性表进行二分查找时, ,要求线性表必须要求线性表必须 。 （A A）以顺序方式存储）以顺序方式存储 （B B）以链接方式存储）以链接方式存储 （C C）以顺序方式存储）以顺序方式存储, ,且结点按关键字有序排序且结点按关键字有序排序 （D D）以链接方式存储）以链接方式存储, ,且结点按关键字有序排序且结点按关键字有序排序 3 3、己知一个有序表为、己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为当二分查找值为2929和和9090的元素时的元素时,

41、,分别需要分别需要( )( )次和次和( )( )次比较才次比较才能查找成功；若采用顺序查找时能查找成功；若采用顺序查找时, ,分别需要分别需要( )( )次和次和( )( )次比较次比较才能查找成功。才能查找成功。 练 习604 4、折半查找有序表（、折半查找有序表（4 4，6 6，1212，2020，2828，3838，5050，7070，8888，100100），若查找表中元素），若查找表中元素2020，它将依次与表中元素，它将依次与表中元素 比较大小。比较大小。 5 5、有一个长度为、有一个长度为1212的有序表，按二分查找法对其查找，在表内各的有序表，按二分查找法对其查找，在表内各元

42、素等概率情况下，查找成功的平均比较次数为（元素等概率情况下，查找成功的平均比较次数为（ ）。）。（A A）35/12 35/12 （B B）37/12 37/12 （C C）39/12 39/12 （D D）43/1243/12 6 6、对下列数据进行分块查找。、对下列数据进行分块查找。最大关键字起始地址72189276 1 610207694172172104189150201276211271练 习617、已知序列50，72，43，85，75，20，35，45，65，30，请构造二叉排序树，并依次给出插入结点58和删除结点20、72之后的二叉排序树。 插入插入58：437220456585

43、5035307558436545588550353075删除删除72：4375456585503530或者或者5843724565855035307558删除删除20：练 习628 8、请将下面序列构成一棵平衡二叉排序树：请将下面序列构成一棵平衡二叉排序树： （ 3939，5858，2727，1212，6464，8888，4747，9696）39395858272712126464888858586464888847479696练 习639、请在下面的3阶B_树上依次插入关键字22、66、88，80；再依次删除 89，88。37 7337 7317 2917 29575779 8979 8937 7337 7317 17 2222 29 29575779 8979