第五部分重要运算部分之查找第11章

《第五部分重要运算部分之查找第11章》由会员分享，可在线阅读，更多相关《第五部分重要运算部分之查找第11章（101页珍藏版）》请在装配图网上搜索。

1、数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华1第五部分 重要运算部分无论是在我们的日常生活中，还是在计算机应用中，都涉及到大量的查找和排序操作。本部分主要介绍了几种常见的、经典的查找、排序算法。在排序过程中涉及到有内外存交互的排序算法不是本部分介绍的重点，本部分主要介绍的是多种内部排序算法。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华2第十一章 查找o查找的相关概念o主要查找方法简介o静态查找o动态查找o散列查找数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华3查找查找设数据集合之中有n个数据元素，ki为数据元素Ri的关键字，现给定关键字

2、k,将寻找相应数据元素R的过程称为查找。查找的相关概念数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华4关键字关键字查找的相关概念主关键字主关键字：能唯一标识数据元素的数据项。次关键字次关键字：不能唯一标识数据元素的数据项。在“查找”概念中提到的关键字指的是主关键字。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华5查找表查找表查找表是一种以集合为逻辑结构、以查找为核心的数据结构。由于集合中的数据元素之间只有属于同一个集合的关系，因此查找表的实现就比较灵活，可以根据实际应用对查找的具体要求去组织查找表，以便实现高效的查找。查找的相关概念数据结构与应用算法C语言描

3、述配套课件湖北工业大学计算机学院 沈华6查找的分类查找的分类（1）分为静态查找静态查找和动态查找动态查找。根据查找的过程中是否修改查找表，将查找分为静态查找和动态查找。（2）分为内查找内查找和外查找外查找。根据查找的过程中是否有内外存的交互，将查找分为内查找和外查找。查找的相关概念数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华7n静态查找静态查找对查找表的查找仅是以查询为目的，不改动查找表中的数据。n动态查找动态查找在查找的过程中同时插入不存在的记录，或删除某个已存在的记录。查找的相关概念数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华8n内查找内查找整个查找

4、过程都在内存中进行。n外查找外查找在查找过程中需要访问外存。查找的相关概念数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华9两种查找结果两种查找结果查找的相关概念成功查找：成功查找：给出整个数据元素信息，或给出该数据元素的位置。不成功查找：不成功查找：返回0或空指针。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华10查找效率查找效率是判定查找算法好坏的关键因素 一般用平均查找长度平均查找长度ASL(Average Search Length)来分析一个算法的查找效率。查找的相关概念数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华11平均查找长度

5、平均查找长度ASL 查找成功时的ASL计算方法：其中：n 记录的个数pi 查找第 i 个记录的概率 (不特别声明时认为等概率 pi=1/n)ci 找到第 i 个记录所需的比较次数查找的相关概念数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华12主要查找方法简介数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华13静态查找假设记录类型定义如下：#define MAX 50typedef int KeyType;typedef structKeyType key;/关键字InfoType otheritems;/其它数据项RecType;数据结构与应用算法C语言描述配

6、套课件湖北工业大学计算机学院 沈华14静态查找在静态查找表的组织方式中，线性表是最简单的一种。下面介绍的三种静态查找方法均是在线性表上进行的。u顺序查找u二分查找（折半查找）u分块查找数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华15基本思想基本思想顺序查找将给定关键字k与表中各个记录的关键字逐个进行比较，若相等则查找成功，否则失败。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华16适用范围适用范围顺序存储的或链式存储的有序或无序线性表。即 有序顺序表 无序顺序表 有序链表 无序链表顺序查找数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华17

