creat.h

本程序是用哈夫曼树来实现哈夫曼编码译码的。

#include <stdio.h>
#include <iostream>
#define NULL 0
#define MaxWidth 50
#define Maxsize 100

typedef struct                 //哈夫曼树结点类型
{
	char data;             //结点值
	int weight;            //权值
	int parent;            //父结点
	int left;              //左结点
	int right;             //右结点
}huffnode;

typedef struct                 //哈夫曼编码的类型
{
	char cd[Maxsize];
	int start;
}huffcode;

int Creahuffman(huffnode ht[],int n)                     //构造哈夫曼树的函数
{                                                        //n为叶子结点数
	int i,k,l,r,m1,m2;
	if(n<=1)
		return 0;
	for(i=1;i<=2*n-1;i++)                             //2*n-1为结点总数
		ht[i].parent=ht[i].left=ht[i].right=0;
	for(i=n+1;i<=2*n-1;i++)                           //构造哈夫曼树
	{
		m1=m2=32767;                  
		l=r=0;                                     //l,r为最小权值的两个结点位置
		for(k=1;k<=i-1;k++)                        //在ht[1...r-1]中选择parent为0
		{
			if(ht[k].parent==0)                //且weight最小的两个结点，其序号分别为l和r
			{
				if(ht[k].weight<m1)        //找权值最小的树
				{
					m2=m1;
					r=l;
					m1=ht[k].weight;
					l=k;
				}
				else if(ht[k].weight<m2)    //找权值其次小的树
				{
					m2=ht[k].weight;
					r=k;
				}
			}
		}
				ht[l].parent=i;              //换掉l,r两个结点的双亲域
				ht[r].parent=i;                        
				ht[i].weight=ht[l].weight+ht[r].weight;
				if(l<=r)
				{
					ht[i].left=l;
				    ht[i].right=r;
				}
				else {
					 ht[i].left=r;
				     ht[i].right=l;
				}
	}
	ht[i].weight=ht[i].right=ht[i].left=ht[i].parent=0;
	return i-1;
}


void Creahfcode(huffnode ht[],huffcode hcd[])     //求每个叶子结点的哈夫曼编码函数
{
	int i,f,c,n;
	huffcode d;
	for(i=1;ht[i].weight!=0;i++)
	n=i;
    n=(n+1)/2;                                  //n为叶子结点个数
	for(i=1;i<=n;i++)                          //根据哈夫曼树求哈夫曼编码
	{
		d.start=n+1;                          //编码结束符位置
		c=i;
		f=ht[i].parent;
		while(f!=0)                          //从叶子到根逆向求编码
		{
			if(ht[f].left==c)
				d.cd[--d.start]='0';
			else 
				d.cd[--d.start]='1';
			c=f;
			f=ht[f].parent;
		}
		hcd[i]=d;
	}
}


void Disphuffman(huffnode ht[],huffcode hcd[],int n)        //输出函数
{
	int i,k;
	cout<<"  输出哈夫曼编码："<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<  ht[i].data<<"的编码为：";
		for(k=hcd[i].start;k<=n;k++)
			cout<<hcd[i].cd[k];
		cout<<endl;
	}
}


void Disptree(huffnode ht[],int x)                         //以凹入法显示哈夫曼树
{
	huffnode stack[Maxsize],p;
	int lever[Maxsize][2],top,n,i,width=4;
	FILE *fp;
	if((fp=fopen("TreePrint.txt","w"))==NULL)          //将凹入表显示的哈夫曼树存入文件TreePrint
	{
		cout<<"  Cannot open file!"<<endl;
		return;
	}
	if(ht[x].weight!=NULL)
	{
		cout<<endl;
		cout<<"  凹入表表示法："<<endl;
		fprintf(fp,"  凹入表表示法:\n");
		top=1;
		stack[top]=ht[x];                           //根结点入栈
		lever[top][0]=width;
		while(top>0)
		{
			p=stack[top];                       //退栈并凹入显示该结点值
			n=lever[top][0];
			for(i=1;i<=n;i++)
			{
				cout<<" ";
				fprintf(fp," ");
			}
			cout<<p.data;
			fputc(p.data,fp);
			for(i=n+1;i<=MaxWidth;i++)
			{
				cout<<"-";
				fprintf(fp,"-");
			}
			    cout<<endl;
				fprintf(fp,"\n");
				top--;
				if(p.right!=NULL)                //将右子树根结点入栈
				{
					top++;
					stack[top]=ht[p.right];
					lever[top][0]=n+width;     //显示场宽增width
					lever[top][1]=2;
				}
				if(p.left!=NULL)                  //将左子树根结点入栈
				{
					top++;
					stack[top]=ht[p.left]; 
					lever[top][0]=n+width;     //显示场宽增width
					lever[top][1]=1;
				}
		}
	}
}



