《数据结构》课件第五章.ppt

*写哈夫曼树的算法（哈夫曼树是否唯一？）*PPT改，由于哈夫曼树不是唯一的，编码也不唯一理解意思是最重要的*为什么需要15个空间？（结点个数来算）第五步：选择23，19141578292923428531119第六步：选择29，2958141578292923428531119第六步：选择42，5810058141578292923428531119赫夫曼树的构造算法weightlchildrchildparent判定结点是否已加入设置一个结构组HuffNode保存赫夫曼树中各结点的信息。因为赫夫曼树没有度为1的结点，所以有n个叶结点的赫夫曼树有2n-1个结点。数组设置大小为2n-1将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中。根据构造赫夫曼树的方法，不断地将两个小子树合并为较大的子树，每次构成的新子树的根结点顺序放入HuffNode数组中的前n个分量后面WPrLchRch500029000700080001400023000300011000123456789101112131415WPrLchRch5900290007000800014000230003900110008017123456789101112131415123456789101112131415WPrLchRch5900290007000800014000230003900110008017123456789101112131415WPrLchRch59002900071000810001400023000390011000801715034WPrLchRch59002900071000810001400023000390011000801715034123456789101112131415123456789101112131415WPrLchRch590029000710008100014000230003900111100811171503419089151413121110987654321RchLchPrW000110003000230001400080007000290005RchLchPrW1413010012215581161542105142998131943121571118001111009300132300121400108001070014290095151413121110987654321哈夫曼树的静态链表生成算法主程序子程序Typedefstruct{Unsignedintweight;Unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;Typedefchar**HuffmanCode;赫夫曼树的应用1.得到最佳判定算法——判定树同个问题，不同判定过程，不同的比较次数2.哈夫曼编码赫夫曼编码编码的定义：将文件中的每个字符均转换为一个唯一的二进制串等长编码（例）：优点易于翻译，缺点利用率不高不等长编码（例）：优点存储容量小，缺点不易翻译，不好断句赫夫曼编码的过程构造一棵赫夫曼树选取权最小的两棵树合并（左右子树的确定按照存储位置的先后决定）重复上述工作，一直到集合中为一棵树为止在赫夫曼树上求叶结点的编码（左子树编码为0，右子树编码为1）以一个四元组依次存放每个结点rchildLchild