《数据结构课件(c语言)9》由会员分享，可在线阅读，更多相关《数据结构课件(c语言)9（39页珍藏版）》请在金锄头文库上搜索。
1、第8章 查找1第8章 查找8.1 基本概念与基本运算8.2 静态查找表 8.3 动态查找表1树表 8.4 动态查找表2哈希表查找 第8章 查找回顾 1 静态查找表查找的ASL是？对应的时间复杂度 2 动态树表查找的ASL，对应的时间复杂度 3 一个查找算法最理想的的时间复杂度应该是什么？ 4 在数组中按编号查找某个元素的时间复杂度是？ 5 对给定的查找表（数据元素的集合）能否把它们采用特别的方法组织到数组中呢？第8章 查找把数据元素的关键码通过某种计算方法直接确它在数组中的 存储位置 这样构造的数组就是哈希表0m1h(k1)h(k4)h(k3)U (universe of keys)k1k2k
2、3k5k4第8章 查找 8.4 动态查找表2哈希表查找 8.4.1 哈希表的概念1. 哈希查找的基本思想在记录的存储地址和它的关键字之间建立一个确定的对 应关系；这样不经过比较(或进行少量比较），一次存取就能得到所查元素的查找方法。2. 哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数可写成：addr(ai)=H(ki)其中：ai 是表中的一个元素, addr(ai)是ai的存储地址, ki 是ai的关键字第8章 查找 3 哈希表 应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成 的表叫哈希表( 数组的推广）。第8章 查找4. 哈希
3、查找又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。(注意到哈希表建立的时候用哈希函数） 例 30个地区的各民族人口统计表编号 地区 总人口 汉族 回族. 1 北京2 上海.以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2以地区作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19第8章 查找5. 冲突k1k2，但H(k1)=H(k2)的现象叫冲突(Collision) ，映射到同一哈希地址上的关键码称为“同义词 ”。 0m1h(k1)h(k4)h(k3)U (universe
4、 of keys)k1k2k3k5k4第8章 查找我们希望能找到尽可能产生均匀映射的哈希函数，从而尽可能降低发生冲突的概率；哈希方法需要解决 以下两个问题： 尽量构造好的哈希函数，好的哈希函数有三个方面的含义：一是所构造的函数应该尽可能简单，以便提高哈希地址的计算速度；二是所构造的函数应该尽量减少存储空间的浪费；三是根据所选函数计算出的地址，应在哈希地址集中大致均匀分布，减少冲突。 制定解决冲突的方案，如果发生了冲突怎么解决。 第8章 查找8. 4.2 哈希函数的构造方法 1. 直接定址法 【构造】取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+b
5、比如：统计1-100岁的人口，用年龄做关键字，哈希函授可 以就取关键字本身。 【特点】 直接定址法所得地址集合与关键字集合大小相等，不会 发生冲突 实际中能用这种哈希函数的情况很少第8章 查找2. 数字分析法【构造】对关键字进行分析，取关键字的若干位或其组合作哈希地址。比如：取学号某些位排定学生宿舍号。11 0611 2 01楼号 层号 房间号【特点】适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。第8章 查找例 有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
6、 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数字分布近乎随机 所以：取任意两位或两位与另两位的叠加作哈希地址第8章 查找3. 平方取中法n构造：取关键字平方后中间几位作哈希地址n适于不知道全部关键字情况n例如，若关键码K1234，哈希表长为1000，则有：K2=1522756，取中间3位227作为哈希地址。第8章 查找4. 折叠法n构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址n种类移位叠加：将
7、分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加n适于关键字位数很多，且每一位上数字分布大致均匀情况第8章 查找例 关键字为 ：0442205864，哈希地址位数为45 8 6 4 4 2 2 0 0 4 1 0 0 8 8H(key)=0088移位叠加5 8 6 4 0 2 2 4 0 46 0 9 2H(key)=6092间界叠加第8章 查找5. 除留余数法n构造：取关键字被某个不大于哈希表表长 m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pmn特点u简单、常用，可与上述几种方法结合使用up的选取很重要；p选的不好，容易产生同义词第8章 查找
8、 例：设有关键码序列2049，1756，0056，3187，4356，6349 若p = 100， 则对应的哈希地址就是关键码的后两位即49，56，56，87，56，49，很不均匀 实践证明 一般选取 pdata.key!=0) /*待放入散列表的元素，其关键码0表示结束*/d= Hash(eptr-data.key); /*求当前元素的散列地址*/while (SeqHTbld!=0) d=(d+1)% m;SeqHTbld=*eptr; / *找到空单元，填装结点*/eptr+;第8章 查找 2 以线性探测法处理冲突构造的散列表中的查找 int ReSeqHTbl (datetype Se
9、qHTbl , int m, keytype key) /*SeqHTbl散列表，散列函数Hash()，m为散列表的长度*/*查找关键码为key的元素，成功返回其地址，否则返回-1*/int d,begin; /*求当前元素的散列地址，并将起始点记录在begin中*/begin=d=Hash(key); while(SeqHTbld.key!=0 if (d=begin) d=-1; break; /*表满且查找失败*/if (SeqHTbld.key=0) d=-1; /*找到空单元，查找失败*/return d; /*查找成功返回的是地址，不成功为-1*/ 第8章 查找3 拉链法哈希表的建
10、立存储结构：typedef struct hnode datatype data; /*关键字*/ /*其它信息*/struct hnode *next; /*指向下一个同义词的指针*/HNode;定义散列表（指针向量或指针数组）：#define m /*m为散列表的容量*/HNode *HashTblm; 第8章 查找以拉链法构造散列表的算法void CreateLHTbl(HNode *LHashTblm, datatype *eptr) /*用拉链法处理冲突建立散列表LHashTbl */*eptr为待放入散列表中的数据基址，Hash()为散列函数*/int d; HNode *q;fo
11、r(i=0; idata.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+; /*指向下一个元素*/第8章 查找 4 拉链法哈希表的查找HNode *CreateLHTbl(HNode *LHashTblm, keytype ke
12、y)/*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;第8章 查找5 哈希表的删除当在散列表上删除一个元素时，首先是查找 ，查找成功情况下才能做删除。对于拉链法解决冲突构造的散列表，其删 除等价于单链表上的删除；对于开放地址法解决冲突构造的散列表， 不能简单的将删除元素所在单元置为空，这样 做会断掉原来的探测地址序列，查找后面的元 素将受到影响，删除这个元素可以将这个单元 置为有别于空单元表示的特殊值（如-1），在 查找时当遇到这个特殊值，继续探测序列上的 查找，而插入时遇到这个值则可以作为一个空 单元将新元素插入。第8章 查找 本章小结 作业1. 应用题page 198 四、应用题的第2题和第5题2. 设计题page 198 五、设计题的第1题和第5题
