NOIp数据结构.ppt

堆栈、队列、树形结构;栈;栈;栈的应用;分析;栈的应用;;;例题三：最长词链;;分析;;算法框架;;栈的应用;表达式：3 × ( 5 – 2 ) + 7 @;算法流程;算法框架;队列;队列;队列的应用;算法框架;队列的其它应用;牙医诊所;二叉树;多叉树转二叉树;多叉转二叉的例子;几类特殊的树形结构;哈夫曼树;哈夫曼树;构造二叉哈夫曼树;哈夫曼树应用;假设英文原串中的字符存放于字符集Ｓ中，‖Ｓ‖＝　Ｘ，每个字符在字串中出现的概率为Ｗ［ｉ］，Ｌ［ｉ］为字符ｉ的编码长． 　　依题意得，对Ｓ集合中的不同字符进行Ｎ进制编码后要求 １）新字串的码长最短　　 ＷＰＬ＝∑Ｗ［ｉ］＊Ｌ［ｉ］ （ｉ∈１．．Ｘ） 使得在ＷＰＬ是所有编码方式中的最小值 ２）编码无二义性 任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的．Ｎ为此哈夫曼树的分叉数，Ｓ字符集里的元素即为此　　 Ｎ叉哈夫曼树的叶子，概率Ｗ［ｉ］即为叶子结点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长Ｌ［ｉ］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短． ;但具体应该怎样建立起此Ｎ叉哈夫曼树呢？ 2叉哈夫曼树已经讲过，我们来看3叉。 Ｎ＝３时又是怎样一种情况呢？ 设　Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝ 　　Ｗ＝［７，４，２，５，３｝ 则按权重排序可得 　　Ｓ＝｛Ａ，Ｄ，Ｂ，Ｅ，Ｃ｝　　　　　 　　Ｗ＝［７，５，４，３，２］;那么此哈夫曼树的树形应为怎样呢？　　是以下的左图，还是右图，或是两者均不是 　　　　　 　?　　　　　　　　　　　　　　 　? 　　 ? ? ?　　　　　　　　 　　　　　? 　? 　　　　 ? 　? 　?　　　　　　　　　　　?　　 ? 　　　 ?? ??　 A　　　　　　　　　　Ａ 　?　?　　　　　　　　 　　　? 　? ?　?　　　　　　　　　　　　　　　　?　 ? 　　 D　 　B E　 C 　　　　　　　　　 Ｄ ?　? 　　　　　　　　　　　　　　 　 ? ? 　　　　　　　　　　　　　　　　　　　　　　　 　　　Ｂ　　?　? 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　? 　 ? 　　　　　　　　　　　　　　　　　　　　　　　　　　　　 Ｅ　 Ｃ;显然，要带权路径长ＷＰＬ最短，那么，此树的高度就应尽可能的小，由此可知将此树建成 丰满Ｎ叉树是最合理的，于是我们尽量使树每一层都为Ｎ个分枝． 这样，我们得到了初步算法。;类似2叉哈夫曼树，我们把每次取2个改成每次取3个，对于 Ｓ＝｛Ａ，Ｄ，Ｂ，Ｅ，Ｃ｝　　　　　 　　Ｗ＝［７，５，４，３，２］ 我们进行如下操作： ;哈夫曼树应用;7;思考： 我们发现对于这种情况恰巧每层均为Ｎ个分枝，但事实上并非所有的Ｎ叉哈夫曼树都可得到每层Ｎ个分枝．例于当Ｎ＝３，‖Ｓ‖＝６时就不可能构成一棵每层都为三个分枝的三叉树．如何来处理这种情况呢 ？;最简单的处理方式就是添加若干出现概率为０的空字符填补在Ｎ叉树的最下一层，这些权为０的虚结点并无实际意义但却非常方全便于这棵Ｎ叉树的建立．空字符的添加个数ａｄｄ的计算如下： 　　Ｙ＝‖Ｓ‖　ｍｏｄ　（ｎ－１） 　　ａｄｄ＝０　　　（Ｙ＝１）　　　 　　ａｄｄ＝１　　　（Ｙ＝０） 　　ａｄｄ＝Ｎ－Ｙ　（Ｙ＞１）　　 　　虚结点的加入使得权重最小的Ｎ－ａｄｄ个字符构成了距根结点最远的分枝，使其它字符构成的Ｎ叉树保持了丰满的Ｎ叉结构．;例：　Ｎ＝３　 　　　　　Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ｝ 　　　　　Ｗ＝［１，２，３，４，５，６｝;由此可知，对于N叉二叉树我们也可以类似处理。;堆;堆;堆(以小根堆为例);算法描述（建堆）;堆——选择与维护;算法描述（堆排序）;堆排序算法;堆的应用;堆的应用;堆的应用;注意到，每次合并完果子会删掉两堆，并添加一堆新的，如果采用线性表，时间复杂度将高达O（N^2），对于N=20000是不够的。 所以，我们考虑用小根堆优化。;算法： 建立空堆 每读入一个数插入堆中 每次取两个堆顶元素合并，并插入合并后的数，总共合并n-1次。;用堆优化dijstra算法;例题分析;例题分析;例题分析;例题分析;二叉有哪些信誉好的足球投注网站树;二叉有哪些信誉好的足球投注网站树;二叉排序树用于动态查找;查找相信大家都想得到。 根据性质只要每次查找时，符合则退出，否则就在左孩子（查找值小于当前值）