数据结构第22讲哈希表和插入排序1.ppt

《数据结构第22讲哈希表和插入排序1.ppt》由会员分享，可在线阅读，更多相关《数据结构第22讲哈希表和插入排序1.ppt（58页珍藏版）》请在三一办公上搜索。

1、第9章 查找9.1 静态查找表9.2 动态查找表9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析,9.3.1 什么是哈希表,哈希表技术的主要目标是提高查找效率。1.哈希函数：根据关键字直接计算出元素所在位置的函数。例：设哈希函数为：H(K)=K/3+1，则构造关键字序列为 1、2、5、9、11、13、16、21、27 的散列表（哈希表）为：,2.冲突 两个不同的关键字具有相同的存储位置。,3.哈希表 根据设定的哈希函数 H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字

2、在地址集中的“象”作为记录在表中的存储位置，这种表便称为哈希表，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。,在哈希存储中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。(1)装填因子；装填因子是指哈希表中己存入的元素个数 n 与哈希表的大小 m 的比值，即=n/m（=1）。越小，发生冲突的可能性越小，反之，发生冲突的可能性就越大。但是，太小又会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两个方面。(2)所构造的哈希函数;(3)解决冲突的方法。,构造好的哈希函数，使冲突尽可能的少

3、 设计有效的解决冲突的方法,第9章 查找9.1 静态查找表9.2 动态查找表9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析,9.3.2 哈希函数的构造方法,例：关键码集合为 100，300，500，700，800，900，选取哈希函数为 Hash(key)=key/100，则存储结构（哈希表）如下：,1.直接定址法 取关键字或关键字的某个线性函数值为散列地址，即（K）=K 或 H（K）=a*K+b（其中a、b为常数）。,优点：以关键码 key 的某个线性函数值为哈希地址，不会产生冲突。缺点：要占用连续地址空

4、间，空间效率低。,2.除后余数法 取关键字被不大于散列表表长 m 的数 p 除后所得的余数为哈希函数。即 H（K）=K mod p（pm）经验得知：一般可选p为质数或不包含小于20的质因素的合数。3.平方取中法 取关键字平方后的中间几位为哈希函数。因为中间几位与数据的每一位都相关。例：2589的平方值为6702921，可以取中间的029为地址。,选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。,3 4 7 0 5 2 4 3 4 9 1 4 8 73 4 8 2 6 9 63 4 8 5 2 7 03 4 8 6 3 0 53 4 9 8 0 5 83 4

5、 7 9 6 7 13 4 7 3 9 1 9,例：有一组（例如80个）关键码，其样式如下：,讨论：第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。,位号：,若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。,4.数字分析法,5.折叠法 是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。适用于：每一位上各符号出现概率大致相同的情况。,移位法：将各部分的最后一位对齐相加。间界

6、叠加法：从一端向另一端沿分割界来回折叠后，最后一位对齐相加。例：元素42751896,移位法：42751896=1041 间界叠加法：427 518 96 724+518+69=1311,6.随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。,实际工作中需视不同情况采用不同的哈希函数。通常考虑的因素：(1)计算哈希函数所需时间(包括硬件指令的因素)；(2)关键字的长度；(3)哈希表的大小；(4)关键字的分布情况；(5)记录的查找频率。,第9章 查找9.1 静态查

7、找表9.2 动态查找表9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析,9.3.3 处理冲突的方法1.开放地址法 开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，即转而寻找其它尚开放的地址。,（1）线性探测法 设散列函数 H（K）=K mod m（m为表长），若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为：Hi=(H(K)+di)mod m(di=1,2,m-1),例 关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11；哈希函数为

8、Hash(key)=key mod 11；拟用线性探测法处理冲突。建哈希表：,0 1 2 3 4 5 6 7 8 9 10,29,22,8,3,线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i 个哈希地址的同义词存入第i+1 个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，,因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。,可采用二次探测法或伪随机探测法，以改善“堆积”问题。,1.开放地址法,（2）二次探测法 二次探测法对应的探查地址序列的计算公式为：Hi=(H(k)+di)

9、mod m 其中di=12,-12,22,-22,j2,-j2(jm/2)。,0 1 2 3 4 5 6 7 8 9 10,若di伪随机序列，就称为伪随机探测法,例 关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；拟用二次探测法处理冲突。建哈希表如下：,Hi=(H(k)+di)mod m其中di=12,-12,22,-22,j2,-j2(jm/2),2.链地址法,优点：插入、删除方便。缺点：占用存储空间多。,基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设 m个单链表，然后用一个数组将m

