算法与数据结构检索及基本算法课件

《算法与数据结构检索及基本算法课件》由会员分享，可在线阅读，更多相关《算法与数据结构检索及基本算法课件（160页珍藏版）》请在金锄头文库上搜索。

1、算法与数据结构第7章 检索及基本算法算法与数据结构 检索及基本算法第7章 检索及基本算法 7.1 检索的概念7.2 线性表的检索7.3 树表的检索7.4 哈希检索算法与数据结构 检索及基本算法检索的概念 n检索（searching）也称作查找，是一种常用的基本运算。n人们几乎每天都要做检索的工作，如在电话号码薄中查找某单位或某个人的电话号码，在字典中查找某个词的含义或读法，在图书馆查找某本书刊的编号，上网在各种数据库中查找某些需要的文献资料等等。n在语言翻译的编译程序中要对符号表查找，在数据库系统中要用SQL语言为各种应用设计查找程序，如此等等。 算法与数据结构 检索及基本算法检索的概念(续)

2、 n简言之，检索就是在“大量信息”中查找一个“特定的”信息。n这里的大量信息是检索所依赖的数据结构，称之为检索表（search table）；n检索表是由同一类型的数据元素（或记录）组成的集合。n由于集合是一种松散型数据结构，数据元素除了同属于一个集合外再无别的关系，所以检索表是一种非常灵活的数据结构。 算法与数据结构 检索及基本算法检索的概念(续) n对检索表常做的运算和操作有：n 查找某个特定的数据元素是否在检索表中；n 检索某个特定的数据元素的各种属性；n 在检索表中插入一个数据元素；n 从检索表中删去某个数据元素。n若对查找表只作前两种统称为“检索”的操作，称此类检索表为静态检索表（s

3、tatic search table）；n若在检索的过程中同时插入表中不存在的数据元素，或者从检索表中删除已存在的某个数据元素，称此类检索表为动态检索表（dynamic search table）。 算法与数据结构 检索及基本算法检索的概念(续) n 所谓特定的信息，是指关键字值等于给定值的信息，信息的单位是数据元素或记录。n 关键字（key）是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。显然，在一个记录中的每个数据项都可以作为标识该记录的关键字。如人事档案记录结构为： 它含有五个关键字，其中性别这个关键字标识了一个职工的性别情况。算法与数据结构 检索及基本算法检索

4、的概念(续) n主关键字（primary key）是指能惟一标识一个数据元素（或记录）的关键字。如上述记录中身份证号码是主关键字，可以惟一标识一条记录；而姓名、性别、年龄、工资级别不能惟一标识一条记录，它们都不是主关键字。n辅关键字（secondary key）是用以标识若干数据元素（或记录）的关键字，也称作次关键字或从关键字。如上述记录中的姓名、性别、年龄、工资级别都是辅关键字。算法与数据结构 检索及基本算法检索的概念(续) n检索，就是根据给定的某个值，在检索表中查找一个关键字等于给定值的记录的运算或操作。n若在检索表中存在这样的记录，则称检索成功，检索的结果是找到记录的全部信息（或找到记

5、录在检索表中的位置）；n若检索表中不存在关键字值等于给定值的记录，则称检索失败，给出在检索表中无要查找的记录的信息提示，并在动态检索时插入关键字等于给定值的记录于检索表中。算法与数据结构 检索及基本算法检索的概念(续) n 在检索表中查找某个数据元表（或记录）的过程，依赖于这个数据元表（或记录）在查找表中所处的位置；对检索表的检索方法取决于检索表中数据元表（或记录）的组织策略。n如在字典中查找一个英文单词，由于字典是按字母顺序编排的，所以不需从第一个单词顺序查找，而只是按待查单词中每个字母在字母表中的位置快速找到该单词；n而在数据元素（或记录）之间无任何关系组织起来的集合中查找，则需要从第一个

6、元素（或记录）开始依次顺序查找。算法与数据结构 检索及基本算法检索的概念(续) n 在计算机中进行检索是对已存入计算机中的数据进行检索，取决于采用何种数据结构来组织检索表；往往需要在数据元素（或记录）之间人为地加上一些关系，即用非集合结构如数组、文件、二叉树、散列表等结构来组织检索表，以便按某种规律来进行检索。n依数据组织方式不同，检索分为线性表检索、树表检索和散列表检索等。n 衡量一个检索算法的优劣，主要依据在检索过程中给定值和关键字的比较操作次数。为此，我们引入平均检索长度的概念。算法与数据结构 检索及基本算法平均检索长度n检索算法的平均检索长度（average search length

7、），即在检索过程中用给定值和关键字进行比较的平均比较次数，n或者说是为找到具有给定值关键字的记录所需要的比较次数的平均值。n它是为确定记录在检索表中的位置，需要和给定值进行比较的关键字个数的期望值。算法与数据结构 检索及基本算法平均检索长度（续）n 对于含有n个记录的检索表，检索成功时的平均检索长度为 n其中，Pi为检索第i个记录的概率，且 ；一般在不特殊说明的情况下均认为是等概率，即检索每个记录的概率相等， 。nCi为找到第i个记录需要和给定值比较的关键字的个数，它随检索方法的不同而不同。 算法与数据结构 检索及基本算法第7章 检索及基本算法 7.1 检索的概念7.2 线性表的检索7.3 树

8、表的检索7.4 哈希检索算法与数据结构 检索及基本算法线性表的检索n 在检索表的数据组织方式中，线性表是最基本的，也是最常用的一种组织方式。本节主要讨论在顺序存储结构实现的线性表上的检索算法，其类型定义描述为 typedef struct keytype key; /*关键字类型*/ elemtype other; /*其它域*/ sqlist; sqlist Rn+1; /*顺序表*/n本节介绍的线性表检索方法有顺序检索、二分法检索、黄金点检索、精算点检索和分块检索等。算法与数据结构 检索及基本算法7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2

9、.4 精算点检索7.2.5 分块检索算法与数据结构 检索及基本算法顺序检索n 顺序检索（sequential search）是一种最简单的基本检索方法。n其基本思路为：n从表的一端开始，用给定值逐个与表中各记录的关键字值比较。n若找到某个关键字值等于给定值的记录，则检索成功，并给出该记录在表中的位置；n若检索完整个表仍未找到关键字值等于给定值的记录，则检索失败，并给出失败信息。n 顺序检索方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。算法与数据结构 检索及基本算法顺序检索举例n以顺序存储结构为例，设数据元素存放在数组中下标从1到n的记录中，0号记录位置留作监视哨，从下标为n的

10、一端开始向另一端检索，顺序检索算法可描述如下：int seqsearch(sqlist R,keytype k) int i=n; R0.key=k; /*设置R0为监视哨*/ while(Ri.key != k) i-; return i; /*返回检索结果i*/ 算法与数据结构 检索及基本算法顺序检索举例（续）n 算法中设置监视哨R0，可以使得在检索成功和检索失败时的处理一致，在检索失败时也能在监视哨位置找到关键字值为k的记录，可省去在while循环中的位置越界检查（i=1）。n若从R0处向后顺序检索，监视哨可设置在Rn处。n算法执行之后，非0的函数值表示待查找记录在数组中的位置（下标）；

