数据结构课件c语言

,第二级,第三级,第,8,章 查找,*,1,第,8,章 查找,8.1,基本概念与基本运算,8.2,静态查找表,8.3,动态查找表,1,树表,8.4,动态查找表,2,哈希表查找,回顾,1,静态查找表查找的,ASL,是？对应的时间复杂度,2,动态树表查找的,ASL,，对应的时间复杂度,3,一个查找算法最理想的的时间复杂度应该是什么？,4,在数组中按编号查找某个元素的时间复杂度是？,5,对给定的查找表（数据元素的集合）能否把它们采用特别的方法组织到数组中呢？,把,数据元素的关键码,通过,某种计算,方法直接确它在,数组中的存储位置,这样构造的数组就是,哈希表,0,m,1,h,(,k,1,),h,(,k,4,),h,(,k,3,),U,(,universe of keys),k,1,k,2,k,3,k,5,k,4,8.4,动态查找表,2,哈希表查找,8.4.1,哈希表的概念,1.,哈希查找的基本思想,在记录的,存储地址,和它的,关键字,之间建立一个确定的,对应关系,；这样不经过比较,(,或进行少量比较），一次存取就能得到所查元素的查找方法。,2.,哈希函数,在记录的关键字与记录的存储地址之间建立的一种对应关系叫,哈希函数,。,哈希函数可写成：,addr(a,i,)=H(k,i,),其中：,a,i,是表中的一个元素,addr(a,i,),是,a,i,的存储地址,k,i,是,a,i,的关键字,3,哈希表,应用哈希函数，由记录的关键字确定记录在表中的,地址,，并将记录放入此地址，这样构成的表叫,哈希表,(,数组的推广）。,4.,哈希查找,又叫散列查找，利用哈希函数进行查找的过程叫,哈希查找。,(,注意到哈希表建立的时候用哈希函数）,例,30,个地区的各民族人口统计表,编号 地区 总人口 汉族 回族,.,1,北京,2,上海,.,.,以编号作关键字，,构造,哈希函数：,H(key)=key,H(1)=1,H(2)=2,以地区作关键字，取地区,名称第一个拼音字母的序号,作哈希函数：,H(Beijing)=2,H(Shanghai)=19,H(Shenyang)=19,5,.,冲突,k1,k2,，,但,H(k1)=H(k2),的现象叫,冲突,(Collision),，映射到同一哈希地址上的关键码称,为“同义词”。,0,m,1,h,(,k,1,),h,(,k,4,),h,(,k,3,),U,(,universe of keys),k,1,k,2,k,3,k,5,k,4,我们希望能找到尽可能,产生均匀映射的,哈希函数，从而尽可能降低发生冲突的概率；哈希方法需要解决以下两个问题：,尽量构造好的哈希函数，,好的哈希函数有三个方面的含义：,一是,所构造的函数应该尽可能简单，以便提高哈希地址的计算速度；,二是,所构造的函数应该尽量减少存储空间的浪费；,三是,根据所选函数计算出的地址，应在哈希地址集中大致均匀分布，减少冲突。,制定解决冲突的方案，如果发生了冲突怎么解决。,8.4.2,哈希函数的构造方法,1.,直接定址法,【,构造,】,取关键字或关键字的某个线性函数作哈希地址，即,H(key)=key,或,H(key)=akey+b,比如：统计,1-100,岁的人口，用年龄做关键字，哈希函授可以就取关键字本身。,【特点】,直接定址法所得地址集合与关键字集合大小相等，不会发生冲突,实际中能用这种哈希函数的情况很少,2.,数字分析法,【,构造,】,对,关键字,进行分析，取关键字的若干位或其组合作哈希地址。,比如：取学号某些位排定学生宿舍号。,11 0611 2 01,楼号 层号 房间号,【,特点,】,适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。,例 有,80,个记录，关键字为,8,位十进制数，哈希地址为,2,位十进制数，怎么取合适？,8 1 3 4 6 5 3 2,8 1 3 7 2 2 4 2,8 1 3 8 7 4 2 2,8 1 3 0 1 3 6 7,8 1 3 2 2 8 1 7,8 1 3 3 8 9 6 7,8 1 3 6 8 5 3 7,8 1 4 1 9 3 5 5,.,.,分析：,只取,8,只取,1,只取,3,、,4,只取,2,、,7,、,5,数字分布近乎随机,所以：取任意两位或两位,与另两位的叠加作哈希地址,3.,平方取中法,构造：取关键字平方后中间几位作哈希地址,适于不知道全部关键字情况,例如，若关键码,K,1234,，哈希表长为,1000,，则有：,K2=15,227,56,，取中间,3,位,227,作为哈希地址。,4.,折叠法,构造：将关键字分割成位数相同的几部分，然后取这几部分的,叠加,和（舍去进位）做哈希地址,种类,移位叠加,：将分割后的几部分低位对齐相加,间界叠加,：从一端沿分割界来回折送，然后对齐相加,适于关键字位数很多，且每一位上数字分布大致均匀情况,例 关键字为：,0442205864,，哈希地址位数为,4,5 8 6 4,4 2 2 0,0 4,1,0 0 8 8,H(key)=0088,移位叠加,5 8 6 4,0 2 2 4,0 4,6 0 9 2,H(key)=6092,间界叠加,5.,除留余数法,构造：,取关键字被某个不大于哈希表表长,m,的数,p,除后所得余数作哈希地址，即,H(key)=key MOD p,，,p,m,特点,简单、常用，可与上述几种方法结合使用,p,的选取很重要；,p,选的不好，容易产生同义词,例：设有关键码序列2049，1756，0056，3187，4356，6349 若p=100，则对应的哈希地址就是关键码的后两位即49，56，56，87，56，49，很不均匀,实践证明 一般选取 p=m的最大质数效果比较好。,6.,随机数法,构造：,取关键字的随机函数值作哈希地址,，即,H(key,)=,random(key,),适于关键字长度不等的情况,【,选取哈希函数应考虑的因素,】,计算哈希函数所需时间,关键字长度,哈希表长度（哈希地址范围）,关键字分布情况,记录的查找频率,8.4.3,处理冲突的方法,1,开放定址法,2,再哈希方法,3,拉链方法,4,建立公共溢出区,1.,开放定址法,【,方法,】,当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即,Hi=(H(key)+di)MOD m,，,i=1,2,k(k,m-1),其中：,H(key),哈希函数,m,哈希表表长,di,增量序列,【,分类,】,线性探测再散列：,d,i,=1,2,3,m-1,二次探测再散列：,d,i,=1,-1,2,-2,3,k(km/2),伪随机探测再散列：,d,i,=,伪随机数序列,例 表长为,11,的哈希表中已填有关键字为,17,，,60,，,29,的记录，,H(key)=key MOD 11,现有第4个记录，其关键字为38，,按三种处理冲突的方法，将它填入表中,0 1 2 3 4 5 6 7 8 9 10,60 17 29,(,1,)H(38)=38 MOD 11=5,冲突,H1=(5+1)MOD 11=6,冲突,H2=(5+2)MOD 11=7,冲突,H3=(5+3)MOD 11=8,不冲突,38,(,2,)H(38)=38 MOD 11=5,冲突,H1=(5+1,)MOD 11=6,冲突,H2=(5-1,)MOD 11=4,不冲突,38,(,3,)H(38)=38 MOD 11=5,冲突,设伪随机数序列为,9,，则：,H1=(5+9)MOD 11=3,不冲突,38,2.,再哈希法,方法,：,构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：,H,i,=,Rh,i,(key,)i=1,2,k,其中：,Rh,i,不同的哈希函数,特点,：,计算时间增加,3.,链地址法（拉链法）,方法,：,将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针,例 已知一组关键字,(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数为：,H(key)=key MOD 13,用链地址法处理冲突,0 1 2 3 4 5 6 7 8 9 10 11 12,14,1,27,79,68,55,19,84,20,23,10,11,4.,建立一个公共溢出区,设哈希函数产生的哈希地址集为,0,，,m-1,，则分配两个表：一个,基本表,，每个单元只能存放一个元素；一个,溢出表,。,只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入溢出表中。查找时，对给定值通过哈希函数计算出哈希地址，先与基本表的单元比较，若相等，查找成功；否则，再到溢出表中进行查找。,8.4.4,哈希查找过程及分析,1.,哈希查找过程,给定,k,值,计算,H(k),此地址为空,关键字,=k,查找失败,查找成功,按处理冲突,方法计算,Hi,Y,N,Y,N,2.,哈希查找分析,哈希查找过程仍是一个给定值与关键字进行比较的过程,评价哈希查找效率仍要用,ASL,哈希查找过程与给定值进行比较的关键字的个数取决于：,哈希函数,处理冲突的方法,哈希表的填满因子,=,表中填入的记录数,/,哈希表长度,例 已知一组关键字,(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数为：,H(key)=key MOD 13,哈希表长为,m=16,，,设每个记录的查找概率相等,(1),用线性探测再散列处理冲突，即,Hi=(H(key)+di)MOD m,H(,55,)=3,冲突，,H1=(3+1)MOD16=4,冲突，,H2=(3+2)MOD16=5,H(,79,)=1,冲突，,H1=(1+1)MOD16=2,冲突，,H2=(1+2)MOD16=3,冲突，,H3=(1+3)MOD16=4,冲突，,H4=(1+4)MOD16=5,冲突，,H5=(1+5)MOD16=6,冲突，,H6=(1+6)MOD16=7,冲突，,H7=(1+7)MOD16=8,冲突，,H8=(1+8)MOD16=9,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,ASL=(,1,*6+,2,+,3,*,3,+,4,+,9,)/,12,=2.5,14,1,68,27,55,19,20,84,79,23,11,10,H(,19,)=6,H(,14,)=1,H(,23,)=10,H(,1,)=1,冲突，,H1=(1+1)MOD16=2,H(,68,)=3,H(,20,)=7,H(,84,)=6,冲突，,H1=(6+1)MOD16=7,冲突，,H2=(6+2)MOD16=8,H(,27,)=1,冲突，,H1=(1+1)MOD16=2,冲突，,H2=(1+2)MOD16=3,冲突，,H3=(1+3)MOD16=4,H(,11,)=11,H(,10,)=10,冲突，,H1=(10+1)MOD16=11,冲突，,H2=(10+2)MOD16=12,(2),用链地址法处理冲突,0 1 2 3 4 5 6 7 8 9 10 11 12,14,1,27,79,68,55,19,84,20,23,10,11,ASL=(,1,*6+,2,*,4+3,+,4,)/,12,=1.75,关键字,(19,14,23,1,68,20,84,27,55,11,10,79),8.4.5,哈希表算法实现,1,线性探测哈希表的建立,2,线性探测哈希表的查找,3,拉链哈希表的建立,4,拉链哈希表的查找,5,哈希表的删除,1,线性探测哈希表的建立,void CreateSeqHTbl(datetype SeqHTbl,int m,datatype*eptr),/*,用,线性探测法,处理冲突建立散列表,SeqHTbl*/,/*eptr,为待放入散列表中的,数据基址,*,/,/*Hash(),为散列函数，,m,为散列表的长度*,/,int d;,for(i=0;idata.key!=0),/*,待放入散列表的元素，其关键码,0,表示结束*,/,d=Hash(eptr-data