《哈夫曼编码译码》由会员分享，可在线阅读，更多相关《哈夫曼编码译码（23页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告哈夫曼编码译码信息工程学院计算机科学与技术2班设计题目学院名称 专 业 班 级 姓名摘要Huffman 编码是一种可变长编码方式，是二叉树的一种特殊转化形式。它 的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使 用较长的编码，并且保持编码的唯一可解性。本文根据Huffman编码原理，在详 细设计中，根据权值和最小的根本原则，我们输入要编码的字符集及其它的权值， 再根据在概要设计中提到的节点Node类，算法SuanFa类以及主类JieMian类， 建立哈夫曼树，并进行编码，最后输出哈夫曼编码。在完成Huffman编码后，我们利用其构建的哈夫曼编码树来进行
2、译码。与编 码过程不同，译码过程中，我们将用户输入的二进制代码串依次与字符集中的每 个字符的编码进行比较，译出一个字符后，循环比较下一个字符的编码，直到所 有二进制码全部译出为止。在编码和译码的过程中，我们遇到很多问题，诸如算法、语法问题，但我们 都通过不断的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译 码系统。关键词：Huffman编码树；最优二叉树；编码；译码AbstractHuffman coding is a encoding of variable length and a special transformation form of the binary tree.
3、Its principle is: the code that be used more often will be changed into the code of shorter lengths, while the codes that be used less often can be transformed into the code of longer lengths and the unique solution of coding will be kept. According to the theory of Huffman coding, firstly we enter
4、the character set which will be used to coding and their weights. Secondly, according to the fundanmental principle that the sum of the weights needs to be the smallest , the program designs Huffman tree in accordance with these class which are initialized in the outline such as class Node,class Sua
5、nFa,and class JieMian. At last, the computer will output Huffman coding on user interface.And then, we use the Huffman coding tree to decoding after the completion of Huffman coding tree.Here are difference with encoding process. We will compare the binary string that the user input with the charact
6、er set one by one during the processs of decoding .And then, the cycle of the next character encoding will continue which is based on the completion of translation of a character. It will be finished until all the binary code is translated.During the process of coding and decoding, we encounter many
7、 problems, such as the problem on arithmetic and grammar. However, we try our best to solve these problems through constant analysis and debugging.Eventually, we achieve the goal that establish a complete system on coding and decoding successfully.Key Words：Huffman coding tree；optimal binary tree；co
8、ding；decoding目录摘要ABSTRACT II1.绪论1.1设计目的11.2问题描述11.3设计思想2. 概要设计3. 需求分析4. 详细设计5测试数据与实验结果106课程设计总结14 参考文献15附录（源程序代码）16绪论1.1 设计目的学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算 类型的应用问题。本课程设计要求同学独立完成一个较为完整的应用需求分析， 在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、 理论和方法的理解；训练综合运用所学知识处理实际问题的能力，使同学的程序 设计与调试水平有一个明显的提高。1.2 问题描述利用赫夫曼编码进行
9、通信可以大大提高信道利用率，缩短信息传输时间，降 低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收 端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道）， 每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码 的编/译码系统。1.3.设计思想哈夫曼编码（Huffman Coding）是一种编码方式，以哈夫曼树一即最优 二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊 的编码表将源字符（例如某文件中的一个符号）进行编码。这种方法是由 David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的
10、出 现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位 （bit）来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个 英文字母均占用一个字节（byte）,即8个位。二者相比，e使用了一般编码的 1/8的长度，z则使用了 3倍多。倘若我们能实现对于英文中各个字母出现概率 的较准确的估算，就可以大幅度提高无损压缩的比例。总体流程图如下图2.概要设计开始否结点数是否大于1是否Iv2*N?是否是是否是否结束是否为根结点?左子是否为空?右子是否为空输出根结点和权值 /输出两子结点和已构造的结点I+将data和权值赋给ht调用SELECT函数父结点为两子结点之和此时编
11、码为0编码为1计算根结点函数赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有 n 棵只含有根 结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树， 合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。 显然要进行n1次合并，所以共产生n1个新结点，它们都是具有两个孩子的 分支结点。由此可知，最终求得的赫夫曼树中一共有2n1个结点，其中n个结 点是初始森林的 n 个孤立结点。并且赫夫曼树中没有度数为 1 的分支结点。我们 可以利用一个大小为 2n-1 的一维数组来存储赫夫曼树中的结点。2.2 哈夫曼编码要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据
12、设计要求和实际需 要定义的类型如下： typedet struct char ch; / 存放编码的字符 char bitsN1; / 存放编码位串 int len; / 编码的长度 CodeNode; / 编码结构体类型2.3 代码文件的译码译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到 相等时，即取出其对应的字符存入一个新串中。3. 需求分析3.1：初始化（Initialization）。从终端读入字符集大小n以及n个字符和n个权值，建立哈夫曼树，并将 它存于文件hfmTree中。输出哈夫曼树，及各字符对应的编码。3.2：编码（Encoding）与译码（Decodin
13、g）。3.2.1编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件 htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件 CodeFile 中。3.2.2译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代 码进行译码，结果存入文件 TextFile 中。3.2.3印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上， 每行50个代码。同时将此字符形式的编码写入文件CodePrint中。3.3:印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上， 同时
14、将此字符形式的哈夫曼树写入文件 TreePrint 中。4. 详细设计4.1 哈夫曼树的存储结构描述typedef structunsigned int weight;unsigned int parent, lchild, rchild; HTNode, *HuffmanTree;4.2 哈弗曼树的算法void CreateHT(HTNode ht,int n)数nint i,k,lnode,rnode;int min1,min2;for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1;for (i=n;i2*n-1;i+)min1=m
15、in2=32767; lnode=rnode=-1;个结点位置for (k=0;k=i-1;k+)调用输入的数组ht,和节点/所有结点的相关域置初值-1/构造哈夫曼树/int 的范围是-3276832767/lnode 和 rnode 记录最小权值的两if (htk.parent=-1)/只在尚未构造二叉树的结点中查找if(htk.weightmin1)/若权值小于最小的左节点的权值min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weightmin2)min2=htk.weight;rnode=k;/两个最小节点htlnode.parent=i;htrnode.parent=i;的父节点是iht
