设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。
（1） 从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）；
（2） 统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；
（3） 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；
（4） 图形化输出哈夫曼树、哈夫曼编码；
（5） 将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf）
（6） 用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；
（7） 进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。
[测试数据]文本文件自行选择，至少含3000个字符。
[实现代码]
#include<iostream>
#include<fstream>
#include<queue>
#include<math.h>
using namespace std;
struct Node{
public:
Node *right;
Node *left;
char data;
int weight;
int x[];
};
void InsertionSort(Node*A[],int n){
for(int i=;i<n;i++){
Node *get=A[i];
int j=i-;
while(j>=&&A[j]->weight>get->weight){
A[j+]=A[j];
j--;
}
A[j+]=get;
}
}
Node* father(Node*root,Node*son){
Node*temp;
if(root==NULL||son==NULL)
return NULL;
if(root->left==son||root->right==son)
return root;
temp=father(root->left,son);
if(temp!=NULL)
return temp;
else
return father(root->right,son);
}
void preorder(Node*root){
if(root!=NULL) {
cout<<root->weight<<" ";
preorder(root->left);
preorder(root->right);
}
}
void sumlevel(Node*root,int *count,int l){
if(root!=NULL) {
count[l]=count[l]+;
sumlevel(root->left,count,l+);
sumlevel(root->right,count,l+);
}
}
void levelorder(Node*t,int*count){
queue<Node*>q;
int x=,i=;
if(t!=NULL){
Node*p;
for(int z=;z<;z++){
cout<<" ";
}
cout<<t->data<<"("<<t->weight<<")"<<endl;
x=x+;
i=i+;
q.push(t);
while(!q.empty()){
p=q.front();
q.pop();
if(p->left){
for(int z=;z</(i+);z++) cout<<" ";
cout<<p->left->data<<"("<<p->left->weight<<")";
if(x==count[i]){
cout<<endl;
i++;
x=;
}
x=x+;
q.push(p->left);
}
if(p->left){
for(int z=;z</(i);z++) cout<<" ";
cout<<p->right->data<<"("<<p->right->weight<<")";
if(x==count[i]){
cout<<endl;
i++;
x=;
}
x=x+;
q.push(p->right);
}
}
}
}
void TreePrint(Node *T,int level)
{
if (T!=NULL) return;
TreePrint(T->right,level+); //打印右子树，并将层次加1
for (int i=;i<level;i++) //按照递归的层次打印空格
{
printf(" ");
}
cout<<T->weight<<endl;
TreePrint(T->left,level+); //打印左子树，并将层次加1
}
int main(){
//打开待压缩文件
ifstream file("C:\\Users\\wenjian\\start.txt");
char a;
Node *root1;
int n[]={};
int x,i,j,num=;
while(!file.eof()){
file.get(a);
if(file.fail()) break;
x=a;
n[x]++;
}
for(i=;i<;i++){
if(n[i]!=) num++;
}
Node *m[num],*mm[num];
for(i=;i<num;i++){
m[i]=new Node;
m[i]->left=NULL;
m[i]->right=NULL;
}
j=;
for(i=;i<;i++){
if(n[i]!=){
m[j]->data=i;
m[j]->weight=n[i];
j++;
}
}
InsertionSort(m,num);
Node *p1,*p2,*p,*t;
j=;
for(i=;i<num;i++){
mm[i]=m[i];
}
for(i=;i<num-;i++){
t=new Node;
p1=m[i];
p2=m[i+];
t->weight=m[i]->weight+m[i+]->weight;
t->left=p1;
t->right=p2;
p=t;
j=i+;
while(j<num&&p->weight > m[j]->weight){
m[j-]=m[j];
j=j+;
}
m[j-]=p;
}
root1=m[num-];
int zz[];
Node *s,*z;
for(i=;i<num;i++){
for(int xx=;xx<;xx++){
zz[xx]=-;
}
s=father(root1,mm[i]);
z=mm[i];
j=;
while(s!=root1){
if(s->left==z){
zz[-j]=;
}
if(s->right==z){
zz[-j]=;
}
z=s;
s=father(root1,z);
j++;
}
if(s->left==z) zz[-j]=;
if(s->right==z) zz[-j]=;
x=;
for(int xx=g0;xx<;xx++){
if(zz[xx]>-) x++;
}
for(int xx=;xx<;xx++){
zz[xx]=zz[xx+-x];
}
for(int xx=x;xx<;xx++){
zz[xx]=-;
}
for(int xx=;xx<;xx++){
mm[i]->x[xx]=zz[xx];
}
}
for(i=;i<num;i++){
cout<<mm[i]->data<<":"<<mm[i]->weight<<" ";
for(j=;j<;j++){
if(mm[i]->x[j]>=) cout<<mm[i]->x[j];
}
cout<<endl;
}
file.close();
//再次打开文件
ifstream file1("C:\\Users\\wenjian\\start.txt");
//生成的中间文件
ofstream putfile("C:\\Users\\daima\\progress.txt");
//生成压缩.huf文件
ofstream assicfile("C:\\Users\\wenjian\\assic.huf");
int f=,o=,w=;
while(!file1.eof()){
file1.get(a);
if(file1.fail()) break;
for(i=;i<num;i++){
if(mm[i]->data==a){
for(j=;j<;j++){
o=;
if(mm[i]->x[j]==-) break;
putfile<<mm[i]->x[j];
if(f<){
for(int d=;d<-f;d++){
o=*o;
}
w=mm[i]->x[j]*o+w;
f=f+;
}
if(f==){
w=mm[i]->x[j]+w;
f=;
char ww=w;
assicfile<<ww;
w=;
}
}
}
}
}
file1.close();
putfile.close();
// ifstream outfile("progress.txt");
// ofstream infile("end.txt"); /////
//重新打开中间文件，生成最终解压文件
ifstream outfile("C:\\Users\\daima\\progress.txt");
ofstream infile("C:\\Users\\wenjian\\end.txt");
char y;
while(!outfile.eof()){
if(outfile.fail()) break;
s=root1;
z=s;
while(z->left){
outfile.get(y);
if(y==''){
s=z;
z=s->left;
}
if(y==''){
s=z;
z=s->right;
}
}
if(outfile.fail()) break;
infile<<z->data;
}
outfile.close();
infile.close();
int sum[]={};
sumlevel(root1,sum,);
levelorder(root1,sum);
int q=;
for(i=;i<;i++){
q=q*;
if(q>=num) break;
}
int zzz=i+;
ifstream file2("end.txt");
while(!file2.eof()){
if(file2.fail()) break;
file2.get(a);
for(i=;i<zzz;i++){
}
if(file2.fail()) break;
}
file2.close();
float g,h;
cout<<"请分别输入原文件与压缩文件大小："<<endl;
cin>>g;
cin>>h;
float hh=h/g;
cout<<"压缩率："<<-hh<<endl;
}