资源描述
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(universeofkeys),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)=keyH(1)=1H(2)=2,以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19,5.冲突k1k2，但H(k1)=H(k2)的现象叫冲突(Collision)，映射到同一哈希地址上的关键码称为“同义词”。,0,m1,h(k1),h(k4),h(k3),U(universeofkeys),k1,k2,k3,k5,k4,我们希望能找到尽可能产生均匀映射的哈希函数，从而尽可能降低发生冲突的概率；哈希方法需要解决以下两个问题：尽量构造好的哈希函数，好的哈希函数有三个方面的含义：一是所构造的函数应该尽可能简单，以便提高哈希地址的计算速度；二是所构造的函数应该尽量减少存储空间的浪费；三是根据所选函数计算出的地址，应在哈希地址集中大致均匀分布，减少冲突。制定解决冲突的方案，如果发生了冲突怎么解决。,8.4.2哈希函数的构造方法,1.直接定址法【构造】取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=akey+b比如：统计1-100岁的人口，用年龄做关键字，哈希函授可以就取关键字本身。【特点】直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少,2.数字分析法,【构造】对关键字进行分析，取关键字的若干位或其组合作哈希地址。比如：取学号某些位排定学生宿舍号。110611201楼号层号房间号【特点】适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。,例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数，怎么取合适？,分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址,3.平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况例如，若关键码K1234，哈希表长为1000，则有：K2=1522756，取中间3位227作为哈希地址。,4.折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况,5.除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=keyMODp，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词,例：设有关键码序列2049，1756，0056，3187，4356，6349若p=100，则对应的哈希地址就是关键码的后两位即49，56，56，87，56，49，很不均匀实践证明一般选取pdata.key);/*求当前元素的散列地址*/while(SeqHTbld!=0)d=(d+1)%m;SeqHTbld=*eptr;/*找到空单元，填装结点*/eptr+;,2以线性探测法处理冲突构造的散列表中的查找intReSeqHTbl(datetypeSeqHTbl,intm,keytypekey)/*SeqHTbl散列表，散列函数Hash()，m为散列表的长度*/*查找关键码为key的元素，成功返回其地址，否则返回-1*/intd,begin;/*求当前元素的散列地址，并将起始点记录在begin中*/begin=d=Hash(key);while(SeqHTbld.key!=0/*查找成功返回的是地址，不成功为-1*/,3拉链法哈希表的建立存储结构：typedefstructhnodedatatypedata;/*关键字*/*其它信息*/structhnode*next;/*指向下一个同义词的指针*/HNode;定义散列表（指针向量或指针数组）：#definem/*m为散列表的容量*/HNode*HashTblm;,以拉链法构造散列表的算法voidCreateLHTbl(HNode*LHashTblm,datatype*eptr)/*用拉链法处理冲突建立散列表LHashTbl*/*eptr为待放入散列表中的数据基址，Hash()为散列函数*/intd;HNode*q;for(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+;/*指向下一个元素*/,4拉链法哈希表的查找HNode*CreateLHTbl(HNode*LHashTblm,keytypekey)/*LHashTbl是用拉链法处理冲突建立的散列表，散列函数为Hash()，m为散列表的长度,查找关键码为key的元素，成功返回其地址，否则返回NULL*/intd;HNode*q;d=Hash(key);/*求当前元素的散列地址*/q=LhashTbld;/*同义词链表的头指针*/while(q)if(q-data.key=key)break;elseq=q-next;returnq;,5哈希表的删除,当在散列表上删除一个元素时，首先是查找，查找成功情况下才能做删除。对于拉链法解决冲突构造的散列表，其删除等价于单链表上的删除；对于开放地址法解决冲突构造的散列表，不能简单的将删除元素所在单元置为空，这样做会断掉原来的探测地址序列，查找后面的元素将受到影响，删除这个元素可以将这个单元置为有别于空单元表示的特殊值（如-1），在查找时当遇到这个特殊值，继续探测序列上的查找，而插入时遇到这个值则可以作为一个空单元将新元素插入。,本章小结作业1.应用题page198四、应用题的第2题和第5题2.设计题page198五、设计题的第1题和第5题,
展开阅读全文