实验五哈夫曼编码与译码的设计与实现.doc

实验五 哈夫曼编码与译码的设计与实现
一、问题描述
运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成本。但是，这规定在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。
基本规定：
（1）接受原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文献nodedata.dat中。
（2）编码：运用已建好的哈夫曼树（如不在内存，则从文献nodedata.dat中读入），对文献中的正文进行编码，然后将结果存入文献code.dat中。
（3）译码：运用已建好的哈夫曼树将文献code.dat中的代码进行译码，结果存入文献textfile.txt中。
（4）打印编码规则：即字符与编码的一一相应关系。
（5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。
二、数据结构设计
1、
构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。
在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设立为2n-1，描述结点的数据类型为：
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
char inf;

}HNodeType;
2.求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
求哈夫曼编码事实上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所通过的途径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位码。所以设计如下数据类型：
#define MaxBit 10
struct HcodeType
{
int bit[MaxBit];
int start;
};
3、文献nodedata.dat、code.dat、textfile.txt
三、功能函数设计
1、初始化功能模块
此功能模块的功能为从键盘接受字符集大小n，以及n个字符和n个权值。
2、建立哈夫曼编码的功能模块
此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文献nodedata.dat中。
函数原型为：
void Creat_Haffmantree(int &n)
{
HNodeType *HaffNode=new HNodeType[2*n-1];
int i,j;
int m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
HaffNode[i].weight=0;
HaffNode[i].parent=-1;
HaffNode[i].lchild=-1;
HaffNode[i].rchild=-1;
HaffNode[i].inf='0';
}
for(i=0;i<n;i++)
{
cout<<"请输入字符"<<endl;
cin>>HaffNode[i].inf;
cout<<"请输入该字符的权值"<<endl;
cin>>HaffNode[i].weight;
}
for(i=0;i<n-1;i++)//构造哈夫曼树
{
m1=m2=Maxvalue;
x1=x2=0;
for(j=0;j<n+i;j++)//选取最小和次小
{
if(HaffNode[j].parent==-1&&HaffNode[j].weight<m1)
{
m2=m1;
x2=x1;
m1=HaffNode[j].weight;
x1=j;
}
else
{
if(HaffNode[j].parent==-1&&HaffNode[j].weight<m2)
{
m2=HaffNode[j].weight;
x2=j;
}
}
}
//将找出的最小和次小合并，发明其父母结点
HaffNode[x1].parent=n+i;
HaffNode[x2].parent=n+i;
HaffNode[n+i].weight=HaffNode[x1].weight+HaffNode[x2].weight;
HaffNode[n+i].lchild=x2;
HaffNode[n+i].rchild=x1;
HaffNode[n+i].inf=NULL;
}
cout<<"显示存储的哈弗曼树信息:"<<endl;
cout<<"权值左孩子右孩子双亲"<<endl;
for(i=0;i<2*n-1;i++)
{
cout<<HaffNode[i].inf<<" ";
cout<<HaffNode[i].weight<<" ";
cout<<HaffNode[i].lchild<<" ";
cout<<HaffNode[i].rchild<<" ";
cout<<HaffNode[i].parent<<endl;

}
//写入文献
fstream outfile1;
outfile1.open("E:\\nodedata.dat",ios::out|ios::trunc|ios::binary);//建立进行写入的文献
if(!outfile1) //没有创建成功则显示相应信息
{
cout<<"nodedata.dat文献不能打开"<<endl;
abort();
}
for(i=0;i<2*n-1;i++) //将内存中从HaffNode[i]地址开始的sizeof(HaffNode[i])的内容写入文献中
outfile1.write((char*)&HaffNode[i],sizeof(HaffNode[i]));
outfile1.close ();//关闭文献
delete []HaffNode;

}
3、建立哈弗曼编码功的功能模块
此模块功能是从文献nodedata.dat中读入相关的字符信息进行哈弗曼编码，然后将结果存入code.dat中，同时将字符与0和1代码串的一一相应关系显示到屏幕上。
函数原型为：
void HaffCode(int &n)//哈夫曼编码
{

HNodeType *HaffNode=new HNodeType[Maxnode];
HcodeType *HaffCode=new HcodeType[Maxleaf];
HcodeType cd;
int i,j,c,p;
fstream in("E:\\nodedata.dat",ios::in|ios::binary);
in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType));
in.close();
fstream outfile;
outfile.open("E:\\codedata.dat",ios::out|ios::binary);//建立进行写入的文献
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HaffNode[c].parent;
while(p!=-1)
{
if(HaffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HaffNode[c].parent;
}
for(j=cd.start+1;j<n;j++)
HaffCode[i].bit[j]=cd.bit[j];
HaffCode[i].start=cd.start;
}
for(i=0;i<n;i++)
{
outfile<<HaffNode[i].inf;
for(j=HaffCode[i].start+1;j<n;j++)
outfile<<HaffCode[i].bit[j];

}
cout<<"字符信息--编码信息"<<endl;
for(i=0;i<n;i++)
{
cout<<HaffNode[i].inf<<"---";
for(j=HaffCode[i].start+1;j<n;j++)
cout<<HaffCode[i].bit[j];
cout<<endl;
}
outfile.close ();
cout<<"请输入要编码的字符串,基本元素为（";
for(i=0;i<n;i++)
cout<<HaffNode[i].inf<<",";
cout<<")"<<endl;
char inf[100];
cin>>inf;
int f=strlen(inf);
fstream outfile1;
outfile1.open("E:\\code.dat",ios::out|ios::binary);//建立进行写入的文献
if(!outfile1)
{
cout<<"code.dat文献不能打开!"<<endl;
abort();
}
else
{ cout<<endl;
cout<<"字符串编码后为:";
for(int x=0;x<f;x++)
{
for(i=0;i<n;i++)
{
if(inf[x]==HaffNode[i].inf)
{
for(j=HaffCode[i].start+1;j<n;j++)
{
outfile1.write((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]));
cout<<HaffCode[i].bit[j];
}
}
}
}
}
cout<<endl;
cout<<"编译后的代码串已经存入code.dat文献中!"<<endl;
cout<<endl;
outfile1.close();
delete []HaffNode;
delete []HaffCode;

}
4. 此模块功能为接受需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文献textfile.dat，同时将翻译的结果在屏幕上打印输出。接受0、1代码串有两种形式，一种是直接输入，一种是从文献中读取。
函数原型为：
void decode( int &n)//解码
{
int i;
HNodeType *HaffNode=new HNodeType[2*n-1];
fstream infile1;
infile1.open("E:\\nodedata.dat",ios::in|ios::binary);//读出哈夫曼树
if(!infile1)
{
cout<<"nodedata.dat文献不能打开"<<endl;
abort();
}
for(i=0;i<2*n-1;i++)
infile1.read((char*)&HaffNode[i],sizeof(HNodeType));
infile1.close();
int tempcode[100];
int num=0;
for(i=0;i<100;i++)
tempcode[i]=-1;
HcodeType *Code=new HcodeType[n];
cout<<"请选择要做的操作："<<endl;
cout<<"输入串解码，请按4"<<endl;
cout<<"从文献中解码，请按5"<<endl;
int q;
cin>>q;
while(q>5||q<4)
{
cout<<"输入错误请重新输入";
cin>>q;
}
switch(q)
{
case 4:
{
cout<<"请输入要解码的0,1串(按其他键结束输入）："<<endl; i=0;
cin>>tempcode[i];
while(tempcode[i]==0||tempcode[i]==1)
{
i++;
num=i;
cin>>tempcode[i];
}
cout<<"输入的编码为：";
for(i=0;i<num;i++)
cout<<tempcode[i];
cout<<endl;
int m=2*n-2;
i=0;
cout<<"译码后为："<<endl;
fstream outfile;
outfile.open("E:\\textfile.txt",ios::out);
if(!outfile)
{
cout<<"textfile.txt文献不能打开!"<<endl;
abort();
}
while(i<num)// 小于字符串的长度

{
while(HaffNode[m].lchild!=-1&&HaffNode[m].rchild!=-1)
{
if(tempcode[i]==0)
{
m=HaffNode[m].lchild;
i++;
}
else if(tempcode[i]==1)
{
m=HaffNode[m].rchild;
i++;
}
}
cout<<HaffNode[m].inf;
outfile<<HaffNode[m].inf;
m=2*n-2;
}
cout<<endl;
outfile.close();
cout<<"译码后的结果已经存入textfile.txt中!"<<endl;
delete []HaffNode;
break;
}
case 5:
{

fstream infile2;//读编码
infile2.open("E:\\code.dat",ios::in|ios::binary);
while(!infile2.eof())
{
infile2.read((char*)&tempcode[num],sizeof(tempcode[num]));
num++;
}
infile2.close();
num--;
cout<<"从文献中读出的编码为"<<endl;
for(i=0;i<num;i++)
cout<<tempcode[i];
cout<<endl;
int m=2*n-2;
i=0;
cout<<endl;
cout<<"译码后为:"<<endl;
fstream outfile;
outfile.open("E:\\textfile.txt",ios::out);
if(!outfile)
{
cout<<"textfile.txt文献不能打开!"<<endl;
abort();
}
while(i<num)// 小于字符串的长度

{
while(HaffNode[m].lchild!=-1&&HaffNode[m].rchild!=-1)
{
if(tempcode[i]==0)
{
m=HaffNode[m].lchild;
i++;
}
else if(tempcode[i]==1)
{
m=HaffNode[m].rchild;
i++;
}
}
cout<<HaffNode[m].inf;
outfile<<HaffNode[m].inf;
m=2*n-2;
}
cout<<endl;
outfile.close();
cout<<"译码后的结果已经存入textfile.txt中!"<<endl;
delete []HaffNode;
break;
}
}

}
四．编码实现
#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define MaxBit 10
#define Maxvalue 100//应当大于权重之和
#define Maxleaf 100
#define Maxnode Maxleaf*2-1
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
char inf;

}HNodeType;
struct HcodeType
{
int bit[MaxBit];
int start;
};

