数据结构课件(c措辞)9.ppt

1回顾把数据元素的关键码通过某种计算方法直接确它在数组中的存储位置8.4动态查找表2——哈希表查找4.哈希查找
又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。(注意到哈希表建立的时候用哈希函数）8.4.2哈希函数的构造方法2.数字分析法例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数，怎么取合适？3.平方取中法
构造：取关键字平方后中间几位作哈希地址
适于不知道全部关键字情况

例如，若关键码K＝1234，哈希表长为1000，则有：K2=1522756，取中间3位227作为哈希地址。5.除留余数法
构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即
H(key)=keyMODp，pm
特点
简单、常用，可与上述几种方法结合使用
p的选取很重要；p选的不好，容易产生同义词【选取哈希函数应考虑的因素】

计算哈希函数所需时间
关键字长度
哈希表长度（哈希地址范围）
关键字分布情况
记录的查找频率8.4.3处理冲突的方法例表长为11的哈希表中已填有关键字为17，60，29的记录，
H(key)=keyMOD11,现有第4个记录，其关键字为38，
按三种处理冲突的方法，将它填入表中2.再哈希法
方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,……k
其中：Rhi——不同的哈希函数
特点：计算时间增加例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为：H(key)=keyMOD13,
用链地址法处理冲突8.4.4哈希查找过程及分析
1.哈希查找过程2.哈希查找分析
哈希查找过程仍是一个给定值与关键字进行比较的过程
评价哈希查找效率仍要用ASL
哈希查找过程与给定值进行比较的关键字的个数取决于：
哈希函数
处理冲突的方法
哈希表的填满因子
=表中填入的记录数/哈希表长度例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为：H(key)=keyMOD13,哈希表长为m=16，
设每个记录的查找概率相等(2)用链地址法处理冲突8.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