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

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

一、问题描述

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。

基本要求：

（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

cout<<\请输入字符\<>HaffNode[i].inf;

cout<<\请输入该字符的权值\<>HaffNode[i].weight; }

for(i=0;i

m1=m2=Maxvalue; x1=x2=0;

for(j=0;j

if(HaffNode[j].parent==-1&&HaffNode[j].weight

m2=m1; x2=x1;

m1=HaffNode[j].weight; x1=j; }

else {

if(HaffNode[j].parent==-1&&HaffNode[j].weight

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<<\显示存储的哈弗曼树信息:\<

cout<

//写入文件

fstream outfile1;

outfile1.open(\,ios::out|ios::trunc|ios::binary);//建立进行写入的文件

if(!outfile1) //没有创建成功则显示相应信息 {

cout<<\文件不能打开\<

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(\,ios::in|ios::binary); in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType)); in.close();

fstream outfile;

outfile.open(\,ios::out|ios::binary);//建立进行写入的文件

for(i=0;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

HaffCode[i].bit[j]=cd.bit[j]; HaffCode[i].start=cd.start; }

for(i=0;i

outfile<

for(j=HaffCode[i].start+1;j

}

cout<<\字符信息--编码信息\<

cout<

for(j=HaffCode[i].start+1;j

outfile.close ();

cout<<\请输入要编码的字符串,基本元素为（\; for(i=0;i

cout<>inf;

int f=strlen(inf); fstream outfile1;

outfile1.open(\,ios::out|ios::binary);//建立进行写入的文件

if(!outfile1) {

cout<<\文件不能打开!\<

{ cout<

cout<<\字符串编码后为:\; for(int x=0;x

for(i=0;i

if(inf[x]==HaffNode[i].inf) {

for(j=HaffCode[i].start+1;j

outfile1.write((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]));

cout<

}

cout<

cout<<\编译后的代码串已经存入code.dat文件中!\<

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(\,ios::in|ios::binary);//读出哈夫曼树

if(!infile1) {

cout<<\文件不能打开\<

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<<\请选择要做的操作：\<>q;

while(q>5||q<4) {

cout<<\输入错误请重新输入\; cin>>q; }

switch(q) {

case 4: {

cout<<\请输入要解码的0,1串(按其他键结束输入）：\<>tempcode[i];

while(tempcode[i]==0||tempcode[i]==1) {

i++; num=i;

cin>>tempcode[i]; }

cout<<\输入的编码为：\; for(i=0;i

cout<<\译码后为：\<

outfile.open(\,ios::out); if(!outfile) {

cout<<\文件不能打开!\<

while(i

{

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<

m=2*n-2; }

cout<

outfile.close();

cout<<\译码后的结果已经存入textfile.txt中!\<

case 5: {

fstream infile2;//读编码

infile2.open(\,ios::in|ios::binary); while(!infile2.eof()) {

infile2.read((char*)&tempcode[num],sizeof(tempcode[num])); num++; }

infile2.close(); num--;

cout<<\从文件中读出的编码为\<

cout<

cout<<\译码后为:\<

outfile.open(\,ios::out); if(!outfile) {

cout<<\文件不能打开!\<

while(i

{

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<

cout<

outfile.close();

cout<<\译码后的结果已经存入textfile.txt中!\<

} 四．编码实现

#include \#include #include #include #include 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

cout<<\请输入字符\<>HaffNode[i].inf;

cout<<\请输入该字符的权值\<>HaffNode[i].weight; }

for(i=0;i

m1=m2=Maxvalue; x1=x2=0;

for(j=0;j

if(HaffNode[j].parent==-1&&HaffNode[j].weight

m2=m1; x2=x1;

m1=HaffNode[j].weight; x1=j; } else {

if(HaffNode[j].parent==-1&&HaffNode[j].weight

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<<\显示存储的哈弗曼树信息:\<

cout<

//写入文件

fstream outfile1;

outfile1.open(\,ios::out|ios::trunc|ios::binary);//建立进行写入的文件

if(!outfile1) //没有创建成功则显示相应信息 {

cout<<\文件不能打开\<

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(\,ios::in|ios::binary);

in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType)); in.close();

fstream outfile;

outfile.open(\,ios::out|ios::binary);//建立进行写入的文件

for(i=0;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

HaffCode[i].bit[j]=cd.bit[j]; HaffCode[i].start=cd.start; }

for(i=0;i

outfile<

for(j=HaffCode[i].start+1;j

cout<<\字符信息--编码信息\<

cout<

for(j=HaffCode[i].start+1;j

outfile.close ();

cout<<\请输入要编码的字符串,基本元素为（\; for(i=0;i

cout<

char inf[100]; cin>>inf;

int f=strlen(inf); fstream outfile1;

outfile1.open(\,ios::out|ios::binary);//建立进行写入的文件

if(!outfile1) {

cout<<\文件不能打开!\<

{ cout<

cout<<\字符串编码后为:\; for(int x=0;x

for(i=0;i

if(inf[x]==HaffNode[i].inf) {

for(j=HaffCode[i].start+1;j

outfile1.write((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]));

cout<

cout<

cout<<\编译后的代码串已经存入code.dat文件中!\<

outfile1.close(); delete []HaffNode; delete []HaffCode; }

void decode( int &n)//解码 {

int i;

HNodeType *HaffNode=new HNodeType[2*n-1]; fstream infile1;

infile1.open(\,ios::in|ios::binary);//读出哈夫曼树

if(!infile1) {

cout<<\文件不能打开\<

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<<\请选择要做的操作：\<>q;

while(q>5||q<4) {

cout<<\输入错误请重新输入\; cin>>q; }

switch(q) {

case 4: {

cout<<\请输入要解码的0,1串(按其他键结束输入）：\<

cin>>tempcode[i];

while(tempcode[i]==0||tempcode[i]==1) {

i++; num=i;

cin>>tempcode[i]; }

cout<<\输入的编码为：\; for(i=0;i

cout<<\译码后为：\<

outfile.open(\,ios::out); if(!outfile) {

cout<<\文件不能打开!\<

while(i

{

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<

cout<

outfile.close();

cout<<\译码后的结果已经存入textfile.txt中!\<

case 5: {

fstream infile2;//读编码

infile2.open(\,ios::in|ios::binary); while(!infile2.eof()) {

infile2.read((char*)&tempcode[num],sizeof(tempcode[num])); num++; }

infile2.close(); num--;

cout<<\从文件中读出的编码为\<

cout<

cout<<\译码后为:\<

outfile.open(\,ios::out); if(!outfile) {

cout<<\文件不能打开!\<

while(i

{

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<

cout<

outfile.close();

cout<<\译码后的结果已经存入textfile.txt中!\<

} int main() {

int n;

cout<<\欢迎进入编/译码系统！*********************\<

int ch1;

do{

cout<<\建树\<

cout<<\编码，并显示字符和对应的编码\<

cout<<\<

cout<<\请选择(0~3):\; cin>>ch1;

while(!(ch1<=3&&ch1>=0)) //输入不在到之间无效 {

cout<<\数据输入错误，请重新选择(0~3):\; cin>>ch1; }

switch(ch1) {

case 1: {

cout<<\请输入编码个数\<

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—010,C—00,D—1

4输入字符串ABCD，使其编译成0,1串，结果为011010001

5、调用译码的功能模块，输入代码串“111110100”后，屏幕上显示译码结果：

111110100 ―――― ABCD

6、从文件中读取0,1串，从而译码结果为：

7、若操作选择错误，会提示：

8若0、1串输入多了，后面无法译码则会提示错误：

七、实验总结

刚看见实验题目时我一点头绪都没有，通过看数据结构书知道了编码如何写代码，但是译码还不不太明白如何进行编写，后来通过网上的资料将自己的思路捋顺了。在译码处，不单实现了从文件读入，同时也实现了从键盘读入，这让我很有满足感。随着对数据结构学习的深入，感觉自己的算法思想在逐步形成中。

本文来源：https://www.bwwdw.com/article/rmvx.html