哈夫曼编译码系统实验报告.doc

数学与计算机学院 数据结构 实验报告年级 大二 学号********* 姓名 ******* 成绩 专业 电气信息类（计算机） 实验地点 主楼402 指导教师 实验项目 实验日期 2010年11月20日 一、实验目的和要求通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现二、 问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统试为这样的信息收发编写一个哈夫曼码的编/译码系统三、 数据结构设计1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1;描述结点的数据类型为：struct HNodeType{ char data; //结点字符 int weight;//结点权值 int parent; int lchild; int rchild; int level;};2、求哈夫曼树编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。

求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码为所求编码的低位码，后得到的分支代码为所求编码的高位码，所以设计如下数据类型：struct HCodeType{ int bit[MAXBIT]; int start;};3、文件hfmtree.txt、codefile.txt、textfile.txt四、 功能设计 （1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中 （2）编码：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中 （3）译码：利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中 （4）打印编码规则：即字符与编码的一一对应关系 （5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。

五、 测试数据（1） 利用教科书中的数据调试程序 令叶子结点个数n为4，权值集合为{1 3 5 7}，字符集合为{A B C D}，并有如下对应关系，A——1，B——3，C——5，D——7，调用初始化功能模块可以正确接收这些数据调用建立哈夫曼树的功能模块，构造静态链表HuffNode的存储调用建立哈夫曼编码规则的功能模块，在屏幕上显示如下对应关系：A——1，B——3，C——5，D——7调用哈夫曼编码的功能模块，在屏幕上输入“ABCD”后，显示编码：调用译码的功能模块，输入代码串“111110100”后，屏幕上显示译码结果：100101110——ABCD调用打印哈夫曼树的功能模块在屏幕上显示哈夫曼树（用凹入法表示）打印编码规则：（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161调用建立哈夫曼树的功能模块，构造静态链表HuffNode的存储。

调用建立哈夫曼编码规则的功能模块： 调用哈夫曼编码的功能模块：调用译码的功能模块：调用打印哈夫曼树的功能模块在屏幕上显示哈夫曼树（用凹入法表示） 打印编码规则：六、 程序代码// HUFF.cpp : 定义控制台应用程序的入口点//#include "stdafx.h"#include#include#includeusing namespace std;const int MAXBIT=100;const int MAXVALUE=2000;const int MAXNODE=100;struct HNodeType{ char data; int weight; int parent; int lchild; int rchild; int level;};struct HCodeType{ int bit[MAXBIT]; int start;};static int n;static HNodeType *HuffNode;static HCodeType *HuffCode;//字符和权值的输入及建立哈夫曼树模块******************************HNodeType *huffmanTree(){ cout<<"请输入字符总数："<>n; HuffNode=new HNodeType[2*n-1]; int i,j; int m1,m2,x1,x2; //初始化 for(i=0;i<2*n-1;i++) { HuffNode[i].level=1; HuffNode[i].data='0'; HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } //输入字符及权值 cout<<"请输入字符(可以识别空格，两个非空格字符之间请不要再加空格):"<>HuffNode[i].weight; } //建立哈夫曼树 for(i=0;i