2022年数据结构哈夫曼编码实验报告.docx

《2022年数据结构哈夫曼编码实验报告.docx》由会员分享，可在线阅读，更多相关《2022年数据结构哈夫曼编码实验报告.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 北京邮电高校信息与通信工程学院数据结构试验报告试验名称：试验 3树（哈夫曼编 /解码器）同学姓名：班 级：班内序号：学 号：日 期： 2022 年 12 月 5 日1试验要求利用二叉树结构实现哈夫曼编 / 解码器；基本要求：1、 初始化 Init ：能够对输入的任意长度的字符串 度,并建立哈夫曼树s 进行统计,统计每个字符的频2、 建立编码表 CreateTable ：利用已经建好的哈夫曼树进行编码,并将每个字符的编码输出；3、 编码 Encoding ：依据编码表对输入的字符串进行编码,并将编码后的字符串输出；4、 译码 Decoding ：

2、利用已经建好的哈夫曼树对编码后的字符串进行译码,并输出译码结果；5、 打印 Print：以直观的方式打印哈夫曼树（选作）运算输入的字符串编码前和编码后的长度,并进行分析,争论哈夫曼编码的压缩成效；并用 I love data Structure, I love Computer ；I will try my best to study data Structure. 进行测试；2. 程序分析哈夫曼树结点的储备结构包括双亲域parent,左子树lchild ,右子树rchild ,仍有字符word ,权重 weight ,编码 code对用户输入的信息进行统计,将每个字符作为哈夫曼树的叶子结点；

3、统计每个字符显现的次数作为叶子的权重,统计次数可以依据每个字符不同的 重建立一个哈夫曼树；建立每个叶子的编码从根结点开头,规定通往左子树路径记为ASCII 码,依据叶子结点的权 0,通往右子树路径记为1；由于编码要求从根结点开头,所以需要前序遍历哈夫曼树,故编码过程是以前序遍历二 叉树为基础的；同时留意递归函数中能否直接对结点的编码域进行操作；编码信息只要遍历字符串中每个字符,从哈夫曼树中找到相应的叶子结点,取得相应的编码；最终再将全部找到的编码连接起来即可；译码就是将编码串从左到右逐位判别,直到确定一个字符；这就是哈夫曼树的逆过程；第 1 页名师归纳总结 - - - - - - -第 1 页

4、,共 6 页精选学习资料 - - - - - - - - - 北京邮电高校信息与通信工程学院遍历编码串, 从哈夫曼树中找到相应的叶子结点,即可；2.1 储备结构 哈夫曼树结点储备结构取得相应的字符再将找到的字符连接起来parent lchild rchild word weight code 2.2 关键算法分析1. 统计字符频度自然语言描述：（1）取出字符串中的一个字符（2）遍历全部初始化的哈夫曼树结点（3）假如结点中有记录代表的字符且字符等于取出的字符,说明该字符的叶子存在,就将该结点的权值加 1 （4）假如全部结点记录的字符均没有与取出的字符一样,说明该字符的叶子不存在,就将结点的字符记

5、为取出字符,并将权重设为 1 （5）重复以上步骤,直至字符串中全部字符全部遍历伪代码描述：1. forint i=0;ilength;i+ 1.1 for int j=0;jlength;j+ 1.1.1if WordStri=HuffTreej.word/ 1.1.1.1 权重 +; 1.1.1.2 break; 如字符已被统计,就增加权值即可1.1.2 else if.HuffTreej.word/ 否就需要一个新结点储存这个字符1.1.2.1 HuffTreej.word=WordStri; 1.1.2.2 HuffTreej.weight=1;1.1.2.3 叶子结点个数 +; 1.1

6、.2.4 break; 时间复杂度On2,空间复杂度S02. 构造哈夫曼树自然语言描述：（1）选出权值最小的两个结点,其权值和作为其根结点的权值,最小的结点作为左子树,次小的作为右子树,不断将两棵子树合并为一棵树；（2）重复上述过程,直至全部结点全被遍历完伪代码描述：1. int leaves=n; 第 2 页名师归纳总结 - - - - - - -第 2 页,共 6 页精选学习资料 - - - - - - - - - 北京邮电高校信息与通信工程学院2.for int j=n;j2*n-1;j+ 2.1 int j1=0;int j2=0; 2.2 SelectHuffTree,leaves,

7、j,j1,j2;/ 选出两个权值最小结点2.3 HuffTreej1.parent=j;HuffTreej2.parent=j; 2.4 HuffTreej.weight=HuffTreej1.weight+HuffTreej2.weight;/ 根结点权值等于两个结点权值和2.5 HuffTreej.lchild=j1;HuffTreej.rchild=j2;/2.6 叶子数 -;时间复杂度On,空间复杂度S23. 为每个叶子结点编码自然语言描述：左子树为权值最小,右子树权值次小（1）初始化一个字符数组Code 暂存每个叶子结点的编码；编码相（2）前序遍历哈夫曼树-1,就将 code 复制到

8、编码的code 串,预备返回上一层,（3）如结点左右子树都为应少一位, code 长度减 1,返回（4）否就依据从左到右的次序前序遍历根结点的全部子树0；（5）如拜访左子树,就进入下一层,编码相应多一位,code 长度加 1 并将最终一位赋拜访右子树,进入下一层,code 长度加 1 并将最终一位赋为0伪代码描述：1.if 结点左右孩子均为-1 1.1.将 Code 复制到 huffTree 的 code 1.2.return; 1.3.否就 1.3.1.if 结点左子树存在 1.3.1.1.Code 长度增一 1.3.1.2.Code 最终一位赋 0；1.3.1.3.拜访左子树；1.3.1.

