数据结构第讲哈希表和插入排序

《数据结构第讲哈希表和插入排序》由会员分享，可在线阅读，更多相关《数据结构第讲哈希表和插入排序（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 的 散列表（哈希表）为：序号12345678910 H(K)15913162127 2112.冲突两个不同的关键字具有相同的存储位置。序号12345678910H(K)15913162127 2113.

2、哈希表根据设定的哈希函数 H(key) 和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为哈希表，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。在哈希存储中，若发生冲突，则必须采取特殊的方法 来解决冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。(1)装填因子；装填因子是指哈希表中己存入的元素个数 n 与哈希 表的大小 m 的比值，即=n/m（ 724+518+69 =13116. 随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，

3、即H(key)=random (key)，其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。 实际工作中需视不同情况采用不同的哈希函数。通常考虑的因素：(1)计算哈希函数所需时间(包括硬件指令的因素)；(2)关键字的长度；(3)哈希表的大小；(4)关键字的分布情况；(5)记录的查找频率。第9章 查找9.1 静态查找表9.2 动态查找表9.3 哈希表9.3.1 什么是哈希表9.3.2 哈希函数的构造方法9.3.3 处理冲突的方法9.3.4 哈希表的查找及其分析9.3.3 处理冲突的方法1.开放地址法开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，

4、即转而寻找其它尚开放的地址。（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；哈希函数为Hash(key)=key mod 11；拟用线性探测法线性探测法处理冲突。建哈希表：0 1 2 3 4 5 6 7 8 9 10477291116922283线性探测法的优点：只要哈希表未被填满，保证 能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使

5、第i 个哈希地址的同 义词存入第i+1 个哈希地址，这样本应存入 第i+1个哈希地址的元素变成了第i+2个哈希 地址的同义词，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。可采用二次探测法二次探测法或或伪随机探测法伪随机探测法，以改善“ 堆积”问题。 1.开放地址法（2）二次探测法二次探测法对应的探查地址序列的计算公式为 ：Hi = ( H(k)+di ) mod m其中di =12,-12,22,-22,j2,-j2 (jm/2)。0 1 2 3 4 5 6 7 8 9 1011 22347 92167298若di伪随机序列，就称为伪随机探测法例 关键码集为 47

6、，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个单链表的表头指针存储起来，形成一个动态的结构。例：设 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函数为：Hash(key)

7、=key mod 11，用拉链法处理冲突，建表。 0123456789 1022118934737922971650810 有冲突的元素可以插在 表尾,也可以插在表头。3.再哈希法Hi= RHi(key) RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产生“聚集”，但是增加了计算时间。 4.建立一个公共溢出区第9章 查找9.1 静态查找表9.2 动态查找表9.3 哈希表9.3.1 什么是哈希表9.3.2 哈希函数的构造方法9.3.3 处理冲突的方法9.3.4 哈希表的查找及其分析9.3.4 哈希表的查找及其分析散列表的目的主要是用于快速查找。

8、在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。例：设有一组关键字 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=6H(01)=01 mod 13=1H(23)=23 mod 13=10H(14)=

9、14 mod 13=1 (冲突)H(14)=(1+1) mod 19=2H(55)=55 mod 13=3H(20)=20 mod 13=7H(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=40123456789 10 11 12 13 14 15 16 17 181919,01,23,14,55,20,84,27,68,11,10

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

11、SL=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二分查找的判定树（中序序列为从小到大排列的 有序序列） 由图

12、可得：二分查找的成功平均查找长度为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.7511 101 3 2 478213 1 11 2 10 4 78 21 (a)二叉排序树(b)平衡二叉树线性探查法解决冲突的哈希表如图所示。 由图可得：线性探查法

13、的成功平均查找长度为ASL=（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 归并排序1

14、0.6 基数排序10.7 各种内部排序方法的比较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）作为排序依据的记录中的一个属性。它可以是 任何一种可比的有序数据类型，它可以是记录的关 键字，也可以是任何非关键字。如果待排序

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

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