int Encoding(huffnode ht[],huffcode hcd[])              //编码函数
{
	int i,j,k,n,l=0;
  	for(i=1;ht[i].weight!=0;i++)
	n=i;
	n=(n+1)/2;                                           //哈夫曼数的叶子结点数
	char s[Maxsize];
	char t[5*Maxsize];
	int temp;
	cout<<"**************************************************************************"<<endl;
	cout<<"  选择你想要编码的方式："<<endl;
	cout<<"  1.从文件中读取要编码的内容。"<<endl;
	cout<<"  2.直接输入要编码的内容。"<<endl;	
	cout<<"**************************************************************************"<<endl;
	for(; ;)
	{
		cin>>temp;
		if(temp==1||temp==2)
			break;
		else cout<<"  选择错误，请重新选择！"<<endl;
	}
	if(temp==2)
	{
		cout<<"  输入你想编码的正文：";
	    cout.flush();
		gets(s);
	}
	else if(temp==1)
	{
		FILE *fp;
		char name[20];
		cout<<"  请输入你要读入的文件名：";
	    cin>>name;
	    if((fp=fopen(name,"r"))==NULL)
		{
			cout<<"  该文件不存在！"<<endl;
		    return 0;
		}
		while(!feof(fp))                                //判断文件是否结束
		{
			s[i]=fgetc(fp);
			i++;
		}
		fclose(fp);
	}
	i=0;
	cout<<"  编码结果为:"<<endl;
	while(s[i]!='\0')                                  //当s[i]不是结束符的时候
	{
		int count;
		for(j=1;j<=n;j++)                              //在叶子结点中寻找跟s[i]值相等的结点
		{
			count=0;
			if(ht[j].data==s[i])                       //找到后将其编码输出并存进数组t[l]中
			{
				for(k=hcd[j].start;k<=n;k++)
				{
					cout<<hcd[j].cd[k];
				    t[l]=hcd[j].cd[k];
					l++;
				}
				count=1;
				break;
			}
		}
		i++;
	}
	t[l]='\0';
	cout<<endl;
    FILE *fp;                                 //将编码结果写入文件CodeFile
	if((fp=fopen("CodeFile.txt","w+"))==NULL)
	{
		cout<<"  Cannot open file!"<<endl;
		return 0;
	}
	l=0;
	while(t[l]!='\0')
	{
		fputc(t[l],fp);
		l++;
	}
	fclose(fp);
	return 1;
}



void Decoding(huffnode ht[],int x)           //译码函数(从键盘中直接输入编码）
{
	int i=0;
	FILE *fp;
	if((fp=fopen("TextFile.txt","w+"))==NULL)
	{
		cout<<"  Cannot open file!"<<endl;
		return;
	}
	huffnode p=ht[x];
	cout<<"  输入你想要译码的编码:";
	cout.flush();
	char s[Maxsize];
	gets(s);
	cout<<"  译码结果为：";
	while(s[i]!='\0')
	{
		p=ht[x];
		do{
			if(s[i]=='0')
			p=ht[p.left];
		else if(s[i]=='1')
			p=ht[p.right];
			i++;
		}while(p.left!=NULL&&p.right!=NULL);
		cout<<p.data;
		fputc(p.data,fp);  
	}
	cout<<endl;
	fclose(fp);
}

void Decoding2(huffnode ht[],int x,char t[])           //译码函数（从文件中读入译码）
{
	int i=0;	
	FILE *fp;
	if((fp=fopen("TextFile.txt","w+"))==NULL)
	{
		cout<<"  Cannot open file!"<<endl;
		return;
	}
	huffnode p=ht[x];
    cout<<"  译码结果为：";
	while(t[i]!=EOF)                                  //当t[i]不等于EOF即－1时
	{
		p=ht[x];
		while(p.left!=NULL&&p.right!=NULL)
		{
			if(t[i]=='0')
			p=ht[p.left];
			else if(t[i]=='1')
			p=ht[p.right];
			i++;
		}
		cout<<p.data;
		fputc(p.data,fp);                           //将译码结果存入文件TextFile
	}
	fclose(fp);
	cout<<endl;
}


int Filewrite(huffnode ht[],int n,int j)                   //写入文件htmTree函数
{
    FILE *fp;
	int i;
	if((fp=fopen("htmTree","w"))==NULL)
	{
		cout<<"  Cannot open file!"<<endl;
		return 0;
	}
	for(i=1;i<=2*n;i++)
		if(fwrite(&ht[i],sizeof(huffnode),1,fp)!=1)
			cout<<"  File write error！"<<endl;
	fputc(j,fp);
	fclose(fp);
	return 1;
}

int Fileread(huffnode ht[])                          //读入文件htmTree函数
{
	FILE *fp;
	int i=0,j;
	if((fp=fopen("htmTree","r"))==NULL)
	{
		cout<<"  该文件不存在！"<<endl;
		return 0;
	}
	do
	{
		i++;
		fread(&ht[i],sizeof(huffnode),1,fp);
	}while(ht[i].weight!=0);
	j=fgetc(fp);
	fclose(fp);
	return j;
}


int Readfile1(char t[])                   //读入要译码的文件
{
	int i=0;
    FILE *fp;
    char s[20];
	cout<<"  请输入你要读入的文件名：";
	cin>>s;
	if((fp=fopen(s,"r"))==NULL)
	{
		cout<<"  该文件不存在！"<<endl;
		return 0;
	}
	while(!feof(fp))                   //判断文件是否结束
	{
		t[i]=fgetc(fp);
		i++;
	}
		fclose(fp);
		return 1;
}


void Printcode(char t[])              //打印代码函数
{
	int i,j;
	FILE *fp;
	if((fp=fopen("CodePrin.txt","w"))==NULL)
	{
		cout<<"  Cannot open file！"<<endl;
		return;
	}
	cout<<"  输出代码为"<<endl;
	for(i=0,j=1;t[i]!=EOF;i++,j++)
	{
		cout<<t[i];
		fputc(t[i],fp);
		if(j%50==0)
		{
			cout<<endl;
			fprintf(fp,"\n");
		}
	}
	fclose(fp);
}