11、若函数值为0说明检索表中没有要查找的记录。算法与数据结构 检索及基本算法顺序检索（续）n对于具有n个记录的检索表，若待查找记录在Rn处，需要和给定值k比较一次，即Cn=1；n若待查找记录在Rn-1处，需要和给定值k比较两次，即Cn-1=2；n一般地，若待查找记录在Ri处，需和给定值k比较n-i+1次，即Ci=n-i+1。n因此，在等概率的情况下顺序检索的平均检索长度为算法与数据结构 检索及基本算法顺序检索（续）n在检索成功时顺序检索的平均比较次数约为表长的一半。n在检索失败时，顺序检索需要进行n+1次的比较。n当n很大时，平均检索长度也很大，检索效率较低，这是顺序检索的主要缺点。n但由于顺序检

12、索对表的存储结构和元素存放次序没有要求，且算法简单，在许多实际应用中常被采用。 算法与数据结构 检索及基本算法7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2.4 精算点检索7.2.5 分块检索算法与数据结构 检索及基本算法二分法检索n二分法检索（binary search），也称作折半检索，它是一种效率较高的检索方法。它要求检索表是用顺序存储结构表示，且数据元素的存放要按关键字值有序排列。n二分法检索的基本思想是：n在有序表中先取中间位置作为比较对象，若给定值与中间记录的关键字值相等，则检索成功；n若给定值小于中间记录的关键值则在表的左半区查找，

13、n若给定值大于中间记录的关键字值则在表的右半区查找。n就这样经过一次的比较缩小一半的检索区间，在每一个检索区间都是选取中间位置作为比较对象，不断地重复这样的检索过程直到检索成功，或者检索区间已无记录时检索失败。算法与数据结构 检索及基本算法二分法检索举例n例如：已知一个含15个记录的有序表，其关键字序列如下：（07 10 14 18 21 23 25 29 31 35 38 42 46 49 52）n现在要检索给定值k为19、46和11的记录，其检索过程如下：n用low和high分别表示检索区间的下界和上界；n用mid指示中间位置，即mid=(low +high)/2；n检索开始时low=1，

14、high=n；即检索区间为1，n。算法与数据结构 检索及基本算法二分法检索举例检索k=18n检索k=18的过程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=8 high=15n检索开始时，low=1，high=15，mid=(1+15)/2=8。由于k=1829=R8.key，所以应在右半区继续检索；此时low=mid+1=8+1=9，mid= (9+15)/2=12，即：07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=9 mid=12 high=15n由于k=4642=R14

15、.key，所以应在当前区间的右半区继续检索； 算法与数据结构 检索及基本算法二分法检索举例检索k=46(续)n此时low=12+1 =13，mid=(13+15)/2=14，即：07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=13mid=14high=15n由于k=4649=R14.key，所以应在当前区间的左半 区 继 续 检 索 ； 此 时 high=mid-1= 14-1=13，mid=(13+13)/2=13，即：07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=13 mid=13 hig

16、h=13 n由于k=46=R13.key，此时检索46成功。算法与数据结构 检索及基本算法二分法检索举例检索k=11n检索k=11的过程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=8 high=15n由于k=1129=R8.key，应在左半区继续检索；此时high= mid-1=8-1=7，mid= (1+7)/2=4，即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=4 high=7n由于k=1110=R2.key，应在当前区间的右半区继续检索；此时low=

