哈夫曼编码译码器课程设计

课程设计说明书课程名称：数据结构和算法设计主题：哈夫曼篇解码器本科：计算机科学与信息工程学院学生名称：刘文杰学位：专业班：软件工程16-2指导教师：孙飞2017年12月11日设计主题霍夫曼编码/解码器限定人数3问题的说明用哈夫曼编码思想实现字符串编码和编码译码。 字符串的长度至少为5000字节。读取要编码的文本文件，对文件内容进行编码，生成新文件。 解码编码的文件并获取文本文件。 将解码的文本文件与原始文件进行比较时，恢复文件与原始文件必须完全匹配。设置字符集和频率，如下表所示文字空间a.a乙组联赛c.cd.def.fghI日本职业足球联赛Klm频率1866413223210321154757153220文字no.opq.qrst.tuvwxyz轴频率5763151485180238181161基本要求和说明1、基于霍夫曼编码原理构建霍夫曼编码并创建了霍夫曼编码集2 .读取文本文件，对文件内容进行编码，生成编码后的文件3 .解码编码的文件并获取恢复文件4 .比较恢复文件和原始文件是否相同。课程设计任务书设计主题霍夫曼编码/解码器学生姓名刘文杰所在学部计算机科学与信息工程学院专业，年级，班级软件工程16-2设计要求：1 .根据霍夫曼编码原理构建霍夫曼编码并创建霍夫曼编码集。2 .读入文本文件，对文件内容进行编码，生成编码后的文件。3 .解码编码的文件并获取恢复文件。4 .比较恢复文件和原始文件是否相同。学生应完成的工作：1 .学生要认真学习参考程序，了解各文件、各函数以及各变量的作用和意义。 在此基础上进一步改进程序，最后正确执行程序。2 .测试程序，设计详细的测试计划，根据测试计划设计测试用例，测试程序。 在测试时，请注意测试各种边缘情况。3 .完成课程设计报告。参考文献：严蔚敏.数据结构(c语言版).清华大学出版社，20112 .谭浩强. c编程(第四版).清华大学出版，2010蒋立翔. c编程技能百练习M .中国铁路出版社，2004工作计划：1 .小组审查问题，查阅资料，准备设计前必要的资料(3日)。2 .完全执行程序(4天)。3 .增加改进方案(3天)。4 .编写课程设计报告(3天)。5 .提交课程设计报告和答辩书(一天)任务提交日期： 2017年12月01日任务完成日期： 2017年12月19日指导教师(签名): 学生(签名): 霍夫曼编码/解码器摘要：用霍夫曼编码思想实现字符串编码和编码译码。 字符串的长度至少为5000字节。 读取要编码的文本文件，对文件内容进行编码，生成新文件。 解码编码的文件并获取文本文件。 将解码的文本文件与原始文件进行比较时，恢复文件与原始文件必须完全匹配。关键词：构建哈夫曼树的哈夫曼编码哈夫曼编码字符串编码打印编码函数目录1 .设计背景11.1哈夫曼树简介11.2设计的作用，目的11.3设计任务和要求2二.设计方案22.1实验内容22.2操作思路22.3基本操作3三.方案实施43.1 C语言编程43.2程序介绍123.3程序的流程图和说明13图3主程序流程图图13四.结果和结论144.1程序执行结果144.2总结165 .收获和感谢176 .参考文献171 .设计背景1.1哈夫曼树介绍哈夫曼树，中文名是哈夫曼树、哈夫曼树或哈夫曼树，它是最好的二叉树。定义：将n个权重作为n个叶节点给出，构筑1根二叉树，树的加权路径长度最小时，将该树称为霍夫曼树。(01 )路径和路径长度定义：在一棵树中，从一个节点可以到达下方的子孙节点之间的通道称为路径。 路径的分支数称为路径长度。 如果设根节点的层数为1，则从根节点到第l层节点的路径长度为L-1。(02 )节点的权重和加权路径长度定义：给树中的节点一个有意义的数值，这个数值就称为该节点的权重。 节点的加权路径长度是从根节点到该节点的路径长度及其权重的乘积。(03 )树的加权路径长度定义：树的加权路径长度作为所有叶节点的加权路径长度之和，设为WPL。1.2设计的作用、目的完成具体编码算法的编程和调试，提高编程能力，深入理解源代码、信道编译代码的基本思想和目的，掌握代码的基本原理和编码过程，增强逻辑思维能力，培养和提高自学能力，综合运用学到的理论知识主要目的是加深对理论知识的理解，掌握查阅相关资料的技能，提高实践技能，独立分析问题，解决问题，培养实用能力。通过课程设计各环节的实践，应当满足以下要求1 .理解无失真源代码的理论基础，并了解无失真源代码的基本方法2 .根据Huffman编码算法，考虑具有多个可能符号(出现各种符号的概率不同)的源，得到Huffman编码和编码树3 .掌握哈夫曼码的优缺点4 .完成具体编码算法的编程和调试，提高编程能力，深入理解源代码、信道编译代码的基本思想和目的，掌握代码的基本原理和编码过程，强化逻辑思维能力，培养和提高自学能力，综合学习理论知识1.3设计任务和要求1 .理解无失真源代码的理论基础，并了解无失真源代码的基本方法2.Huffman编码/finol编码方法的基本步骤和优缺点3、深刻理解信道编码的基本思想和目的，了解线性组编码的基本原理和编码过程2 .设计方案2.1实验内容假设有n个权重的话，构筑的哈夫曼树有n个叶节点。 将n个权重值分别设为w1、w2、wn，霍夫曼树的结构规则如下1 .将w 1、w2、视为wn有n棵树的森林(每棵树只有一个节点)。2 .在森林中选择根节点的权重最小的2棵树合并，作为1棵新树的左、右子树，新树的根节点的权重作为其左、右子的根节点的权重之和3 .删除从森林中选出的两棵树，把新树加入森林4 .重复(02 )、(03 )的步骤直到森林里只剩下一棵树，那棵树就变成了所要求的霍夫曼树。2.2操作思路以 5，6，7，8，15 为例，构筑哈夫曼树。第一步：建造森林，森林包括5棵树，这5棵树的权重分别为5，6，7，8，15。步骤2 :在森林中，选择根节点权重最小的两棵树(5和6 )合并，将其作为新树左右的孩子(谁对左右不重要，这里，我们选择较小的一棵作为左边的孩子)，新树的权重是孩子的权重之和。 换句话说，新树的权重是11。 然后，从森林中删除“树5”和“树6”，将新树(树11 )追加到森林中。步骤3 :在森林中，选择根节点权重最小的两棵树(7和8 )进行合并。 得到的新树的权重是15。 然后，从森林中删除“树7”和“树8”，将新树(树15 )追加到森林中。步骤4 :在森林中，选择根节点权重最小的两棵树(11和15 )进行合并。 得到的新树的权重是26。 然后，从森林中删除“树11”和“树15”，将新树(树26 )追加到森林中。步骤5 :在森林中，选择根节点权重最小的两棵树(15和26 )进行合并。 得到的新树的权重是41。 然后，从森林中删除“树15”和“树26”，将新树(树41 )追加到森林中。这时，森林里只有一棵树(树41 )。 这棵树是我们需要的哈夫曼树！三.方案的实施3.1 C语言编程#include#include#include#define MAX 99999定义#define N 27/节点的最大数量#define M 2*N - 1/中间节点数typedef struct装模作样int weight；int parent；int LChild；int RChild；HTNode，霍夫曼treem1； /不使用零号单元typedefchar*霍夫曼代码 n1 ；哈夫曼codeco； /创建存储霍夫曼代码的全局变量char CHN；int weight n = 64，13，22，32，103，21，15，47，57，1，5，32，20，57，63，15，1，48，51，80，23，8，18，1，16，1 ；哈夫曼treeht；char word30； /全局变量用于保存您输入的内容v