数据结构课件c语言.ppt

《数据结构课件c语言.ppt》由会员分享，可在线阅读，更多相关《数据结构课件c语言.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第8 8章章 查找查找1第第8章章 查找查找8.1 基本概念与基本运算基本概念与基本运算8.2 静态查找表静态查找表 8.3 动态查找表动态查找表1树表树表 8.4 动态查找表动态查找表2哈希表查找哈希表查找 第第8 8章章 查找查找回顾回顾1 静态查找表查找的静态查找表查找的ASL是？对应的时间复杂度是？对应的时间复杂度2 动态树表查找的动态树表查找的ASL，对应的时间复杂度，对应的时间复杂度3 一个查找算法最理想的的时间复杂度应该是什么？一个查找算法最理想的的时间复杂度应该是什么？4 在数组中按编号查找某个元素的时间复杂度是？在数组中按编号查找某个元素的时间复杂度是？5 对给定的查找表（

2、数据元素的集合）能否把它们采对给定的查找表（数据元素的集合）能否把它们采用特别的方法组织到数组中呢？用特别的方法组织到数组中呢？第第8 8章章 查找查找把把数据元素的关键码数据元素的关键码通过通过某种计算某种计算方法直接确它在方法直接确它在数组中的数组中的存储位置存储位置这样构造的数组就是这样构造的数组就是哈希表哈希表0m1h(k1)h(k4)h(k3)U(universe of keys)k1k2k3k5k4第第8 8章章 查找查找8.4 动态查找表动态查找表2哈希表查找哈希表查找 8.4.1 哈希表的概念哈希表的概念1.哈希查找的基本思想哈希查找的基本思想 在记录的在记录的存储地址存储地址