7、【顺序查找举例说明】例11.1 对线性表L:(2,4,3,12,6,5)进行顺序查找，若查找成功，则返回元素在线性表中的位置，否则返回0。给出待查关键字为3和7时的查找过程。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华18【顺序查找举例说明（续）】解：（1）L采用顺序存储结构数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华19【顺序查找举例说明（续）】算法实现如下：typedef RecType ElemType;int SeqSearch(SqList L,KeyType key)int j;L.data0.key=key;/设置哨兵for(j=L.len

8、;L.dataj.key!=key;j-);return j;数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华20【顺序查找举例说明（续）】解：（2）L采用链式存储结构使用单链表作为存储结构时，扫描必须从表头开始，即从第一个结点开始，其算法已在4.3节中讨论过，这里就不详细叙述了。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华21【顺序查找的性能分析】（1）以顺序表作为存储结构时假设查找表的长度为n，则有l当待查关键字是查找表的最后一个关键字时，需要1(=n-n+1)次关键字比较就能查找成功；l当待查关键字是第一个关键字时，需要进行n(=n-1+1)次关键字比

9、较才能查找成功；数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华22【顺序查找的性能分析（续）】（1）以顺序表作为存储结构时（Cont.）l当成功查找查找表的第i个关键字时，需要进行n-i+1次的关键字比较；故在等概率的情况下，查找成功时的平均查找长度为：数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华23【顺序查找的性能分析（续）】（1）以顺序表作为存储结构时（Cont.）l当待查关键字key不在表中时，需要依次和表中的所有关键字比较一次，直到与哨兵也比较一次后才能确定查找失败，因此，查找不成功的顺序查找的平均查找长度为：数据结构与应用算法C语言描述配套课件湖

10、北工业大学计算机学院 沈华24【顺序查找的性能分析（续）】（2）以单链表作为存储结构时分析查找表以单链表作为存储结构的顺序查找的平均查找长度，可以得到与上面类似的结论，这里就不再叙述了。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华25【顺序查找小结】顺序查找算法简单，适用范围广，但查找效率较低，当n较大时不宜采用顺序查找。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华26适用范围适用范围顺序存储的有序线性表，即有序顺序表。二分查找（折半查找）数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华27基本思想基本思想二分查找（折半查找）先取表的中间

11、位置上的记录的关键字与给定关键字k进行比较,若相等则查找成功;否则,若k值比该记录的关键字大,则下次比较在后半部分(递增的有序表);否则应在前半部分。这样,每经过一次比较就将查找范围缩小一半。如此反复进行,直到查找不成功为止。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华28【二分查找举例说明】例11.2 有序顺序表L为6，11，25，31，48，53，67，72，84，待查关键字key为31。画出对该有序顺序表L进行二分查找的过程。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华29【二分查找举例说明（续）】数据结构与应用算法C语言描述配套课件湖北工业大学计

12、算机学院 沈华30【二分查找举例说明（续）】数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华31【二分查找举例说明（续）】若将待查关键字key改为32，显然该关键字也依次和48、11、25、31进行比较，但在第四次比较中，32 L.datam.key=L.data4=31，此时应修改下界为l=m+1=4+1=5，得到的新查找范围为5,4，发现，下界反而大于了上界，说明该查找表中不存在关键字等于key的记录，查找失败。故在二分查找中，查查找失找失败败的条件是：的条件是：l h。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华32【二分查找举例说明（续）】算法实现如

13、下：int BinSearch(SqList L,KeyType key)int l,h,m;l=1;h=L.len;while(l key)h=m-1;else l=m+1;数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华33性能分析（平均查找长度性能分析（平均查找长度ASL）二分查找（折半查找）可用一棵二叉树描述折半查找的过程，这种描述查找过程的二叉树成为判定树判定树。可利用判定树来求折半查找的查找成功的平均查找长度和查找不成功的平均查找长度。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华34例11.2对应的判定树如下所示：所有长度为9的查找表的二分查找对

14、应的判定树都形如上图所示的判定树，它描述了对长度为9的查找表进行二分查找的查找路线。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华35如果待查关键字key是查找表中的某个关键字，那么一定查找成功，需要的比较次数可以通过相应的判定树得到。假设此关键字在判定树中对应的结点为i，那么成功成功查查找找该该关关键键字的比字的比较较次数次数为为从根从根结结点到达点到达结结点点i的路的路径径长长度度。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华36根据判定树的构造过程可知，它具有这样的特点：除去最大层是一棵满二叉树，叶子只分布在最大层和次大层上。对于满足这个特点的所有二