10、个单链表的表头指针存储起来，形成一个动态的结构。,例：设 47,7,29,11,16,92,22,8,3,50,37,89 的哈希函数为：Hash(key)=key mod 11，用拉链法处理冲突，建表。,有冲突的元素可以插在表尾,也可以插在表头。,3.再哈希法Hi=RHi(key)RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产生“聚集”，但是增加了计算时间。,4.建立一个公共溢出区,第9章 查找9.1 静态查找表9.2 动态查找表9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.

11、4 哈希表的查找及其分析,9.3.4 哈希表的查找及其分析,散列表的目的主要是用于快速查找。在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。,例：设有一组关键字 19,01,23,14,55,20,84,27,68,11,10,77，采用哈希函数为：H（k）=k mod 13。采用开放地址的线性探测法解决冲突，试在018的散列地址空间中，对该关键字序列构造哈希表。,解：依题意 m=19，得到线性探测法对应的探查地址序列计算公式为：di=(H(k)+j)mod 19;j=1,2,18 其计算函数如下：,H(19)=19 mod 13=6,H(01)=

12、01 mod 13=1,H(23)=23 mod 13=10,H(14)=14 mod 13=1(冲突),H(14)=(1+1)mod 19=2,H(55)=55 mod 13=3,H(20)=20 mod 13=7,H(84)=84 mod 13=6(冲突),H(84)=(6+1)mod 19=7(冲突),H(84)=(6+2)mod 19=8,H(27)=27 mod 13=1（冲突）,H(27)=(1+1)mod 19=2(冲突),H(27)=(1+2)mod 19=3(冲突),H(27)=(1+3)mod 19=4,19,19,01,23,14,55,20,84,27,68,11,10

13、,77,01,23,14,55,20,84,27,哈希查找的性能分析 哈希查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。,1.线性探查法的性能分析 由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的哈希函数H及装填因子的值和该处理方法有关。这时的成功的平均查找长度为：ASL=(1+1/(1-)/2,2.链地址法查找的性能分析 由于链地址法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。平均查找长度：

14、ASL=1+/2,例：给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、哈希查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种哈希查找的哈希表)，并求出每一种查找的成功平均查找长度。设哈希函数为：H(k)=k mod 11，哈希表表长m=11。,顺序查找的顺序表（一维数组）,由图可得：顺序查找的成功平均查找长度为 ASL=(1+2+3+4+5+6+7+8)/8=4.5,二分查找的判定树（中序序列为从小到大排列的有序序列）

15、,由图可得：二分查找的成功平均查找长度为 ASL=(1+2*2+3*4+4)/8=2.625,二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图(b)所示。,由图(a)可得：二叉排序树查找的成功平均查找长度为 ASL=(1+2*2+3*2+4+5*2)/9=3.125由图(b)可得：平衡二叉树的成功平均查找长度为 ASL=(1+2*2+3*3+4*2)/8=2.75,11,10,1,3,2,4,3,1,11,2,10,4,78,21,线性探查法解决冲突的哈希表如图所示。,由图可得：线性探查法的成功平均查找长度为 A

16、SL=（1+1+2+1+3+2+8+1）/8=2.375,链地址法解决冲突的哈希表如图所示。,由图可得：链地址法的成功平均查找长度为 ASL=(1*6+2*2)/8=1.25,小结 1.掌握查找的基本概念；2.熟练掌握静态查找表的查找算法思想并灵活应用；3.熟练掌握动态查找表的特点以及二叉排序树、平衡二叉树的各种操作思想 4.了解B-、B+树的概念及插入和删除操作；5.熟练掌握哈希表的基本概念、哈希函数的构造方法和解决冲突的方法，并能计算平均查找长度。,第10章 内部排序10.1 排序的基本概念10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序10.6 基数排序10.7

17、各种内部排序方法的比较,10.1 排序的基本概念,1.排序 设含有n个记录的文件R1，R2，Rn，相应的关键字为K1，K2，Kn，需确定一种排列P(1),P(2)P(n)使其相应的关键字满足递增(或递减)关系：KP(1)KP(2)KP(n)或 KP(1)KP(2)KP(n)使上述文件成为一个按其关键字线性有序的文件RP(1)，RP(2)，RP(n)，这种运算就称为排序。将数据元素的无序序列调整为有序序列的过程。,2.排序算法的稳定性排序码（Key）作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。如果待排序的序列中，存在多个具有相同

18、排序码的数据元素，若经过排序这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，若经过排序，这些数据元素的相对次序发生了改变，则称这种排序算法是不稳定的。,3.内部排序与外部排序内部排序 指当文件的数据量不太大时，全部信息放内存中处理的排序方法。外部排序 当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排序的目的，这种排序称为外排序。,4.内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。使有序区中记录的数目增加一个或几个的操作称为一趟排序。内部排序的方法很多，每种方法都有各自