17、2+1=3，mid= (3+3)/2=3，即： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=3 mid=3 high=3n由于k=1114=R3.key，应在当前区间的左半区继续检索；此时high=mid-1= 3-1=23=low，左半区已没有元素（不存在区间了），检索k11失败。 算法与数据结构 检索及基本算法二分法检索过程可用C语言描述 n二分法检索过程可用C语言描述为如下算法： int binarysearch (sglist R,keytype k) int low,mid,high; low=1; high=n; while(l

18、ow=high) mid=(low+high)/2; if(k=Rmid.key) return mid; else if(k100，则可有如下近似结果： 算法与数据结构 检索及基本算法二分法检索过程分析（续） n由此可见，二分法检索的效率比顺序检索高得多，如n=127时，顺序检索ASL64而二分法则为ASL6。n二分法检索只适用于检索表为顺序存储结构之下的有序表，即这种较高的检索效率是以对检索表预先按关键字值大小排序为代价的，所以二分法检索适合于一旦建立很少变动而又需要经常检索的检索表。 算法与数据结构 检索及基本算法7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3

19、黄金分割点检索7.2.4 精算点检索7.2.5 分块检索算法与数据结构 检索及基本算法黄金分割点检索n黄金分割点检索（gold-partition search），简称黄金点检索。它是利用我国著名数学家华罗庚院士当年推广优选法时介绍的黄金分割点的概念，即利用黄金分割数0.618把检索区间分为两个不等的区间。n每次用给定值与黄金点上的记录的关键字比较，若相等检索成功，若给定值小于黄金点关键字值，继续在黄金点之前的区间检索；若给定值大于黄金点关键字值，继续在黄金点之后的区间检索。n通过黄金点逐次缩小检索区间，直到检索成功，或区间已无记录检索失败时止。 算法与数据结构 检索及基本算法黄金分割点检索举

20、例n 例如，仍以前面的15个记录为例，检索k46的黄金分割点检索过程为： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=9 high=15n开 始 时 low=1， high=15， mid=low+0.618*(high-low+1)-1=1+0.618*(15-1+1)-1=9.329。给定值k=4631=R9.key，在黄 金 点 之 后 的 区 间 继 续 检 索 。 此 时 low=9+1=10，mid=10+0.618*(15-10+1)-1=12.70813。即： 07 10 14 18 21 23 25 29 31

21、 35 38 42 46 49 52 low=10 mid=13 high=15n 由于k=46=R13.key 检索成功。一个用二分法检索需4次比较的工作，黄金分割点检索只需两次比较就完成了。算法与数据结构 检索及基本算法黄金分割点检索算法描述 int goldpartsearch(sqlist R,keytype k) int low,mid,high; low=1; high=n; while(low=high) /*逐次缩小区间检索*/ mid=low+0.618*(high-low+1)-1+0.5; if(k=Rmid.key) return mid; else if(kRmid.

22、key) high=mid-1; /*修改区间上界*/ else low=mid+1; /*修改区间下界*/ return 0;算法与数据结构 检索及基本算法黄金分割点检索（续）n 该算法的时间性能与二分法相比，在平均性能上优于二分法，但仍然是；在最坏情况下，每次比较之后都在较大的区间内继续检索，比二分法差；在最好情况下，每次比较之后都在小区间内继续检索，比二分法好。n 所谓黄金分割点，就是利用Fibonacci数列对检索表分割得到的一系列位置。Fibonacci数列的定义为： 算法与数据结构 检索及基本算法黄金分割点检索（续）n注意观察“Fibonacci数列及其相邻项的比值”表中给出的F(

23、n)/F(n+1)的值，从n=6之后基本上稳定在0.618处。n因此，我们可以对长度为F(n)的检索表，第一次用F(n-1)处记录的关键字同给定值比较；由F(n-1)分割的两个区间的长度分别为F(n-2)-1和F(n-3)，又都可以利用Fibonacci数列找出新的分割点；如此一直进行下去，就可获得检索成功或失败的结果。n然而，检索表的长度很难是某个Fibonacci数列或接近Fibonacci数的值；其次即就是Fibonacci数，也还得为Fibonacci检索准备一张Fibonacci数表或通过循环递推求出每次要用的Fibonacci数，所以说利用Fibonacci数列设计检索算法不如直接

24、使用黄金分割数0.618设计检索算法方便。 算法与数据结构 检索及基本算法7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2.4 精算点检索7.2.5 分块检索算法与数据结构 检索及基本算法精算点检索n对于有序的检索表，如果记录的关键字值不仅有序，而且分布均匀或比较均匀，我们能不能很快地完成关键字值等于给定值记录的检索任务呢？回答是肯定的，下面将要介绍的精算点检索就可以解决这个问题。n所谓精算点检索（precise computing search），也称作插值检索。它是利用检索区间有序关键字值范围和给定值的大小比例关系估算检索位置的一种检索方法。

25、算法与数据结构 检索及基本算法精算点检索（续）n当关键字值分布均匀时应满足下式：n其中k为给定值，mid为估算位置，low和high分别为检索区间下界和上界位置，经整理可得估算公式为： n当给定值k等于Rmid.key则检索成功；否则若kRmid.key则在mid之后检索。 算法与数据结构 检索及基本算法精算点检索（续）n在关键字值均匀分布时，如呈等差数列时一次比较便可检索成功；在关键字值分布比较均匀时，若一次比较不能找到也会在mid位置附近，这两种情况的检索长度与检索表的大小n无关，所以称之为精算点检索。n如果关键字值分布不均匀，可缩小检索区间继续用前面的估算公式确定检索点检索，其检索性能也

26、优于黄金分割点检索和二分法检索。算法与数据结构 检索及基本算法精算点检索举例n例如，对于前述的15个记录的检索表，检索k=14的记录，low=1，high=15， ，R3.key=14等于给定值，一次比较检索成功；又如检索k=29时， ，一次比较Rn.key=29等 于 给 定 值 检 索 成 功 ； 再 如 检 索 k=46时 ， ，一次比较R13.key=46等于给定值检索成功；等等。 算法与数据结构 检索及基本算法精算点检索举例（续）n既然在关键字值分布较均匀时，即使一次比较不能检索成功也会在mid位置附近，在算法设计时就只需一次计算mid的值。n若k=Rmid.key，则一次比较检索成

27、功；n若kRmid.key，则可由mid后一个记录开始向后顺序检索，直到检索成功或某个记录的关键字值大于给定值k时检索失败。 算法与数据结构 检索及基本算法精算点检索算法描述 n这种与顺序检索相结合的精算点检索算法可描述如下： int precisesearch(sqlist R,keytype k) int low,mid,high; low=1; high=n; mid=low+(k-Rlow.key)*(high-low)/ (Rhigh.key-Rlow.key)+0.5; if(k=Rmid.key) return mid; else if(kk) mid-; 算法与数据结构 检索及

28、基本算法精算点检索算法描述（续） if(Rmid.key=k) return mid; /*检索成功返回位置*/ else return 0; /*检索失败返回0*/ else mid+; /*若给定值大于mid时在mid后检索*/ while(Rmid.keyk) /*向后顺序检索*/ mid+; if(Rmid.key=k) return mid; /*检索成功返回位置*/ else return 0; /*检索失败返回0*/ 算法与数据结构 检索及基本算法精算点检索算法分析n该算法中的两个当型循环，在关键字值分布较均匀的情况下，检索长度与检索表的长度n无关，平均检索长度趋近于某个常数；n

29、在关键字值分布不均匀的情况下，检索长度在最坏的情况下也不会超过二分法检索和黄金分割点检索；n精算点检索是平均性能最好的检索方法，对于检索表较大和分布较均匀时，使用精算点检索特别合适。算法与数据结构 检索及基本算法7.2 线性表的检索7.2.1 顺序检索7.2.2 二分法检索7.2.3 黄金分割点检索7.2.4 精算点检索7.2.5 分块检索算法与数据结构 检索及基本算法精算点检索算法分析n 分块检索（blocking search），又称作索引检索，它是顺序检索的一种改进方法，其效率介于顺序检索和二分法检索之间。n 分块检索不要求检索表中所有记录关键值有序排列，但要求把检索表分成若干块之后各块

30、之间按关键字值大小有序。n即分块检索要求检索表的特点是：块间有序，块内无序。n所谓块间有序是指块间升序或块间降序。n在块间升序时，每一块中所有记录的关键字值均大于和该块相邻的前一块中最大的关键字值；n在块间降序时，每一块中所有记录的关键字值均小于和该块相邻的前一块中最小的关键字值。算法与数据结构 检索及基本算法精算点检索算法分析（续）n 在分块检索中，除检索表本身之外，还需要建立一张索引表。如下图给出了一张块间升序的检索表的索引表，每个块在索引表中有一个索引项，每个索引项中包含有该块中最大的关键字值和该块第一个记录在检索表中的位置。n本例中检索表分为三块，各块中最大关键字值依次为22、48和8

31、6，各块中第一个记录在检索表中的位置依次为1、7和13；第二块中的最小关键字值24大于第一块中的最大关键字值22，第三块中的最小关键字值49大于第二块中的最大关键字值48。算法与数据结构 检索及基本算法精算点检索算法分析（续）n下图中给出了一张块间降序的检索表的索引表，每个块在索引表中也是一个索引项，但索引项中包含的是块中最小的关键字值和该块第一个记录在检索表中的位置。n该例中检索表分为四块，各块中最小关键字值依次为47、32、22和9，各块中第一个记录在检索表中的位置依次是1、6、11和16；第二块中的最大关键字值45小于第一块中最小的关键字值47，第三块中的最大关键字值31小于第二块中的最

32、小关键字值32，第四块中的最大关键字值20小于第三块中最小的关键字值22。 算法与数据结构 检索及基本算法精算点检索的基本思想n分块检索的基本思想是：n首先依据给定值在索引表中检索，以确定待查找记录所属的块；n由于索引表是有序表，所以可以用二分法检索，也可以用顺序检索或其它检索方法进行。n然后在确定的块内检索关键字值等于给定值的记录，由于块内记录无序排列，所以只能用顺序检索方法进行。算法与数据结构 检索及基本算法精算点检索举例n例如，要在前例“块间升序的检索表及其索引表示例”中检索k=38的记录：n先将k依次和索引表中各个最大关键字进行比较，由于22k48，所以k=38的记录若存在必在第二个块

33、中；n然后从第二个块的起始地址开始顺序检索，直到R10.key=k时检索成功。n再如检索k=76的记录：n将k和索引表中各个最大关键字值比较，由于48k50则在右子树中继续检索；再用80和右子树的根70比较，8070则继续在当前根结点70的右子树中检索；当再次和新的当前根结点比较时二者相等检索成功，返回指向当前根结点的指针。n又如检索k=15的记录时，由于15小于根结点50，在其左子树继续检索；15又小于左子树的根结点40，继续在当前根结点40的左子树中检索；15也小于当前根结点40的左子树的根结点20，当在20的左子树中继续检索时发现20的左子树为空，检索失败返回NULL。 算法与数据结构

34、检索及基本算法二叉检索树的二叉链表类型n 设二叉检索树以如下描述的二叉链表作为存储结构： typedef struct node keytype key; /*关键字域*/ elemtype other; /*其它数据域*/ struct node *lchild, *rchild; /*左右孩子指针域*/ bstnode; /*定义结点类型bstnode*/ typedef bstnode *bstlist; /*定义二叉检索树表类型bstlist*/算法与数据结构 检索及基本算法二叉检索树的检索算法描述 n 二叉检索树的检索算法可描述如下： bstlist bstsearch(bstlis

35、t t,keytype k) bstlist p ; p=t; if(p=NULL)|(p-key=k) return p; else if(p-keyrchild,k); else return bstsearch(p-lchild,k); /*bstsearch end*/算法与数据结构 检索及基本算法2.二叉检索树的构造过程和插入操作 n对于一组关键字无序的记录，构造其相应的二叉检索树的方法是：从一棵空的二叉检索树开始，每当读入一个记录就生成一个结点，然后按关键字值的大小插入到当前的二叉检索树之中；当所有记录的结点都已插入二叉检索树中时便构造完毕。n虽然，插入操作是构造二叉检索树的关键操

36、作。要保证在一棵二叉检索树中插入一个结点之后，仍然满足二叉检索树的定义。其插入过程为：n若二叉检索树为空，则插入结点作为新的根结点；n若二叉检索树非空，则在非空的二叉检索树中检索插入结点；如果检索成功就不必插入，否则插入结点作为新的叶结点，并成为检索路径上最后一个结点的左孩子或右孩子。 算法与数据结构 检索及基本算法二叉检索树的构造过程和插入操作(续)n为了实现这一插入过程，在二叉检索树非空时需要知道检索路径上的最后一个结点位置，才能够准确地把插入结点作为左孩子或右孩子插入二叉检索树中；为此；需要在检索过程中设一指针变量记下当前结点的前趋（即双亲）结点位置。n插入算法的形式化描述如下： bst

37、list insertbst(bstlist t,keytype k) bstlist s,p,q; if(t=NULLl) p=(bstlist)malloc(sigeof(bstnode); p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; return p; 算法与数据结构 检索及基本算法二叉检索树的构造过程和插入操作(续) p=t; while(p!=NULL) q=p; if(p-key=k) /*检索成功不必插入*/ return t; /*返回原二叉检索树*/ else if(p-keyrchild; else p=p-lc

38、hild; p=(bstlist)malloc(sizeof(bstnode); 算法与数据结构 检索及基本算法二叉检索树的构造过程和插入操作(续) p-key=k; p-lchild=NULL; p-rchild=NULL; p-other=data; if(kq-key) q-rchild=p; else q-lchild=p; return t; 算法与数据结构 检索及基本算法二叉检索(排序)树构造过程举例 n从空树出发经过一系列的检索插入操作之后，就可生成一棵二叉检索树。一个无序序列可以通过构造一棵二叉检索树而变成一个有序序列（即中序遍历次序序列），构造的过程就是对无序序列进行排序的过

39、程，所以又称作二叉排序树。n设关键字序列为（45，22，57，18，29，92），生成二叉检索树（即二叉排序树）的过程如下图所示。 算法与数据结构 检索及基本算法3.二叉树检索树的删除操作 n在二叉检索树中删除一个结点，相当于在检索表中删除一个记录，不能把以待删除结点为根结点的子树全部删去，并且要保证删除某个结点后的二叉树仍然是一棵二叉检索树。下面，我们分三种情况讨论如何在二叉检索树中删除一个结点。 待删除结点是度为0的叶子结点 删除一个叶子结点*p，不破坏整棵树的结构，只需将其双亲结点*f与*p之间相链接的指针域置为空即可： f-lchild=NULL; 或 f-rchild=NULL;算法

40、与数据结构 检索及基本算法二叉树检索树的删除操作（续） 待删除结点是度为1的单枝结点 即待删除结点只有左子树或只有右子树的情况，如下图所示。此时只需将待删除结点*p的惟一后继结点（左孩子或右孩子）直接链接到其双亲结点*f的相应位置（即左链域或右链域）上即可： (a) f-lchild=p-lchild; 或 (b) f-lchild=p-rchild; 或 (c) f-rchild=p-lchild; 或 (d) f-rchild=p-rchild;算法与数据结构 检索及基本算法二叉树检索树的删除操作（续） 待删除结点是度为2的双枝结点 即待删除结点既有左子树又有右子树的情况， 如下图所示，为

41、了保持二叉检索树的特性，通常有如下四种做法。 算法与数据结构 检索及基本算法二叉树检索树的删除操作方法一 n方法一：找出待删除结点*p的中序前趋结点*q，把*q的关键字域和数据域的值赋给*p的相应域，即： p-key=q-key; p-other=q-other;n然后删除其中序前趋结点*q，由于*p的中序前趋*q是*p左子树上的最右下结点，所以*q必是叶子结点或单左枝结点，如下图所示；其删除方法见和。 算法与数据结构 检索及基本算法二叉树检索树的删除操作方法二 n方法二：找出待删除结点*p的中序后继结点*q，把*q的关键字域和数据域的值赋给*p的相应域，即： p-key=q-key; p-o

42、ther=q-other;n然后删除其中序后继结点*q。由于*p的中序后继*q是*p右子树上的最左下结点，所以*q必是叶子结点或单右枝结点，如下图所示；其删除方法见和。 算法与数据结构 检索及基本算法二叉树检索树的删除操作方法三 n方法三：将待删除结点*p的右子树链接到它的中序前趋结点（即左子树上的最右下结点）*q的右孩子域上，然后把它的左子树直接链接到其双亲结点*f的左（或右）孩子域上。即： q-rchild=p-rchild; f-lchild（或f-rchild）=p-lchild; 算法与数据结构 检索及基本算法二叉树检索树的删除操作方法四 n 方法四：将删除结点*p的左子树链接到它的

43、中序后继（即右子树上的最左下结点）*q的左孩子域上，然后把它的右子树直接链接到其双亲结点*f的左（或右）孩子域上。即： q-lchild=p-lchild; f-lchild（或f-rchild）=p-rchild;算法与数据结构 检索及基本算法二叉树检索树的删除操作（续）n前两种方法是以删除待删除结点*p的中序前趋或中序后继*q来实现删除结点*p之目的，不需要知道待删除结点的双亲结点位置；n后两种方法是直接删除待删除结点*p，不仅需要知道其中序前趋或中序后继*q的位置，还需要在检索待删除结点*p的同时记住其双亲结点的位置。算法与数据结构 检索及基本算法二叉树检索树的删除操作（续）n 方法一和

44、方法三中*p的中序前趋*q（即左子树中的最右下结点）可以如下确定： q=p-lchild; while(q-rchild!=NULL) q=q-rchild;n而方法二和方法四中*p的中序后继*q（即右子树中的最左下结点）的确定方法为： q=p-rchild; while(q-lchild!=NULL) q=q-lchild;算法与数据结构 检索及基本算法二叉检索树的删除算法描述 n下面我们给出采用方法四删除双枝结点时的二叉检索树的删除算法描述如下： bstlist deletebst(bstlist t,keytype k) bstlist p,q,r,f; p=t; f=NULL; whi

45、le(p!=NULL)&(k!=p-key) f=p; if(kkey) p=p-lchild; else p=p-rchild; 算法与数据结构 检索及基本算法二叉检索树的删除算法描述（续） if(p=NULL) break; /*检索失败时不用删除中断执行*/ if(p-lchild=NULL)|(p-rchild=NULL) q=p; /*待删除的*p为叶子结点或单枝结点时*/ else q=p-rchild; while(q-lchild!=NULL) q=q-lchild; if(q-lchild!=NULL) r=q-lchild; else r=q-rchild;算法与数据结构

46、检索及基本算法二叉检索树的删除算法描述（续） if(p!=q) q-lchild= p-lchild; if(f-lchild=p) f-lchild=r; else f-rchild=r; return t; /*返回删除操作后的二叉检索树*/ /*deletebst end*/算法与数据结构 检索及基本算法4.二叉检索树的检索性能分析n在二叉检索树上检索关键字值等于给定值k的记录，正好是走了一条从根结点到关键字值为k的结点的路径，和给定值k的比较次数为路径长度加1（或结点所在层次数），和二分法检索类似，其比较次数不超过树的深度。n然而，用二分法检索一个长度为n的检索表其检索过程的二叉树表示

47、是惟一的，而含有n个结点的二叉检索树却不惟一。 算法与数据结构 检索及基本算法二叉检索树的检索性能分析举例n例如，如下图给出了结点值都相同的两棵二叉检索树，由于构造时的关键字序列不同，前者深度为3，而后者深度为7；在等概率的情况下，前者的平均检索长度为ASL=(1+2+2+3+3+3+3)/7=17/7，后者的平均检索长度为ASL=(1+2+3+4+5+6+7)/7= 28/7=4。 算法与数据结构 检索及基本算法二叉检索树的检索性能分析（续）n 因此，含有n个结点的二叉检索树的平均检索长度和二叉检索树的形态有关，当先后插入的关键字按值有序时，构造的二叉检索树蜕变为单枝树；n升序时为单右枝二叉

48、树，降序时为单左枝二叉树；n树的深度为n，平均检索长度为(n+1)/2（和顺序检索相同），这是最差的情况。最好的情况是二叉检索树的形态和二分法检索过程得到的树相同，树的高度和完全二叉树的高度相同，其平均检索长度为 。算法与数据结构 检索及基本算法二叉检索树的检索性能分析（续）n现在我们考虑在一般情况下二叉检索树的平均检索长度，假设在含有n个结点的二叉树中，有i个结点关键字值小于根结点的关键字值，n-i-1个结点关键字值大于根结点的关键字值。n在等概率检索的情况下平均检索长度为：n其中，p(i)为含有i个结点的二叉检索树的平均检索长度；p(i)+1为检索左子树中每个结点所用比较次数的平均值，p(

49、n-i-1)+1为检索右子树中每个结点所用比较次数的平均值。 算法与数据结构 检索及基本算法二叉检索树的检索性能分析（续）n由于根结点的左子树中有0个，1个，n-1个结点的情况是等概率的，对上式取平均值得：n用数学归纳法可以证明， ，即二叉检索树的平均长度为 。算法与数据结构 检索及基本算法7.3 树表的检索7.3.1 二叉检索树7.3.2 二叉检索树的平衡性调整7.3.3 B树和B+树算法与数据结构 检索及基本算法平衡因子n平衡因子（balance factor）n二叉树上任一结点的平衡因子，定义为该结点的左子树深度减去右子树深度的差。n如下图中给出了一些二叉树，其结点上所示数值为该结点的平

50、衡因子值。算法与数据结构 检索及基本算法平衡二叉树n平衡二叉树（balance binary tree）n如果一棵二叉树中所有结点的平衡因子的绝对值不超过1，则称该二叉树为平衡二叉树；平衡二叉树也称作AVL树。n显然，AVL树要么是一棵空树，要么其左右子树深度不超过1且都是AVL树；只要二叉树上有一个结点的平衡因子的绝对值大于1，该二叉树就是不平衡的。如前例图中，(a)和(b)都是平衡二叉树（即AVL树），而(c)和(d)都不是平衡二叉树（即非AVL树）。 算法与数据结构 检索及基本算法平衡二叉树（续）n由于AVL树具有良好的形态，其左右子树的深度差不超过1；对于给定的结点数目n，AVL树的平

51、均深度接近于完全二叉树的深度 ；n所以我们希望由任何初始序列构成的二叉检索树都是AVL树，使得其平均检索长度接近于 。 n如 何 使 构 造 的 二 叉 树 成 为 AVL树 呢 ？ Adelson-Velskii和Landis提供了一个动态地保持二叉检索树平衡性的方法；n其基本思想是在构造二叉检索树的过程中，每当插入一个结点后都去检查是否由于该结点的插入而破坏了二叉检索树的平衡性；若出现绝对值超过1的平衡因子，则需要在保持二叉检索树特性的前提下通过调整使之达到新的平衡。 算法与数据结构 检索及基本算法平衡二叉树（续）n在一般情况下，设在插入结点的过程中使二叉检索树失去平衡的最小子树的根结点为

52、a，即a为离插入结点最近且平衡因子绝对值超过1的祖先结点；n因插入结点的位置不同而失去平衡需要调整的规律可归纳为如下四种情况：nLL型平衡旋转（右单旋型） nRR型平衡旋转（左单旋型） nLR型平衡旋转（先左后右双旋型） nRL型平衡旋转（先右后左双旋型） 算法与数据结构 检索及基本算法1.LL型平衡旋转（右单旋型）n这种失衡是由于在结点a的左孩子b的左子树上插入结点，使结点a的平衡因子由1增至2而造成的。n其调整策略是以a的左孩子b为轴心顺时针旋转（即向右旋转）一次；使结点a成为其左孩子b的右孩子，而b的右子树成为a的左子树，如下图所示。这种调整策略既使结点的平衡因子满足AVL树的要求，又保

53、持了二叉检索树的特性（即中序遍历次序为上升序列）。 算法与数据结构 检索及基本算法2.RR型平衡旋转（左单旋型）n这种失衡是由于在结点a的右孩子b的左子树上插入结点，使a的平衡因子由-1变成-2而造成的；n其调整策略是以a的右孩子b 为轴心逆时针旋转（即向左旋转）一次；使a成为b的左孩子，而b的左子树成为a的右子树，如下图所示。 算法与数据结构 检索及基本算法3. LR型平衡旋转（先左后右双旋型） n这种失衡是由于在结点a的左孩子b的右子树上插入结点，使a的平衡因子由1增至2造成的。n设c是b的右孩子，插入结点的位置有三种可能性：nc就是插入结点，这是由于插入前b为叶子结点且a无右孩子而产生的

54、一种可能；n插入结点在c的左子树上；n插入结点在c的右子树上。 算法与数据结构 检索及基本算法LR型平衡旋转（续） n对这三种导致LR型失衡的情况，其调整策略是一致的：n即以a的左孩子b的右孩子c为轴心，先逆时针（即向左）旋转一次，再顺时针（即向右）旋转一次；使c的左子树成为b的右子树，c的右子树成a的左子树，b成为c的左孩子而a成为c的右孩子，以“插入在c的左子树上”为例，两次旋转的调整过程如下图所示。 算法与数据结构 检索及基本算法4. RL型平衡旋转（先右后左双旋型） n这种失衡是由于在结点a的右孩子b的左子树上插入结点，使a的平衡因子由-1变成-2造成的，设c是b的左孩子，插入结点位置

55、的三种可能性如下图所示：算法与数据结构 检索及基本算法RL型平衡旋转（续） n对这三种导致RL型失衡的情况，其调整策略为：n以a的右孩子b的左孩子c为轴心，先顺时针（即向右）旋转一次，再逆时针（即向左）旋转一次；使c的左子树成为a的右子树，c的右子树成为b的左子树，a成为c的左孩子而b成为c的右孩子。以“插入在c的左子树上”为例，两次旋转的调整过程如下图所示：算法与数据结构 检索及基本算法构造平衡二叉检索树举例 n例如，对于一组记录其关键字序列为（18，5，10，15，12，11，20），要建立一棵平衡的二叉检索树，其构造过程如下图所示： 算法与数据结构 检索及基本算法构造型平二叉检索树的算法

56、n 在设计构造平衡的二叉检索树的算法时，需要先为每个结点增加一个平衡因子域，然后在二叉检索树构造算法的基础上做几点修改：n 插入一个结点后，要修改树中各结点平衡因子的值；n 判别是否因插入结点产生失衡，在失衡时找到失衡的最小子树；n 判别失衡类型并做相应的调整处理。n在平衡的二叉检索树上进行检索的过程，和在二叉检索树上的检索过程一致，在检索过程中和给定值比较的次数不会超过树的深度，而含有n个结点的平衡二叉检索树的最大深度为 ， 其中 。算法与数据结构 检索及基本算法7.3 树表的检索7.3.1 二叉检索树7.3.2 二叉检索树的平衡性调整7.3.3 B树和B+树算法与数据结构 检索及基本算法B

57、树n B树是一种平衡的多路检索树，是文件系统（包括大型数据库文件系统）中的一种重要的数据组织结构。n 一棵m阶B树，或者为空树，或者为满足下列特性的m叉树： 树中每个结点至多有m棵子树（即至多有m-1个关键字）； 除非根结点为叶子结点，否则至少有两棵子树（即至少有一个关键字）； 除根结点之外的所有非终端结点至少有棵子树；算法与数据结构 检索及基本算法B树（续） 所有的非终端结点中包含以下信息： （n，A0，k1，A1，k2，kn，An ）n其中： n（nm-1）为关键字的个数，即子树个数为n+1； ki（1in）为关键字，且kiki+1（1in）；n Ai（0in）为指向其子树的根结点的指针，

58、且Ai（0in）所指子树中所有结点的关键字值都小于ki+1，An所指子树中所有结点的关键字值都大于kn； 所有叶子结点在同一个层次上，且不含有任何信息（可以看作是外部结点或检索失败的结点；实际上这些结点不存在，指向这些结点的指针为NULL）。算法与数据结构 检索及基本算法B树示全例n下图给出了一棵4阶 B树的示例： 算法与数据结构 检索及基本算法B树的插入操作n在B树上插入一个关键字，不是象在二叉检索树中那样添加一个叶子结点，而是在B树的最底层的某个非终端结点中添加一个关键字。n若该结点中关键字的个数小于m-1个则插入完成；否则添加后关键字个数由m-1个变为m个与B树定义不符，需要进行结点的“

59、分裂”以满足B树定义。n结点的分裂方法为，把中间一个关键字拿出来插入到该结点的双亲结点上，前后两部分各自形成一个结点；双亲结点中也可能有m个关键字，就需要继续分裂结点，直到插入到某个关键字个数小于m-1的祖先结点。n由这种分裂过程可见，B树是由底向上生长的。 算法与数据结构 检索及基本算法B树的插入操作举例nB树的插入过程如下图所示，图中只画出了非终端结点，省去了最底层的叶子结点。 算法与数据结构 检索及基本算法B树的删除操作n 在B树上删除一个关键字和插入关键字类似也是由底向上的调整过程，n先找到该关键字所在的结点并删除这个关键字。n若找到的结点是最底层的非终端结点，当关键字个数大于则删除完

60、成，否则删除后关键字个数由个变为个与B树定义不符，需要进行结点的“合并”以满足B树定义。n合并的方法是把删除了关键字的结点同其左兄弟结点（或右兄弟结点）合并，连同它们的双亲结点中的相关关键字项一块合并重新分配，在其双亲结点不满足B树定义时继续向上调整直到根结点。n若找到的待删除关键字所在结点不是底层非终端结点，则是将该关键字用其B树中的后继替代，而删除其后继的信息。算法与数据结构 检索及基本算法B树的删除操作举例nB树的删除过程如下图所示： 算法与数据结构 检索及基本算法B树的检索操作n在B树中进行检索的过程是：n首先在根结点中所包含的关键字中检索给定的关键字，若找到则检索成功，否则确定待检索

61、关键字所在的子树，并在该子树中继续检索，直到检索成功或指针为空时检索失败。n例如，在前例中的一棵4阶B树中检索关键字值为61的记录，因根结点中不存在此关键字，则到大于39的子树中检索；又因为子树的根结点中没有此关键字，而506180，故再到s所指子树中检索，在这个结点中含有61的关键字值则检索成功。n又如在此4阶B树中检索关键字值为75的记录，也是沿前面的这一条路线检索，由于s所指结点中没有值为75的关键字而检索失败。 算法与数据结构 检索及基本算法B树的检索操作（续）n B树的检索是在B 树上找结点和在结点中找关键字两个基本操作的交叉进行过程，待查关键字所在结点在B树中的层次是决定B树检索效

62、率的首要因素，最坏的情况下是含n个关键字的m阶B树的最大深度。n由B树定义，第一层至少有1个结点，第二层至少有2个结点；由于除根结点外的每个非终端结点至少有 棵子树，则第三层至少有2（ ）个结点；依此类推，第h+1层至少有 个结点；而h+1层为叶子结点。若m阶B树有n个关键字，则叶子结点即查找不成功的结点数为n+1，由此有 算法与数据结构 检索及基本算法B+树 nB+树是应用于文件系统中的B树的一种变形树，它与B树的差异主要在于： 有n棵子树的结点中含有n个关键字； 所有叶子结点中包含了全部关键字的信息及指向相应记录的指针，且叶子结点以关键字递增顺序链接； 所有的非终端结点可以看成是索引部分，

63、结点中仅含有其子树中的最大（或最小）关键字。算法与数据结构 检索及基本算法B+树举例 n如下图给出了一棵3阶B+树。n通常B+树上有两个指针，一个指向根结点，一个指向关键字值最小的叶子结点。n因此，对于B+树既可从根结点开始多级索引顺序检索，又可以从最小关键字开始顺序检索。 算法与数据结构 检索及基本算法B+树的操作 n在B+树上进行插入、删除和检索的过程与B树基本相似。n在检索过程中在非终端结点上找到给定值后并不终止，而是继续向下直到叶子结点；因而无论是检索成功还是检索失败，每次检索都是走了一条从根结点到叶子结点的路径。nB+树的插入仅在叶子结点上进行，当叶子结点中关键字个数大于m时也要分裂

64、成两个结点，并且其双亲结点中同时也包含这两个结点的关键字最大值。nB+树的删除也在叶子结点中进行，其在非终端结点中的值可以作为分界关键字存在；当然在删除后若使结点中关键个数小于 时也要进行结点的合并操作。 算法与数据结构 检索及基本算法第7章 检索及基本算法 7.1 检索的概念7.2 线性表的检索7.3 树表的检索7.4 哈希检索算法与数据结构 检索及基本算法哈希检索 n在前两节介绍的线性表检索和树表检索方法后，由于记录在检索表中的位置是随机的或按关键字值大小次序排列的，记录的存储位置和其关键字值之间不存在某种确定的关系，存储位置依赖于关键字的初始随机序列或在检索表中其它关键字值的大小。n所以

65、在检索时需要进行一系列的关键字值与给定值之间的比较，其检索效率和检索过程中进行的比较次数有关。n本节介绍一种直接利用关键字值计算记录在检索表中的存储位置来进行检索的方法哈希（Hash）检索技术。 算法与数据结构 检索及基本算法7.4 哈希检索7.4.1 哈希检索与哈希表 7.4.2 哈希函数的构造方法7.4.3 地址冲突的消解策略7.4.4 哈希表的检索算法及性能分析算法与数据结构 检索及基本算法哈希检索与哈希表 n哈希检索技术的初衷是组织理想状态的检索表。n检索表的理想状态是：把记录的关键字值与记录在检索表中的存储位置建立起某种一对一的关系，这种一对一的关系可以用关于关键字的一个函数h(ke

66、y)来表示，这样就可以不必进行关键字与给定值的比较，而是直接依据给定的关键字值来直接计算得到记录在检索表中的存储地址。 算法与数据结构 检索及基本算法哈希检索与哈希表举例 n例如，对于一组关键字序列（25，74，36，15，40，29，82，19，65，33，57，47，50），选取函数h(key)key%13建立记录与其在检索表中存储位置之间的关系，可得到如下表所示的一张检索表：n当对该表检索时，只需用给定关键字值k通过这个函数计算出地址，以该地址从检索表的对应位置取出记录的有关信息即可，不需要进行关键字值的比较操作。n如检索key=57的记录，通过h(57)=57%13=5知关键字值为57

67、的记录在检索表的存储位置5处，从而得到关键字值为57的记录的有关信息。 算法与数据结构 检索及基本算法哈希检索与哈希表（续）n 我们把这种反映关键字值与存储位置的一对一关系的函数h(key)称作哈希函数，也称作散列函数或杂凑函数；n利用哈希函数来实现从记录的关键字值到该记录在检索表中存储位置地址的计算，哈希函数h(key)的值称作哈希地址，也称作散列地址或杂凑地址；n把利用哈希函数h(key)组织检索表并利用h(key)进行检索的这种方法称作哈希方法，也称作散列法或杂凑法；n把用这种思想方法（即哈希方法）组织起来的检索表称作哈希表，也称作散列表或杂凑表。算法与数据结构 检索及基本算法哈希检索与

68、哈希表（续）n对于n个记录的关键字集合，我们总能找到其关键字值与存储地址之间的一对一函数。n若最大关键字值为m，可以分配m个记录空间组织哈希表，选取哈希函数h(key)key即可。然而，这样会造成存储空间的大量浪费，甚至不可能分配有这么大的存储空间。n在实际应用中，通常关键字的取值范围比哈希地址的取值范围要大得多，因而经过哈希函数h(key)变换后，可能会将不同的关键字值映射到同一个哈希地址上，我们称这种现象为地址冲突（address collision）。算法与数据结构 检索及基本算法哈希检索与哈希表（续）n在一般情况下，地址冲突是不可避免的，只能通过选取合适的哈希函数尽可能地减少这种冲突现

69、象，而不可能做到完全避免这种冲突现象，所以哈希检索技术中必须解决如下两个问题： 如何选择一个计算简单且地址冲突尽可能少的哈希函数； 在出现地址冲突时采用怎样的办法来消解冲突。 算法与数据结构 检索及基本算法7.4 哈希检索7.4.1 哈希检索与哈希表 7.4.2 哈希函数的构造方法7.4.3 地址冲突的消解策略7.4.4 哈希表的检索算法及性能分析算法与数据结构 检索及基本算法哈希函数的构造方法n哈希函数是记录的关键字值到记录在哈希表中存储地址的映射函数，若对于关键字值集合中的任何一个关键字经哈希函数映射到哈希表中任何一个地址的概率相等（即得到一个随机地址），这组关键字的哈希地址就会均匀地分布

70、在哈希表中整个地址区间中从而减少地址冲突。n构造哈希函数的一般原则是，哈希函数的运算尽可能地简单，哈希函数的值在表长范围内，并且尽可能使不同的关键字值有不同的哈希函数值（即尽可能地减少地址冲突）。算法与数据结构 检索及基本算法常见的哈希函数构造方法n常见的哈希函数构造方法有如下七种：n直接定址法（immediately allocate）n数字分析法（digital analysis method）n平方取中法（middle-sguare method）n折叠法（floding method）n除留余数法（division method）n乘余取整法（multiplication method

71、）n随机数法（random number method）算法与数据结构 检索及基本算法1. 直接定址法 n直接定址法是取关键字的某个线性函数值为哈希地址，即： h(key)=a*key+b n其中a和b为常数，当a=1和b=0时即为关键字本身的值作为哈希地址，这类函数是一对一的函数，地址集合和关键字集合大小相同，不会发生地址冲突。该方法适用于关键字集合中的值分布连续或基本连续的情况，如果关键字值分布不连续则会造成空间的大量浪费。n 例如，对于一个各年龄（如1到110岁）人口统计表，年龄作为关键字，哈希函数可取自身即h(key)=key，又如对于一个解放后各年份出生的人口统计表，年份作为关键字，

72、哈希函数可取为h(key)=key-1948，等等。 算法与数据结构 检索及基本算法2. 数字分析法 n数字分析法（digital analysis method） 如果预先知道关键字值的集合，则可通过分析关键字值在各位的分布情况，选取分布较均匀的若干位组成哈希地址，称这种方法为数字分析法。n例如对于一个班的学生记录，其关键字为学号，学号的前面几位为学校编号、年份、院系编号和专业编号等，而最后两位或三位是学生编号分布较均匀，因此可选后两位或三位作为哈希地址。算法与数据结构 检索及基本算法3.平方取中法 n平方取中法是先求出关键字的平方，然后取其中间的几位作为哈希地址的一种常用的哈希函数构造方法

73、。n这种方法常用于预先不知道关键字的全部情况，取其中哪几位都不一定合适；而一个数的平方之后的中间几位和数的每一位都相关，由此可使随机分布的关键字对应的哈希地址也是随机的，所取的位数可由表长（即哈希地址的范围）而定，如下表给出了一个平方取中法确定哈希地址的示例。 算法与数据结构 检索及基本算法4.折叠法 n折叠法是先把关键字分割成位数相等的几段（最后一段可以不等），然后取这几段的叠加和作为哈希地址。n叠加的方法有两种，n一种是移位叠加，即把每一段的最低位对齐后相加；n一种是间界叠加，即从一端向另一端沿分割界来回折叠对齐后相加。n对于关键字数位较多，且每位数字分布大致均匀，而哈希地址范围有限的情况

74、，可使用此法求哈希地址。 算法与数据结构 检索及基本算法折叠法举例n 例如对于15位关键字，哈希地址范围为4位，则可四位一段叠加产生哈希地址，如key7564，其哈希地址用上述两种叠加方法得到的哈希地址如下：算法与数据结构 检索及基本算法5.除留余数法 n除留余数法是用关键字key的值除以某个正整数p所得余数作为哈希地址。即： h(key)=key%pn采用此法选用合适的p值非常重要，一般地选取p为不超过哈希表长m的最大素数。n例如当表长为600时，可选p=599。该方法计算简单，在许多情况下使用效果较好，是一种较常用的哈希函数构造方法。算法与数据结构 检索及基本算法6.乘余取整法 n 乘余取

75、整法是以关键字乘以常数A，取其小数部分之后再乘以整数B，取其整数部分作为哈希地址。其中 B选择依赖于哈希表的表长m；而A的选择依赖于关键字集合的特征。一般地选 ，B=m较为理想。n乘余取整法的公式表示为： 算法与数据结构 检索及基本算法7.随机数法 n选择一个随机函数，取关键字值的随机函数值为相应记录的哈希地址。即： h(key)=random(key)n其中random为一个随机函数，此方法常用于关键字长度不等的情况下来构造哈希函数。算法与数据结构 检索及基本算法哈希函数的构造方法（续）n在实际使用中，要视关键字的不同选用相应的哈希函数。n通常要考虑的因素有：n哈希函数的计算时间；n关键字的

76、长度；n哈希表的大小；n关键字的分布情况；n记录的检索频率。n在综合考虑各因素之后，构造和选用适合实际问题的哈希函数。 算法与数据结构 检索及基本算法7.4 哈希检索7.4.1 哈希检索与哈希表 7.4.2 哈希函数的构造方法7.4.3 地址冲突的消解策略7.4.4 哈希表的检索算法及性能分析算法与数据结构 检索及基本算法地址冲突的消解策略n 虽然通过精心构造的哈希函数可以使地址分布比较均匀，最大限度地减少了地址冲突的发生。n然而地址冲突实际上是不可能避免的，必须寻求消解地址冲突的方法，才能使哈希表的构造和哈希检索技术在实际应用中派上用场。n常用的地址冲突的消解策略有两类：n一类是开放定址法；

77、n一类是拉链法。算法与数据结构 检索及基本算法1. 开放定址法 n开放定址法（open addressing）就是把哈希表中的空位置向处理地址冲突开放。n具体做法是，当发生地址冲突时，从发生地址冲突的那个位置开始，使用某种方法在哈希表中形成一个探查序列，沿此序列逐个位置查看，直到找到一个空闲的位置把发生地址冲突时的待插入记录存入其中。n产生探查序列的常用方法有线性探查法，平方探查法和随机探查法等。算法与数据结构 检索及基本算法线性探查法n线性探查法是开放定址法消解地址冲突的一种最简单的探查方法。它把表长为m的哈希表看作是环形表，若发生地址冲突的位置地址为d，则依次探查d+1、d+2、m-1、0

78、、1、d-1，直到找到一个空闲位置为止。其开放定址公式为： n例如一组关键字为（65，40，15，29，82，57，19，33，47，74，36），哈希函数为h(key)=key%11，消解地址冲突的策略是线性探查法，构造的长度为11的哈希表如下表所示。 算法与数据结构 检索及基本算法用线性探查法构造哈希表过程 n构造的具体过程为：nf(65)=10，地址10为空填入65；nf(40)=7，地址7为空填入40；nf(15)=4，地址4为空填入15；nf(29)=7，地址7已填入40，需线性探查，下一个地址8为空填入29；nf(82)=5，地址5为空填入82；nf(57)=2，地址2为空填入57

79、；nf(19)=8，地址8已有29填入，故线性探查到地址9为空填入19；nf(33)0，地址0为空填入33；nf(47)3，地址3为空填入47；nf(74)8，地址8已填入29，线性探查直到地址1为空填入74；nf(36)=3，地址3已填入47，线性探查直到地址6为空填入36。n此时完成如上所示的哈希表。 算法与数据结构 检索及基本算法线性探查法（续）n 使用线性探查法易造成堆积现象，如构造上述哈希表为了填入74和36的情况，即不同哈希地址的记录争夺同一个后继散列地址的现象，它使得不同哈希地址的记录处在同一个探查序列之中，增加了探查序列的长度，下述两种方法可以较好地消解堆积现象：n平方探查法

80、n随机探查法 算法与数据结构 检索及基本算法平方探查法 n平方探查法也称作二次探查法。在发生地址冲突时，依次探查位置d+i，其中i取12、-12、22、-22、32、-32、等等，即在发生冲突的地址两端逐步扩大间隔地探查。其开放定址公式为： n其中1i(m-1)/2。这种方法可以减少堆积现象，但不能探查到哈希表中的所有位置。 算法与数据结构 检索及基本算法随机探查法 n随机探查法是采用一个随机数作为地址位移来计算下一个位置的地址，即： n其中1im-1；r1、r2、rm-1是1到m-1的一个随机排列。 算法与数据结构 检索及基本算法 2. 拉链法n拉链法（linked addressing）是

81、将哈希地址相同的关键字的记录链接到同一个单链表中。n例如对一组关键字（65，40，15，29，82，57，19，33， 47， 74， 36） 和h(key)=key%11，其消解地址冲突为拉链法的哈希表如右图所示。n拉链法不会产生堆积，因而平均检索长度较短；且各单链表中的结点是动态生成的，便于表长经常变化的情况。算法与数据结构 检索及基本算法地址冲突的消解策略（续）n 此外，消解哈希表地址冲突的方法还有建立公共溢出区法和再散列法等。n前者是建立一个公共的溢出表，一旦发生地址冲突都填入溢出表中；n后者是为了消解地址冲突，再选择一个哈希函数处理。算法与数据结构 检索及基本算法7.4 哈希检索7.

82、4.1 哈希检索与哈希表 7.4.2 哈希函数的构造方法7.4.3 地址冲突的消解策略7.4.4 哈希表的检索算法及性能分析算法与数据结构 检索及基本算法哈希表的检索算法 n哈希表的检索过程和建表过程基本一致，即对于给定的关键字值k，根据建表时设定的哈希函数h(key)求得哈希地址h(k)。n若表中对应位置上没有记录则检索失败，否则与记录的关键字值进行比较；n若关键字等于给定值k则检索成功，否则按建表时所采用的消解地址冲突的方法找到下一个地址；n如此反复探查比较，直到某个记录的关键字等于给定值k时检索成功，或某个位置上为空时检索失败为止。n对于开放定址法解决地址冲突的哈希表，某位置为空是检索失

83、败的条件，若在哈希表中进行删除操作应该给出删除标识，否则会中断检索过程中的探查序列。算法与数据结构 检索及基本算法哈希表的记录结构定义n 设哈希表的记录结构定义如下： #define m 600 /*定义表长*/ typedef struct /*定义记录结构*/ keytype key; /*关键字域*/ datatype other; /*其它数据域*/ hoshtable;算法与数据结构 检索及基本算法用线性探查法消解地址冲突算法n用线性探查法消解地址冲突的哈希检索算法可描述如下： int hoshsearch(hashtable hstable,keytype k) int i,d;

84、i=0; d=h(k); while(hstabled.key!=k)&(hstabled!=nullrecd)&(ikey!=k) p=p-link; return p; 算法与数据结构 检索及基本算法哈希表检索算法的性能分析n 由哈希表的检索过程可以看出，虽然由关键字值用哈希函数可以直接计算哈希地址，但由于地址冲突的产生，哈希表的检索过程仍然是一个给定值与关键字的比较过程。n也就是说，检索效率的度量还要用平均检索长度来衡量，平均检索长度取决于哈希函数、消解地址冲突的策略和哈希表的装填因子这三个因素。算法与数据结构 检索及基本算法哈希表检索算法的性能分析（续）n哈希函数影响地址冲突的频度，所

85、以设计一个哈希地址分布均匀的哈希函数是哈希检索的首要任务。n其次，在相同的哈希函数但处理地址冲突的方法不同时，得到的哈希表不同，其平均检索长度也不同。算法与数据结构 检索及基本算法哈希表检索算法的性能分析举例n在检索概率相等的前提下，左图的拉链法的平均检索长度为ASL=(1*8+2*3)/11=14/111.27 算法与数据结构 检索及基本算法哈希表检索算法的性能分析举例n在检索概率相等的前提下，上图的线性探查法的平均检索长度为 ASL=(1*7+2*2+4*1+5*1)=20/111.82 算法与数据结构 检索及基本算法哈希表检索算法的性能分析（续）n哈希表的装填因子定义为表中已填入的记录数

86、和表的长度之比。即： n对于哈希函数相同、处理地址冲突的方法也相同的哈希表，其平均检索长度依赖于哈希表的装填因子 ，它标志了哈希表的装满程度， 越小发生冲突的可能性就越小； 越大表中已填入的记录越多，发生冲突的可能性就越大，检索时同给定值的比较次数也就越多。 算法与数据结构 检索及基本算法哈希表检索算法的性能分析（续）n可以证明，在几种不同的解决地址冲突方法之下，哈希表的平均检索长度与装填因子之间的关系如下表所示。n可以看出，哈希表的平均检索长度是装填因子的 函数，而不是问题规模n（即记录数）的函数。由此，不管n多大，我们总可以选择一个合适的 把平均检索长度限定在一定的范围内。 算法与数据结构 检索及基本算法