3、和它的和它的关键字关键字之间建立一个确定的之间建立一个确定的对应对应关系关系；这样不经过比较；这样不经过比较(或进行少量比较），一次存取就能或进行少量比较），一次存取就能得到所查元素的查找方法。得到所查元素的查找方法。2.哈希函数哈希函数 在记录的关键字与记录的存储地址之间建立的一种对应关在记录的关键字与记录的存储地址之间建立的一种对应关系叫系叫哈希函数哈希函数。哈希函数可写成：哈希函数可写成：addr(ai)=H(ki)其中：其中：ai 是表中的一个元素是表中的一个元素,addr(ai)是是ai的存储地址的存储地址,ki 是是ai的关键字的关键字第第8 8章章 查找查找3 哈希表哈希表 应用

4、哈希函数，由记录的关键字确定记录在应用哈希函数，由记录的关键字确定记录在表中的表中的地址地址，并将记录放入此地址，这样构成，并将记录放入此地址，这样构成的表叫的表叫哈希表哈希表(数组的推广）。数组的推广）。第第8 8章章 查找查找4.哈希查找哈希查找 又叫散列查找，利用哈希函数进行查找的过程叫又叫散列查找，利用哈希函数进行查找的过程叫哈希哈希查找。查找。(注意到哈希表建立的时候用哈希函数）注意到哈希表建立的时候用哈希函数）例例 30个地区的各民族人口统计表个地区的各民族人口统计表编号编号 地区地区 总人口总人口 汉族汉族 回族回族.1 北京北京2 上海上海.以编号作关键字，以编号作关键字，构造

5、构造哈希函数：哈希函数：H(key)=keyH(1)=1H(2)=2以地区作关键字，取地区以地区作关键字，取地区名称第一个拼音字母的序号名称第一个拼音字母的序号作哈希函数：作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19第第8 8章章 查找查找5.冲突冲突 k1 k2，但但H(k1)=H(k2)的现象叫的现象叫冲突冲突(Collision)，映射到同一哈希地址上的关键码称，映射到同一哈希地址上的关键码称为为“同义同义词词”。0m1h(k1)h(k4)h(k3)U(universe of keys)k1k2k3k5k4第第8 8章章 查找查找 我们

6、希望能找到尽可能我们希望能找到尽可能产生均匀映射的产生均匀映射的哈希函数，哈希函数，从而尽可能降低发生冲突的概率；哈希方法需要解决从而尽可能降低发生冲突的概率；哈希方法需要解决以下两个问题：以下两个问题：尽量构造好的哈希函数，尽量构造好的哈希函数，好的哈希函数有三个方面的好的哈希函数有三个方面的含义：含义：一是一是所构造的函数应该尽可能简单，以便提高哈希地所构造的函数应该尽可能简单，以便提高哈希地址的计算速度；址的计算速度；二是二是所构造的函数应该尽量减少存储空间的浪费；所构造的函数应该尽量减少存储空间的浪费；三是三是根据所选函数计算出的地址，应在哈希地址集中根据所选函数计算出的地址，应在哈希

7、地址集中大致均匀分布，减少冲突。大致均匀分布，减少冲突。制定解决冲突的方案，如果发生了冲突怎么解决。制定解决冲突的方案，如果发生了冲突怎么解决。第第8 8章章 查找查找 8.4.2 哈希函数的构造方法哈希函数的构造方法1.直接定址法直接定址法【构造】取关键字或关键字的某个线性函数作哈希地址，即取关键字或关键字的某个线性函数作哈希地址，即 H(key)=key 或或 H(key)=akey+b 比如：统计比如：统计1-100岁的人口，用年龄做关键字，哈希函授可以岁的人口，用年龄做关键字，哈希函授可以就取关键字本身。就取关键字本身。【特点】直接定址法所得地址集合与关键字集合大小相等，不会直接定址法

8、所得地址集合与关键字集合大小相等，不会发生冲突发生冲突实际中能用这种哈希函数的情况很少实际中能用这种哈希函数的情况很少第第8 8章章 查找查找2.数字分析法数字分析法【构造构造】对对关键字关键字进行分析，取关键字的若干位或其组合作哈进行分析，取关键字的若干位或其组合作哈希地址。希地址。比如：取学号某些位排定学生宿舍号。比如：取学号某些位排定学生宿舍号。11 0611 2 01 楼号楼号 层号层号 房间号房间号【特点特点】适于关键字位数比哈希地址位数大，且可能出现的关适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。键字事先知道的情况。第第8 8章章 查找查找例例 有有80个记录

9、，关键字为个记录，关键字为8位十进制数，哈位十进制数，哈希地址为希地址为2位十进制数，怎么取合适？位十进制数，怎么取合适？8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.分析：分析：只取只取8 只取只取1 只取只取3、4 只取只取2、7、5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位任意两位或两位 与另两位的叠加作哈希地址与另两位的叠加作哈希地址第第8 8章章 查找查找3.平方取中

10、法平方取中法n构造：取关键字平方后中间几位作哈希地址构造：取关键字平方后中间几位作哈希地址n适于不知道全部关键字情况适于不知道全部关键字情况n例如，若关键码例如，若关键码K1234，哈希表长为，哈希表长为1000，则有：，则有：K2=1522756，取中间，取中间3位位227作为哈希地址。作为哈希地址。第第8 8章章 查找查找4.折叠法折叠法n构造：将关键字分割成位数相同的几部分，然后构造：将关键字分割成位数相同的几部分，然后取这几部分的取这几部分的叠加叠加和（舍去进位）做哈希地址和（舍去进位）做哈希地址n种类种类移位叠加移位叠加：将分割后的几部分低位对齐相加：将分割后的几部分低位对齐相加间界

11、叠加间界叠加：从一端沿分割界来回折送，然后：从一端沿分割界来回折送，然后对齐相加对齐相加n适于关键字位数很多，且每一位上数字分布大致适于关键字位数很多，且每一位上数字分布大致均匀情况均匀情况第第8 8章章 查找查找例例 关键字为关键字为：0442205864，哈希地址位数为，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加第第8 8章章 查找查找5.除留余数法除留余数法n构造：取关键字被某个不大于哈希表表长取关键字被某个不大于哈希表表长m的数的数p除

12、后所得余数作哈希地址，即除后所得余数作哈希地址，即 H(key)=key MOD p，p mn特点u简单、常用，可与上述几种方法结合使简单、常用，可与上述几种方法结合使用用up的选取很重要；的选取很重要；p选的不好，容易产生选的不好，容易产生同义词同义词第第8 8章章 查找查找例：设有关键码序列例：设有关键码序列2049，1756，0056，3187，4356，6349 若若p=100，则对应的哈希地址就是关键码的则对应的哈希地址就是关键码的后两位即后两位即49，56，56，87，56，49，很不均匀，很不均匀实践证明实践证明 一般选取一般选取 p=m的最大质数效果比较好。的最大质数效果比较好

13、。第第8 8章章 查找查找6.随机数法随机数法n构造：取关键字的随机函数值作取关键字的随机函数值作哈希地址哈希地址，即H(key)=random(key)n适于关键字长度不等的情况第第8 8章章 查找查找【选取哈希函数应考虑的因素选取哈希函数应考虑的因素】n计算哈希函数所需时间计算哈希函数所需时间n关键字长度关键字长度n哈希表长度（哈希地址范围）哈希表长度（哈希地址范围）n关键字分布情况关键字分布情况n记录的查找频率记录的查找频率第第8 8章章 查找查找8.4.3 处理冲突的方法处理冲突的方法1 开放定址法开放定址法2 再哈希方法再哈希方法3 拉链方法拉链方法4 建立公共溢出区建立公共溢出区第

14、第8 8章章 查找查找1.开放定址法开放定址法【方法方法】当冲突发生时，形成一个探查序列；沿此当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即地址），将发生冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD m，i=1,2,k(k m-1)其中：其中：H(key)哈希函数哈希函数 m哈希表表长哈希表表长 di增量序列增量序列第第8 8章章 查找查找【分类】线性探测再散列：线性探测再散列：di=1,2,3,m-1二次探测再散列：二次探测再散列：di=1,-1,2,-2,

15、3,k(k m/2)伪随机探测再散列：伪随机探测再散列：di=伪随机数序列伪随机数序列第第8 8章章 查找查找 例例 表长为表长为1111的哈希表中已填有关键字为的哈希表中已填有关键字为1717，6060，2929的记录，的记录，H(key)=key MOD 11,H(key)=key MOD 11,现有第现有第4 4个记录，其关键字为个记录，其关键字为3838，按三种处理冲突的方法，将它填入表中按三种处理冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1)H(38)=38 MOD 11=5 冲突冲突 H1=(5+1)MOD 11=6 冲突冲突 H2=(5

16、+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第第8 8章章 查找查找2.再哈希法再哈希法n方法方法：构造若干个哈希函数，当发生冲构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,k其中：其中：

17、Rhi不同的哈希函数不同的哈希函数n特点特点：计算时间增加计算时间增加第第8 8章章 查找查找3.链地址法（拉链法）链地址法（拉链法）n方法方法：将所有关键字为同义词的将所有关键字为同义词的记录存储在一个单链表中，并用记录存储在一个单链表中，并用一维数组存放头指针一维数组存放头指针第第8 8章章 查找查找例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：哈希函数为：H(key)=key MOD 13,H(key)=key MOD 13,用链地址法处理冲突用

18、链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011第第8 8章章 查找查找4.建立一个公共溢出区建立一个公共溢出区 设哈希函数产生的哈希地址集为设哈希函数产生的哈希地址集为0，m-1，则分配，则分配两个表：一个两个表：一个基本表基本表，每个单元只能存放一个元素；，每个单元只能存放一个元素；一个一个溢出表溢出表。只要关键码对应的哈希地址在基本表上产生冲突，只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入溢出表中。查找时，对则所有这样的元素一律存入溢出表中。查找时，对给定值通过哈希函数计算出哈希地址，先与基本

19、表给定值通过哈希函数计算出哈希地址，先与基本表的单元比较，若相等，查找成功；否则，再到溢出的单元比较，若相等，查找成功；否则，再到溢出表中进行查找。表中进行查找。第第8 8章章 查找查找8.4.4 哈希查找过程及分析哈希查找过程及分析1.哈希查找过程哈希查找过程给定给定k值值计算计算H(k)此地址为空此地址为空关键字关键字=k查找失败查找失败查找成功查找成功按处理冲突按处理冲突方法计算方法计算HiYNYN第第8 8章章 查找查找2.哈希查找分析哈希查找分析n哈希查找过程仍是一个给定值与关键字进行比较的过程哈希查找过程仍是一个给定值与关键字进行比较的过程n评价哈希查找效率仍要用评价哈希查找效率仍

20、要用ASLn哈希查找过程与给定值进行比较的关键字的个数取决于：哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数哈希函数处理冲突的方法处理冲突的方法哈希表的填满因子哈希表的填满因子 =表中填入的记录数表中填入的记录数/哈希表长度哈希表长度第第8 8章章 查找查找例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：哈希函数为：H(key)=key MOD 13,哈希表长为哈希表长为m=16，设每个记录的查找概率相等设每个记录的查找概率相等(1)用线性探测再散列处理冲突，即用线性探测再散列处理冲突，即Hi=(H(key)+d

21、i)MOD mH(55)=3 冲突，冲突，H1=(3+1)MOD16=4 冲突，冲突，H2=(3+2)MOD16=5H(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=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12

22、=2.514 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(23)=10H(1)=1 冲突，冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6 冲突，冲突，H1=(6+1)MOD16=7 冲突，冲突，H2=(6+2)MOD16=8H(27)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，冲突，H1=(10+1)MOD16=11 冲突，冲突，H2=(10+2)MOD16=12第第8 8章章 查找

23、查找(2)用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字关键字(19,14,23,1,68,20,84,27,55,11,10,79)第第8 8章章 查找查找8.4.5 哈希表算法实现哈希表算法实现1 线性探测哈希表的建立线性探测哈希表的建立2 线性探测哈希表的查找线性探测哈希表的查找3 拉链哈希表的建立拉链哈希表的建立4 拉链哈希表的查找拉链哈希表的查找5 哈希表的删除哈希表的删除第第8 8章章 查找查找1 线性探测哈希表的建立线性探测哈希表的

24、建立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)

25、d=(d+1)%m;SeqHTbld=*eptr;/*找到空单元，填装结点找到空单元，填装结点*/eptr+;第第8 8章章 查找查找2 2 以线性探测法处理冲突构造的散列表中的查找以线性探测法处理冲突构造的散列表中的查找int ReSeqHTbl(datetype SeqHTbl,int m,keytype key)/*SeqHTbl散列表，散列函数散列表，散列函数Hash()，m为散列表的长度为散列表的长度*/*查找关键码为查找关键码为key的元素，成功返回其地址，否则返回的元素，成功返回其地址，否则返回-1*/int d,begin;/*求当前元素的散列地址，并将起始点记录在求当前元素的

26、散列地址，并将起始点记录在begin中中*/begin=d=Hash(key);while(SeqHTbld.key!=0&SeqHTbld.key!=key)d=(d+1)%m;if(d=begin)d=-1;break;/*表满且查找失败表满且查找失败*/if(SeqHTbld.key=0)d=-1;/*找到空单元，查找失败找到空单元，查找失败*/return d;/*查找成功返回的是地址，不成功为查找成功返回的是地址，不成功为-1*/第第8 8章章 查找查找3 3 拉链法哈希表的建立拉链法哈希表的建立 存储结构：存储结构：typedeftypedef structstruct hnode

27、hnode datatypedatatype data;data;/*/*关键字关键字*/*/*其它信息其它信息*/structstruct hnodehnode*next;/*next;/*指向下一个同义词的指针指向下一个同义词的指针*/HNodeHNode;定义散列表（定义散列表（指针向量或指针向量或指针数组指针数组）：）：#define m /*m#define m /*m为散列表的容量为散列表的容量*/HNodeHNode*HashTblmHashTblm;第第8 8章章 查找查找以拉链法构造散列表的算法以拉链法构造散列表的算法void CreateLHTbl(HNode*LHashT

28、blm,datatype*eptr)/*用拉链法处理冲突建立散列表用拉链法处理冲突建立散列表LHashTbl*/*eptr为待放入散列表中的数据基址，为待放入散列表中的数据基址，Hash()为散列函数为散列函数*/int d;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;/

29、*填装结点信息填装结点信息*/;q-next=LHashTbld;/*插入到同义词的链表插入到同义词的链表*/LHashTbld=q;/注意是向前插入注意是向前插入 eptr+;/*指向下一个元素指向下一个元素*/第第8 8章章 查找查找 4 拉链法哈希表的查找拉链法哈希表的查找 HNode*CreateLHTbl(HNode*LHashTblm,keytype key)/*LHashTbl是用拉链法处理冲突建立的散列表，散列函数为是用拉链法处理冲突建立的散列表，散列函数为Hash()，m为散列为散列表的长度表的长度,查找关键码为查找关键码为key的元素，成功返回其地址，否则返回的元素，成功返

30、回其地址，否则返回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 8章章 查找查找5 哈希表的删除哈希表的删除 当在散列表上删除一个元素时，当在散列表上删除一个元素时，首先是查找首先是查找，查找成功情况下才能做删除。查找成功情况下才能做删除。对于拉链法对于拉链法解决冲突构造的散列表，其删解决冲突构造的散列表，其删除等价于单链表上的删除；除等价于单链

31、表上的删除；对于开放地址法对于开放地址法解决冲突构造的散列表，解决冲突构造的散列表，不能简单的将删除元素所在单元置为空，这样不能简单的将删除元素所在单元置为空，这样做会断掉原来的探测地址序列，做会断掉原来的探测地址序列，查找后面的元查找后面的元素将受到影响，删除这个元素可以将这个单元素将受到影响，删除这个元素可以将这个单元置为有别于空单元表示的特殊值（如置为有别于空单元表示的特殊值（如-1-1），在），在查找时当遇到这个特殊值，继续探测序列上的查找时当遇到这个特殊值，继续探测序列上的查找，而插入时遇到这个值则可以作为一个空查找，而插入时遇到这个值则可以作为一个空单元将新元素插入。单元将新元素插入。第第8 8章章 查找查找本章小结本章小结 作业作业 1.应用题应用题 page 198 四、应用题的第四、应用题的第2题和第题和第5题题 2.设计题设计题 page 198 五、设计题的第五、设计题的第1题和第题和第5题题