数据结构第四讲ppt课件

1、本章出题特点本章出题特点 在历年统考里,大多以客观题的方式出现,详细如下:年份年份内容内容客观客观主观主观2009查找查找1（2分）分）排序排序2（4分）分）2010查找查找1（2分）分）1（10分）分）排序排序2（4分）分）2011查找查找1（2分）分）排序排序2（4分）分）2012查找查找1（2分）分）排序排序2（4分）分）一、查找一、查找查找的根本概念查找的根本概念顺序查找顺序查找折半查找折半查找B树查找树查找散列表散列表根本概念根本概念 在查找表上进展的根本操作有：查询，检索，插入和删除。假设只是前两种操作的查找表那么称为静态查找表，假设兼有后面两种，那么称为动态查找表。 查找的根本操

2、作是关键字间的比较，查找每一个元素所需比较次数的平均值称为平均查找长度，即通常用平均查找长度来衡量查找算法的好坏。通常用平均查找长度来衡量查找算法的好坏。 n1iiicpASL 例 如例 如 , , 在 关 键 字 序 列 为在 关 键 字 序 列 为3,9,1,5,8,10,6,7,2,43,9,1,5,8,10,6,7,2,4的线性表的线性表查找关键字为查找关键字为6 6的元素。的元素。 顺序查找过程如下：顺序查找过程如下：顺序查找顺序查找 开场开场: 3 9 1 5 8 10 6 7 2 4 第第1次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=0 第第2次比较次比较: 3

3、 9 1 5 8 10 6 7 2 4 i=1 第第3次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=2 第第4次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=3 第第5次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=4 第第6次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=5 第第7次比较次比较: 3 9 1 5 8 10 6 7 2 4 i=6 查找胜利查找胜利,前往序号前往序号6 从顺序查找过程可以看到从顺序查找过程可以看到(不思索越界比较不思索越界比较in),ci取决于取决于所查记录在表中的位置。如查找表中第所查记录在表中的位置。

