hfmfunc.cpp

实现霍夫曼编码系统。包含文件hfmfunc.cpp、main.cpp、huffman.h

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include"huffman.h"
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
	int i,t;
	for(i=1;i<=n&&HT[i].parent;i++);
		s1=i;
	for(i=i+1;i<=n&&HT[i].parent;i++);
		s2=i;
	for(i=i+1;i<=n;i++)
	{
		if(HT[s1].weight>HT[s2].weight)t=s1;
		else t=s2;
		if(HT[i].parent==0&&HT[i].weight<HT[t].weight)
		{
			t=i;
            if(HT[s1].weight>HT[s2].weight)s1=t;
			else s2=t;
		}
	}
	if(HT[s1].lchild!=0&&HT[s2].lchild==0||s1>s2)
	{//若s1为非叶子结点而s2是叶子结点或者s1>s2则调换s1和s2的次序
		t=s1;
		s1=s2;
		s2=t;
	}
}
Status HfmCoding(Huffman &Hfm)
{
      int i,s1,s2,n,start,c,f;
	  char *cd;
	  n=Hfm.length;
	  for(i=n+1;i<=2*n-1;++i)
	  {//s1为左孩子而s2为右孩子
		  s1=s2=0;
		  Select(Hfm.HT,i-1,s1,s2);
		  Hfm.HT[s1].parent=i;
		  Hfm.HT[s2].parent=i;
		  Hfm.HT[i].lchild=s1;
          Hfm.HT[i].rchild=s2;
		  Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;
	  }
	  Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	  cd=(char *)malloc(n*sizeof(char));
	  cd[n-1]='\0';
	  for(i=1;i<=n;++i)
	  {
		  start=n-1;
		  for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
			  if(Hfm.HT[f].lchild==c)cd[--start]='0';
			  else cd[--start]='1';
			  Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
			  strcpy(Hfm.HC[i],&cd[start]);
			  //TEXT:printf("%s\n",Hfm.HC[i]);
	  }
	  free(cd);
	  return OK;
}
Huffman InputHuffman(Huffman Hfm)
{
	int i,n,m;
	printf("\n请输入字符长度\n");
	fflush(stdin);
	scanf("%d",&n);
	while(n<1)
	{
		printf("\n请输入字符长度\n");
		fflush(stdin);
		scanf("%d",&n);
	}
	getchar();
	m=2*n-1;
	Hfm.HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
	Hfm.CH=(char *)malloc((n+1)*sizeof(char));//0号单元不用
    for(i=1;i<=n;++i)
	{
		fflush(stdin);
		printf("\n请输入第%d个字符\n",i);
		scanf("%c",&Hfm.CH[i]);
		printf("\n请输入第%d个字符对应的权值\n",i);
		scanf("%d",&Hfm.HT[i].weight);
		Hfm.HT[i].parent=0;
		Hfm.HT[i].lchild=0;
		Hfm.HT[i].rchild=0;
	}
	for(;i<=m;++i)
	{
		Hfm.HT[i].parent=0;
		Hfm.HT[i].lchild=0;
		Hfm.HT[i].rchild=0;
		Hfm.HT[i].weight=0;
	}
	Hfm.length=n;
	return Hfm;


}
Status InitHuffman(Huffman &Hfm)
{
	int i,n;
	FILE *fp;
	fp=fopen("hfmTree.txt","r+");
	if(fp==NULL)
	{
		Hfm=InputHuffman(Hfm);
		fp=fopen("hfmTree.txt","w+");
		fprintf(fp,"%d\n",Hfm.length);//将叶子结点的长度存入文件
		for(i=1;i<=Hfm.length;i++)
		{
			//fputc(Hfm.CH[i],fp);//将字符写入文件
			//putw(Hfm.HT[i].weight,fp);//将对应的权值写入文件
			fprintf(fp,"%c%d",Hfm.CH[i],Hfm.HT[i].weight);//将字符和对应的权值写入文件
		}
		rewind(fp);
	}
	else
	{
		printf("\n赫夫曼树已存在\n");
		fscanf(fp,"%d",&n);//接收叶子结点的长度
		Hfm.CH=(char *)malloc((n+1)*sizeof(char));//0号单元不用，存储字符
		Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));//0号单元未用，建树
		fgetc(fp);
		for(i=1;i<=n;i++)
		{
			//Hfm.CH[i]=fgetc(fp);
            //Hfm.HT[i].weight=getw(fp);
			fscanf(fp,"%c%d",&Hfm.CH[i],&Hfm.HT[i].weight);
		}
		for(i=1;i<=n;++i)
		{
			Hfm.HT[i].parent=0;
			Hfm.HT[i].lchild=0;
			Hfm.HT[i].rchild=0;
		}
		for(;i<=2*n-1;++i)
		{
			Hfm.HT[i].parent=0;
			Hfm.HT[i].lchild=0;
			Hfm.HT[i].rchild=0;
			Hfm.HT[i].weight=0;
		}
		Hfm.length=n;
	}
	fclose(fp);
	HfmCoding(Hfm);//进行编码
	return OK;
}

