数据结构课件第九章学习教案.pptx
会计学1数据结构数据结构(sh j ji u)课件第九章课件第九章第一页，共43页。D01曲守宁数据库004S01王永燕数据结构003L01潘玉奇程序设计002S01严蔚敏数据结构001课程号课程名教师课程类别课程安排表文件(wnjin)记录(jl)数据项主关键字次关键字第1页/共43页第二页，共43页。对文件经常进行(jnxng)的操作有:1) 查询(chxn)某个“特定”的数据元素是否存在4) 对数据(shj)元素进行排序2) 插入某个数据元素3) 删除某个数据元素查找算法排序算法不管何种操作，都遵循一个重要的性质:都是对主关键字操作第2页/共43页第三页，共43页。9.1 静态(jngti)查找9.1.1 顺序(shnx)查找从表最后一个记录开始(kish)，逐个向前进行记录关键字和给定值的比较，相等，查找成功；不等，比较下一个记录；思想:直至第一个记录，若均不等，则查找不成功。第3页/共43页第四页，共43页。12. . .n-2n-1nTomAnnieJohnRoseJack查找(ch zho) John 比较(bjio) 2 次查找(ch zho) Jack 比较 n - 1 次若查找不存在比较 n 次第4页/共43页第五页，共43页。9.1.2 有序表的查找(ch zho)表中数据元素(yun s)按照主关键字顺序排列。 折半(zhbn)查找 斐波那契查找 插值查找5 ，13 ，19 ，21 ，37 ，56 ，64 ，75 ，80 ，88 ，92第5页/共43页第六页，共43页。折半(zhbn)查找5 ，13 ，19 ，21 ，37 ，56 ，64 ，75 ，80 ，88 ，92lowhighmid = ( low + high ) / 2查找(ch zho) 211 2 3 4 5 6 7 8 9 10 11midmid = 6high = mid 1 = 5highmid = 3midlow = mid + 1 = 4lowmid = 4mid找到查找 85lowhighmid = 6midlow = mid + 1 = 7lowmid = 9midlow = mid + 1 = 10lowmid = 10midhigh = mid 1 = 9highhigh low 查找(ch zho)不成功第6页/共43页第七页，共43页。9.2 动态(dngti)查找表静态查找只是对表中元素进行(jnxng)检索，返回成功或不成功；动态查找不但对表中元素进行检索，还可以通过(tnggu)检索过程来实现表的更新；检索到，则返回成功；检索不到，则将新元素插入到表中适当位置。第7页/共43页第八页，共43页。9.2.1 二叉排序(pi x)树(二叉分类树)二叉排序(pi x)树或者是一棵空树；或者是具有下列性质的二叉树： (1) 左子树上所有(suyu)结点的值均小于等于它的根结点的值； (2) 右子树上所有结点的值均大于它的根结点的值； (3) 根结点的左、右子树也分别为二叉排序树。 13 8523 1837第8页/共43页第九页，共43页。查询(chxn)操作: 13 8523 1837如何查找(ch zho)元素 5 ?555查找(ch zho)成功！第9页/共43页第十页，共43页。 13 8523 1837如何(rh)查找元素 9 ?99 9查询+插入(ch r)操作:查找不成功，执行(zhxng)插入。第10页/共43页第十一页，共43页。同一序列，不同(b tn)二叉排序树的查找性能差别很大。例， 45 , 24 , 53 , 12 , 37 , 93 452453123793122437455393O(n)O( log n +1 )第11页/共43页第十二页，共43页。为了实现(shxin)二叉排序树的平均查找长度和 log n 等数量级，需要对二叉排序树进行“平衡化”处理，即构造平衡二叉树。9.2.2 平衡(pnghng)二叉树AVL树AdelsonVelskiiLandis平衡(pnghng)二叉树或者是一棵空树，或者是具有下列性质的二叉树:其左子树和右子树的深度之差的绝对值不超过 1 ；其左子树和右子树都是平衡二叉树 ；平衡二叉树首先是一棵二叉排序树 ；第12页/共43页第十三页，共43页。例,ABCDABCDEFGABCDEFABCDFGE第13页/共43页第十四页，共43页。结点的平衡(pnghng)因子: 该结点的左子树的深度减去右子树的深度。由于平衡二叉树要求左右子树深度之差的绝对值不大于 1 ，故结点(ji din)的平衡因子只可能为 -1 、0 、1 。4524531293例，0100-1可以(ky)证明平衡二叉树的深度与 log n 同数量级。第14页/共43页第十五页，共43页。如何在二叉排序树的构造过程中实现平衡(pnghng)化从而得到平衡(pnghng)二叉树？例，序列(xli) 13 24 37 90 53 13024-1037-2-10左旋，以失去平衡结点的儿子(r zi)结点为基准。37241300090-10-1053-20-210先右旋，以失去平衡结点的儿子结点为基准。再左旋，以失去平衡结点的儿子结点为基准。53905390370-1000平衡！第15页/共43页第十六页，共43页。平衡(pnghng)二叉树调整规则:RR型: 新结点(ji din)加入到右子树的右子树中。1调整规则: 左旋，以失去平衡的结点的儿子(r zi)结点为基准，整棵子树向左下方旋转。ABBLBRAL-10-2-1BAALBLBR00第16页/共43页第十七页，共43页。LL型: 新结点(ji din)加入到左子树的左子树中。11021调整规则: 右旋，以失去平衡的结点(ji din)的儿子结点(ji din)为基准，整棵子树向右下方旋转。ABBLBRARBABRARBL00第17页/共43页第十八页，共43页。RL型: 新结点(ji din)加入到右子树的左子树中。1调整(tiozhng)规则:ABBRALCCLCR-100-211先右旋，以失去平衡的结点的儿子结点为基准(jzhn)，构造成RR型。后左旋。ACCLALBCRBR-2-1-1CBCLALACRBR0-10第18页/共43页第十九页，共43页。LR型: 新结点(ji din)加入到左子树的右子树中。1调整(tiozhng)规则:ABBLARCCLCR先左旋(zu xun)，以失去平衡的结点的儿子结点为基准，构造成LL型。后右旋。1002-11第19页/共43页第二十页，共43页。9.3 哈希表前面(qin mian)介绍的内容中，记录在文件中的存储地址是随机的。200302200305200301张三李四王五192120200305200301200302李四王五张三212019查找某一条记录(jl)需要进行一系列的“比较”。查找的效率依赖于比较(bjio)的次数。能否在记录的关键字和存储地址之间构造这样一种关系 f ，使得关键字和存储地址一一对应 ？此对应关系 f 称为哈希函数。学号姓名年龄010203第20页/共43页第二十一页，共43页。例，设关键字为年龄(ninlng)字段，H(key) = key年龄学号姓名01020356100. . . . . . . . . . . . . . . . .12356100192021192021. . . . .张三王五李四200302200301200305第21页/共43页第二十二页，共43页。1. 哈希函数(hnsh)的构造方法(1) 直接(zhji)定址法取关键字或关键字的某个线性函数(hnsh)值为哈希地址。H(key) = key (i)或 H ( key) = a key + b .(ii)(i) 例，以年龄作为关键字(ii) 例，统计解放后出生人口，以出生年份作为关键字地址出生年份011949021950231971481996. . . . . . . . . . . . .H(key) = key 1949 + 1第22页/共43页第二十三页，共43页。(2) 数字(shz)分析法对关键字进行按“位”分析(fnx)，取重复度小的若干位组合成哈希地址。例，多条记录，关键字为 8 位十进制数，要求取两位作为(zuwi)哈希地址。8 1 3 4 6 5 3 77 1 3 7 2 2 4 78 1 3 8 7 4 2 28 2 3 0 1 3 6 78 1 4 2 2 8 1 78 1 3 3 8 9 6 7取 4、5、6、7 位中的任意两位即可。第23页/共43页第二十四页，共43页。(3) 平方(pngfng)取中法取关键字平方后的中间(zhngjin)几位作为哈希函数。实验证明: 一个数字的平方(pngfng)值的中间部分通常对各位数字都比较敏感。2 0 0 5 2 42 0 0 5 0 20 1 2 0 0 50 2 2 0 0 50 3 2 0 0 5X402098745764020105200400144120025X20048422002501024320025209820101441取4位48420243第24页/共43页第二十五页，共43页。(4) 折叠(zhdi)法将关键字从低到高分割成位数相同(xin tn)的几部分，然后取各部分的叠加和(舍去进位)作为哈希函数。例， 图书(tsh)编号 0 442 20586 4 0 4 4 2 2 0 5 8 6 45 8 6 44 2 2 00 4+)1 0 0 8 8最终取四位 0 0 8 8 作为哈希地址。第25页/共43页第二十六页，共43页。(5) 除留余数(ysh)法H(key) = key mod p例， 关键字 28 33 68 82 107p = 21哈希地址(dzh)7125192第26页/共43页第二十七页，共43页。(6) 随机数法取关键字的随机(su j)函数值作为哈希地址。H(key) = random (key)总结(zngji):灵活运用协同工作第27页/共43页第二十八页，共43页。2. 哈希冲突(chngt)对于不同的关键字可能得到(d do)同一哈希地址，即 key1 key2 ，而 f(key1) f(key2) ，这种现象称为哈希冲突。造成(zo chn)原因:A. 主观设计不当例，数字分析法中8 1 3 4 6 5 3 77 1 3 7 2 2 4 78 1 3 8 7 4 2 28 2 3 0 1 3 6 78 1 4 2 2 8 1 78 1 3 3 8 9 6 7冲突！第28页/共43页第二十九页，共43页。例，除留余数(ysh)法中关键字 28 35 63 77 105p = 21哈希地址(dzh)7140140解决(jiju)方法:因地制宜提高素质第29页/共43页第三十页，共43页。B. 客观存在如何设计都不可能(knng)完全避免冲突的出现 ？哈希地址是有限的，而记录(jl)是无限的。解决(jiju)方法:(1) 开放定址法(2) 再哈希法(3) 链地址法(4) 建立一个公共溢出区第30页/共43页第三十一页，共43页。(1) 开放(kifng)定址法H(key) = ( key ) mod m在 key mod m 的基础上，若发现冲突(chngt)，则使用增量 di 进行新的探测，直至无冲突(chngt)出现为止。H(key) 哈希函数(hnsh)m 哈希表长di 增量序列关键如何设计 di 线性探测法二次探测法随机探测法H(key) = ( key + di ) mod m第31页/共43页第三十二页，共43页。线性探测(tnc)法 di = 1 , 2 , 3 , , m-1随机(su j)探测法 di = 随机(su j)数 二次探测法 di = 12 , -12 , 22 , -22 , 32 , , +k2-例，关键字为 ( 17 , 60 , 29 , 38 ) ，哈希表长 11 ，H(key)=key%11初始(ch sh)，0 1 2 3 4 5 6 7 8 9 10176029线性探测法38冲突d = 1 冲突d = 2 冲突d = 3 无冲突38二次探测法d = 1 冲突d= -1 无冲突38随机探测法 不妨设第一次随机数为 9d = 9 无冲突38第32页/共43页第三十三页，共43页。(2) 再哈希法定义双重(shungchng)哈希函数。H(key)R (key)若H(key)出现冲突，则再使用R (key)求取(qi q)哈希地址。第33页/共43页第三十四页，共43页。第34页/共43页第三十五页，共43页。第35页/共43页第三十六页，共43页。第36页/共43页第三十七页，共43页。第37页/共43页第三十八页，共43页。第38页/共43页第三十九页，共43页。第39页/共43页第四十页，共43页。第40页/共43页第四十一页，共43页。第41页/共43页第四十二页，共43页。第42页/共43页第四十三页，共43页。