9、4.层数减一；1.3.2.If 结点右子树存在 1.3.2.1.Code 长度增一 1.3.2.2.Code 最终一位赋 1；1.3.2.3.拜访右子树；1.3.2.4.层数减一；S60算法时间复杂度On 2,空间复杂度4. 编码 自然语言描述：（1）定义字符串CodeStr 储存编码word 逐个比较,相同就将该结（2）遍历输入字符串的每一个字符（3）对每一个字符,将其与HuffTree 前 n 个叶子结点的（4）点的编码串code 连接到 CodeStr 的末尾遍历终止后,输出CodeStr第 3 页名师归纳总结 - - - - - - -第 3 页,共 6 页精选学习资料 - - - -

10、 - - - - - 北京邮电高校信息与通信工程学院伪代码描述：1.while 字符串字符不为0 1.1while （叶子结点word 不为空）1.1.1 if（字符等于word 中的字符）1.1.1.1 strcatCodeStr,code; 1.1.1.2.break; 2. coutCodeStrendl;算法时间复杂度On 2 ,空间复杂度S25. 译码自然语言描述：（1）从编码串CodeStr 的第一个字符开头与HuffTree 第一个结点的编码域第一个字符比较（2）相等就连续比较后面的字符（3）否就,从 CodeStr 第一个字符与 HuffTree 其次个结点的编码比较（4）重复

11、上述过程,将 CodeStr 中的全部字符比较完毕伪代码描述：1.在 CodeStr 和 huffTree.code 中设比较的起始下标 i 和 j 2. 遍历数组 huffTree 2.1.循环至 CodeStr 或 huffTree.code 全部的字符均比较完2.1.1.假如 CodeStri=huffTreek.code ,连续比较下一个字符,否就2.1.2.将 i 和 j 回溯,跳出该层循环2.2 假如 huffTreek.code 全比较完, 输出 huffTreek.word ；否就取 huffTree 下一个结点连续循环主串 CodeStr 本趟匹配开头位置i 回溯；huffT

12、reek+1 huffTreek j 回溯时间复杂度On2,空间复杂度S3第 4 页名师归纳总结 - - - - - - -第 4 页,共 6 页精选学习资料 - - - - - - - - - 北京邮电高校信息与通信工程学院3. 程序运行结果开头菜单界面 ,挑选编码器1 编码表2 3 4 5 6 退出程序解码器重新编码关于程序输入要编码输出要编码输出输入要编码输出程序信息的信息的信息编码的信息任意键操作输出编码输出编码表输出翻译输出编码的结果任意键操作出的信息的结果任意键操作任意键操作任意键操作终止测试条件：问题规模n 的数量级为1；测试内容： I love data Structure,

13、I love Computer. I will try my best to study data Structure. 测试结论：测试的功能有：建立哈夫曼树、对每个字符进行编码、对信息字符串进行编码、对编码串进行译码,重新进行编码； 各项功能均能正常运行；界面的跳转也能实现；编码前信息总长度为664bits,编码后的长度为339bits；由于哈夫曼编码采纳不等长编码,有效缩短了编码长度,节约了空间；4. 总结调试时显现的问题及解决的方法递归函数中的参数传递在给每个字符编码时,由于编码是从根结点开头,所以选用与前序遍历相像的递归遍历形式； 其中需要一个字符型数组来记录路径和编码,由于递归一次才

14、有一位编码,所以这个数组也要随着递归函数的进行而不断修改；开头时我没有用指针最为参数而是直接将数组作为参数, 结果发觉每次调用递归函数时数组都是空；原先我用的是值传递,数组就算修改了也无法返回； 这提示了我之后运用递归函数时假如需要某个变量随函数递归而修改时应当使第 5 页名师归纳总结 - - - - - - -第 5 页,共 6 页精选学习资料 - - - - - - - - - 北京邮电高校信息与通信工程学院用地址传递而非值传递；心得体会哈夫曼树又称做最优二叉树,它是 n 个带权叶子结点构成的全部二叉树中,带权路径长度 WPL 最小的二叉树；在n 个带权叶子结点所构成的二叉树中,满二叉树或

15、完全二叉树不肯定是最优二叉树；权值越大的结点离树根越近的二叉树才是最优二叉树；哈夫曼树是依据字符显现的概率来构造平均长度最短的编码；它是一种变长的编码；在编码中, 如各码字长度严格依据码字所对应符号显现概率的大小的逆序排列,就编码的平均长度是最小的；哈夫曼树的应用特别广泛,在通信中,采纳0,1 的不同排列来表示不同的字符,而哈夫曼树在数据编码中的应用,如每个字符显现的频率相同,就可以采纳等长的二进制编码,如频率不同, 就可以采纳不等长的二进编码,频率较大的采纳位数较少的编码,频率较小的字符采纳位数较多的编码,这样可以使字符的整体编码长度最小,哈夫曼编码就是一种不等长的二进制编码, 且哈夫曼树是一种最优二叉树,它的编码也是一种最优编码,在哈夫曼树中,规定往左编码为 0,往右编码为 1,就得到叶子结点编码为从根结点到叶子结点中全部路径中 0 和 1 的次序排列；下一步的改进程序中多次使用了遍历数组或对数据进行逐个比对,循环的次数可以通过运算再削减,提高时间效率；第 6 页名师归纳总结 - - - - - - -第 6 页,共 6 页