【数据结构】哈夫曼树及哈夫曼编码译码

时间：2022-08-21 10:32:45

一.原理：

1.      哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树共有2*n-1个结点（性质）。

2.      哈夫曼树构建：选取权值最小的两个值，将其作为新树的左右子树，且新树的根结点权值为其左右子树根节点权值之和。删除上两棵树，将新树加入森林

 

 

二.思路：

1． 哈夫曼树的建立：根据输入的字符以及权值，按照哈夫曼树的构建过程，首先建立N个叶子结点，建立过程中双亲结点，左右孩子结点全置为0，之后建立剩余结点（不存数据，仅作为储存权值的中间结点）。从n开始循环到2*n-1,选取权值最小的两结点，将其双亲结点位置改为循环量i，同时根结点权值变为两孩子只和并与左右孩子建立连接。

2． 哈夫曼编码：HC二维数组的指针形式，用来存储每一个字符哈夫曼编码串。若为左孩子，则编码为0，右孩子则编码为1。为方便判断，设fa为当前结点父节点，若HT[fa].lch==current，则数组存0，反之存1，存储时数组从高下标端开始，最后应将其复制到另一字符数组中，便于输出。

3． 将明文转变成暗文（编码）：输入一串字符，将其转化成形如01010001…形式的暗文。即将每一个字符与之前存储的HT字符数组比较，若相等此时的HC[k][]几位所对应的编码串，最后比较完之后所得到的即整条编码串。

4． 将暗文转变成明文(译码）：输入一串形如01010001…形式的暗文，将其转化成有意义的字符串。在根结点按暗文顺序沿哈夫曼树向下走，为0则走左子树，为1则走右子树，当结点左右子树都不存在时，输出此时的字符数据，回溯到根节点。


代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

typedef struct Node{
int weight;  //权值 
int parent;  //父节点序号，0表示根节点 
int lch,rch; //左右孩子节点序号，0为叶子节点 
char data;
}HTNode ,*HuffmanTree;//储存每个叶子节点的哈夫曼编码 
typedef char **HuffmanCode;  //储存每个节点的哈夫曼编码 
int n;           //需要编码的字符个数

int min(HuffmanTree HT,int k)
{
int i=0;
int min;// 用来存放weight最小且parent为0的元素的下标 
int min_weight;//temp值
while(HT[i].parent!=0) i++;
min_weight=HT[i].weight;
min=i;

//选出weight最小的且parent为0的元素 ，将其序号赋值给min
for(;i<k;i++){
if(HT[i].weight<min_weight&&HT[i].parent==0 ){
min_weight=HT[i].weight;
min=i;
} 
} 
//将weight最小的元素的parent置为1，下一次求第二小时将其排除在外 
HT[min].parent=1;
return min;
}

int select_min(HuffmanTree HT,int k,int &min1,int &min2){
min1=min(HT,k);
min2=min(HT,k);
}

HuffmanTree Initialzation(){
FILE *fp=fopen("DataFile.txt","r");
char Arti[1000]; 
//cout<<"输入要编码的字符个数："<<endl;
fscanf(fp,"%d",&n);
while(n<=1){
cout<<"字符个数必须大于1！请重新输入："<<endl;
fscanf(fp,"%d",&n);
}
int *wet=(int *)malloc(n*sizeof(int));  //wet存放权值 
//cout<<"请输入这"<<n<<"个字符和字符的权值(int型) :"<<endl;
for(int i=0;i<n;i++) {
fscanf(fp," %c %d",&Arti[i],wet+i);
}


//哈夫曼树特点：N个叶子节点，共有2N-1个节点
int total=2*n-1;
HuffmanTree HT=(HuffmanTree )malloc(total*sizeof(HTNode));
if(!HT){
cout<<"Malloc Failue!";
} 
int i;

//建立N个叶节点 
for(i=0;i<n;i++){
HT[i].parent=0;  //parent之后会改变（在建立哈夫曼树时，产生根节点）
HT[i].lch=HT[i].rch=0;
HT[i].weight=*wet;
HT[i].data=Arti[i];
wet++; 
}
//HT[n],HT[n+1]...HT[2n-2]中存放的是中间构造出的每棵二叉树的根节点
for(;i<total;i++) {
HT[i].parent=0;
HT[i].lch=HT[i].rch=0;
HT[i].weight=0;
}

int min1,min2;//保存每一轮选出的两个weight值最小（哈夫曼的意义）且parent为0（无根节点，筛选作用）的节点下标 
//每一轮比较之后选出min1,min2构成一颗二叉树，最后成为一颗树（即为所求哈夫曼树）
for(i=n;i<total;i++){
select_min(HT,i,min1,min2);  //在i之前寻找叶节点（前文）,min由于用了引用&，可带回值 
//将i赋min1，min2 的根节点 
HT[min1].parent=i;
HT[min2].parent=i;
//给i的左右孩子赋值 ，即为刚求出的min1,min2 
HT[i].lch=min1;
HT[i].rch=min2;
HT[i].weight=HT[min1].weight+HT[min2].weight;//权值为左右孩子的和 
} 
fclose(fp);
return HT;
}

void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n){
//用来保存指向每个哈夫曼编码串的指针
HC=(HuffmanCode)malloc(n*sizeof(char *));  //注意申请的指针类型char *
if(!HC ) {
cout<<"HuffmanCode malloc FAILED"<<endl;
exit(0);
} 

//临时空间，保存每一次求得的一个哈夫曼编码串
char *code=(char *)malloc(100*sizeof(char));
if(!code) {
cout<<"Code malloc FAILED"<<endl;
exit(0);
} 
code[99]='\0';
//求每个字符的哈夫曼编码
int i;
for(int i=0;i<n;i++){
int current=i;//定义当前访问的节点 
int fa=HT[i].parent;//定义当前节点的父节点 
int start = 99;//每次编码位置，初始为编码结束符的位置
//从叶子节点开始遍历到根节点为止
while(fa!=0){
if(HT[fa].lch==current) code[--start]='0';
else code[--start]='1';
current=fa;
fa=HT[current].parent;
}
 HC[i]=(char *)malloc((99-start+1)*sizeof(char));
 if(!HC) {
 cout<<"HC[i] malloc failed"<<endl;
exit(0); 
 }
 strcpy(HC[i],code+start);
} 
free(code);
}

