数据结构课件c语言

《数据结构课件c语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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)k1k2k3

2、k5k48.4动态查找表2——哈希表查找8.4.1哈希表的概念1.哈希查找的基本思想在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较(或进行少量比较），一次存取就能得到所查元素的查找方法。2.哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数可写成：addr(ai)=H(ki)其中：ai是表中的一个元素,addr(ai)是ai的存储地址,ki是ai的关键字3哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表(数组的推广）。4.哈

3、希查找又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。(注意到哈希表建立的时候用哈希函数）例30个地区的各民族人口统计表编号地区总人口汉族回族…...1北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=195.冲突k1k2，但H(k1)=H(k2)的现象叫冲突(Collision)，映射到同一哈希地址上的关键码称为“同义词”。0m–1h(

4、k1)h(k4)h(k3)U(universeofkeys)k1k2k3k5k4我们希望能找到尽可能产生均匀映射的哈希函数，从而尽可能降低发生冲突的概率；哈希方法需要解决以下两个问题：⑴尽量构造好的哈希函数，好的哈希函数有三个方面的含义：一是所构造的函数应该尽可能简单，以便提高哈希地址的计算速度；二是所构造的函数应该尽量减少存储空间的浪费；三是根据所选函数计算出的地址，应在哈希地址集中大致均匀分布，减少冲突。⑵制定解决冲突的方案，如果发生了冲突怎么解决。8.4.2哈希函数的构造方法1.直接定址法【构造】取关键字或关键字的某个

5、线性函数作哈希地址，即H(key)=key或H(key)=a·key+b比如：统计1-100岁的人口，用年龄做关键字，哈希函授可以就取关键字本身。【特点】直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少2.数字分析法【构造】对关键字进行分析，取关键字的若干位或其组合作哈希地址。比如：取学号某些位排定学生宿舍号。110611201楼号层号房间号【特点】适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数，怎么取合适

6、？8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址3.平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况例如，若关键码K＝1234，哈希表长为1000，则有：K2=1522756，取中间3位227作为哈希地址。4.折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分

7、的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加58640224046092H(key)=6092间界叠加5.除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=keyMODp，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产

8、生同义词例：设有关键码序列{2049，1756，0056，3187，4356，6349}若p=100，则对应的哈希地址就是关键码的后两位即49，56，56，87，56，49，很不均匀实践证明一般选取p<=m的最大质数效果比较好。6.随机数法构造：取关键字的随机函数值作哈希地址，即H(key