void Creat_Haffmantree(int &n)
{
HNodeType *HaffNode=new HNodeType[2*n-1];
int i,j;
int m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
HaffNode[i].weight=0;
HaffNode[i].parent=-1;
HaffNode[i].lchild=-1;
HaffNode[i].rchild=-1;
HaffNode[i].inf='0';
}
for(i=0;i<n;i++)
{
cout<<"请输入字符"<<endl;
cin>>HaffNode[i].inf;
cout<<"请输入该字符的权值"<<endl;
cin>>HaffNode[i].weight;
}
for(i=0;i<n-1;i++)//构造哈夫曼树
{
m1=m2=Maxvalue;
x1=x2=0;
for(j=0;j<n+i;j++)//选取最小和次小
{
if(HaffNode[j].parent==-1&&HaffNode[j].weight<m1)
{
m2=m1;
x2=x1;
m1=HaffNode[j].weight;
x1=j;
}
else
{
if(HaffNode[j].parent==-1&&HaffNode[j].weight<m2)
{
m2=HaffNode[j].weight;
x2=j;
}
}
}
//将找出的最小和次小合并，发明其父母结点
HaffNode[x1].parent=n+i;
HaffNode[x2].parent=n+i;
HaffNode[n+i].weight=HaffNode[x1].weight+HaffNode[x2].weight;
HaffNode[n+i].lchild=x2;
HaffNode[n+i].rchild=x1;
HaffNode[n+i].inf=NULL;
}
cout<<"显示存储的哈弗曼树信息:"<<endl;
cout<<"权值左孩子右孩子双亲"<<endl;
for(i=0;i<2*n-1;i++)
{
cout<<HaffNode[i].inf<<" ";
cout<<HaffNode[i].weight<<" ";
cout<<HaffNode[i].lchild<<" ";
cout<<HaffNode[i].rchild<<" ";
cout<<HaffNode[i].parent<<endl;

}
//写入文献
fstream outfile1;
outfile1.open("E:\\nodedata.dat",ios::out|ios::trunc|ios::binary);//建立进行写入的文献
if(!outfile1) //没有创建成功则显示相应信息
{
cout<<"nodedata.dat文献不能打开"<<endl;
abort();
}
for(i=0;i<2*n-1;i++) //将内存中从HaffNode[i]地址开始的sizeof(HaffNode[i])的内容写入文献中
outfile1.write((char*)&HaffNode[i],sizeof(HaffNode[i]));
outfile1.close ();//关闭文献
delete []HaffNode;

}
void HaffCode(int &n)//哈夫曼编码
{

HNodeType *HaffNode=new HNodeType[Maxnode];
HcodeType *HaffCode=new HcodeType[Maxleaf];
HcodeType cd;
int i,j,c,p;
fstream in("E:\\nodedata.dat",ios::in|ios::binary);
in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType));
in.close();
fstream outfile;
outfile.open("E:\\codedata.dat",ios::out|ios::binary);//建立进行写入的文献
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HaffNode[c].parent;
while(p!=-1)
{
if(HaffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HaffNode[c].parent;
}
for(j=cd.start+1;j<n;j++)
HaffCode[i].bit[j]=cd.bit[j];
HaffCode[i].start=cd.start;
}
for(i=0;i<n;i++)
{
outfile<<HaffNode[i].inf;
for(j=HaffCode[i].start+1;j<n;j++)
outfile<<HaffCode[i].bit[j];

}
cout<<"字符信息--编码信息"<<endl;
for(i=0;i<n;i++)
{
cout<<HaffNode[i].inf<<"---";
for(j=HaffCode[i].start+1;j<n;j++)
cout<<HaffCode[i].bit[j];
cout<<endl;
}
outfile.close ();
cout<<"请输入要编码的字符串,基本元素为（";
for(i=0;i<n;i++)
cout<<HaffNode[i].inf<<",";
cout<<")"<<endl;
char inf[100];
cin>>inf;
int f=strlen(inf);
fstream outfile1;
outfile1.open("E:\\code.dat",ios::out|ios::binary);//建立进行写入的文献
if(!outfile1)
{
cout<<"code.dat文献不能打开!"<<endl;
abort();
}
else
{ cout<<endl;
cout<<"字符串编码后为:";
for(int x=0;x<f;x++)
{
for(i=0;i<n;i++)
{
if(inf[x]==HaffNode[i].inf)
{
for(j=HaffCode[i].start+1;j<n;j++)
{
outfile1.write((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]));
cout<<HaffCode[i].bit[j];
}
}
}
}
}
cout<<endl;
cout<<"编译后的代码串已经存入code.dat文献中!"<<endl;
cout<<endl;
outfile1.close();
delete []HaffNode;
delete []HaffCode;

}
void decode( int &n)//解码
{
int i;
HNodeType *HaffNode=new HNodeType[2*n-1];
fstream infile1;
infile1.open("E:\\nodedata.dat",ios::in|ios::binary);//读出哈夫曼树
if(!infile1)
{
cout<<"nodedata.dat文献不能打开"<<endl;
abort();
}
for(i=0;i<2*n-1;i++)
infile1.read((char*)&HaffNode[i],sizeof(HNodeType));
infile1.close();
int tempcode[100];
int num=0;
for(i=0;i<100;i++)
tempcode[i]=-1;
HcodeType *Code=new HcodeType[n];
cout<<"请选择要做的操作："<<endl;
cout<<"输入串解码，请按4"<<endl;
cout<<"从文献中解码，请按5"<<endl;
int q;
cin>>q;
while(q>5||q<4)
{
cout<<"输入错误请重新输入";
cin>>q;
}
switch(q)
{
case 4:
{
cout<<"请输入要解码的0,1串(按其他键结束输入）："<<endl;
i=0;
cin>>tempcode[i];
while(tempcode[i]==0||tempcode[i]==1)
{
i++;
num=i;
cin>>tempcode[i];
}
cout<<"输入的编码为：";
for(i=0;i<num;i++)
cout<<tempcode[i];
cout<<endl;
int m=2*n-2;
i=0;
cout<<"译码后为："<<endl;
fstream outfile;
outfile.open("E:\\textfile.txt",ios::out);
if(!outfile)
{
cout<<"textfile.txt文献不能打开!"<<endl;
abort();
}
while(i<num)// 小于字符串的长度

{
while(HaffNode[m].lchild!=-1&&HaffNode[m].rchild!=-1)
{
if(tempcode[i]==0)
{
m=HaffNode[m].lchild;
i++;
}
else if(tempcode[i]==1)
{
m=HaffNode[m].rchild;
i++;
}
}
cout<<HaffNode[m].inf;
outfile<<HaffNode[m].inf;
m=2*n-2;
}
cout<<endl;
outfile.close();
cout<<"译码后的结果已经存入textfile.txt中!"<<endl;
delete []HaffNode;
break;
}
case 5:
{

fstream infile2;//读编码
infile2.open("E:\\code.dat",ios::in|ios::binary);
while(!infile2.eof())
{
infile2.read((char*)&tempcode[num],sizeof(tempcode[num]));
num++;
}
infile2.close();
num--;
cout<<"从文献中读出的编码为"<<endl;
for(i=0;i<num;i++)
cout<<tempcode[i];
cout<<endl;
int m=2*n-2;
i=0;
cout<<endl;
cout<<"译码后为:"<<endl;
fstream outfile;
outfile.open("E:\\textfile.txt",ios::out);
if(!outfile)
{
cout<<"textfile.txt文献不能打开!"<<endl;
abort();
}
while(i<num)// 小于字符串的长度

{
while(HaffNode[m].lchild!=-1&&HaffNode[m].rchild!=-1)
{
if(tempcode[i]==0)
{
m=HaffNode[m].lchild;
i++;
}
else if(tempcode[i]==1)
{
m=HaffNode[m].rchild;
i++;
}
}
cout<<HaffNode[m].inf;
outfile<<HaffNode[m].inf;
m=2*n-2;
}
cout<<endl;
outfile.close();
cout<<"译码后的结果已经存入textfile.txt中!"<<endl;
delete []HaffNode;
break;
}
}

}
int main()
{
int n;
cout<<"************* 欢迎进入编/译码系统！*********************"<<endl;
int ch1;

do{

cout<<" 1.建树"<<endl;
cout<<" 2:编码，并显示字符和相应的编码"<<endl;
cout<<" 3:译码"<<endl;
cout<<" 0:退出"<<endl;
cout<<"********************************************************"<<endl;
cout<<"请选择(0~3):";
cin>>ch1;
while(!(ch1<=3&&ch1>=0)) //输入不在到之间无效
{
cout<<"数据输入错误，请重新选择(0~3):";
cin>>ch1;
}
switch(ch1)
{
case 1:
{
cout<<"\t\t\t请输入编码个数"<<endl;//叶子结点个数
cin>>n;
Creat_Haffmantree(n);
break;
}
case 2: HaffCode(n); break;
case 3: decode(n); break;
}
}while(ch1!=0);
return 0;
}
五、界面设立
在主函数中运用do while语句，使程序可以不断循环

六、运营与测试
1、令叶子结点个数n为4，权值集合为{1，3，5，7}，字符集合为{A，B，C，D}，并有如下相应关系，A――1、B――3，C――5，D――7，调用初始化功能模块可以对的接受这些数据。
2、调用建立哈夫曼树的功能模块，构造静态链表HuffNode的存储。

3、调用建立哈夫曼编码的功能模块，在屏幕上显示如下相应关系：
A---011，B—0