void EnCoding(HuffmanTree HT,HuffmanCode HC)
{
FILE *fp1=fopen("ToBeTran.txt","r");
FILE *fp2=fopen("Code.txt","wb");
char str[100];
fscanf(fp1,"%s",str);
for(int i=0;i<n;i++){
int k=0;
while(str[i]!=HT[k].data) k++;
//cout<<HC[k];
fprintf(fp2,"%s",HC[k]);
}
cout<<endl;
fclose(fp1);
fclose(fp2);
}

void Decoding(HuffmanTree HT)
{
FILE *fp1=fopen("CodeFile.txt","r");
FILE *fp2=fopen("TextFile.txt","w");
char s[100];
int lenth;
int p=n*2-1-1;
//cout<<"输入编码长度："<<endl; 
fscanf(fp1,"%d",&lenth);
//cout<<"输入编码："<<endl;
fscanf(fp1,"%s",s); 
for(int i=0;i<lenth;i++){
if(s[i]=='0') p=HT[p].lch;
else if(s[i]=='1')  p=HT[p].rch;
if(HT[p].lch==0&&HT[p].rch==0) {
//cout<<HT[p].data;
fprintf(fp2,"%c",HT[p].data);
p=n*2-1-1;
}
}
cout<<endl;
fclose(fp1);
fclose(fp2);
}


void Output(){
FILE *fp1=fopen("DataFile.txt","r");
FILE *fp2=fopen("ToBeTran.txt","r");
FILE *fp3=fopen("Code.txt","r");
FILE *fp4=fopen("CodeFile.txt","r");
FILE *fp5=fopen("Textfile.txt","r");
char datafile[255];
char tobetran[255];
char code[255];
char codefile[255];
char textfile[255];
cout<<"1-datafile数据输出："<<endl<<"  出现的字符以及各字符出现的频度:"<<endl;
fgets(datafile,255,fp1); cout<<datafile<<endl<<endl;
cout<<"2-ToBeTran数据输出："<<endl<<"  编码前"<<endl;
fgets(tobetran,255,fp2); cout<<tobetran<<endl<<endl;
cout<<"3-Code数据输出："<<endl<<"  报文是："<<endl;
fgets(code,255,fp3); cout<<code<<endl<<endl;
cout<<"4-CodeFile数据输出："<<endl<<"  解码前："<<endl;
fgets(codefile,255,fp4); cout<<codefile<<endl<<endl;
cout<<"5-Textfile数据输出："<<endl<<"  原文是："<<endl;
fgets(textfile,255,fp5); cout<<textfile<<endl<<endl;

}
int main(){
HuffmanCode HC;   //保存每个字符的哈夫曼编码 （HuffmanCode为指针的指针类型） 
HuffmanTree HT=Initialzation();//生成哈夫曼树（数组） 
HuffmanCoding(HT,HC,n);//求解每个字符的哈夫曼编码 
EnCoding(HT,HC);
Decoding(HT);
Output();
return 0;
}

标签：

相关文章