hfm.cpp

数据结构实习题目哈弗曼编码-译码系统的完整设计

#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<stdio.h>
#include<process.h>
#include<limits.h>
//定义全局变量来存放相关字符及相应的权值
char string[100];
int w[100]; 
//赫夫曼树和赫夫曼编码的存储表示 
typedef struct HTNode1
{
   unsigned int weight;
   char ch;//存放字符 
   unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树
typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表 
HuffmanCode HC;
HuffmanTree *HT2;




int min1(HuffmanTree t,int i)
 { /* 函数void select()调用 */
   int j,flag;
   unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */
   for(j=1;j<=i;j++)
     if(t[j].weight<k&&t[j].parent==0)
       k=t[j].weight,flag=j;
   t[flag].parent=1;
   return flag;
 }

 void select(HuffmanTree t,int i,int *s1,int *s2)
 { /* s1为最小的两个值中序号小的那个 */
   int j;
   *s1=min1(t,i);
   *s2=min1(t,i);
   if(*s1>*s2)
   {
     j=*s1;
     *s1=*s2;
     *s2=j;
   }
 }

HTNode **HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int n) 
 { /* 构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
   int m,i,s1,s2,start;
   unsigned c,f;
   HuffmanTree p;
   char *cd;
   if(n<=1)
     return 0;
   m=2*n-1;
   *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
   for(p=*HT+1,i=1;i<=n;++i,++p)
   {
     (*p).weight=w[i-1];
     (*p).parent=0;
     (*p).lchild=0;
     (*p).rchild=0;
     (*p).ch='#';//字符初始化为'#'
	
   }
   for(;i<=m;++i,++p)
   { (*p).parent=0;
     (*p).ch='#';//字符初始化为'#'
   }
   for(i=n+1;i<=m;++i) /* 建赫夫曼树 */
   { /* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
     select(*HT,i-1,&s1,&s2);
     (*HT)[s1].parent=(*HT)[s2].parent=i;
     if(s1<=n) (*HT)[s1].ch=string[s1-1];
	 if(s2<=n)	(*HT)[s2].ch=string[s2-1];
     (*HT)[i].lchild=s1;	 
     (*HT)[i].rchild=s2;	 
     (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
   }

   /* 从叶子到根逆向求每个字符的赫夫曼编码 */
   *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
   /* 分配n个字符编码的头指针向量([0]不用) */
   cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
   cd[n-1]='\0'; /* 编码结束符 */
   for(i=1;i<=n;i++)
   { /* 逐个字符求赫夫曼编码 */
     start=n-1; /* 编码结束符位置 */
     for(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));
     /* 为第i个字符编码分配空间 */
     strcpy((*HC)[i],&cd[start]); /* 从cd复制编码(串)到HC */
   }
   free(cd); /* 释放工作空间 */
    return HT;
}


void Initialization()
{
	FILE *fp1;
	
	int j,tempnum;
	char ch;
	if((fp1=fopen("Init.txt","r"))==NULL)
	{
		printf("read Init.txt failed! \n ");
		return ;

	}
	
	j=0;
	fgets(string,100,fp1);
	tempnum=0;
	while(!feof(fp1))
	{	ch=fgetc(fp1);	
		if(ch>='0'&&ch<='9')	
		{  
			tempnum=tempnum*10+(ch-48);
		    w[j]=tempnum;
		}
		else {tempnum=0;j++;}	
		
	}
	
	
	fclose(fp1);
	


}

void Encoding()
{	
   FILE *fp1,*fp2;
   int i;
   char ch;
   if((fp1=fopen("ToBeTran.txt","r"))==NULL)
	{
		printf("open ToBeTran.txt failed! \n");
		return ;

	}
   if((fp2=fopen("CodeFile.txt","w"))==NULL)
	{
		printf("write CodeFile.txt failed! \n ");
		return ;

	}
   while(!feof(fp1))
   {
		ch=fgetc(fp1);
		for(i=0;i<strlen(string)-1;i++)
		{
			if(string[i]==ch) fputs(HC[i+1],fp2);
		}


   }
   fclose(fp1);
   fclose(fp2);


}