15、叉树，二叉树的性质4均适用。故可知，对长度为n的有序顺序表进行二分查找，查查找成功找成功时时的关键字最最大比大比较较次数次数为log2n+1或者log2(n+1)，查查找成找成功功时时的关键字最小比最小比较较次数次数显然为1。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华37利用判定树也可以分析查找失败时的平均查找长度，为了便于理解，对判定树稍作修改，即向其中添加外部结点（用方结点表示），树中原来的结点称为内部结点（用圆结点表示）。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华38就例11.2所给的关键字序列而言，凡是比关键字6小的元素均落在编号为的外部结点

16、内；编号为的外部结点表示的关键字范围为7,10；以此类推。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华39可见，当待查关键落入上述10个区间内的任何一个，都将意味着查找失败。查找失败对应的是根结点到达某外部结点的路径，查查找失找失败时败时的关的关键键字比字比较较次数次数为该为该路径上路径上经过经过的内部的内部结结点个数点个数。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华40通过上述分析可知，查找失败的关键字比较次数不会超过判定树的深度，即查查找失找失败时败时的关键字最大比最大比较较次数次数为 log2n +1或者 log2(n+1)。因为外部结点分布在添

17、加外部结点后的判定树的最大层和次大层上，故可知查查找找失失败时败时的关键字最小比最小比较较次数次数为 log2n 或者 log2(n+1)-1。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华41【思考题12.1】对拥有22个记录的有序顺序表进行二分查找，（1）当查找成功时，至多需要进行多少次关键字的比较？至少需要进行多少次关键字的比较？（2）当查找失败时，至多需要进行多少次关键字的比较？至少需要进行多少次关键字的比较？数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华42分析：因为长度为22的有序顺序表对应的判定树的深度为log222+1=5，故可知：当查找成功

18、时，至多需要进行5次关键字的比较；当查找失败时，至多需要进行5次关键字的比较，至少需要进行4次关键字的比较。当待查关键字为中间位置上的关键字时，只需进行1次关键字的比较就可以查找成功，故查找成功时，至少需要进行1次关键字的比较。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华43【思考题10.2】建立一棵具有13个结点的判定树，并求其查找成功和查找不成功的平均查找长度各为多少？已知关键字序列3，11，17，21，39，45，51，60，68，73，81，88，92，请问欲查找k=39的记录须比较多少次？欲查找k=92的记录须比较多少次？数据结构与应用算法C语言描述配套课件湖北工

19、业大学计算机学院 沈华44分析：具有13个结点的判定树如下图所示。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华45分析（续）：关键字k=39的记录在序列中的位序为5，判定树中它对应的结点位于第3层，所以成功查找k=39的记录须比较3次，且依次与关键51、17和39进行了比较；关键字k=92的记录在序列中的位序为13，判定树中它对应的结点位于第4层，所以成功查找k=92的记录须比较4次，且依次与关键51、73、88和92进行了比较。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华46【二分查找小结】平均查找长度较小，查找速度快，特别是当n较大时，它的查找效率较

20、高。但在查找前需要将顺序表按记录关键字的大小排序，而排序本身是一种比较耗时的运算。二分查找只适用于顺序存储结构。二分查找特别适合长度较大、改动较少且又经常进行查找的顺序表。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华47适用范围适用范围分块查找（Blocking Search）又称为索引顺序查找，它是一种性能介于顺序查找和二分查找之间的查找方法。它适用于“分块有序”的线性表，采用顺序、链式存储结构均可。分块查找数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华48分块有序分块有序所谓“分块有序”是指查找表中的记录可按其关键字的大小分成若干“块”，且“前一块”中

