Huffman编码与解码 (必做)（Huffman编码、二叉树）
[问题描述]
对一篇不少于5000字符的英文文章（source.txt），统计各字符出现的次数，实现Huffman编码(code.dat)，以及对编码结果的解码(recode.txt)。
[基本要求]
（1） 输出每个字符出现的次数和编码,并存储文件(Huffman.txt)。
（2） 在Huffman编码后，英文文章编码结果保存到文件中(code.dat)，编码结果必须是二进制形式，即0 1的信息用比特位表示，不能用字符’0’和’1’表示。
（3） 实现解码功能。
数据结构
用到的数据结构为二叉树、文本文件的读写、Huffman的编码与解码。
算法设计与思想
建立一个数组，从文件中一个个读取文章数据，利用哈希表的思想，根据所得字符的ASCII值在数组里分配地址，并对其值加一，以此统计字符的出现次数。
建立一个值为树结点的数组，存储文章的字符，每次选出ASCII值最小的两个字符作为新结点的左右子树，将新节点的权值置为左、右子树上根结点的权，即为ASCII值的和，再将刚刚所选的字符从数组里删除。重复上述步骤，直到构建出一个二叉树为止。设置数组存储编码，利用中序遍历依次递归遍历哈夫曼树，对哈夫曼树中存储的字符调用编码函数进行编码，编码函数也用递归实现，向左走为0，向右为1。对树中结点编码完毕后，从文章中依次读取字符，在树中查找相应的字符并存储编码到文件中；最后再从文件中读取哈弗曼编码，在树中查找字符，0便进入左子树，1便进入右子树，找到后直接输出。
测试数据和结果
源代码
#include<iostream>
#include<stdlib.h>
#include<fstream>
using namespace std;
#define max 257
int zm[max]={0}; //存储每个字母的出现次数
int word[5000]={0}; //存储字符
int num=0; //储存字符的总数量
typedef struct BiTNode
{
int weight; //权值
int word=300; //字母(ASCLL码)
int code[150]; //Huffman编码
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void Statistic_zm(int zm[])
{
ifstream readfile;
readfile.open("source.txt");
if(readfile.fail())
{
cout<<"不能打开文件"<<endl;
exit(0);
}
int i=0,j;
char ch;
while(!readfile.eof())
{
readfile.get(ch);
j=(int)ch;
zm[j]++;
word[i]=j;
i++;
}
num=i-2;
/*int sum=0;
for(int k=0;k<max-1;k++)
{
cout<<zm[k]<<" ";
sum=sum+zm[k];
}
cout<<"sum="<<sum;*/
readfile.close();
}
void CreateHuffmanTree(int a[],BiTree &T)
{
BiTree point[max];
BiTNode *b,*q;
int i=0,j,k=0;
for(j=0;j<max;j++)
{
if(a[j]!=0)
{
b=(BiTNode*)malloc(sizeof(BiTNode));
b->word=j;
b->weight=a[j];
b->lchild=NULL; b->rchild=NULL;
point[k]=b;
k++;
}
} //k的数量为结点的数量，point中储存每个结点的地址
/*for(int i=0;i<k;i++)
{
cout<<point[i]->weight<<" ";
}*/
//建立Huffman树
for(i=1;i<k;i++) //k个结点建树，需要k-1次归并
{
int small = -1, big;
//让small初始指向森林中第一棵树，big指向第二棵
for ( j=0; j<k; j++ )
{
if ( point[j]!= NULL && small==-1 )
{
small = j;
continue;
}
if ( point[j]!= NULL )
{
big = j;
break;
}
}
//从当前森林中求出最小权值树和次最小
for ( j=big; j<k; j++)
{
if ( point[j]!= NULL)
{
if ( point[j]->weight < point[small]->weight )
{
big = small ;
small = j;
}
else if ( point[j]->weight < point[big]->weight )
big = j;
}
}
//由最小权值树和次最小权值树建立一棵新树，q指向树根结点
q = (BiTNode *) malloc ( sizeof(BiTNode) );
q->weight = point[small]->weight + point[big]->weight;
q->word = 300;
q->lchild = point[small];
q->rchild = point[big];
point[small] = q;//将指向新树的指针赋给b指针数组中small位置
point[big] = NULL;
}
T = q;
}
void bianma_T ( BiTree T, int b[], int ch, int n )
{
int i;
if ( T )
{
if ( ch == T->word )//复制编码
{
b[0] = n;//存储编码长度
for( i=0; i<=n; i++ )
{
T->code[i] = b[i];
}
}
else
{
b[n]=0;
bianma_T ( T->lchild , b , ch , n+1 );
b[n]=1;
bianma_T ( T->rchild , b , ch , n+1 );
}
}
}
//利用递归依次创建编码
void Creat_HCode ( BiTree T , BiTree B )
{
if ( T == NULL )
{
return;
}
else
{
if ( T->word!=300 )//若此节点为文章内的字符，则对它进行编码
{
int ch = T->word;
int b[100];
bianma_T ( B , b , ch , 1);
}
Creat_HCode ( T->lchild , B );
Creat_HCode ( T->rchild , B);
}
}
void WriteCode ( BiTree T )
{
int i;
if ( T == NULL )
{
return;
}
else
{
WriteCode( T->lchild );
if ( T->word!=300 )//若此节点为文章内的字符，则向Huffman.txt存储结点信息
{
ofstream read_out;
read_out.open( "Huffman.txt", ios::app );
if( !read_out )
{
cout<< "文件打开失败!" <<endl;
return;
}
char ch;
ch = T->word;//将整型转化为字符型
read_out<< "字符："<< ch <<" 出现次数："<< T->weight <<" 编码：";
for( i=1; i < T->code[0]; i++ )
read_out<< T->code[i];
read_out<<endl;
read_out.close();
read_out.clear();
}
WriteCode( T->rchild);
}
}
BiTNode* search(BiTree T,int ch)
{
BiTNode* p=NULL;
if(T==NULL) return NULL;
else if(T->word==ch) return T;
else
{
p=search(T->lchild,ch);
if(p==NULL) return search(T->rchild,ch);
else return p;
}
}
void StorageCode(BiTree T)
{ char ch;
BiTNode* p;
ifstream readfile;
readfile.open("source.txt");
fstream file("code.dat",ios::out | ios::binary);
if(readfile.fail())
{
cout<<"不能打开文件"<<endl;
exit(0);
}
int i=0,y,H[20];
while(!readfile.eof())
{
readfile.get(ch);
y=(int)ch;
p=search(T,y);
H[0]=p->code[0];
for(int i=1;i<p->code[0];i++)
H[i]=p->code[i];
file.write((char*)H, sizeof(H));
}
readfile.close();
file.close();
}
int jiema ( BiTree T, int H[] )
{
int i=0;
for( i=1; i<H[0]; i++ )
{
if( H[i]==0 )
T = T->lchild;
else if ( H[i]==1 )
T = T->rchild;
}
return T->word;
}
void CrackCode(BiTree T)
{
int y, H[20];
char ch;
fstream file("code.dat",ios::in | ios::binary);
fstream writefile;
writefile.open("recode.txt");
if(writefile.fail())
{
cout<<"不能打开文件"<<endl;
exit(0);
}
while( !file.eof() )
{
file.read( (char*)H, sizeof(H) );
y = jiema ( T , H );//j存储编码H所对应的字符
ch=(char) y;
writefile.put(ch);
}
}
int main()
{
Statistic_zm(zm);
BiTree T;
CreateHuffmanTree(zm,T);
cout<<endl;
Creat_HCode(T,T);
cout<<endl;
WriteCode( T );
/*char ch;
cin>>ch;
int y=(int)ch;
BiTNode* p=search(T,y);
for(int i=1;i<p->code[0];i++)
printf("%d",p->code[i]);*/
StorageCode(T);
CrackCode(T);
}
Source.txt文件中的内容
Huffman.txt文件中的内容
recode.txt文件中的内容