19、的优缺点，适合在不同的环境(如记录的初始排列状态等)下使用。,排序,简单排序方法，其时间复杂度为O(n2),先进排序方法，其时间复杂度为O(nlogn),基数排序，其时间复杂度为O(dn),按内部排序过程中所需的工作量来区分：,插入类（直插排序、二分排序、希尔排序）,交换类（冒泡排序、快速排序）,选择类（直选排序、树型排序、堆排序）,归并类（二路归并排序、多路归并排序）,分配类（多关键字排序、基数排序）,按排序过程中依据的原则分,排序,#define MAXSIZE 20/一个顺序表的最大长度typedef int KeyType;/定义关键字为整数类型Typedef struct KeyTy

20、pe key;/关键字项 InfoType otherinfo;/其他数据项RedType;/记录类型Typedef struct RedType rMAXSIZE+1;/r0用作哨兵单元 int length;/顺序表长度SqList;/顺序表类型,第10章 内部排序10.1 排序的基本概念10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序10.6 基数排序10.7 各种内部排序方法的比较,10.2 插入排序 直接插入排序 折半插入排序 2-路插入排序 表插入排序 希尔排序,1）一趟直接插入排序的基本思想 将记录L.ri插入到有序子序列L.r1.i-1中，使记录的有序序

21、列从L.r1.i-1变为L.r1.i。完成这个“插入”分三步进行：1查找L.ri在有序子序列L.r 1.i-1中的插入位置j；2将L.r j.i-1中的记录后移一个位置；3将L.r i复制到L.r j的位置上。整个排序过程进行n1趟插入，即：先将序列中的第1个记录着成一个有序的子序列，然后从第2个记录起逐个插入，直至整个序列变成接关键字非递减有序序列为止。,1.直接插入排序,待排元素序列：53 27 36 15 69 42第一次排序：(27)27 53 36 15 69 42第二次排序：(36)27 36 53 15 69 42第三次排序：(53)15 27 36 53 69 42第四次排序：

22、(69)15 27 36 53 69 42第五次排序:(42)15 27 36 42 53 69 直接插入排序示例（插入操作要进行n-1次）,2）直接插入排序算法描述 void InsertionSort(SqList/插入到正确位置/InsertSort,3）直接插入排序性能分析 实现排序的基本操作有：（1）“比较”关键字的大小（2）“移动”记录对于直接插入排序：最好情况“比较”次数：n-1；“移动”次数：2(n-1)最坏的情况“比较”和“移动”的次数均达到最大值，分别为：(n+2)(n-1)/2；(n+4)(n-1)/2 由于待排记录序列是随机的，取上述二值的平均值。所以直接插入排序的时间

23、复杂度为 O(n2)。直接插入排序是“稳定的”：关键码相同的两个记录，在整个排序过程中，不会通过比较而相互交换。,2.折半插入排序1）基本思想 考虑到 L.r1.i-1 是按关键字有序的有序序列，则可以利用折半查找实现“L.r1i-1中查找 L.ri 的插入位置”如此实现的插入排序为折半插入排序。,(highlow，查找结束，插入位置为low 或high+1),(4236),(4253),折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。,low high,mid,high low,void BinsertSort(SqList,2)

24、折半插入排序算法,3)折半插入排序性能分析,折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。,折半插入排序是“稳定的”,3.2-路插入排序,1）基本思想 2-路插入排序是在折半插入排序的基础上改进的，目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。,2）具体做法,另设一个和 L.r 同类型的数组d，首先将 L.r1 赋值给 d1，并将 d1 看成是在排好序的序列中处于中间位置的记录，然后从 L.r 中第 2 个记录起依次插入到d1 之前或之后的有序序列中。先将待插入记录的关键字和 d1 的关键字进行比较。若 L.rid1.key，则将

25、 L.ri 插入到 d1 之前的有序表中。反之，插入到 d1 之后的有序表中。,【初始关键字】49 38 65 97 76 13 27 49 排序过程中d 的状态如下：i=1:(49)i=2:(49)(38)i=3:(49 65）（38）i=4:(49 65 97）（38）i=5:(49 65 76 97）（38）i=6:(49 65 76 97）（13 38）i=7:(49 65 76 97）（13 27 38）i=8:(49 49 65 76 97）（13 27 38）,2路插入排序过程示例：,3）2-路插入排序性能分析,2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。2-路插入排序中，移动记录的次数约为n2/8。当L.r1是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去了它的优越性。,