21、的最大关键字小于“后一块”中的最小关键字，而各块内部的关键字不一定有序。分块查找数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华49【分块查找举例说明分块查找举例说明】对如下一个采用顺序存储的线性表采用分块查找，共分成3块，每一块含有4个记录，并从各块中抽取最大关键字构成一个索引表。maxkeyaddr12 22 13 8 28 33 38 42 86 76 50 631 2 3 4 5 6 78 9 10111222 42 86159索引表索引表数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华50分块查找的步骤分块查找的步骤分块查找（1）折半或者顺序查找索引表

22、，确定待查关键字可能存在的块。（2）在已确定的块中顺序查找（若块中有序也可折半查找）。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华51分块查找性能分析（平均查找长度性能分析（平均查找长度ASL）设b为索引表长度，s为块中记录个数n 顺序查找索引表+顺序查找被确定的块ASL成功 =当 s 取 时，ASL成功 取最小值 。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华52分块查找性能分析（续）性能分析（续）n折半查找索引表+顺序查找被确定的块ASL成功=log2(b+1)-1+(s+1)/2 log2(n/s+1)+s/2数据结构与应用算法C语言描述配套课件湖

23、北工业大学计算机学院 沈华53动态查找本节主要讨论树表和用树结构存储元素集合时的动态查找算法，树表本身是在查找过程中动态建立的。树表主要有二叉排序树（也称为二叉查找树或二叉搜索树）、平衡二叉树、红-黑树、B-树、B+树等。二叉排序树和平衡二叉树已在第9章进行了介绍，这里主要介绍B-树。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华54B-树DefinitionB-树又称为平衡多路查找树或外部查找树，是一种组织和维护外存文件系统的有效数据结构。一棵m(m3)阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：1）每个结点至多有m个孩子结点；2）除根外，其他每个结点至少有m/2

24、个孩子结点；数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华55B-树Definition(Cont.)3）若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树；4）所有叶子结点都在同一层上，叶子结点不包含任何信息，仅表示查找失败（可以把叶子结点看成是实际上不存在的外部结点，指向这些结点的指针为空）；数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华56Definition(Cont.)5）每个非叶子结点中包含以下信息：（n，P0，K1，P1，K2，P2，K3，Kn，Pn）其中，n为该结点中关键字的个数（m/2-1 n m-1）。Ki为关键字，关键字

25、序列递增有序，即Ki Ki+1（1 i n-1）。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华57Definition(Cont.)Pi为孩子指针：P0所指子树上的所有结点中的关键字均小于K1；P1所指子树上的所有结点中的关键字均大于K1且均小于K2；P2所指子树上的所有结点中的关键字均大于K2且均小于K3；Pn-1所指子树上的所有结点中的关键字均大于Kn-1且均小于Kn；Pn所指子树上的所有结点中的关键字均大于Kn。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华58【B-树示意图】下图所示为一棵包含11个关键字的4阶B-树。数据结构与应用算法C语言描述配

26、套课件湖北工业大学计算机学院 沈华59B-树B-树的查找在B-树上的查找过程中，当到达某个结点时，先在结点内进行顺序查找或二分查找，若找到，则查找成功；否则，若key K1，则到P0指向的子树中继续进行查找，若Ki key Kn，则到Pn指向的子树中继续进行查找。当到达叶子结点时，说明树中没有相应的关键字，查找失败。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华60【B-树上的查找(成功)举例说明】查找关键字63。搜索过程：从根根结结点点a开始，因为63 35，所以到结点c中继续进行查找；在结结点点c中采用顺序查找或者折半查找，发现54 63 35，所以到结点c中继续进行查找

27、；在结结点点c中采用顺序查找或者折半查找，发现54 65 78，因此到结结点点g中继续进行查找；在结点g内发现63 65 78，因此沿着结点g的第3个指针向下搜索，但此指针为空，意味着查找失败。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华62B-树B-树的插入和生成在B-树的插入一个关键字的步骤是：1）按照B-树查找的方法找到待插入关键字的适当位置：若找到了与待插入关键字相等的关键字，则插入操作结束；否则搜索过程一定止步于最底层的某个非终端结点，即找到了插入的结点。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华63B-树B-树的插入和生成（续）2）假设找到

