《（2020年7月整理）数据结构哈夫曼编译码器.doc》由会员分享，可在线阅读，更多相关《（2020年7月整理）数据结构哈夫曼编译码器.doc（17页珍藏版）》请在金锄头文库上搜索。
1、 东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术 数据结构课设哈夫曼编译码器学 号：姓 名：提交日期：成 绩： 一、 实验名称哈夫曼编/译码器的实现二、 实验要求【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传来数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【基本要求】一个完整的系统应具有以下功能：(1)I：初始化(Initialization)。从终端读入字符集大小n ,
2、 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。(2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件TextFile中。(4)P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。(5)T：打印哈夫曼树(Tree printing)
3、。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】(1)利用教科书例 6-2 中的数据调试程序。(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树 , 并实现以下报文的编码和译码：THIS PROGRAM IS MY FAVORITE。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161三、 需求分析Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立的，是
4、二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。3.1设计简介本设计是通过对给定字符及其使用频度构造哈夫曼树再根据哈夫曼树进行哈夫曼编码，在此之前，首先要理解哈夫曼树、哈夫曼算法、哈夫曼编译码的概念和原理。3.1.1哈夫曼树从树的根结点到树的每个结点的路径长度之和即为该树的路径长度。而在实际应用中，常将树的结点赋予一个有某种含义的数值，这个数值就称为结点的权。从树的根
5、结点到该结点之间的路径长度与结点权的乘积称为该结点的带权路径长度，树中所有叶结点的带权路径长度之和称为树的带权路径长度。通常记作：WPL = 式中，n表示树中叶子结点的数目，wi表示叶结点ki的权，li表示根结点到叶结点Ki之间的路径长度。在n个权值为w1,w2,wn的带权叶结点构成的所有二叉树中，其带权路径长度WPL最小的二叉树即为哈夫曼树或最优二叉树。3.1.2哈夫曼算法给定n个带权叶结点，如何构造一棵n个带有给定权值的叶结点的二叉树，使其带权路径长度最小？哈夫曼首先给出了构造最有二叉树的方法，故称其为哈夫曼算法，其基本的算法思想如下：将n个权值分别是w1,w2,wn的结点按权值递增排列。
6、将每个权值作为一个二叉树，构成n棵二叉树的森林F=T1,T2,Tn，其中每棵二叉树都只有一个权值为wi的根结点，其左右子树均为空。在森林F中选两棵根结点权值最小的二叉树，作为左右子树构造一棵新的二叉树，并使得新二叉树根结点的权值为其左右子树上根结点权值之和。在森林F中，删除这两棵树，同时将新得到的二叉树代替这两棵树加入到森林F中去，因此，森林F中二叉树的个数比以前少一棵。对新的森林F重复和，直到森林中只有一棵树为止。这棵树就是哈夫曼树。3.1.3哈夫曼编码用哈夫曼树得到的二进制前缀编码就是哈夫曼编码。具体做法是：对于给定的字符集C=c1,c2,cn及字符出现的频率W=w1,w2,wn，以c1,
7、c2,cn作为叶结点，以w1,w2,wn作为该结点上的权，利用哈夫曼算法，构造一棵带权路径长度最小的的哈夫曼树。然后对哈夫曼树中每个分支结点的左右分支分别用0和1进行编码，这样从树的根结点到每个叶结点之间，沿途路径上0和1组成的编码序列就是叶结点所代表字符的二进制编码。3.1.4哈夫曼译码哈夫曼译码过程与编码过程相反，译码过程就是分解电文中字符串的过程，具体步骤如下：首先输入要一点问的二进制编码，然后从哈夫曼树的根结点出发，对于电文的二进制编码，按照二进制位串中的0和1确定是进入左分支还是右分支：若编码为0，则进入结点的左孩子，否则进入结点的右孩子，一旦到达叶结点，就译出该叶子结点所代表字符。
8、3.2设计方案3.2.1设计思路要编程实现该系统，需逐步实现：1. 哈夫曼树的建立，即根据所给字符及对应频度构造哈夫曼树，哈夫曼树构造函数包括对哈夫曼树的初始化、赋值和建立；2. 哈夫曼编码表的建立，即编写程序实现对所给字符进行哈夫曼编码，将每个字符的哈夫曼编码存储到一个位串数组中去；3. 打印输出哈夫曼树和哈夫曼编码表，在终端上显示出哈夫曼树的结构和各字符名称及对应的哈夫曼编码；4. 编码，对输入的字符串进行哈夫曼编码，将结果写入文件；5. 译码，将文件中的哈夫曼编码按照编码表翻译成对应字符串并显示到终端上3.2.2设计流程图给定字符串及对应频率结束创建哈夫曼编码表输入字符读取codefil
9、e文件并译码构造哈夫曼树编码并写入文件codefile数据输出显示图2.1 总流程图1. 定义哈夫曼结点存储结构和哈夫曼编码存储结构，之后定义一个结点存储结构数组用来存放结点信息，和定义一个编码存储结构数组用来存放字符的哈夫曼编码，同时定义全局数组存放字符和它的使用频度。2. 先将已建立好的二叉树初始化，再对其中的叶结点其赋予字符名和对应使用频度作为结点名和结点权值，最后通过哈夫曼算法构造哈夫曼树，同时在屏幕输出哈夫曼树。3. 通过已建立好的哈夫曼树再对字符进行二进制编码，编码结束后，对应每个字符都有一个二进制编码，此编码即为哈夫曼编码，将字符及其哈夫曼编码存放到哈夫曼编码存储结构体数组中去，
10、构成哈夫曼编码表，同时在屏幕上输出哈夫曼编码表。4. 编码函数执行，即对输入的字符串根据哈夫曼编码表进行编码，将字符串的二进制编码存放到一个字符数组中去。5. 建立文件，将字符数组中的二进制编码写入文件，这需要定义输出流类的对象并与文件关联，通过操作对象来操作文件的数据写入。6. 将文件中的二进制编码进行译码，这需要定义输入流类的对象并与文件关联，将文件中的编码读取到另一字符数组中去，调用译码函数进行译码。7. 结束。四、 详细设计 creattreehuffman creatcodehuffman writecodehuffmanmain transcodehuffman printtree
11、huffman printcodehuffman 4.1哈夫曼树的建立4.1.1哈夫曼树的存储结构为了实现通过哈夫曼算法建立哈夫曼树，首先要定义哈夫曼树的存储结构。由于构造哈夫曼树之后，编码时要从叶结点出发走一条从叶结点到根的路径，而译码时要从根结点出发走一条从根到叶结点的路径。对于每个结点而言，既需知道双亲的信息，又需知道孩子的信息。因此，可以使用带双亲的孩子链表作为结点的存储结构。由哈夫曼算法可知，如果哈夫曼有n个叶结点，则最终生成的哈夫曼树共有2n-1个结点。因此，可以用一个长度为2n的一维数组存放哈夫曼树的所有结点。详细定义如下：#define Leafnum 27#define Hu
12、fnum 2*Leafnumtypedef char DataType;typedef struct Tnode DataType name;double weight;int lchild, rchild, parent;Huftree;Huftree TreeHufnum;其中，name表示结点数据的名称（即字符名称），weight表示结点的权值（即字符使用频度），lchild、rchild分别是结点的左、右孩子在数组中的下标值，叶结点的左右孩子的下标值均为0；parent表示结点双亲在数组中的位置。它的主要作用有两点：第一，区分根结点和非根结点；第二，使得查找某个结点的双亲变的更为简单。
13、若parent=0，则该结点是树的根结点，否则为非根结点。因为把森林中的两棵二叉树合并成一棵二叉树时，必须从森林的所有结点中选取两个根结点的权值为最小的结点，此时就是根据parent来区分根与非根结点的。4.1.2建立哈夫曼树本设计只对26个英文大写字符及空格进行了哈夫曼编码，各字符及对应使用频度如下表所示：表4.1 字符及其使用频度字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161需要定义全局数组来存放这些字符名称和对应频度：char ch = 0, ,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;float w = 0,186,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;定义函数CreatTreeHuffman，其中包括对已建立好的哈夫曼树的初始化，即将结点数据名称初始化为0，将结点权值、结点双亲及左右孩子的下标值都初始化为0；对已初始化的哈夫曼树赋值，将全局数组ch中存放的字符名称赋到叶结点的name上，将全局数组w中存放的字符使用频度赋到叶结点的weight上；最后根据哈夫曼算法对
