数据结构c语言9课件

1第8章查找

8.1基本概念与基本运算8.2静态查找表8.3动态查找表1——树表8.4动态查找表2——哈希表查找

回顾1静态查找表查找的ASL是？对应的时间复杂度2动态树表查找的ASL，对应的时间复杂度3一个查找算法最理想的的时间复杂度应该是什么？4在数组中按编号查找某个元素的时间复杂度是？5对给定的查找表（数据元素的集合）能否把它们采用特别的方法组织到数组中呢？把数据元素的关键码通过某种计算方法直接确它在数组中的存储位置这样构造的数组就是哈希表0m–1h(k1)h(k4)h(k3)U(universeofkeys)k1k2k3k5k43哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表(数组的推广）。4.哈希查找又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。(注意到哈希表建立的时候用哈希函数）例30个地区的各民族人口统计表编号地区总人口汉族回族…...1北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=195.冲突

k1k2，但H(k1)=H(k2)的现象叫冲突(Collision)，映射到同一哈希地址上的关键码称为“同义词”。

0m–1h(k1)h(k4)h(k3)U(universeofkeys)k1k2k3k5k48.4.2哈希函数的构造方法1.直接定址法【构造】

取关键字或关键字的某个线性函数作哈希地址，即

H(key)=key或H(key)=a·key+b

比如：统计1-100岁的人口，用年龄做关键字，哈希函授可以就取关键字本身。【特点】直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少2.数字分析法【构造】

对关键字进行分析，取关键字的若干位或其组合作哈希地址。

比如：取学号某些位排定学生宿舍号。

110611201

楼号层号房间号【特点】

适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数，怎么取合适？8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址4.折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092间界叠加5.除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即

H(key)=keyMODp，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词6.随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)适于关键字长度不等的情况【选取哈希函数应考虑的因素】计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率8.4.3处理冲突的方法1开放定址法2再哈希方法3拉链方法4建立公共溢出区【分类】线性探测再散列：

di=1,2,3,……m-1二次探测再散列：

di=1²,-1²,2²,-2²,3²,……±k²(km/2)伪随机探测再散列：

di=伪随机数序列例表长为11的哈希表中已填有关键字为17，60，29的记录，

H(key)=keyMOD11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中012345678910601729(1)H(38)=38MOD11=5冲突

H1=(5+1)MOD11=6冲突

H2=(5+2)MOD11=7冲突

H3=(5+3)MOD11=8不冲突

38(2)H(38)=38MOD11=5冲突

H1=(5+1²)MOD11=6冲突

H2=(5-1²)MOD11=4不冲突38(3)H(38)=38MOD11=5冲突设伪随机数序列为9，则：

H1=(5+9)MOD11=3不冲突382.再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：

Hi=Rhi(key)i=1,2,……k其中：Rhi——不同的哈希函数特点：计算时间增加例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函数为：H(key)=keyMOD13,

用链地址法处理冲突0123456789101112

14^127796855198420231011^^^^^^^^^^^^4.建立一个公共溢出区

设哈希函数产生的哈希地址集为[0，m-1]，则分配两个表：一个基本表，每个单元只能存放一个元素；一个溢出表。只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入溢出表中。查找时，对给定值通过哈希函数计算出哈希地址，先与基本表的单元比较，若相等，查找成功；否则，再到溢出表中进行查找。

例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函数为：H(key)=keyMOD13,

哈希表长为m=16，

设每个记录的查找概率相等(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MODmH(55)=3冲突，H1=(3+1)MOD16=4

冲突，H2=(3+2)MOD16=5H(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=90123456789101112131415ASL=(1*6+2+3*3+4+9)/12=2.514

168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6冲突，H1=(6+1)MOD16=7

冲突，H2=(6+2)MOD16=8H(27)=1冲突，H1=(1+1)MOD16=2

冲突，H2=(1+2)MOD16=3

冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10冲突，H1=(10+1)MOD16=11

冲突，H2=(10+2)MOD16=12(2)用链地址法处理冲突0123456789101112

14^127796855198420231011^^^^^^^^^^^^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线性探测哈希表的建立voidCreateSeqHTbl(datetypeSeqHTbl[],intm,datatype*eptr){/*用线性探测法处理冲突建立散列表SeqHTbl*//*eptr为待放入散列表中的数据基址*//*Hash()为散列函数，m为散列表的长度*/

intd;for(i=0;i<m;i++)SeqHTbl[i]=0;/*散列表初始化，设0表示空*/while(eptr->data.key!=0){/*待放入散列表的元素，其关键码0表示结束*/d=Hash(eptr->data.key);/*求当前元素的散列地址*/ while(SeqHTbl[d]!=0)d=(d+1)%m;SeqHTbl[d]=*eptr;/*找到空单元，填装结点*/eptr++;} }2以线性探测法处理冲突构造的散列表中的查找intReSeqHTbl(datetypeSeqHTbl[],intm,keytypekey){/*SeqHTbl散列表，散列函数Hash()，m为散列表的长度*//*查找关键码为key的元素，成功返回其地址，否则返回-1*/intd,begin;/*求当前元素的散列地址，并将起始点记录在begin中*/begin=d=Hash(key);while(SeqHTbl[d].key!=0&&SeqHTbl[d].key!=key){d=(d+1)%m; if(d==begin){d=-1;break;}/*表满且查找失败*/

}if(SeqHTbl[d].key==0)d=-1;/*找到空单元，查找失败*/returnd;/*查找成功返回的是地址，不成功为-1*/}3拉链法哈希表的建立存储结构：

typedefstructhnode{datatypedata; /*关键字*/… /*其它信息*/structhnode*next;/*指向下一个同义词的指针*/}HNode;

定义散列表（指针向量或指针数组）：

#definem…/*m为散列表的容量*/HNode*HashTbl[m];

以拉链法构造散列表的算法voidCreateLHTbl(HNode*LHashTbl[m],datatype*eptr){

/*用拉链法处理冲突建立散列表LHashTbl*//*eptr为待放入散列表中的数据基址，Hash()为散列函数*/

intd;HNode*q;

for(i=0;i<m;i++)LHashTbl[i]=NULL;/*散列表初始化*/

while(eptr->data.key!=0) {/*待放入散列表的元素，其关键码0表示结束*/d=Hash(eptr->data.key);/*求当前元素的散列地址*/ q=(HNode*)malloc(sizeof(HNode));/*申请新结点*/ q->data.key=eptr->data.key; /*填装结点信息*/…;

q->next=LHashTbl[d];/*插入到同义词的链表*/LHashTbl[d]=q; //注意是向前插入 eptr++; /*指向下一个元素*/ }}