哈夫曼编译码器实验报告
实验五 哈夫曼编/译码器
学院: 工学院 系: 计算机系 专业: 计算机科学与技术 年级: 2009 姓名: 学号: 完成实验时间: 2011-5-19
一． 需求分析
1. 问题描述
用huffman 编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。是为着这样的信息收发站写一个huffman 编/译码系统。
2. 基本要求
该系统应具有以下功能：
（1） I ：初始化（Initialization ）。从终端读入字符集大小n, 以及n 个字符和n 个权
值，建立哈夫曼树，并将它存进文件hfmTree 中。
（2） E ：编码（Encoding ）。利用建好的哈夫曼树（如不在内存中，则从文件hfmTree 中
读入），对文件ToBeTran 中的正文进行编码，然后将结果存入文件CodeFile 中。
（3） D ：译码(Decoding)。(利用已经建好的哈夫曼树将文件CodeFile 中的代码进行译
码，结果存入文件TextFile 中。
（4） P ：印代码文件(Print)。将文件CodeFile 以紧凑格式显示在终端上，每行50个代
码。同时将此字符形式的编码文件写入文件CodePrin 中。
（5） T ：印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式（凹入表
形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrin 中。
3. 测试数据
（1）利用下面这道题中的数据调试程序。
某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROMGRAM IS MY FAVORITE”。
二．概要设计
本程序的数据类型定义为
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;
typedef char** HuffmanCode;
所实现的功能函数如下
void initHuffmanTree();//选择初始化哈夫曼树的方式
int openfileInit();//通过打开的data.txt 文件初始化哈夫曼树 该文件是为了测试数据2 包涵26个字符
int inputInit();//通过手动输入字符初始化哈夫曼树
int HuffmanCoding(int *w); //初始化哈夫曼数，按照哈夫曼规则建立二叉树。此函数块调用了Select （）函数。
void Select(int j,int &s1,int &s2); //选择parent 为0，且weight 最小的两个节点 序号为s1，s2
void encoding();//选择哈夫曼编码方式
void openfileEnco();//通过打开文件encode.txt 的方式进行编码 void inputEnco();//通过手动输入的方式进行编码 void decode();//选择译码方式
void openfileDeco();//通过打开文件CodeFile.txt 的方式进行译码 void inputDeco();//通过手动输入的方式进行译码
void dispHT( HuffmanTree nodeRoot, int level ); //以缩进方式输出哈夫曼树直观图
主函数
主函数主要设计的是一个分支语句，让用户挑选所实现的功能。 如图所示：
三．详细设计
#include #include #include using namespace std; ofstream outstuf;
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;
typedef char** HuffmanCode;
HuffmanTree HT=NULL; int n=0;
HuffmanCode HC=NULL; char *ch=NULL;
void initHuffmanTree(); int openfileInit(); int inputInit();
int HuffmanCoding(int *w);
void Select(int j,int &s1,int &s2); void encoding(); void openfileEnco(); void inputEnco(); void decode(); void openfileDeco(); void inputDeco();
void dispHT( HuffmanTree nodeRoot, int level );
void initHuffmanTree(){ //选择初始化哈夫曼树 int sel=0; for(;;){
cout
cout
cout>sel; if(sel==3) break; switch(sel)
{case 1:openfileInit();break; case 2:inputInit();break;
default:cout
int openfileInit(){ //通过打开的data.txt 文件初始化哈夫曼树 该文件是为了测试数据2 包涵26个字符
int *w=(int*)malloc(28*sizeof(int)); ch=(char*)malloc(28*sizeof(char)); n=27;
ifstream infile("data.txt",ios::in); if(!infile){
cerr
cout>ch[i]; infile>>w[i]; } cout
for(i=1;i
for(i=1;i
for(i=10;i
for(i=10;i
for(i=19;i
for(i=19;i
HuffmanCoding(w);
cout
cout
outstuf.open("code.txt",ios::out);
for(i=1;i
int inputInit(){ //通过手动输入字符初始化哈夫曼树 cout
outstuf.close();
return 0;
cin>>n;
int *w=(int *)malloc((n+1)*sizeof(int)); if(!w) {cout>ch[i]; cout>w[i]; //outstuf.close();
outstuf.open("hfmTree.txt",ios::out); for(i=1;i
cout
cout
outstuf.open("code.txt",ios::out); for(i=1;i
int HuffmanCoding(int *w){ //哈夫曼编码 if(n
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); if(!HT) {cout
HT[i].weight=w[i];
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
outstuf.close();
return 0;
outstuf
}
for(;i
for(i=n+1;i
HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+ HT[s2].weight; }
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); char *cd=(char*) malloc(n*sizeof(char)); if(!cd) {cout
for(int c=i,unsigned int f=HT[i].parent;f!=0;c=f,f=HT[f].parent) {if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; }
HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); return 0; }
void Select(int j,int &s1,int &s2){ //选择parent 为0，且weight 最小的两个节点 序号为s1，s2
for(int h=1;h
if(HT[h].parent==0) {s1=h;break;} h++; for(;h
if(HT[h].parent==0) {s2=h;break;} int m;
if(HT[s1].weight>HT[s2].weight) {m=s1;s1=s2;s2=m;} h++;
for(;h
if(HT[s1].weight>HT[h].weight&&HT[h].parent==0) s1=h; for(m=1;m
if(HT[s2].weight>HT[m].weight&&m!=s1&&HT[m].parent==0) s2=m; }
void encoding(){ //选择哈夫曼编码方式 int sel=0; for(;;){
if(!HT) {cout
cout
cout>sel; if(sel==3) break; switch(sel)
{case 1:openfileEnco();break; case 2:inputEnco();break;
default:cout
void openfileEnco(){ //通过打开文件encode.txt 的方式进行编码 cout
cerr
char *file=(char *)malloc(200*sizeof(char)); for(int i=1;infile.eof()==0&&i!=200;i++){ infile>>file[i]; cout
if(i==200) {
file=(char *)realloc(file,(200+80)*sizeof(char)); for(;infile.eof()==0&&i!=280;i++){ infile>>file[i]; cout
cout
outstuf.open("CodeFile.txt",ios::out); for(i=1;i
for(int j=1;j
if(j==(n+1)) {cout
void inputEnco(){ //通过手动输入的方式进行编码
cout>file[i]; if(file[i]=='$') break; }
if(i==200) {
file=(char *)realloc(file,(200+80)*sizeof(char)); for(;i>file[i]; if(file[i]=='$') break; } }
outstuf.close();
cout
outstuf.open("CodeFile.txt",ios::out); for(i=1;i
for(int j=1;j
void decode(){ //选择译码方式 int sel=0; for(;;){
if(!HT) {cout
cout
cout>sel; if(sel==3) break; switch(sel)
{case 1:openfileDeco();break; case 2:inputDeco();break;
default:cout
void inputDeco(){ //通过手动输入的方式进行译码
cout
}//将编码结果写入 CodeFile.txt
if(j==(n+1)) {cout
int m=2*n-1;
char *password=(char *)malloc(200*sizeof(char)); cout>password[i]; if(i==200) {
password=(char *)realloc(password,(200+80)*sizeof(char)); for(;i>password[i]; }
cout
//outstuf.close();
outstuf.open("TextFile.txt",ios::out); for(i=1;password[i]!='$';){ char record[20];
for(int j=0,q=i;password[q]!='$';j++,q++){
if(password[q]=='0') {record[j]='0';m=HT[m].lchild;} else {record[j]='1';m=HT[m].rchild;} if(HT[m].rchild==0) {record[j+1]='\0';break;} }
if(HT[m].rchild!=0) {cout
for(int p=1;p
if(!strcmp(record,HC[p])) {outstuf
}
i=i+strlen(record); m=2*n-1; }
cout
void openfileDeco(){ //通过打开文件CodeFile.txt 的方式进行译码 int m=2*n-1;
cout
cerr
outstuf.close();
}
char *password=(char *)malloc(200*sizeof(char)); for(int i=1;infile.eof()==0&&i!=200;i++){ infile>>password[i]; cout
password=(char *)realloc(password,(200+80)*sizeof(char)); for(;infile.eof()==0&&i!=280;i++){ infile>>password[i]; cout
cout
//outstuf.close();
outstuf.open("TextFile.txt",ios::out); for(i=1;password[i]!='$';){ char record[20];
for(int j=0,q=i;password[q]!='$';j++,q++){
if(password[q]=='0') {record[j]='0';m=HT[m].lchild;} else {record[j]='1';m=HT[m].rchild;} if(HT[m].rchild==0) {record[j+1]='\0';break;} }
if(HT[m].rchild!=0) {cout
i=i+strlen(record); m=2*n-1; }
cout
outstuf.close();
if(!strcmp(record,HC[p])) { outstuf
for(int p=1;p
void dispHT( HuffmanTree nodeRoot, int level ) {//以缩进方式输出哈夫曼树
if(HT==NULL) return; if(nodeRoot->rchild) {
dispHT(HT+nodeRoot->rchild,level+1); }
for(int i=0;i
else
{cout
{cout
coutweightweight
if(nodeRoot->lchild!=0 ) {
dispHT(HT+nodeRoot->lchild,level+1); } }
int main(){ int sel=0;
cout欢迎使用哈夫曼编码/译码器
cout
cout>sel; if(sel==5) break; switch(sel)
{case 1:initHuffmanTree();break; case 3:encoding();break;
case 2:{if(HC==NULL) cout
"
else {outstuf.open("TreePrint.txt",ios::out);
dispHT(HT+2*n-1,1);outstuf.close();}break;} case 4:decode();break;
default:cout
outstuf.close();
cout
四、调试分析：
在写程序与调试的过程中，发现自己对于函数的调用与参数的传递的方面还是存在很多问题，从参数的类型等等方面都出现了很多问题。
关于这个程序的要求比较复杂，刚开始做的时候没有任何思路，最后分模块一点一点的进行。在输出树的直观图的问题上一开始困扰了我很久，后来想到用一个level 记录层数，以缩进的方式分层显示，解决了这个问题。
在调试过程中，出现了很多次明明建立了文件却发现未存入数据的情况，为此我多次进行调试，发现是打开文件的操作放在了循环体内部导致数据无法写入。
整体而言，整个程序主要使用了HuffmanCoding()的方式进行哈夫曼编码，在encoding （）里面用了字符串的匹配进行译码，在decode （）里进行了重新遍历树的过程，在算法的效率以及如何更为节省空间的存储数据上都要进一步改进。
五．测试
欢迎界面
构建哈夫曼树
使用权值文件构建
各字符编码显示
自行输入建树
输入的字符与权值被保存在hfmTree.txt 里面
使用data.txt 建立的哈夫曼树 输出直观图
（不全）
同时存入了文件
自行输入文件进行编码
编码结果被存储在CodeFile.txt 文件里
通过打开文件进行译码
译码结果被存储
通过打开encode.txt 文件进行编码
编码结果同时被存储
通过自行输入文件进行译码
译码同时被存储 退出
六．附录 Hfm.cpp Hfm.exe data.txt