28、的添加结点为A，如果添加前，结点A中的关键字个数小于m-1，则将待插入关键字插入到结点A的适当位置即可；如果添加前，结点A中的关键字个数已经等于m-1，那么将待插入关键字按照其大小插入到结点A后，必会破坏结点A的B-树性质。为了保证结点的B-树性质，要进行结点A的“分裂”。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华64结点A“分裂”的过程：把结点A中间位置上的关键字k取出来插入到A的双亲结点中；位于k前面的关键字和后面的关键字分属于分裂得到的两个结点；将k插入A的双亲结点，可能引起双亲结点的再分裂，从而可能引起祖先的连锁分裂，甚至可能一直传播到根。当根分裂时，因根没有双亲

29、，故需要建立一个新的根，这时B-树增加了一层，因此B-树是一棵自底向上成长的树。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华65【B-树上的插入举例说明】插入关键字8。插入过程：根据B-树的查找方法可知，当查找路径到达结点d时，查找失败，则结点d就是关键字8的插入结点。此时结点d包含1(m-1=4-1=3)个关键字，故直接将关键字8插入到结点d的适当位置即可，同时注意修改结点d的关键字个数。情况1：数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华66【B-树上的插入举例说明】插入关键字8。情况1（续）：插入关键字8后得到的4阶B-树如下图所示。数据结构与应用

30、算法C语言描述配套课件湖北工业大学计算机学院 沈华67【B-树上的插入举例说明】继续插入关键字70。插入过程：通过查找可知，结点g就是关键字的插入结点。因为结点g包含3(=m 1)个关键字，故关键字的插入会引起结点g的分裂。其中，63会进入结点c，而57属于分裂得到的新结点i，70、76则属于另一个分裂得到的新结点j。因为结点c中所含的关键字个数并未达到最大值，因此插入63，不会引起结点c的分裂。情况2：数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华68【B-树上的插入举例说明】继续插入关键字70。情况2（续）：继续插入关键字70后得到的4阶B-树如下图所示。数据结构与应用算

31、法C语言描述配套课件湖北工业大学计算机学院 沈华69B-树B-树的删除在B-树的删除一个关键字的步骤是：1）利用B-树的查找运算对待删除的关键字进行定位，也就是确定该关键字在B-树的哪一个结点上；2）实施删除。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华70B-树的删除（续）假设结点C是B-树中最后一层的一个非叶子结点，下面讨论删除结点C中的关键字key可能出现的各种情况：1）如果结点C包含的关键字个数大于m/2-1，那么只需要删除结点C中的关键字key和key右边的指针即可使删除操作结束。（此情况下的删除举例请参见教材（此情况下的删除举例请参见教材P223-P224）数据

32、结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华71B-树的删除（续）2）如果结点C包含的关键字个数等于m/2-1，那么此时删除结点C中的关键字key和key右边的指针，会破坏结点C的B-树性质（因为删除关键字key后，使得结点C所包含的关键字个数小于B-树规定的最低要求），此时需要进行调整，以帮助结点恢复B-树性质。（具体调整过程描述和举例请参见教材（具体调整过程描述和举例请参见教材P224-P227）数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华72散列查找前面讨论的线性查找（顺序查找、折半查找、分块查找）、二叉查找树查找都是以关键字的比较操作为基础的。本节介

33、绍的散列查找法（也称为哈希查找法或杂凑查找法）是通过对记录的关键字值进行某个函数，直接得到记录的存储地址，不需要进行关键字的反复比较。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华73散列查找u相关概念u散列函数的构造方法u处理冲突的方法u散列表的查找数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华74相关概念冲突冲突&同义词同义词对于某个散列函数（也称为哈希函数）H和两个关键字ki和kj，如果ki kj，而H(ki)=H(kj)，这种现象称为冲突冲突。ki和kj称为散列函数H的同义词同义词。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华75

