索引结构与散列技术.ppt

2023/10/21,1,第11章 索引结构与散列技术,2023/10/21,2,第11章 索引结构与散列技术,查找的基本概念索引结构散列技术习题,2023/10/21,3,查找的基本概念,查找：给定值k，在n个记录中查找一个其关键字等于给定值的记录。若存在这样一个记录，则查找成功；否则查找失败。关键字：数据元素中某个数据项的值，用以标识一个数据元素。主关键字：可唯一地标识一个数据元素的关键字。次关键字：用以识别若干记录的关键字。使用基于主关键字的查找，查找结果应是唯一的。,2023/10/21,4,线性表的查找 顺序查找（线性查找）查找过程：从表的一端开始查找，顺序用各记录的关键字与给定值x进行比较，若找到与其值相等的元素，则查找成功，给出该记录在表中的位置；否则，若直到最后一个记录仍未找到关键字与x相等的对象，则查找失败。线性表可以是顺序存储结构或链式存储结构，可以是有序表或无序表。二分查找（折半查找）线性表必须是顺序存储结构，并且是有序表。具体查找方法在第12章中介绍。,2023/10/21,5,顺序查找算法 typedef struct keytype key;/关键字 datatype other;/其他域 table;table Rn+1;int SEQSEARCH(table R,keytype k)/在R中从后向前顺序查找关键字为k的结点/查找成功，函数返回向量下标，失败返回1 int i;R0.key=k;/R0作为监视哨使用 i=n;/从表尾开始向前扫描 while(Ri.key!=k)i-;if(i=0)return(1);/若i等于0，则是监视哨本身的比较使循环结束 else return i;/SEQSEARCH,2023/10/21,6,算法分析表中原始关键字：26 5 37 1 61 11 59 15 48 19输入希望查找的关键字值：k=37 R0.key=37 第一次查找：R10.key=19，不等于k，继续查找 第二次查找：R 9.key=48，不等于k，继续查找 第三次查找：R 8.key=15，不等于k，继续查找 第四次查找：R 7.key=59，不等于k，继续查找 第五次查找：R 6.key=11，不等于k，继续查找 第六次查找：R 5.key=61，不等于k，继续查找 第七次查找：R 4.key=1，不等于k，继续查找 第八次查找：R 3.key=37，等于k，查找成功 查找结果：要查的数据在表中的3号位置。,2023/10/21,7,输入希望查找的关键字值：k=25 R0.key=25 第1次查找：R10.key=19，不等于k，继续查找 第2次查找：R 9.key=48，不等于k，继续查找 第3次查找：R 8.key=15，不等于k，继续查找 第4次查找：R 7.key=59，不等于k，继续查找 第5次查找：R 6.key=11，不等于k，继续查找 第6次查找：R 5.key=61，不等于k，继续查找 第7次查找：R 4.key=1，不等于k，继续查找 第8次查找：R 3.key=37，不等于k，继续查找 第9次查找：R 2.key=5，不等于k，继续查找 第10次查找：R 1.key=26，不等于k，继续查找 第11次查找：R 0.key=25，等于k，查找失败,2023/10/21,8,顺序查找的平均查找长度,设查找第 i 个元素的概率为 pi，查找到第 i 个元素所需比较次数为 ci，则查找成功的平均查找长度:,在顺序查找情况下，ci=n-i+1,i=1,n，因此,在等概率情况下，pi=1/n,i=1,2,n。,2023/10/21,9,11.1 索引结构,索引结构包括两部分：索引表和数据表索引表指示结点与其存储位置之间的关系，每个索引项包括关键字和地址。数据表存储结点信息。11.1.1 线性索引线性索引：索引表为线性表稠密索引：每个索引项对应数据表中的一个记录稀疏索引：每个索引项对应数据表中的一组记录,2023/10/21,10,若索引表是顺序存储结构并且是有序表，对索引表可以采用顺序查找或折半查找。分块查找 分块查找也称索引顺序查找。进行分块查找时，除数据表本身以外，尚需建立一个“索引表”。,2023/10/21,11,数据表有序或者分块有序。“分块有序”是指第i+1个子表中所有记录的关键字值均大于第i个子表的，而块内无序。索引表存放每块中最大的记录的关键字和块的起始地址，索引表按关键字值有序。若块的长度不等长，在索引表中还需存放块的长度或块的终端地址。分块查找需分两步进行，即先使用顺序查找或折半查找算法确定待查记录所在的块，然后在块内使用顺序查找算法查找所需的记录。分块查找算法：typedef int keytype;typedef struct keytype key;/块的最大关键字 int start,end;/块的起、终点 IDtable;/索引表结点类型,2023/10/21,12,typedef struct keytype key;/记录的关键字项 datatype other;/记录的其他数据项 table;/数据表结点类型int BLKSERCH(table R,IDtable ID,keytype k,int bn)/R为数据表，ID为索引表，k为所要查找的关键字，bn为索引表长度 int i,j;IDbn.key=k;i=0;while(kIDi.key)i+;/从前向后顺序查找索引表 if(i=bn)printf(“查找不到”);return(-1);/在索引表中查找不到 else j=IDi.start;while(jIDi.end)j=-1；/在块内查找不到 return j;,2023/10/21,13,11.1.2 倒排表针对记录的主关键字建立主索引，次关键字建立次索引。主索引指示所有记录，次索引值是具有相同属性的记录。先通过搜索次索引确定该记录的主关键字，再通过搜索主索引确定记录的存放地址。如图11-311.1.3 多级索引若索引表很大，可以建立多级索引表，索引表中有一级索引、二级索引、如图11-4,2023/10/21,14,11.2 散列技术,hash表的查找采用计算寻址的方式进行查找，查找效率与比较次数无关或关系较小，所以查找的效率较高。11.2.1 散列表的概念构造hash表：以结点的关键字k为自变量，通过一个确定的函数关系f，计算出对应的hash函数值f(k)，把这个值解释为结点的存储地址（hash地址），将结点存入f(k)所指的存储位置上。查找hash表：根据给定值k，计算hash函数值f(k),得到hash地址，然后在指定的存储位置上取所查找的记录。用散列法存储的线性表叫散列表或哈希表。通常散列表的存储空间是一个一维数组，数组的长度m应大于结点的个数n。装填因子=n/m。通常0.65 0.9，越小，产生冲突的可能性就越小。,2023/10/21,15,冲突：对于两个不同的关键字，得到相同的hash地址，即key1key2，而f(key1)=f(key2),这种现象称为冲突。一般情况下，冲突不可避免，但选择合适的hash函数可以减少冲突的发生，而且还要采取一种解决冲突的方法。例：关键字序列:at,as,be,can,cat,for,face,force hash函数：H(key)=key0-a（key0存放关键字的第一个字母）例如关键字at、as的hash地址都是0。H(at)=0、H(as)=0 产生冲突,2023/10/21,16,11.2.2 散列函数的构造,构造hash函数的原则：运算尽可能简单能使一组关键字的hash地址均匀分布在整个地址空间上，从而减少冲突。常用的构造hash函数的方法，可以采用数字选择法、平方取中法、折叠法、除留余数法、基数转换法、随机数法等。,2023/10/21,17,数字选择法若关键字的位数比散列表的地址位数多，则可选取数字分布比较均匀的若干位作为散列地址。,散列地址1：取第4、6、7位散列地址2：取第4、6位与第7、8位之和并舍去进位,2023/10/21,18,平方取中法先通过关键字的平方值扩大差别，然后，再取中间的几位或其组合作为散列地址。例如：关键字集合(0100,0110,1010,1001,0111)的平方结果是(0010000,0012100,1020100,1002001,0012321)若表长为1000，则可取中间三位作为散列地址集是(100,121,201,020,123),2023/10/21,19,折叠法若关键字位数较多，也可将关键字分割成位数相同的几段（最后一段的位数可以不同），段的长度取决于散列表的地址位数，然后将各段的叠加和（舍去进位）作为散列地址。折叠法又分移位叠加和边界叠加两种。移位叠加是将各段的最低位对齐，然后相加；边界叠加则是两个相邻的段沿边界来回折叠，然后对齐相加。例如关键字key=58242324169，散列表长度为1000，则将此关键字分成三位一段，两种叠加结果如下：移位叠加 边界叠加 582 582 423 324 241 241+69+96 1315 1243 H(key)=315 H(key)=243,2023/10/21,20,除留余数法基本思想：选择适当的正整数p，用p去除关键字，取所得余数作为散列地址，即：H(key)=key%p一般地选p为小于或等于散列表长度m的某个最大素数比较好。例如：m=8,16,32,64,128,256,512,1024p=7,13,31,61,127,251,503,1019,2023/10/21,21,基数转换法基本思想：把关键字看成是另一个进制上的数后，再把它转换成原来进制上的数，取其中的若干位作为散列地址。一般取大于原来基数的数作为转换的基数，并且两个基数要互素。例如：给定一个十进制数的关键字为(210485)10，我们把它看成以15为基数的十五进制(210485)15，再把它转换为十进制：(210485)15=2155+1154+0153+4152+815+5=(771932)10假设散列表长度10000，则可取低四位1932作为散列地址。,2023/10/21,22,随机数法选择一个随机函数，取关键字的随机函数值为它的散列地址，即 H(key)=random(key)其中：random为随机函数。,2023/10/21,23,11.2.3 解决冲突的方法,选择合适的散列函数可以减少冲突，但不能避免冲突，还需要具有解决冲突的方法。开放地址法当发生冲突时，使用某种方法在散列表中形成一个探查序列，沿着此序列逐个单元进行查找，直到找到一个空的单元时将新结点放入。探查序列包括：线性探查法二次探查法随机探查法,选择不同的开放地址法，散列地址的“堆积”程度不同。,2023/10/21,24,线性探查法,线性探查法的基本思想是：散列表的长度为m，将散列表看成是一个环形表，若发生冲突的单元地址为d，则依次探查d+1,d+2,m1,0,1,d1，直到找到一个空单元为止。开放地址公式为：di=(d+i)%m(1im1)其中d=H(key)。已知一组关键字集(26,36,41,38,44,15,68,12,06,51,25)，用线性探查法解决冲突，试构造这组关键字的散列表。关键字个数n=11，取=0.75，散列表长度m=n/=15。散列函数为：H(key)%13,2023/10/21,25,二次探查法,二次探查法的探查序列依次是：12,12,22,22,等，也就是说，发生冲突时，将同义词来回散列在第一个地址d=H(key)的两端。由此可知，发生冲突时，求下一个开放地址的公式为：d2i1=(d+i2)%m d2i=(di2)%m(1i(m1)/2),2023/10/21,26,随机探查法,采用一个随机数作为地址位移计算下一个单元地址，即求下一个开放地址的公式为：di=(d+Ri)%m(1im1)其中：d=H(key)，R1,R2，,Rm-1是1,2,，m1的一个随机排列。,2023/10/21,27,拉链法,将所有关键字为同义词的结点链接到同一个单链表中。若选定的散列函数的值域为0到m1，则可将散列表定义为一个由m个头指针组成的指针数组HTPm，凡是散列地址为i的结点，均插入到以HTPi为头指针的单链表中。拉链法不会产生散列地址的“堆积”现象。例：已知一组有11个关键字的集(26,36,41,38,44,15,68,12,06,51,25)，用拉链法解决冲突，试构造这组关键字的散列表。取，m=n/=15，取p=13 散列表为HT13 散列函数为：H(key)%13,2023/10/21,28,散列表的查找算法,利用线性探查法解决冲突的查找和插入算法如下：#define nil 0/nil为空结点标记#define m 18/这时假设表长m为18typedef struct/散列表结点结构 keytype key;datatype other;hashtable;hashtable HTm;/散列表 int LINSRCH(HT,k)/在散列表Hm中查找关键字为k的结点hashtable HT;keytype k;int d,i=0;/i为冲突时的地址增量 d=H(k);/d为散列地址 while(im)/结点存在或表满/插入,2023/10/21,29,散列表的查找算法,利用链地址法解决冲突的查找和插入算法如下：typedef struct nodetype keytype key;datatype other;struct nodetype next;chainhash;chainhash HTCm;chainhash CHNSRCH(HTC,k)/在散列表HTCm中查找关键字为k的结点chainhash HTC;keytype k;chainhash p;p=HTCH(k);/取k所在链表的头指针 while(p/插入s,2023/10/21,30,散列表的查找说明,散列表的平均查找长度与表长度无关，而顺序查找和折半查找的平均查找长度与表长度有关，因此散列表的查找效率较高。拉链法由于不存在冲突的“堆积”现象，因此在散列表的几种方法中查找效率最高。,2023/10/21,31,习题,1、2、5、6、7、8、10、12、13,