4、如查找表中第1个记录个记录R0时时,仅需仅需比较一次；而查找表中最后一个记录比较一次；而查找表中最后一个记录Rn-1时时,需比较需比较n次次,即即ci=i。因此。因此,胜利时的顺序查找的平均查找长度为：胜利时的顺序查找的平均查找长度为： 21n2)1n(nn1in1icipsqASLn1in1i 查找胜利时的平均比较次数约为表长的一半查找胜利时的平均比较次数约为表长的一半 。思索题：不胜利时的平均查找长度是多少？思索题：不胜利时的平均查找长度是多少？二分查找二分查找 二分查找也称为折半查找，要求线性表中的二分查找也称为折半查找，要求线性表中的结点必需己按关键字值的递增或递减顺序陈列。结点必需己

5、按关键字值的递增或递减顺序陈列。思绪：首先用要查找的关键字思绪：首先用要查找的关键字k与中间位与中间位置的结点的关键字相比较置的结点的关键字相比较,这个中间结点把线性这个中间结点把线性表分成了两个子表表分成了两个子表,假设比较结果相等那么查找假设比较结果相等那么查找完成完成;假设不相等假设不相等,再根据再根据k与该中间结点关键字与该中间结点关键字的比较大小确定下一步查找哪个子表的比较大小确定下一步查找哪个子表,这样递归这样递归进展下去进展下去,直到找到满足条件的结点或者该线性直到找到满足条件的结点或者该线性表中没有这样的结点。表中没有这样的结点。 例 如例 如 , , 在 关 键 字 有 序

6、序 列在 关 键 字 有 序 序 列2,4,7,9,10,14,18,26,32,402,4,7,9,10,14,18,26,32,40中采用二中采用二分查找法查找关键字为分查找法查找关键字为7 7的元素。的元素。二分查找过程如下：二分查找过程如下： 开场开场: 2 4 7 9 10 14 18 26 32 40 low=0 high=9 mid=0+9/2=4 第第1次比较次比较: 2 4 7 9 10 14 18 26 32 40 low=0 high=3 mid=0+3/2=1 第第2次比较次比较: 2 4 7 9 10 14 18 26 32 40 l o w = 2 h i g h

7、= 3 mid=2+3/2=2第第3次比较次比较: 2 4 7 9 10 14 18 26 32 40 R2.key=7 查找胜利，前往序号查找胜利，前往序号2 二分查找过程可用二叉树来描画：二分查找过程可用二叉树来描画：把当前查找区间的中间位置上的记录作为根；把当前查找区间的中间位置上的记录作为根；左子表和右子表中的记录分别作为根的左子树和右子左子表和右子表中的记录分别作为根的左子树和右子树。树。称为描画二分查找的断定树或比较树。称为描画二分查找的断定树或比较树。 5 2 8 0 3 6 9 -1 1 23 4 56 7 89 10 01 12 34 45 67 78 910 10 = =

8、= = = = = = = = = R0.10的二分查线的断定树的二分查线的断定树(n=11) 因此，在等概率假设下，二分查找胜利时的平均查找长度为：因此，在等概率假设下，二分查找胜利时的平均查找长度为：1) 1(log1) 1(log12122111nnnninicipbnASLniini二分查找的适用场所：二分查找的适用场所：1、元素间必需有序；、元素间必需有序；2、存储构造该当是顺序存储，而不宜适用链式构造。、存储构造该当是顺序存储，而不宜适用链式构造。索引查找分块查找 例如,设有一个线性表,其中包含25个记录,其关键字序列为：8,14,6,9,10,22,34,18,19,31,40,

9、38,54,66, 46,71,78,68,80,85, 100, 4,88,96,87假设将25个记录分为5块,每块中有5个记录,该线性表的索引存储构造如以下图所示。 14 34 66 85 100 0 5 10 15 20 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 100 94 88 96 87 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 key link 假设以二分查找来确定块假设以二分查找来确定块,那么分块查找胜利那么分块查找胜利

10、时的平均查找长度为：时的平均查找长度为： 假设以顺序查找确定块假设以顺序查找确定块,那么分块查找胜利时那么分块查找胜利时的平均查找长度为：的平均查找长度为： 2s)1s/n(log21s1)1h(logASLASLASL22sqbnblk s2ns2s21s21bASLASLLAS2sqbnblk 当当s= 时，时，ASL blk取极小值取极小值 +1，即当采，即当采用顺序查找确定块时，应将各块中的记录数选定用顺序查找确定块时，应将各块中的记录数选定为为 。 nnnB-树树 B-树又称为多路平衡查找树树又称为多路平衡查找树,是一种组织和维护外是一种组织和维护外存文件系统非常有效的数据构造。存文

11、件系统非常有效的数据构造。 B-树中一切结点的孩子结点最大值称为树中一切结点的孩子结点最大值称为B-树的阶树的阶,通常用通常用m表示表示,从查找效率思索从查找效率思索,要求要求m3。一棵。一棵m阶阶B-树或者是一棵空树树或者是一棵空树,或者是满足以下要求的或者是满足以下要求的m叉树：叉树： (1) 树中每个结点至多有树中每个结点至多有m个孩子结点个孩子结点(即至多有即至多有m-1个关键字个关键字)； (2) 除根结点外除根结点外,其他结点至少有其他结点至少有m/2 个孩子结点个孩子结点(即至少有即至少有m/2 -1=(m-1)/2 个关键字个关键字)； (3) 假设根结点不是叶子结点假设根结点

12、不是叶子结点,那么根结点至少有两那么根结点至少有两个孩子结点；个孩子结点； (4) 每个结点的构造为：每个结点的构造为：np0k1p1k2p2knpn 其中其中,n为该结点中的关键字个数为该结点中的关键字个数,除根结点外除根结点外,其其他一切结点的他一切结点的n大于等于大于等于m/2 -1,且小于等于且小于等于m-1；ki(1in)为该结点的关键字且满足为该结点的关键字且满足kiki+1；pi(0in)为该结点的孩子结点指针且满足为该结点的孩子结点指针且满足pi(0in-1)结点上的关键字大于等于结点上的关键字大于等于ki且小于且小于ki+1,pn结点上结点上的关键字大于的关键字大于kn。 (

13、5) 一切叶子结点都在同一层上一切叶子结点都在同一层上,即即B-树是一切结树是一切结点的平衡因子均等于点的平衡因子均等于0的多路查找树。的多路查找树。 3 12 15 22 2 2 7 2 35 41 3 53 54 63 4 68 69 71 76 3 79 84 93 2 11 30 2 66 78 1 51 一棵一棵5阶阶B-树树B-树的查找树的查找 在在B-树中查找给定关键字的方法类似于二叉排序树上的树中查找给定关键字的方法类似于二叉排序树上的查找查找,不同的是在每个记录上确定向下查找的途径不一定是二不同的是在每个记录上确定向下查找的途径不一定是二路路(即二叉即二叉)的的,而是而是n+

14、1路的。由于记录内的关键字序列是有序路的。由于记录内的关键字序列是有序的数量的数量key1.n,故既可以用顺序查找故既可以用顺序查找,也可以用折半查找。在也可以用折半查找。在一棵一棵B-树上顺序查找关键字为树上顺序查找关键字为k的方法为：的方法为：将将k与根结点中的与根结点中的keyi进展比较：进展比较： (1) 假设假设k=keyi,那么查找胜利；那么查找胜利； (2) 假设假设kkey1,那么沿着指针那么沿着指针ptr0所指的子树继所指的子树继续查找；续查找； (3) 假设假设keyikkeyi+1,那么沿着指针那么沿着指针ptri所指所指的子树继续查找；的子树继续查找； (4) 假设假设

15、kkeyn,那么沿着指针那么沿着指针ptrn所指的子树继所指的子树继续查找。续查找。 2. B-树的插入树的插入将关键字将关键字k插入到插入到B-树的过程分两步完成：树的过程分两步完成： (1) 利用前述的利用前述的B-树的查找算法找出该关键字的插入结点树的查找算法找出该关键字的插入结点(留意留意B-树的插入结点一定是叶子结点树的插入结点一定是叶子结点)。 (2) 判别该结点能否还有空位置判别该结点能否还有空位置,即判别该结点能否满足即判别该结点能否满足nm-1,假设该结点满足假设该结点满足nm-1,阐明该结点还有空位置阐明该结点还有空位置,直接把关键字直接把关键字k插入到该结点的适宜位置上插

16、入到该结点的适宜位置上(即满足插入后结点上的关键字仍坚即满足插入后结点上的关键字仍坚持有序持有序)； 假设该结点有假设该结点有n=m-1,阐明该结点已没有空位置阐明该结点已没有空位置,需求把结需求把结点分裂成两个。点分裂成两个。 分裂的做法是分裂的做法是,取一新结点取一新结点,把原结点上的关键字和把原结点上的关键字和k按升按升序排序后序排序后,从中间位置从中间位置(即即m/2=(m+1)/2之处之处)把关键把关键字字(不包括中间位置的关键字不包括中间位置的关键字)分成两部分分成两部分,左部分所含关键字左部分所含关键字放在旧结点中放在旧结点中,右部分所含关键字放在新结点中右部分所含关键字放在新结

17、点中,中间位置的中间位置的关键字连同新结点的存储位置插入到父亲结点中。假设父结关键字连同新结点的存储位置插入到父亲结点中。假设父结点的关键字个数也超越点的关键字个数也超越Max,那么要再分裂那么要再分裂,再往上插再往上插,直至这直至这个过程传到根结点为止。个过程传到根结点为止。例如例如 关键字序列为：关键字序列为：1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15。创建一棵创建一棵5阶阶B-树。树。建立建立B-的过程如以下图所示。的过程如以下图所示。 1 2 6 7插入插入1161 2 6 7 11 插入插入41 2 4插入插入8,137 8

18、11 13插入插入107 8 11 1311 137 8 6 10插入插入51 2 4 5插入插入1711 13 17 6 10 167 8 9 插入插入9插入插入1611 13 16 1711 1317 20插入插入33 6 10 161 24 5插入插入12,14,18,1911 12 13 1417 18 19 20插入插入1514 1511 12 1313 163 6 10插入插入20163101,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15 1 2 6 7 6 1 2 7 11 6 1 2 4 7 8 11 13 6 10 1 2

19、4 11 13 7 8 6 10 1 2 4 5 11 13 16 17 7 8 9 6 10 16 1 2 4 5 7 8 9 3 6 10 16 1 2 7 8 9 17 18 19 20 4 5 10 14 15 13 16 3 6 1 2 7 8 9 (a)插入插入 1,2,6,7 (b)插入插入 11 (c)插入插入 4,8,13 (d)插入插入 10 (e)插入插入 5,17,9,16 (f)插入插入 20 (g)插入插入 3,12,14,18,19 (h)插入插入 15 11 13 17 20 17 18 19 20 11 12 13 14 4 5 11 12 3. B-树的删除

20、树的删除 B-树的删除过程与插入过程类似树的删除过程与插入过程类似,只是稍为复杂一些。要使删只是稍为复杂一些。要使删除后的结点中的关键字个数除后的结点中的关键字个数m/2 -1,将涉及到结点的将涉及到结点的“合并合并问题。在问题。在B-树上删除关键字树上删除关键字k的过程分两步完成：的过程分两步完成： (1) 利用前述的利用前述的B-树的查找算法找出该关键字所在的结点。树的查找算法找出该关键字所在的结点。 (2) 在结点上删除关键字在结点上删除关键字k分两种情况：一种是在叶子结点上分两种情况：一种是在叶子结点上删除关键字；另一种是在非叶子结点上删除关键字。删除关键字；另一种是在非叶子结点上删除

21、关键字。 (3) 在非叶子结点上删除关键字的过程：在非叶子结点上删除关键字的过程：假设要删除关键字假设要删除关键字keyi(1in),在删去该关键字后在删去该关键字后,以该结以该结点点ptri所指子树中的最小关键字所指子树中的最小关键字keymin来替代被删关键字来替代被删关键字keyi所在的位置所在的位置(留意留意ptri所指子树中的最小关键字所指子树中的最小关键字keymin一定是在叶子结点上一定是在叶子结点上)。然后再以指针然后再以指针ptri所指结点为根结点查找并删除所指结点为根结点查找并删除keymin(即再以即再以ptri所指结点为所指结点为B-树的根结点树的根结点,以以keymi

22、n为为要删除的关键字要删除的关键字,然后再次调用然后再次调用B-树上的删除算法树上的删除算法)。这样也就把在非叶子结点上删除关键字这样也就把在非叶子结点上删除关键字k的问题转化成了的问题转化成了在叶子结点上删除关键字在叶子结点上删除关键字keymin的问题。的问题。 (4) 在在B-树的叶子结点上删除关键字共有以下三种情况：树的叶子结点上删除关键字共有以下三种情况： 假设被删结点的关键字个数大于假设被删结点的关键字个数大于Min,阐明删去该关键字后阐明删去该关键字后该结点仍满足该结点仍满足B-树的定义树的定义,那么可直接删去该关键字。那么可直接删去该关键字。 假设被删结点的关键字个数等于假设被

23、删结点的关键字个数等于Min,阐明删去关键字后该阐明删去关键字后该结点将不满足结点将不满足B-树的定义。树的定义。此时假设该结点的左此时假设该结点的左(或右或右)兄弟结点中关键字个数大于兄弟结点中关键字个数大于Min,那么把该结点的左那么把该结点的左(或右或右)兄弟结点中最大兄弟结点中最大(或最小或最小)的关键字上移的关键字上移到双亲结点中到双亲结点中,同时把双亲结点中大于同时把双亲结点中大于(或小于或小于)上移关键字的关键上移关键字的关键字下移到要删除关键字的结点中字下移到要删除关键字的结点中,这样删去关键字这样删去关键字k后该结点以及后该结点以及它的左它的左(或右或右)兄弟结点都仍旧满足兄

24、弟结点都仍旧满足B-树的定义。树的定义。 假设被删结点的关键字个数等于假设被删结点的关键字个数等于Min,并且该结点的左并且该结点的左和右兄弟结点和右兄弟结点(假设存在的话假设存在的话)中关键字个数均等于中关键字个数均等于Min。这时这时,需把要删除关键字的结点与其左需把要删除关键字的结点与其左(或右或右)兄弟结点以兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。假设因此及双亲结点中分割二者的关键字合并成一个结点。假设因此使双亲结点中关键字个数小于使双亲结点中关键字个数小于Min,那么对此双亲结点做同样那么对此双亲结点做同样处置处置,以致于能够直到对根结点做这样的处置而使整个树减以致于能

25、够直到对根结点做这样的处置而使整个树减少一层。少一层。 1014 1513 163 6 1 2 7 8 917 18 19 20 4 511 12 7 9删删8删删161713 13 17 18 19 20删删1514 171814 17 19 20删删4 5 1 2 3 56 6 10 13 18 13 18 对于前例生成的对于前例生成的B-树，给出删除树，给出删除8，16，15，4等四个关键字的等四个关键字的过程。过程。 例如例如,对于上例生成的对于上例生成的B-树树,给出删除给出删除8,16,15,4等四个关等四个关键字的过程。键字的过程。 10 3 6 13 17 1 2 4 5 7

26、9 11 12 14 15 18 19 20 (a) 初始初始 5 阶阶 B- -树树 (b) 删除删除 8,16 后的结果后的结果 10 3 6 13 18 1 2 4 5 11 12 14 17 19 20 (c) 删除删除 15 后的结果后的结果 6 10 13 18 1 2 3 5 7 9 14 17 19 20 (d) 删除删除 4 后的结果后的结果 7 9 11 12 10 14 15 13 16 3 6 1 2 7 8 9 17 18 19 20 4 5 11 12 9.3.4 B+树树 在索引文件组织中在索引文件组织中,经常运用经常运用B-树的一些变形树的一些变形,其中其中B+

27、树是一种运用广泛的变形。一棵树是一种运用广泛的变形。一棵m阶阶B+树满足以下树满足以下条件：条件： (1) 每个分支结点至多有每个分支结点至多有m棵子树。棵子树。 ( 2 ) 除 根 结 点 外除 根 结 点 外 , 其 他 每 个 分 支 结 点 至 少 有其 他 每 个 分 支 结 点 至 少 有(m+1)/2棵子树。棵子树。 (3) 根结点至少有两棵子树根结点至少有两棵子树,至多有至多有m棵子树。棵子树。 (4) 有有n棵子树的结点有棵子树的结点有n个关键字。个关键字。 (5) 一切叶子结点包含全部一切叶子结点包含全部(数据文件中记录数据文件中记录) 关键字及关键字及指向相应记录的指针指

28、向相应记录的指针(或存放数据文件分块后每块的最大关或存放数据文件分块后每块的最大关键字及指向该块的指针键字及指向该块的指针),而且叶子结点按关键字大小顺序链而且叶子结点按关键字大小顺序链接接(可以把每个叶子结点看成是一个根本索引块可以把每个叶子结点看成是一个根本索引块,它的指针不它的指针不再指向另一级索引块再指向另一级索引块,而是直接指向数据文件中的记录而是直接指向数据文件中的记录)。 (6) 一切分支结点一切分支结点(可看成是索引的索引可看成是索引的索引)中仅包含它的各中仅包含它的各个子结点个子结点(即下级索引的索引块即下级索引的索引块)中最大关键字及指向子结点中最大关键字及指向子结点的指针

29、。的指针。 31 52 15 22 31 48 52 10 12 15 18 19 20 22 23 30 31 33 45 47 48 50 52 一棵一棵4阶的阶的B+树树 m阶的阶的B+树和树和m阶的阶的B-树树,定义中的前三点是一样的定义中的前三点是一样的,主要的差别是：主要的差别是： (1) 在在B+树中树中,具有具有n个关键字的结点含有个关键字的结点含有n棵子树棵子树,即即每个关键字对应一棵子树每个关键字对应一棵子树,而在而在B-树中树中,具有具有n个关键字个关键字的结点含有的结点含有(n+1)棵子树。棵子树。 (2) 在在B+树中树中,每个结点每个结点(除根结点外除根结点外)中的

30、关键字个数中的关键字个数n的取值范围是的取值范围是m/2 n m,根结点根结点n的取值范围是的取值范围是1nm；而在；而在B-树中树中,它们的取值范围分别是它们的取值范围分别是m/2 -1n m-1和和1nm-1。 (3) B+树中的一切叶子结点包含了全部关键字树中的一切叶子结点包含了全部关键字,即其即其他非叶子结点中的关键字包含在叶子结点中他非叶子结点中的关键字包含在叶子结点中,而在而在B-树树中中,叶子结点包含的关键字与其他结点包含的关键字是叶子结点包含的关键字与其他结点包含的关键字是不反复的。不反复的。 (4) B+树中一切非叶子结点仅起到索引的作用树中一切非叶子结点仅起到索引的作用,即

31、结点中的即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。而在不含有该关键字对应记录的存储地址。而在B-树中树中,每个关键每个关键字对应一个记录的存储地址。字对应一个记录的存储地址。 (5) 通常在通常在B+树上有两个头指针树上有两个头指针,一个指向根结点一个指向根结点,另一个指另一个指向关键字最小的叶子结点向关键字最小的叶子结点,一切叶子结点链接成一个不定长的一切叶子结点链接成一个不定长的线性链表。线性链表。哈希表查找哈希表查找哈希表的根本概念哈希表的根本概念 哈希表哈希表(Hash Ta

32、ble)又称散列表又称散列表,是除顺序表是除顺序表存储构造、链接表存储构造和索引表存储构造之存储构造、链接表存储构造和索引表存储构造之外的又一种存储线性表的存储构造。外的又一种存储线性表的存储构造。哈希表存储的根本思绪是：设要存储的对象哈希表存储的根本思绪是：设要存储的对象个数为个数为n,设置一个长度为设置一个长度为m(mn)的延续内存单的延续内存单元元,以线性表中每个对象的关键字以线性表中每个对象的关键字ki(0in-1)为自为自变量变量,经过一个称为哈希函数的函数经过一个称为哈希函数的函数h(ki),把把ki映映射为内存单元的地址射为内存单元的地址(或称下标或称下标)h(ki),并把该对象

33、并把该对象存储在这个内存单元中。存储在这个内存单元中。h(ki)也称为哈希地址也称为哈希地址(又称散列地址又称散列地址)。把如此构造的线性表存储构造。把如此构造的线性表存储构造称为哈希表。称为哈希表。 但是存在这样的问题但是存在这样的问题,对于两个关键字对于两个关键字ki和和kj(ij),有有kikj(ij),但但h(ki)=h(kj)。把这种景象叫做哈希冲突。把这种景象叫做哈希冲突。 通常把这种具有不同关键字而具有一样哈希地址的对象通常把这种具有不同关键字而具有一样哈希地址的对象称做称做“同义词同义词,由同义词引起的冲突称作同义词冲突。由同义词引起的冲突称作同义词冲突。在哈希表存储构造的存储

34、中在哈希表存储构造的存储中,同义词冲突是很难防止的同义词冲突是很难防止的,除非关键字的变化区间小于等于哈希地址的变化区间除非关键字的变化区间小于等于哈希地址的变化区间,而这种而这种情况当关键字取值不延续时是非常浪费存储空间的。通常的情况当关键字取值不延续时是非常浪费存储空间的。通常的实践情况是关键字的取值区间远大于哈希地址的变化区间。实践情况是关键字的取值区间远大于哈希地址的变化区间。归纳起来：归纳起来： (1)哈希函数是一个映象哈希函数是一个映象,即：将关键字的集合映射到某即：将关键字的集合映射到某个地址集合上个地址集合上,它的设置很灵敏它的设置很灵敏,只需这个地址集合的大小不只需这个地址集

35、合的大小不超出允许范围即可；超出允许范围即可； (2)由于哈希函数是一个紧缩映象由于哈希函数是一个紧缩映象,因此因此,在普通情况下在普通情况下,很很容易产生容易产生“冲突景象冲突景象,即：即：key1key2,而而 f(key1) = f(key2)。 (3) 很难找到一个不产生冲突的哈希函数。普通情况下很难找到一个不产生冲突的哈希函数。普通情况下,只能选择恰当的哈希函数只能选择恰当的哈希函数,使冲突尽能够少地产生。使冲突尽能够少地产生。哈希函数构造方法哈希函数构造方法 构造哈希函数的目的是使得到的哈希地址尽能够构造哈希函数的目的是使得到的哈希地址尽能够均匀地分布在均匀地分布在n个延续内存单元

36、地址上个延续内存单元地址上,同时使计算过同时使计算过程尽能够简单以到达尽能够高的时间效率。程尽能够简单以到达尽能够高的时间效率。 1. 直接定址法直接定址法 直接定址法是以关键字直接定址法是以关键字k本身或关键字加上某个本身或关键字加上某个数值常量数值常量c作为哈希地址的方法。直接定址法的哈希作为哈希地址的方法。直接定址法的哈希函数函数h(k)为：为： h(k)=k+c 这种哈希函数计算简单这种哈希函数计算简单,并且不能够有冲突发生。并且不能够有冲突发生。当关键字的分布根本延续时当关键字的分布根本延续时,可用直接定址法的哈希可用直接定址法的哈希函数；否那么函数；否那么,假设关键字分布不延续将呵

37、斥内存单假设关键字分布不延续将呵斥内存单元的大量浪费。元的大量浪费。 2. 除留余数法除留余数法 除留余数法是用关键字除留余数法是用关键字k除以某个不大于哈希表长度除以某个不大于哈希表长度m的的数数p所得的余数作为哈希地址的方法。除留余数法的哈希函数所得的余数作为哈希地址的方法。除留余数法的哈希函数h(k)为：为： h(k)=k mod p (mod为求余运算为求余运算,pm) p最好取小于最好取小于m的质数的质数(素数素数)。 例例 假设哈希表长度假设哈希表长度m=13,采用除留余数法哈希函数建立采用除留余数法哈希函数建立如下关键字集合的哈希表：如下关键字集合的哈希表：16,74,60,43

38、,54,90,46,31,29,88,77。 解：解：n=11,m=13,除留余数法的哈希函数为除留余数法的哈希函数为h(k)=k mod p,p应为小于等于应为小于等于m的素数的素数,假设假设p取值取值13。那么有：。那么有： h(16)=3,h(74)=9,h(60)=8,h(43)=4, h(54)=2,h(90)=12,h(46)=7,h(31)=5, h(29)=3, h(88)=10,h(77)=12。 留意：存在冲突。留意：存在冲突。 3. 数字分析法数字分析法 该方法是提取关键字中取值较均匀的数字位作为哈希地址该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法。它适宜于一

39、切关键字值都知的情况的方法。它适宜于一切关键字值都知的情况,并需求对关键字并需求对关键字中每一位的取值分布情况进展分析。中每一位的取值分布情况进展分析。 例如例如,对于一组关键字：对于一组关键字： 92317602,92326875,92739628,92343634,92706816, 92774638,92381262,92394220 经过分析可知经过分析可知,每个关键字从左到右的第每个关键字从左到右的第1、2、3位和第位和第6位位取值较集中取值较集中,不宜作为哈希函数不宜作为哈希函数,剩余的第剩余的第4、5、7和和8位取值较位取值较分散分散,可根据实践需求取其中的假设干位作为哈希地址。

40、假设可根据实践需求取其中的假设干位作为哈希地址。假设取 最 后 两 位 作 为 哈 希 地 址取 最 后 两 位 作 为 哈 希 地 址 , 那 么 哈 希 地 址 的 集 合 为那 么 哈 希 地 址 的 集 合 为2,75,28,34,16,38,62,20。 表中填入的记录数表中填入的记录数哈希表长度哈希表长度 = 既然存在既然存在“冲突问题，我们就要想方法处理冲突。普通来冲突问题，我们就要想方法处理冲突。普通来说，处理冲突的方法有开放定址法和拉链法。根本思想就是另说，处理冲突的方法有开放定址法和拉链法。根本思想就是另外建立一个哈希冲突函数，经过该函数对有冲突的值重新产生外建立一个哈希冲

41、突函数，经过该函数对有冲突的值重新产生一个地址。一个地址。 冲突是很难防止的，但是发生冲突的能够性却是有大有小冲突是很难防止的，但是发生冲突的能够性却是有大有小的。主要有下面三个要素：的。主要有下面三个要素： 1.与装填因子有关与装填因子有关 装填因子越小，冲突装填因子越小，冲突 的能够性就越小。的能够性就越小。 2.与所采用的哈希函数有关与所采用的哈希函数有关 3.与处理冲突的哈希函数有关与处理冲突的哈希函数有关 哈希冲突处理方法哈希冲突处理方法 1. 开放定址法开放定址法 开放定址法是一类以发生冲突的哈希地址为自变量开放定址法是一类以发生冲突的哈希地址为自变量,经经过某种哈希冲突函数得到一

42、个新的空闲的哈希地址的方法。过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。 (1)线性探查测法。线性探查法是从发生冲突的地线性探查测法。线性探查法是从发生冲突的地址址(设为设为d)开场开场,依次探查依次探查d的下一个地址的下一个地址(当到达下标为当到达下标为m-1的哈希表表尾时的哈希表表尾时,下一个探查的地址是表首地址下一个探查的地址是表首地址0),直到找直到找到一个空闲单元为止到一个空闲单元为止(当当mn时一定能找到一个空闲单元时一定能找到一个空闲单元)。线性探查法的数学递推描画公式为：线性探查法的数学递推描画公式为： d0=h(k) di=(di-1+1) mod m (1im-1)

43、 例例 对上面构造的哈希表采用线性探查法处理冲突。对上面构造的哈希表采用线性探查法处理冲突。 解：解：h(16)=3,h(74)=9,h(60)=8,h(43)=4, h(54)=2,h(90)=12,h(46)=7,h(31)=5, h(29)=3 冲突冲突 d0=3,d1=(3+1) mod 13=4 仍冲突仍冲突 d2=(4+1) mod 13=5 仍冲突仍冲突 d3=(5+1) mod 13=6 h(88)=10 h(77)=12 冲突冲突 d0=12,d1=(12+1) mod 13=0 建立的哈希表建立的哈希表ha0.12如下表所示。如下表所示。下标下标01234567891011

44、12k7754164331294660748890探查次探查次数数21111411111哈希表哈希表ha0.12 (2)平方探查法二次探测法。设发生冲突的地址为平方探查法二次探测法。设发生冲突的地址为d,那么平方探查法的探查序列为：那么平方探查法的探查序列为：d+12,d+22,。平方探查法。平方探查法的数学描画公式为：的数学描画公式为： d0=h(k) di=(d0+i2) mod m (1im-1) 平方探查法是一种较好的处置冲突的方法平方探查法是一种较好的处置冲突的方法,可以防止出现可以防止出现堆积问题。它的缺陷是不能探查到哈希表上的一切单元堆积问题。它的缺陷是不能探查到哈希表上的一切单

45、元,但但至少能探查到一半单元。至少能探查到一半单元。2. 拉链法拉链法 拉链法是把一切的同义词用单链表链接起来的方法。拉链法是把一切的同义词用单链表链接起来的方法。在这种方法中在这种方法中,哈希表每个单元中存放的不再是记录本身哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针。由于单链表中可插入恣意而是相应同义词单链表的头指针。由于单链表中可插入恣意多个结点多个结点,所以此时装填因子所以此时装填因子根据同义词的多少既可以设定根据同义词的多少既可以设定为大于为大于1,也可以设定为小于或等于也可以设定为小于或等于1,通常取通常取=1。 例例9.6 对上例构造的哈希表采用拉链法处理冲

46、突。对上例构造的哈希表采用拉链法处理冲突。 解：采用拉链法处理冲突建立的链表如以下图所示。解：采用拉链法处理冲突建立的链表如以下图所示。 0 1 2 3 4 5 6 7 8 9 10 11 12 54 74 88 46 60 31 43 29 16 77 90 下标下标 哈希表哈希表 9.4.4 哈希表上的查找哈希表上的查找 哈希表的主要目的是哈希表的主要目的是用于快速查找，且插入和删用于快速查找，且插入和删除操作都要用到查找。由于除操作都要用到查找。由于散列表的特殊组织方式，其散列表的特殊组织方式，其查找有特殊的方法。查找有特殊的方法。 设地址空间为设地址空间为HT0m-1，散列函数为，散列

47、函数为H(key)，处理冲突的方法为，处理冲突的方法为R(x, i) ，那么在散列表上查，那么在散列表上查找定值为找定值为K的记录的过程如的记录的过程如图右图所示。图右图所示。给定给定k值值计算计算H(k)此地址为空此地址为空?关键字关键字=k?查找失败查找失败查找胜利查找胜利按处置冲突按处置冲突方法计算方法计算HiNYYN 哈希表的查找过程哈希表的查找过程二、排序二、排序根本概念根本概念插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序基数排序基数排序根本概念根本概念 留意：排序的对象是序列，而排序的根据留意：排序的对象是序列，而排序的根据是关键字。只是我们为了方便，对序列中是

48、关键字。只是我们为了方便，对序列中的每个元素只需关键字。的每个元素只需关键字。 假设序列中有一样的关键字，排序后假设序列中有一样的关键字，排序后其相对位置没有改动，那么该排序算法是其相对位置没有改动，那么该排序算法是稳定的，否那么是不稳定的。稳定的，否那么是不稳定的。插入排序插入排序 思想是在一个曾经有序的序列中插入思想是在一个曾经有序的序列中插入元素，并保证插入后的有序性。元素，并保证插入后的有序性。直接插入排序稳定直接插入排序稳定折半插入排序稳定折半插入排序稳定 折半插入排序在查找时节约了时间，折半插入排序在查找时节约了时间，但是挪动的次序不变，所以时间复杂度依但是挪动的次序不变，所以时间

49、复杂度依然不变。然不变。例题：设待排序的表有例题：设待排序的表有10个记录个记录,其关键字分别为其关键字分别为3，10，7，8，20，5，8，2，1，6。给出采用希尔排序方。给出采用希尔排序方法进展排序的过程初始增量为法进展排序的过程初始增量为5。初始形状：初始形状：3，10，7，8，20，5，8，2，1，6di=5的执行结果：的执行结果：3，8，2，1，6，5，10，7，8，20di=2的执行结果：的执行结果：2，1，3，5，6，7，8，8，10，20di=1的执行结果：的执行结果：1，2，3，5，6，7，8，8，10，20此处的关键字此处的关键字8 8是初始记录是初始记录R3R3的还是初始

50、记录的还是初始记录R6R6的呢？的呢？由此可知，希尔排序是稳定的还是不稳定的呢？由此可知，希尔排序是稳定的还是不稳定的呢？不稳定的不稳定的插入排序之希尔排序交换排序交换排序冒泡排序冒泡排序 一趟下来一个元素找到本人的正确一趟下来一个元素找到本人的正确位置位置快速排序快速排序 例例10.3 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为9,8,7,6,5,4,3,2,1,0。阐明采用冒泡排序方法进展排序的过程。阐明采用冒泡排序方法进展排序的过程。 初初始始关关键键字字 9 8 7 6 5 4 3 2 1 0 i=0 0 9 8 7 6 5 4 3 2 1 i=1 0

51、1 9 8 7 6 5 4 3 2 i=2 0 1 2 9 8 7 6 5 4 3 i=3 0 1 2 3 9 8 7 6 5 4 i=4 0 1 2 3 4 9 8 7 6 5 i=5 0 1 2 3 4 5 9 8 7 6 i=6 0 1 2 3 4 5 6 9 8 7 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9 快速排序快速排序 快速排序是由冒泡排序改良而得的。快速排序是由冒泡排序改良而得的。 根本思想是：在待排序的根本思想是：在待排序的n个记录中任取一个记录个记录中任取一个记录(通常取第一个记录通常取第一个记录),把该记录放入适当位置

52、后把该记录放入适当位置后,数据数据序列被此记录划分成两部分。一切关键字比该记录关序列被此记录划分成两部分。一切关键字比该记录关键字小的记录放置在前一部分键字小的记录放置在前一部分,一切比它大的记录放一切比它大的记录放置在后一部分置在后一部分,并把该记录排在这两部分的中间并把该记录排在这两部分的中间(称为称为该记录归位该记录归位),这个过程称作一趟快速排序。这个过程称作一趟快速排序。 首先对无序的记录序列进展“一次划分，之后分别对分割所得两个子序列“递归进展快速排序。无 序 的 记 录 序 列无序记录子序列(1)无序记录子序列(2)枢轴枢轴一次划分分别进展快速排序52 49 80 36 14 5

53、8 61 97 23 75stlowhigh设设 Rs=52 为枢轴为枢轴 将 Rhigh.key 和 枢轴的关键字进展比较，要求Rhigh.key 枢轴的关键字 将 Rlow.key 和 枢轴的关键字进展比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow 可见，经过“一次划分 ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针： low 和high

54、，它们的初值分别为： s 和 t。 之后逐渐减小 high，添加 low，并保证 Rhigh.key52，和 Rlow.key52,否那么进展记录的“交换。 以后对一切的两部分分别反复上述过程以后对一切的两部分分别反复上述过程, ,直至直至每部分内只需一个记录为止。每部分内只需一个记录为止。简而言之简而言之, ,每趟使表的第一个元素放入适当位每趟使表的第一个元素放入适当位置置, ,将表一分为二将表一分为二, ,对子表按递归方式继续这种划分对子表按递归方式继续这种划分, ,直至划分的子表长为直至划分的子表长为1 1。 例例10.4 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关

55、键字分别为6,8,7,9,0,1,3,2,4,5。阐明采用快速排序方法进展排序的过程。阐明采用快速排序方法进展排序的过程。 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 (a) 第 1 次划分 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 (b) 第 2 次划分 1 4 2 3 0 5 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3

56、4 2 3 4 (c) 第 3 次划分 (d) 第 4 次划分 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (e) 第 5 次划分 3 4 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (f) 第 6 次划分 3 4 8 7 9 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (g) 第 7 次划分 3 4 8 7 9 7 8

57、选择排序选择排序直接选择排序直接选择排序堆排序堆排序假设排序过程中，待排记录序列的形状为：假设排序过程中，待排记录序列的形状为：有序序列R0.i-1无序序列 Ri.n 第 i 趟简单项选择择排序从中选出关键字最小的记录有序序列R0.i无序序列 Ri+1.n 例例10.5 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为6,8,7,9,0,1,3,2,4,5。阐明采用直接选择排序方法进展。阐明采用直接选择排序方法进展排序的过程。排序的过程。 初始关键字初始关键字 6 8 7 9 0 1 3 2 4 5 i=0 0 8 7 9 6 1 3 2 4 5 i=1 0 1 7

58、9 6 8 3 2 4 5 i=2 0 1 2 9 6 8 3 7 4 5 i=3 0 1 2 3 6 8 9 7 4 5 i=4 0 1 2 3 4 8 9 7 6 5 i=5 0 1 2 3 4 5 9 7 6 8 i=6 0 1 2 3 4 5 6 7 9 8 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9 10.4.2 堆排序堆排序 堆排序是一树形选择排序堆排序是一树形选择排序,它的特点是它的特点是,在排序过程在排序过程中中,将将R1.n看成是一棵完全二叉树的顺序存储构造看成是一棵完全二叉树的顺序存储构造,利利用完全二叉树中双亲结点和孩子

59、结点之间的内在关系用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大在当前无序区中选择关键字最大(或最小或最小)的记录。的记录。 堆的定义是：堆的定义是：n个关键字序列个关键字序列K1,K2,Kn称为堆称为堆,当且仅当该序列满足如下性质当且仅当该序列满足如下性质(简称为堆性质简称为堆性质)： (1)KiK2i 且且 KiK2i+1 或或 (2)KiK2i 且且 KiK2i+1(1in/2 ) 满足第满足第(1)种情况的堆称为小根堆种情况的堆称为小根堆,满足第满足第(2)种情况种情况的堆称为大根堆。下面讨论的堆是大根堆。的堆称为大根堆。下面讨论的堆是大根堆。12, 36

60、, 27, 65, 40, 34, 98, 81, 73, 55, 49例如例如:12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49R1234567891011是小根堆不是堆KEY:KEY:27,14,rir2i r2i+1 假设将该数列视作完全二叉树，那么假设将该数列视作完全二叉树，那么 r2i 是是 ri 的左孩子；的左孩子； r2i+1 是是 ri 的右孩子。的右孩子。1236276549817355403498例如例如:是堆是堆14不不堆排序思想堆排序思想 对一组待排序的记录，按堆的定义建初始堆；对一组待排序的记录，按堆的定义建初始堆； 将堆顶记录和最