void Encoding(Huffman Hfm)
{
	FILE *fp1,*fp2;
	int j,i=0;
	char ch[MAX];
	fp1=fopen("ToBeRan.txt","r+");
	if(fp1==NULL)
	{//从键盘读入字符串
		fflush(stdin);
		printf("请输入要编码的语句\n");
		gets(ch);
		printf("\n");
	}
	else
	{
		printf("\n要编码的文件已存在\n");
		fgets(ch,MAX,fp1);
		fclose(fp1);
	}

	//TEXT printf("%s",ch);
	
	fp2=fopen("CodeFile.txt","w+");
	while(ch[i]!='\0')
	{
		for(j=1;j<=Hfm.length;j++)
			if(ch[i]==Hfm.CH[j])
			{
				printf("%s",Hfm.HC[j]);
				fprintf(fp2,"%s",Hfm.HC[j]);
				break;
			}
			i++;
	}
	rewind(fp2);
	fclose(fp2);
	
}

void Decoding(Huffman Hfm)
{
	FILE *fp1,*fp2;
	char cd[MAXNUM];
	int i,j=0;
	fp1=fopen("CodeFile.txt","r+");
	if(fp1==NULL)
	{
		printf("\n请输入赫夫曼码进行译码：");
		scanf("%s",cd);
	}
	else
	{
		printf("\n要译码的文件已存在\n");
		fgets(cd,MAXNUM,fp1);
		fclose(fp1);
	}
	fp2=fopen("TextFile.txt","w+");
	while(cd[j]!='\0')
	{
		i=2*Hfm.length-1;//i为根节点
		while(Hfm.HT[i].lchild||Hfm.HT[i].rchild)
		{
			//printf("%c",cd[j]);
			if(cd[j]=='0')i=Hfm.HT[i].lchild;
			else if(cd[j]=='1')i=Hfm.HT[i].rchild;
			j++;
			//printf("%c",cd[j]);
		}

		printf("%c",Hfm.CH[i]);
		fprintf(fp2,"%c",Hfm.CH[i]);
	}
	fclose(fp2);
}
void Print()
{
	FILE *fp1,*fp2;
	char cd;
	int n=0;
	if((fp1=fopen("CodeFile.txt","r+"))==NULL)
	{
		printf("\nThe file cannot open!\n");
		return;
	}
	fp2=fopen("CodePrin.txt","w+");
	cd=fgetc(fp1);
	while(cd!=EOF)
	{
		printf("%c",cd);
		fprintf(fp2,"%c",cd);
		n++;
		if(n%50==0)
		{
			printf("\n");
			fprintf(fp2,"\n",cd);
		}
		cd=fgetc(fp1);
	}
	fclose(fp1);
	fclose(fp2);

}
Status PreOrderTraverse(Huffman Hfm,int n)
{
	if(n)
	{
		if(Hfm.HT[n].lchild||Hfm.HT[n].rchild)printf("*");//不存在字符，用*代替
		else printf("%c",Hfm.CH[n]);
		if(PreOrderTraverse(Hfm,Hfm.HT[n].lchild))
			if(PreOrderTraverse(Hfm,Hfm.HT[n].rchild))
				return OK;
		return ERROR;
	}
	else return OK;
}
void TreePrint(Huffman Hfm)
{
	int i,n;
	n=Hfm.length;
	printf("\n该赫夫曼树的编码规则\n");
	//printf("%s",Hfm.HC[1]);
	for(i=1;i<=n;i++)
	{
		printf("\n");
		printf("字符：%c ",Hfm.CH[i]);
		printf("权值：%d ",Hfm.HT[i].weight);
		printf("对应的编码：%s ",Hfm.HC[i]);
		//puts(Hfm.HC[i]);
	}
	printf("\n打印赫夫曼树(先根)\n");
	PreOrderTraverse(Hfm,2*Hfm.length-1);//先根遍历树

	
}
void menu()
{
	printf("\n************************************************************\n");
	printf("\n欢迎使用赫夫曼编/译码器\n");
	printf("\nI.初始化  E.编码  D.译码  P.印代码文件  T.印赫夫曼树  Q.退出\n");
	printf("\n************************************************************\n");
}