1、数学与计算机学院 数据结构 实验报告年级 大二 学号* 姓名 * 成绩 专业 电气信息类（计算机） 实验地点 主楼402 指导教师 实验项目 实验日期 2010年11月20日 一、实验目的和要求通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。二、 问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码
2、系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。三、 数据结构设计1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1;描述结点的数据类型为：struct HNodeTypechar data; /结点字符int weight;/结点权值int parent;int lchild;int rchild;int level;2、求哈夫曼树编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
3、求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码为所求编码的低位码，后得到的分支代码为所求编码的高位码，所以设计如下数据类型：struct HCodeTypeint bitMAXBIT;int start;3、文件hfmtree.txt、code、text。四、 功能设计 （1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hf
4、mtree.dat中。（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件code中。（3）译码：利用已建好的哈夫曼树将文件code中的代码进行译码，结果存入文件text中。（4）打印编码规则：即字符与编码的一一对应关系。（5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。五、 测试数据（1） 利用教科书中的数据调试程序。 令叶子结点个数n为4，权值集合为1 3 5 7，字符集合为A B C D，并有如下对应关系，A1，B3，C5，D7，调用初始化功能模块可以正确接收这些数据。调用建立哈夫曼树的功能模块
5、构造静态链表HuffNode的存储。调用建立哈夫曼编码规则的功能模块，在屏幕上显示如下对应关系：A1，B3，C5，D7。调用哈夫曼编码的功能模块，在屏幕上输入“ABCD”后，显示编码：调用译码的功能模块，输入代码串“111110100”后，屏幕上显示译码结果：100101110ABCD调用打印哈夫曼树的功能模块。在屏幕上显示哈夫曼树（用凹入法表示）。打印编码规则：（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符ABCDEFGHIJKLM频度18664132232103211547571532
6、20字符NOPQRSTUVWXYZ频度5763151485180238181161调用建立哈夫曼树的功能模块，构造静态链表HuffNode的存储。调用建立哈夫曼编码规则的功能模块： 调用哈夫曼编码的功能模块：调用译码的功能模块：调用打印哈夫曼树的功能模块。在屏幕上显示哈夫曼树（用凹入法表示）。 打印编码规则：六、 程序代码/ HUFF.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include#include#includeusing namespace std;const int MAXBIT=100;const int MAXVALUE=2000;cons
7、t int MAXNODE=100;struct HNodeTypechar data;int weight;int parent;int lchild;int rchild;int level;struct HCodeTypeint bitMAXBIT;int start;static int n;static HNodeType *HuffNode;static HCodeType *HuffCode;/字符和权值的输入及建立哈夫曼树模块*HNodeType *huffmanTree()cout请输入字符总数：n;HuffNode=new HNodeType2*n-1;int i,j;in
8、t m1,m2,x1,x2;/初始化for(i=0;i2*n-1;i+) HuffNodei.level=1;HuffNodei.data=0;HuffNodei.weight=0;HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;/输入字符及权值cout请输入字符(可以识别空格，两个非空格字符之间请不要再加空格):endl;cout形如:(a bc),( abb c)endl;char c;flushall();for(i=0;in;i+)cin.get(c);HuffNodei.data=c;cout字符对应的叶子结点的
9、权值：endl;for(i=0;iHuffNodei.weight;/建立哈夫曼树for(i=0;in-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(j=0;jn+i;j+)if(HuffNodej.parent=-1&HuffNodej.weightm1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;elseif(HuffNodej.parent=-1&HuffNodej.weightm2)m2=HuffNodej.weight; x2=j; HuffNodex1.level=n-i;HuffNodex2.level=n-i;/结点在哈夫曼树的层
10、次HuffNodex1.parent=n+i;HuffNodex2.parent=n+i;HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild=x1;HuffNoden+i.rchild=x2;/输出哈夫曼树cout已成功建立哈夫曼树！endl;for(i=0;i2*n-1;i+)coutHuffNodei.weightt;coutHuffNodei.lchildt;coutHuffNodei.rchildt;coutHuffNodei.parentt;coutHuffNodei.levelt;cou
11、tendl;/把哈夫曼树写入文件ofstream outFile;out(hfmtree.txt,ios:out);for(i=0;i2*n-1;i+)outFileHuffNodei.datat;outFileHuffNodei.weightt;outFileHuffNodei.lchildt;outFileHuffNodei.rchildt;outFileHuffNodei.parentt;outFileendl;out(); cout已成功建立哈夫曼树并存入文件hfmtree.txt!endl;return HuffNode;/建立哈夫曼编码规则模块*void huffmanCode()
12、HuffCode=new HCodeTypen;HCodeType cd;int i,j,c,p;/建立编码规则for(i=0;in;i+)cd.start=MAXBIT-1;c=i;p=HuffNodec.parent;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HuffNodec.parent;for(j=cd.start+1;jMAXBIT;j+)HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start;/输出编码规则c
13、out已成功建立以下编码规则并存入code文件中！endl;for(i=0;in;i+)coutHuffNodei.data-;for(j=HuffCodei.start+1;jMAXBIT;j+)coutHuffCodei.bitj;coutendl;/将编码规则写入文件ofstream outFile(code,ios:out);for(i=0;in;i+)outFileHuffNodei.data-;for(j=HuffCodei.start+1;jMAXBIT;j+)outFileHuffCodei.bitj;outFileendl;out();/哈夫曼编码模块*void coding
14、)cout请输入要编码的字符串：endl;string s;flushall();getline(cin,s);couts对应的编码为：endl;for(int i=0;is.length();i+)for(int j=0;jn;j+)if(si=HuffNodej.data)for(int k=HuffCodej.start+1;kMAXBIT;k+)coutHuffCodej.bitk;elsecout您输入的编码不正确！endl;coutendl;/哈夫曼译码模块*void deCoding()string code;cout请输入要译码的编码序列：code;coutcode编码后的结
15、果(已存入txt文件）为：endl;int next,root;for(int i=0;i2*n-1;i+)if(HuffNodei.parent=-1)root=i;ofstream outFile(txt,ios:out); for(int i=0;icode.length();i+)next=root;while(HuffNodenext.lchild!=-1&HuffNodenext.rchild!=-1)if(codei=0)next=HuffNodenext.lchild;i+;elsenext=HuffNodenext.rchild;i+;coutHuffNodenext.dat
16、a;outFileHuffNodenext.data;i-;coutendl;out();/打印哈夫曼树模块*void printHuffTree()/凹入法打印哈夫曼树for(int i=0;in;i+)for(int j=0;j2*n-1;j+)if(HuffNodej.level=i+1)for(int k=0;kHuffNodej.level;k+)cout ;for(int k=0;k60-HuffNodej.level-i;k+)cout*;cout(HuffNodej.weight);if(jn)coutHuffNodej.data;coutendl; /输出编码规则模块*voi
17、d printPrinciple()for(int i=0;in;i+)coutHuffNodei.data-;for(int j=HuffCodei.start+1;jMAXBIT;j+)coutHuffCodei.bitj;coutendl;/显示菜单函数*void menu()cout请选择功能：endl;cout菜单：-输入字符和频度,建立哈夫曼树endl;cout 2-建立哈夫曼编码规则endl;cout 3-实现哈夫曼编码endl;cout 4-实现哈夫曼译码endl;cout 5-打印哈夫曼树endl;cout 6-打印编码规则endl;cout 0-退出程序endl;int _
18、tmain(int argc, _TCHAR* argv)cout*欢迎使用*endl;cout输入字符和权值，建立哈夫曼树：key;switch(key)case 1:huffmanTree();break;case 2:huffmanCode();break;case 3:coding();break;case 4:deCoding();break;case 5:printHuffTree();break;case 6:printPrinciple();break;case 0:break;default:cout输入错误！请正确选择功能：key;while(key!=0);return 0;14 / 14文档可自由编辑打印