34、相关概念散列表（哈希表、杂凑表）散列表（哈希表、杂凑表）根据散列函数散列函数 H 和处理冲突的方法处理冲突的方法将一组关键字映射到一个有限的连续地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华76问题：问题：如何构造哈希函数？如何构造哈希函数？如何解决冲突？如何解决冲突？数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华77散列函数的构造方法直接地址法直接地址法取关键字的值或关键字的某个线性函数的值作为哈希地址，即 H(key)=key或 H(key)=a key+b数据结

35、构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华78散列函数的构造方法数字分析法数字分析法假设有一组关键字，每个关键字由n位数字组成，如ki1ki2kin，从中提取数字分布比较均匀的若干位作为哈希地址。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华79【数字分析法举例说明】设哈希表长为100，则可从中间四位任取两位作为哈希地址，或取其中两位与另外两位叠加求和后舍去进位作为哈希地址。k1的哈希地址的哈希地址:45 or 43 or 99 or k2的哈希地址的哈希地址:72 or 74 or 96 or k3的哈希地址的哈希地址:84 or 82 or 29 or k

36、4的哈希地址的哈希地址:03 or 06 or 37 or k1:8 1 3 4 6 5 3 2k2:8 1 3 7 2 2 4 2 k3:8 1 3 8 7 4 2 2 k4:8 1 3 0 1 3 6 7 数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华80散列函数的构造方法除留余数法除留余数法取关键字被某个不大于哈希表长（m）的数p除后所得余数作为哈希地址。即H(key)=key MOD p (p m)p一般取不大于表长的最大素数。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华81散列函数的构造方法平方取中法平方取中法先通过求关键字的平方值以扩大相近数的

37、差别，然后根据表长度取关键字平方的中间几位作为哈希地址。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华82【平方取中法举例说明】设哈希表长为1000，可取关键字平方值得中间3位作为哈希地址。eg:key1234 2143 41323214(key)2152275645924491707342410329796哈希函数值哈希函数值227924734297数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华83散列函数的构造方法折叠法折叠法把关键字分成位数相同的几段（最后一段的位数可少一些），段的位数取决于哈希地址的位数，然后将各段的叠加和（舍去最高进位）作为哈希地址

38、。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华84【折叠法举例说明】设哈希表长为1000，则将关键字以3位一分分成几个位数均为3的段，将这些段的叠加和作为该关键字的哈希地址。k1:8 1 3 4 6 5 3 2k2:8 1 3 7 2 2 4 2 k3:8 1 3 8 7 4 2 2 k4:8 1 3 0 1 3 6 7 8 1 3 4 6 5 3 21 3 1 0k1的哈希地的哈希地址为址为:310+8 1 3 7 2 2 4 21 5 7 7+k2的哈希地的哈希地址为址为:577 8 1 3 8 7 4 2 21 7 0 9+k3的哈希地的哈希地址为址为:709 8 1

39、 3 0 1 3 6 7 8 9 3+k4的哈希地的哈希地址为址为:893eg:数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华85散列函数的构造方法随机数法随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华86解决冲突的方法好的散列函数能够减少冲突但是不能避免冲突，在在散列散列法中冲突是不可避免的法中冲突是不可避免的。如何解决冲突是一个非常关键的问题。下面介绍几种常用的解决冲突的方法

40、：l开放地址法（Open Addressing）l链地址法（也称为拉链法）l再散列法l建立公共溢出区数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华87l开放地址法其中：H(key)为散列函数；m为散列表表长。根据根据di的不同求法，将开放地址法又分成以下几种方的不同求法，将开放地址法又分成以下几种方法：法：线性探测法线性探测法 di=1,2,m-1 二次探测法二次探测法 di=12,-12,22,-22,k2 (k m/2)随机探测法随机探测法 di=随机序列随机序列数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华88【线性探测法举例说明】例11.3 关键字集