void Decoding()
{
	FILE *fp1,*fp2;
	int leftch,rightch,l,r,n;
//	int n=strlen(string)-1;
	char ch;


	if((fp1=fopen("CodeFile.txt","r"))==NULL)
	{
		printf("read CodeFile.txt failed! \n ");
		return ;
	}
	if((fp2=fopen("TextFile.txt","w"))==NULL)
	{
		printf("write TextFile.txt failed! \n ");
		return ;
	}

	n=strlen(string)-1;
	leftch=(*HT2)[2*n-1].lchild;
	rightch=(*HT2)[2*n-1].rchild;
	while(!feof(fp1))
	{  ch=fgetc(fp1);
		if(ch=='0') 
			{	
				l=leftch;
				leftch=(*HT2)[leftch].lchild;
				rightch=(*HT2)[l].rchild;
				if(leftch==0)
					{
						//printf("*");
					
						printf("%c",(*HT2)[l].ch);
						fputc((*HT2)[l].ch,fp2);
						leftch=(*HT2)[2*n-1].lchild;
						rightch=(*HT2)[2*n-1].rchild;
					}


			}
		 else if(ch=='1')
				{
					r=rightch;
					rightch=(*HT2)[rightch].rchild;
					leftch=(*HT2)[r].lchild;
					if(leftch==0)
						{
							//printf("*");

							printf("%c",(*HT2)[r].ch);
							fputc((*HT2)[r].ch,fp2);
							leftch=(*HT2)[2*n-1].lchild;
							rightch=(*HT2)[2*n-1].rchild;
						}
				}

 
		}
	fclose(fp1);
        fclose(fp2);





}

void Code_Print()
{
	FILE *fp1,*fp2;
	char str_print[51];
	if((fp1=fopen("CodeFile.txt","r"))==NULL)
	{
		printf("read CodeFile.txt failed! \n ");
		return ;

	}
	if((fp2=fopen("CodePrin.txt","w"))==NULL)
	{
		printf("write CodePrin.txt failed! \n ");
		return ;

	}

	while(!feof(fp1))
	{
	fgets(str_print,51,fp1);
	puts(str_print);
	printf("\n");
	fputs(str_print,fp2);
	fputc('\n',fp2);
	}
   fclose(fp1);
   fclose(fp2);



}
void Tree_Print(int j)
{	
	if(j!=0)
	{
		printf("%d",(*HT2)[j].weight);
		if((*HT2)[j].lchild!=0)
		{
			printf("(");
			Tree_Print((*HT2)[j].lchild);
			if((*HT2)[j].rchild!=0)
			{printf(",");}
			Tree_Print((*HT2)[j].rchild);
			printf(")");

		}

	}

}

void compare()
{
	FILE *fp1,*fp2;
	char ch;
	int sum,i;
	if((fp1=fopen("CodeFile.txt","r"))==NULL)
	{
		printf("read ToBeTran.txt failed! \n ");
		return ;

	}
	if((fp2=fopen("CodeFile_Askm.txt","w"))==NULL)
	{
		printf("write CodeFile_Askm.txt failed! \n ");
		return ;

	}
	while(!feof(fp1))
{
		sum=0;
		for(i=1;i<=32;i++)
		{
			if(!feof(fp1))
			{
				ch=fgetc(fp1);
				if(ch=='1')
				sum=sum+1;
				sum=sum<<1;
			}
			}
		fwrite(&sum,sizeof(int),1,fp2);
}

fclose(fp1);
fclose(fp2);

	
}

void main()
{	
int n,i;
char c='#';
HuffmanTree HT1;
FILE *fp2,*fp3;
if((fp2=fopen("HfmTree.txt","wb"))==NULL)
	{
		printf("write HfmTree.txt failed! \n ");
		return ;

	}
	if((fp3=fopen("HfmTree.txt","rb"))==NULL)
	{
		printf("read HfmTree.txt failed! \n ");
		return ;

	}
	while(c!='Q')
	{	printf("\n");
	printf("1、初始化（I）\n2、编码（E）\n3、比较两种编码(C)\n4、译码（D）\n5、打印代码文件(P)\n6、打印哈夫曼树（T）\n7、退出(Q)\n");
	 printf("请输入您的选择：");c=getchar();
	 switch(c)
	 {
	 case 'I':
     Initialization();
	n=strlen(string)-1;
	HT2=HuffmanCoding(&HT1,&HC,n);
	for(i=1;i<=2*n-1;++i)
	{
		if(fwrite(&((*HT2)[i]),sizeof(struct HTNode1),1,fp2)!=1)
		printf("write error\n");

	}
	fclose(fp2);
	  getchar();
	  break;
	 case 'E':
		  Encoding();
		 getchar();
		 break;
	 case 'C':
		 compare();
		 getchar();
		 break;
	 case 'D':
		 Decoding();
		 getchar();
		 break;
	 case 'P':
		 Code_Print();
		 getchar();
		 break;
	 case 'T':
		 Tree_Print(2*(strlen(string)-1)-1);
		 getchar();
		 break;
	 case 'Q':
		 break;
	 default :
		 printf("输入格式不对！\n");
		 getchar();
		 break;
	 }
	}


	

/*	for(i=1;i<=2*n-1;++i)
	{
	fread(&((*HT2)[i]),sizeof(struct HTNode1),1,fp3);
	printf("%d%c%d%d%d\n",(*HT2)[i].weight,(*HT2)[i].ch,(*HT2)[i].parent,(*HT2)[i].lchild,(*HT2)[i].rchild);
	}*/
	
	
	
	


	


}