数据结构课件(c语言)9.ppt

1,第8章 查找,8.1 基本概念与基本运算 8.2 静态查找表 8.3 动态查找表1树表 8.4 动态查找表2哈希表查找,回顾,1 静态查找表查找的ASL是？对应的时间复杂度 2 动态树表查找的ASL，对应的时间复杂度 3 一个查找算法最理想的的时间复杂度应该是什么？ 4 在数组中按编号查找某个元素的时间复杂度是？ 5 对给定的查找表（数据元素的集合）能否把它们采用特别的方法组织到数组中呢？,把数据元素的关键码通过某种计算方法直接确它在数组中的存储位置,这样构造的数组就是哈希表,0,m1,h(k1),h(k4),h(k3),U (universe of keys),k1,k2,k3,k5,k4,8.4 动态查找表2哈希表查找,8.4.1 哈希表的概念 1. 哈希查找的基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较(或进行少量比较），一次存取就能得到所查元素的查找方法。 2. 哈希函数 在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数可写成：addr(ai)=H(ki) 其中：ai 是表中的一个元素, addr(ai)是ai的存储地址, ki 是ai的关键字,3 哈希表 应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表( 数组的推广）。,4. 哈希查找 又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。(注意到哈希表建立的时候用哈希函数）,以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2,以地区作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19,5. 冲突 k1k2，但H(k1)=H(k2)的现象叫冲突(Collision)，映射到同一哈希地址上的关键码称为“同义词”。,0,m1,h(k1),h(k4),h(k3),U (universe of keys),k1,k2,k3,k5,k4,我们希望能找到尽可能产生均匀映射的哈希函数，从而尽可能降低发生冲突的概率；哈希方法需要解决以下两个问题： 尽量构造好的哈希函数，好的哈希函数有三个方面的含义： 一是所构造的函数应该尽可能简单，以便提高哈希地址的计算速度； 二是所构造的函数应该尽量减少存储空间的浪费； 三是根据所选函数计算出的地址，应在哈希地址集中大致均匀分布，减少冲突。 制定解决冲突的方案，如果发生了冲突怎么解决。,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 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址,3. 平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况 例如，若关键码K1234，哈希表长为1000，则有：K2=1522756，取中间3位227作为哈希地址。,4. 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况,5. 除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即 H(key)=key MOD p，pm 特点 简单、常用，可与上述几种方法结合使用 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(km-1) 其中：H(key)哈希函数 m哈希表表长 di增量序列,【分类】 线性探测再散列： di=1,2,3,m-1 二次探测再散列： di=1,-1,2,-2,3,k(km/2) 伪随机探测再散列： di=伪随机数序列,例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中,(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. 再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即： Hi=Rhi(key) i=1,2,k 其中：Rhi不同的哈希函数 特点：计算时间增加,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,4 .建立一个公共溢出区 设哈希函数产生的哈希地址集为0，m-1，则分配两个表：一个基本表，每个单元只能存放一个元素；一个溢出表。 只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入溢出表中。查找时，对给定值通过哈希函数计算出哈希地址，先与基本表的单元比较，若相等，查找成功；否则，再到溢出表中进行查找。,8.4.4 哈希查找过程及分析 1. 哈希查找过程,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,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) 用链地址法处理冲突,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.key); /*求当前元素的散列地址*/ while (SeqHTbld!=0) d=(d+1)% m; SeqHTbld=*eptr; / *找到空单元，填装结点*/ eptr+; ,2 以线性探测法处理冲突构造的散列表中的查找 int ReSeqHTbl (datetype SeqHTbl , int m, keytype key) /*SeqHTbl散列表，散列函数Hash()，m为散列表的长度*/ /*查找关键码为key的元素，成功返回其地址，否则返回-1*/ int d,begin; /*求当前元素的散列地址，并将起始点记录在begin中*/ begin=d=Hash(key); while(SeqHTbld.key!=0 /*查找成功返回的是地址，不成功为-1*/ ,3 拉链法哈希表的建立 存储结构： typedef struct hnode datatype data; /*关键字*/ /*其它信息*/ struct hnode *next; /*指向下一个同义词的指针*/ HNode; 定义散列表（指针向量或指针数组）： #define m /*m为散列表的容量*/ HNode *HashTblm;,以拉链法构造散列表的算法 void CreateLHTbl(HNode *LHashTblm, datatype *eptr) /*用拉链法处理冲突建立散列表LHashTbl */ /*eptr为待放入散列表中的数据基址，Hash()为散列函数*/ int d; HNode *q; for(i=0; im; i+) LHashTbli=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=LHashTbld; /*插入到同义词的链表*/ LHashTbld=q; /注意是向前插入 eptr+; /*指向下一个元素*/ ,4 拉链法哈希表的查找 HNode *CreateLHTbl(HNode *LHashTblm, keytype key) /*LHashTbl是用拉链法处理冲突建立的散列表，散列函数为Hash()，m为散列表的长度,查找关键码为key的元素，成功返回其地址，否则返回NULL*/ int d; HNode *q; d=Hash(key); /*求当前元素的散列地址*/ q=LhashTbld; /*同义词链表的头指针*/ while (q) if(q-data.key=key) break; else q=q-next; return q; ,5 哈希表的删除