41、为 47,7,29,11,16,92,22,8,3，散列表表长为11，H(key)=key mod 11，用线性探测法处理冲突，建立该散列表。（求解过程请参见教材求解过程请参见教材P230-P231）数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华89【线性探测法举例说明（续）】n 线性探测再散列法的缺点缺点容易产生“二次聚集二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。n 线性探测再散列的优点优点只要散列表不满，就一定能找到一个不冲突的散列地址。从例11.3的解答过程中可以发现：数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华90【二次探测法举例说明

42、】例11.4 关键字集为 47,7,29,11,16,92,22,8,3，散列表表长为11，H(key)=key mod 11，用二次探测法处理冲突，建立该散列表。（求解过程请参见教材求解过程请参见教材P231-P232）从例11.4的解答过程中可以发现：二次探测再散列的缺点缺点：不易探查到整个散列空间。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华91解决冲突的方法l链地址法把具有相同散列地址的关键字放在同一个链表中，有m个散列地址就有m个链表，同时用一个一维数组存放各个链表的头指针。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华92【链地址法举例说明】例

43、11.5 关键码集为 47，7，29，11，16，92，22，8，3，50，37，89，94，21，哈希表表长为11，H(key)=key mod 11，用链地址法处理冲突，建立该哈希表。（求解过程请参见教材求解过程请参见教材P232）数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华93【链地址法举例说明（续）】开放地址法的特点特点：冲突处理简单，无堆积现象，平均查找长 度较短；较适合于事先无法确定表长的情况；删除结点的操作易于实现从例11.5的解答过程中可以发现：数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华94解决冲突的方法l再哈希法RHi均是不同的哈希函

44、数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算的时间。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华95解决冲突的方法l建立公共溢出区这种方法的基本思想是将哈希表分为基本表和溢出表的两个部分。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到哈希地址是什么，一旦发生冲突，都填入溢出表。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华96散列表的查找假设给定关键字key，根据建表时设定的散列函数H，计算出key的散列地址。如果散列表中此地址上并未存放记录（即为空），则查找失败；否则将ke

45、y与该地址中的关键字进行比较，若相等则查找成功，否则按建表时设定的处理冲突的方法找出下一个地址，如此反复，直到找到的地址为空（查找失败）或关键字比较相等（查找成功）为止。基本思想基本思想数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华97散列查找的性能分析散列查找的性能分析查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：1.哈希函数是否均匀；2.处理冲突的方法；3.哈希表的装填因子装填因子。数据结构与应用算法C语言描述配套课件湖北工

46、业大学计算机学院 沈华98l散列表的装填因子散列表的装填因子是散列表装满程度的装填因子。由于表长是定值，与“填入表中的元素个数”成正比，所以，越大，填入表中的元素较多，产生冲突的可能性就越大；越小，填入表中的元素较少，产生冲突的可能性就越小。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华99例11.6 设哈希函数为H(key)=key mod p，哈希表地址空间为012，对给定关键字序列为19，14，23，01，68，21，84，38，分别以链地址法和线性探测法构造哈希表，并计算查找成功和不成功的平均查找长度。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华1

47、00解：（1）以链地址法构造散列表如下所示：H(19)=19 mod 13=6H(14)=14 mod 13=1H(23)=23 mod 13=10H(01)=01 mod 13=01H(68)=68 mod 13=3H(21)=21 mod 13=8H(84)=84 mod 13=6H(38)=38 mod 13=12数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华101解：（2）以线性探测法构造散列表如下所示：H(19)=19 mod 13=6；H(14)=14 mod 13=1；H(23)=23 mod 13=10；H(01)=01 mod 13=01；H(68)=68 mod 13=3；H(21)=21 mod 13=8；H(84)=84 mod 13=6；H(38)=38 mod 13=12；