数据结构哈夫曼编译码器(18页).doc

《数据结构哈夫曼编译码器(18页).doc》由会员分享，可在线阅读，更多相关《数据结构哈夫曼编译码器(18页).doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构课设哈夫曼编译码器学 号：姓 名：提交日期：成 绩： 一、 实验名称哈夫曼编/译码器的实现二、 实验要求【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传来数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【基本要求】一个完整的系统应具有以下功能：(1)I：初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件h

2、fmTree中。(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的结点按权值递增排列。将每个权值作为一个二叉树，构成n棵二叉树的森林F=T1,

6、T2,Tn，其中每棵二叉树都只有一个权值为wi的根结点，其左右子树均为空。在森林F中选两棵根结点权值最小的二叉树，作为左右子树构造一棵新的二叉树，并使得新二叉树根结点的权值为其左右子树上根结点权值之和。在森林F中，删除这两棵树，同时将新得到的二叉树代替这两棵树加入到森林F中去，因此，森林F中二叉树的个数比以前少一棵。对新的森林F重复和，直到森林中只有一棵树为止。这棵树就是哈夫曼树。3.1.3哈夫曼编码用哈夫曼树得到的二进制前缀编码就是哈夫曼编码。具体做法是：对于给定的字符集C=c1,c2,cn及字符出现的频率W=w1,w2,wn，以c1,c2,cn作为叶结点，以w1,w2,wn作为该结点上的权

7、，利用哈夫曼算法，构造一棵带权路径长度最小的的哈夫曼树。然后对哈夫曼树中每个分支结点的左右分支分别用0和1进行编码，这样从树的根结点到每个叶结点之间，沿途路径上0和1组成的编码序列就是叶结点所代表字符的二进制编码。3.1.4哈夫曼译码哈夫曼译码过程与编码过程相反，译码过程就是分解电文中字符串的过程，具体步骤如下：首先输入要一点问的二进制编码，然后从哈夫曼树的根结点出发，对于电文的二进制编码，按照二进制位串中的0和1确定是进入左分支还是右分支：若编码为0，则进入结点的左孩子，否则进入结点的右孩子，一旦到达叶结点，就译出该叶子结点所代表字符。3.2设计方案3.2.1设计思路要编程实现该系统，需逐步

8、实现：1. 哈夫曼树的建立，即根据所给字符及对应频度构造哈夫曼树，哈夫曼树构造函数包括对哈夫曼树的初始化、赋值和建立；2. 哈夫曼编码表的建立，即编写程序实现对所给字符进行哈夫曼编码，将每个字符的哈夫曼编码存储到一个位串数组中去；3. 打印输出哈夫曼树和哈夫曼编码表，在终端上显示出哈夫曼树的结构和各字符名称及对应的哈夫曼编码；4. 编码，对输入的字符串进行哈夫曼编码，将结果写入文件；5. 译码，将文件中的哈夫曼编码按照编码表翻译成对应字符串并显示到终端上3.2.2设计流程图给定字符串及对应频率结束创建哈夫曼编码表输入字符读取codefile文件并译码构造哈夫曼树编码并写入文件codefile数

9、据输出显示图2.1 总流程图1. 定义哈夫曼结点存储结构和哈夫曼编码存储结构，之后定义一个结点存储结构数组用来存放结点信息，和定义一个编码存储结构数组用来存放字符的哈夫曼编码，同时定义全局数组存放字符和它的使用频度。2. 先将已建立好的二叉树初始化，再对其中的叶结点其赋予字符名和对应使用频度作为结点名和结点权值，最后通过哈夫曼算法构造哈夫曼树，同时在屏幕输出哈夫曼树。3. 通过已建立好的哈夫曼树再对字符进行二进制编码，编码结束后，对应每个字符都有一个二进制编码，此编码即为哈夫曼编码，将字符及其哈夫曼编码存放到哈夫曼编码存储结构体数组中去，构成哈夫曼编码表，同时在屏幕上输出哈夫曼编码表。4. 编

10、码函数执行，即对输入的字符串根据哈夫曼编码表进行编码，将字符串的二进制编码存放到一个字符数组中去。5. 建立文件，将字符数组中的二进制编码写入文件，这需要定义输出流类的对象并与文件关联，通过操作对象来操作文件的数据写入。6. 将文件中的二进制编码进行译码，这需要定义输入流类的对象并与文件关联，将文件中的编码读取到另一字符数组中去，调用译码函数进行译码。7. 结束。四、 详细设计 creattreehuffman creatcodehuffman writecodehuffmanmain transcodehuffman printtreehuffman printcodehuffman 4.1

11、哈夫曼树的建立4.1.1哈夫曼树的存储结构为了实现通过哈夫曼算法建立哈夫曼树，首先要定义哈夫曼树的存储结构。由于构造哈夫曼树之后，编码时要从叶结点出发走一条从叶结点到根的路径，而译码时要从根结点出发走一条从根到叶结点的路径。对于每个结点而言，既需知道双亲的信息，又需知道孩子的信息。因此，可以使用带双亲的孩子链表作为结点的存储结构。由哈夫曼算法可知，如果哈夫曼有n个叶结点，则最终生成的哈夫曼树共有2n-1个结点。因此，可以用一个长度为2n的一维数组存放哈夫曼树的所有结点。详细定义如下：#define Leafnum 27#define Hufnum 2*Leafnumtypedef char D

12、ataType;typedef struct Tnode DataType name;double weight;int lchild, rchild, parent;Huftree;Huftree TreeHufnum;其中，name表示结点数据的名称（即字符名称），weight表示结点的权值（即字符使用频度），lchild、rchild分别是结点的左、右孩子在数组中的下标值，叶结点的左右孩子的下标值均为0；parent表示结点双亲在数组中的位置。它的主要作用有两点：第一，区分根结点和非根结点；第二，使得查找某个结点的双亲变的更为简单。若parent=0，则该结点是树的根结点，否则为非根结点

13、。因为把森林中的两棵二叉树合并成一棵二叉树时，必须从森林的所有结点中选取两个根结点的权值为最小的结点，此时就是根据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

14、,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上；最后根据哈夫曼算法对27个结点（每个结点可以看做是一棵树）构造出哈夫曼树。4.2哈夫曼编码表的建

15、立4.2.1哈夫曼编码表的存储结构利用哈夫曼树对字符进行哈夫曼编码，实际上就是求出从根结点到叶结点的路径。由于采用带双亲的孩子链表作为存储结构，因此，对于输入的每个字符，可以从哈夫曼树的叶结点出发，沿结点的双亲链回溯到根结点，在这个过程中，每回溯一步都会经过哈夫曼树的一个分支，从而得到一个哈夫曼编码。因此，可设置一个位串数组bits，将生成的代码序列从后到前依次存放到数组bits中。哈夫曼编码表存储结构定义如下：typedef struct Cnode char bitsLeafnum+1;int start;char ch;hufcode;由于叶子结点总数即字符个数为Leafnum，故不等长

16、编码的长度不会超过Leafnum，再加上结束符号0，位串数组bits的大小应为Leafnum+1，整型变量start用来指示编码在数组中的起始位置，当某个字符编码完成时，从变量的start处开始将编码复制到该字符对应的数组bits中去即可。4.2.2建立哈夫曼编码表建立哈夫曼编码表即建立一个表格用来存储每个字符名称和对应的哈夫曼编码，此过程建立在已经构造好的哈夫曼树上，从叶结点开始，沿着双亲链向上，记录沿途经过分支上的二进制编码，直到到达根结点，于是对应每一个字符都有一个二进制串，即它的哈夫曼编码，用上面定义的哈夫曼编码表存储结构数组存放起来，即存在位串数组bits中。4.3编码本程序的功能是

17、能对从键盘输入的任意有限长度的字符串（限定在大写英文字符和空格）进行哈夫曼编码，因此需要定义函数WritecodeHuffman来实现对输入的字符串逐个进行编码，此过程实质上是将字符与编码表里的字符名称相比较，当名称一致时，就输出对应字符的bits数组中的二进制编码，然后依次输出每个字符的哈夫曼编码，将他们连续的显示在屏幕上。4.4文件写入由于要将这些二进制串写入文件，所以事先再定义一个全局字符数组Huffmancode来存储这些二进制串。在主函数先在某目录下建立一个.txt文件，名为codefile，再定义了一个输出流类ofstream的对象ofs，定义ofs的同时将其与文件codefile

18、关联，于是，就可以通过操作ofs来实现文件数据的写入，即将字符数组Huffmancode中的二进制编码写入文件。14.5译码译码的过程与编码的过程相反，先将codefile文件中的二进制编码读出来，这时在主函数中也定义一个输入流类ifstream的对象ifs，同时将它与文件codefile关联，通过ifs读取codefile文件中的二进制编码，存放到数组buffer中，再通过译码函数进行译码， TranscodeHuffman译码函数定义如下：void TranscodeHuffman (Hufcode code , Huftree tree , char s ) int i;char *q=

19、NULL;i=Hufnum-1; q=s;while (*q!=0)if (*q=0) i=treei.lchild;if (*q=1) i=treei.rchild;if (treei.lchild=0)&(treei.rchild=0)cout codei.ch;i = Hufnum - 1;q+;cout endl;该函数带三个参数，分别是已建立好的哈夫曼树结点数组，哈夫曼编码表数组和需要进行译码的字符数组，该字符数组存放的即为由0、1组成的一串编码，函数中设置字符类型指针q开始指向字符数组的第一个字符，若为0，则进入左孩子，否则进入右孩子，再执行q+，直到某结点的左右孩子下标值均为0的

20、时候，此时的结点即为叶结点，于是输出对应字符，再将起始结点设为根结点，重复上述过程，直到翻译出所有字符。五、 测试结果5.1 哈夫曼树输出根据所给的27个字符及使用频度所建立的的哈夫曼树结构输出如图5.1图5.1哈夫曼树输出第一列是字符序号，也就是在建立的存储结构数组tree中各结点的下标值，1到27对应的是叶结点；第二列是字符名称，每个叶结点对应一个字符；第三列是字符使用频度，也即叶结点的权值；后面三列则列出了每个结点双亲及左右孩子在结构数组中的下标值，虽然是以表格方式表示这棵树，但从中可以体现出整个哈夫曼树的树形结构。5.2哈夫曼编码表输出根据哈夫曼树所建立的哈夫曼编码表输出如图5.2图5

21、.2 哈夫曼编码表输出哈夫曼编码表第一列和第二列仍给出字符序号和字符名称，第三列是字符编码，即对应于各个字符的哈夫曼编码。此表列出了所有27个字符和与其对应的哈夫曼编码，每个哈夫曼编码都存在编码表结构数组中，这样，对任意输入的字符串（限定在大写英文字符和空格）进行哈夫曼编码时，只需逐个按照表格找到其对应编码，再将它们存放到一起，即可得到字符串的哈夫曼编码。5.3 编码和译码对任意字符串的编码和译码运行如图5.3图4.3 字符串编码和译码结果输出主函数执行时，先调用CreatTreeHuffman和CreatcodeHuffman两函数建立哈夫曼树和哈夫曼编码表，对应也输出显示它们。于是再进入功

22、能执行部分，即函数WritecodeHuffman，在窗口中显示“请输入字符串：”，于是手动输入任意大写英文字符或空格，即可将它的哈夫曼编码显示出来。5.4 文件读写本程序还实现了文件的读写过程，即将输入字符串的二进制编码写入文件codefile中，也能读出codefile文件中的二进制编码再进行译码便显示到终端上，这个过程即可视为实际生活中两计算机之间模拟数据传输过程，将发送方的信息数据（字符串）进行哈夫曼编码，得到二进制串，即文件写入过程；接收方再将二进制串翻译成信息，即文件读取过程。codefile文件打开如图5-4主函数中先创建一个文件名为”d:codefile.txt”的文本文件，再

23、定义一个文件输出流类ofstream的对象ofs，并将其与文件codefile关联到一起，再将之前存放字符串哈夫曼编码的数组写入文件，随后定义一个文件输入流类ifstream的对象ifs，并将其与文件codefile关联，同时定义一个缓存字符数组buffer用于存放从codefile文件中读取出来的二进制编码，最后调用译码函数transcodehuffman对buffer中的编码进行译码，把译出的字符显示出来。六、 总结及调试分析本次课程设计涵盖了对字符及其使用频度构造哈夫曼树和哈夫曼编码表，再对输入字符进行哈夫曼编码，将编码写入文件进而读取文件并译码等模块功能，整个过程将结构体、指针、数组、

24、语句循环选择结构，链表，文件读写等知识联系在一起，考察了我们运用C+语言的能力以及对数据结构的理解，通过几天的编写和调试，基本上实现了数据传输的过程。而在这个过程中，我开始进展十分缓慢，主要是因为首次接触有关程序实现编码的问题，对树形结构也不怎么了解，于是在第一步构造哈夫曼树的时候就花了很长时间来理解哈夫曼算法，哈夫曼树构造函数里面设置了很多变量，那个核心部分怎么也看不懂，我带着疑惑地将代码全都打出来，运行成功后我对着结果一步一步列出其中的过程，在循环中确定每一次各变量的值，对照着事先画好的哈夫曼树仔细看了看，终于了解了各变量的作用，哈夫曼树构造的原理大致也就清楚了，于是后面的哈夫曼编码表结构

25、，哈夫曼译码过程也迎刃而解，整个过程的原理就把握住了。在上机调试的时候，也屡次出行过错误，例如对字符进行哈夫曼编码的时候，是从哈夫曼树的根结点开始沿双亲链往上回溯的，于是这样得到的编码实际上是反过来的，但用来存储它们的位串数组也不一般，在编码表结构里还定义了一个位置变量start，用以指示哈夫曼编码在数组中的起始位置，start是从最后一个开始指向的，即从后面开始存储二进制编码，于是从前面开始读取就能获得字符的哈夫曼编码。通过这样不断的调试，我对整个结构的理解就越来越清楚，经过几天的努力，一个小型的哈夫曼编译码系统就完成了。整个系统能实现对任意输入的空格或26个大写英文字符进行哈弗曼编码，再写

26、入文件，最后读取文件并译码的功能。七、 参考文献数据结构 严蔚敏 吴伟民著 清华大学出版社C+程序设计 谭浩强 著 清华大学出版社附录：源代码#include #include using namespace std;#define leafnum 27#define hufnum 2*leafnum#define maxdouble 9999.9typedef char datatype;typedef struct tnode / 哈夫曼树结点存储结构datatype name;double weight;int lchild, rchild, parent;huftree;typedef

27、 struct cnode / 哈夫曼编码表结构char bitsleafnum+1;int start;char ch;hufcode;hufcode codeleafnum+1;huftree treehufnum+1;char huffmancode1000;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;void creattr

28、eehuffman(huftree tree) / 建立哈夫曼树int i, j, p1, p2;double least1, least2;for (i=1; i=hufnum; i+)treei.name = 0;treei.parent = 0;treei.lchild = 0;treei.rchild = 0;treei.weight = 0.0;for (i=1; i=leafnum; i+)treei.name = chi;treei.weight = wi;for (i=leafnum+1; i=hufnum; i+)p1=0; p2=0; least1=least2=maxdo

29、uble;for (j=1; ji; j+)if (treej.parent=0)if (treej.weightleast1)least2=least1;least1=treej.weight;p2=p1;p1=j;elseif(treej.weightleast2)least2=treej.weight;p2=j;treep1.parent=i;treep2.parent=i;treei.lchild=p1;treei.rchild=p2;treei.weight=treep1.weight+treep2.weight;treehufnum-1.parent=0;void creatcod

30、ehuffman(hufcode code, huftree tree) / 建立哈夫曼编码int i, c, p;hufcode buf;for (i=1; i=leafnum; i+)buf.ch=chi;buf.start=leafnum;c=i;p=treei.parent;while (p != 0)buf.start-;if (treep.lchild=c)buf.bitsbuf.start=0;else buf.bitsbuf.start=1;c=p;p=treep.parent;codei=buf;void writecodehuffman(hufcode code, huft

31、ree tree) /哈弗曼编码int i, j, k, n=0;char c100;cout 请输入字符串: endl;gets(c);cout endl;cout 则字符串的哈夫曼编码为: endl;for (i=0; istrlen(c); i+)for (j=1; j=leafnum; j+)if (ci=treej.name)for(k=codej.start; kleafnum; k+)cout codej.bitsk;huffmancoden = codej.bitsk;n+;void transcodehuffman(hufcode code, huftree tree, ch

32、ar s) / 哈夫曼译码int i;char *q=NULL;i=hufnum-1; q=s;while (*q!=0)if (*q=0) i=treei.lchild;if (*q=1) i=treei.rchild;if (treei.lchild=0)&(treei.rchild=0)cout codei.ch;i = hufnum - 1;q+;cout endl;void printtreehuffman(huftree tree) / 输出哈夫曼树int i;cout 根据字符的使用概率所建立的哈夫曼数为:endl;cout 字符序号 字符名称 字符频率 双亲位置 左孩子 右孩子

33、endl;for (i = 1; i hufnum; i+)cout i t treei.name t;cout treei.weight t treei.parent t treei.lchild treei.rchild endl ;void printcodehuffman(hufcode code) /输出每个字符的哈夫曼编码int i, j;cout 根据哈夫曼树对字符所建立的哈夫曼编码为: endl;cout 字符序号 字符名称 字符编码 endl;for (i =1; i = leafnum; i+)cout i t codei.ch ;for(j=codei.start;j l

34、eafnum;j+)cout codei.bitsj;cout tt endl;void main()creattreehuffman(tree);printtreehuffman(tree);creatcodehuffman(code, tree);printcodehuffman(code);writecodehuffman(code, tree);char *filename = e:codefile.txt;ofstream ofs(filename);ofs huffmancode;ofs.close();ifstream ifs(filename);if (!ifs)cout Error: failed to open file. buffer;cout endl endl;cout codefile文件中的代码如下: endl;cout buffer endl endl;ifs.close();cout codefile文件中代码译码为: endl;transcodehuffman(code, tree, buffer);-第 18 页-