huffmantreealgo.h

哈夫曼编码实现的源程序。简单

#include"HuffmanTreeDef.h"
#include"pubuse.h"
#include<iostream>
#include<fstream>
#include<string>
#include<malloc.h>
#include<sstream>
int n;
HuffmanTree HT;
HuffmanCode HC;
Status getsort(HuffmanTree HT,int n,int &a,int &b){
	a=0;
	b=0;
	int max1=32767;
	int	max2=32767;
	for(int i=1;i<=n;++i)
		if(HT[i].parent==0)
			if(HT[i].weight<max1)
				{max2=max1;
				max1=HT[i].weight;
				b=a;
				a=i;
				
				}
			else
				if(HT[i].weight<max2)
				{	b=i;
					max2=HT[i].weight;
				}
		
			
	return OK;
}
		
using namespace std;
Status Initialize(){
	int m;
	cout<<"请输入字符的个数:n=";
	cin>>n;
	m=2*n-1;
	if(n<=1)
		{cout<<"输入的字符数目不合理，请重新输入."<<endl;
		return Initialize();
		}
	
	HT=new HTNode[m+1];
	HT[0].weight=10000;
	for(int i=1;i<=n;++i)
		{char ch;
		cout<<"请输入第"<<i<<"个字符:";
		cin>>ch;
		HT[i].c=ch;
		int w;
		cout<<"请输入第"<<i<<"个字符的权值:";
		cin>>w;
		HT[i].num=i;
		HT[i].weight=w;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for(;i<=m;++i)
		{HT[i].c='$';
		HT[i].num=i;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
		}
	int a=0,b=0;
	for(i=n+1;i<=m;++i)
		{getsort(HT,i-1,a,b);
		HT[a].parent=i;
		HT[b].parent=i;
		HT[i].rchild=a;
		HT[i].lchild=b;
		HT[i].weight=HT[a].weight+HT[b].weight;
		}
	cout<<"                 The HuffmanTree is\n";
	cout<<"number    char     weight     parent    rchild    lchild \n";
	for(i=1;i<=m;++i)
		cout<<"  "<<HT[i].num<<"        "<<HT[i].c<<"         "<<HT[i].weight<<"         "<<HT[i].parent<<"          "<<HT[i].rchild<<"         "<<HT[i].lchild<<endl;
	ofstream out("hfmTree.txt");
	out<<"                  The HuffmanTree is\n";
	out<<"number    char     weight     parent    rchild    lchild \n";
	for(i=1;i<=m;++i)
		out<<"  "<<HT[i].num<<"        "<<HT[i].c<<"         "<<HT[i].weight<<"         "<<HT[i].parent<<"          "<<HT[i].rchild<<"         "<<HT[i].lchild<<endl;
	return OK;	
}
 Status Encode(){
	char *cd=(char*)NULL;
	if(HC!=NULL) free(HC);
    HC=(char **)calloc(n+1,sizeof(char *));
	if(HC==NULL) return OK;
	if(cd!=NULL) free(cd);
    cd=(char *)calloc(n,sizeof(char));
	if(cd==NULL) return OK;
	for(int i=1;i<=n;i++)
    {
        int start=n-1;
        for(int c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
        {
			if(HT[f].lchild==c)
                cd[--start]='0';
            else
                cd[--start]='1';
        }

        HC[i]=(char *)malloc((n-start)*sizeof(char));
        strcpy(HC[i],&cd[start]);
    }
    free(cd);
	char a;
	ifstream in("ToBeTran.txt");
	ofstream out("CodeFile.txt");
	for(string s;getline(in,s);)
		{for(istringstream sin(s);sin>>a;)
			for(i=1;i<=n;++i)
				if(HT[i].c==a)
					out<<HC[i];
			out<<"\n";
		}
	cout<<"编码已经完成!保存在CodeFile.txt文件中.\n";
	return OK;

}
Status Decode(){
	int m=2*n-1;
	char a;
	ifstream in ("CodeFile.txt");
	ofstream out("TextFile.txt");
	for(string s;getline(in,s);)
		{for(istringstream sin(s);sin>>a;)
			{	if(a=='0')
					m=HT[m].lchild;
				else
					m=HT[m].rchild;
				if(HT[m].lchild==0&&HT[m].rchild==0)
					{out<<HT[m].c;
					m=2*n-1;
					}
			}
		out<<"\n";
		}
	cout<<"译码已经完成!保存在TextFile.txt文件中.\n";
	return OK;
	
}
Status Print(){
	ifstream in("CodeFile.txt");
	ofstream out("CodePrin.txt");
	int i=0;
	char a;
	for(string s;getline(in,s);)
		for(istringstream sin(s);sin>>a;)
			{
			cout<<a;
			out<<a;
			++i;
			if(i%50==0)
				{cout<<"\n";
				out<<"\n";
				}
			}
		cout<<endl;
	
		
	return OK;
		
}
Status TreePrint(){
	ofstream out("TreePrint.txt");
	cout<<"char--------code\n";
	out<<"char--------code\n";
	for(int i=1;i<=n;i++)
		{
		cout<<" "<<HT[i].c<<"-----------"<<HC[i]<<endl;
		out<<" "<<HT[i].c<<"-----------"<<HC[i]<<endl;
		}
	return OK;

}
char show()
{
    char choose;
	cout<<endl;
    cout<<"********************* 赫夫曼编码编译系统 **************************\n";
	cout<<"	i/I---Initialize    e/E---Encode         d/D---Decode\n\n";
	cout<<"	p/P---print         t/T---TreePrint      q/Q---Quit program\n";
	cout<<"******************* 赫夫曼编码编译系统 ****************************\n";      
    cout<<"请从菜单中选择一个操作.(不分大小写)\n";
    cout<<">";
    cin>>choose;
    return choose;
}