4.cpp

本程序是一个对哈夫曼编码问题的演示程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK    1
#define NULL  0
#define TURE  1
#define FALSE  0
#define EOF   (-1)
int S1=0;
int i;
int S2=0;
char ch[27];
typedef struct HT
{
	char ch;
	int num;
	int weight;
	int parent,lchild,rchild;

} HTNode,*HuffmanTree;//定义哈夫曼树结点
typedef char* *Huffmancode;
//-------------——————--------------------功能函数列表-----------------------------------------//
int Select(HuffmanTree HT,int n);
int Initialization (HuffmanTree HT,int n);
int Encoding (HuffmanTree HT,int n);
int Decoding (HuffmanTree HT,int n);
int Print ();
int TreePrinting (HuffmanTree HT,int n);
//-----------——————---------------------主函数----------------————-------------------------//
int main ()
{
	int m,n=0;
	char ch; 
	HuffmanTree HT;//定义HT为哈夫曼树
	printf("***********************欢迎使用本系统（开发人 厉启鹏）*************************\n");
    printf("   A  初始化     B  编码   C   译码   D   印码文件   E   印哈夫曼树   F   退出\n");
	while(1)
	{
       
		while(1)
		{
			fflush(stdin);
 		    printf("\n请选择您需要的操作:");
            scanf("%c",&ch);
			fflush(stdin);
            if(ch>=65&&ch<=70) break;
		}
       switch(ch)
		{
			 case'A':
			     printf("请输入字符个数:"); 
                 scanf("%d",&n);//输入需要编码的字符的个数
                 m=2*n-1;
				 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//为哈夫曼树开辟存储空间
				 Initialization (HT,n);
				 break;
             case'B':
				 Encoding(HT,n);
				 break;
			 case'C':
                 Decoding(HT,n);
				 break;
			 case'D':
                 Print ();
				 break;
			 case'E':
                 TreePrinting(HT,n);
				 break; 
			 case'F':

				 return 0;
			 default:  break;
		}
	}
}
//-----------——————---------------------主函数----------------————-------------------------//


int Initialization (HuffmanTree HT,int n)
{   //初始化哈夫曼树函数
	int m,i;
	FILE *out1;
    //将字符存入该数组
	m=2*n-1;
    printf("请输入空格的频度:");
	scanf("%d",&HT[1].weight);
    HT[1].num=1;
	HT[1].ch=NULL;
	HT[1].parent=NULL;//将每个节点的指针均初始化为空
	HT[1].lchild=NULL;
	HT[1].rchild=NULL;
    for(i=2;i<=n;i++)
	{
		printf("请输入第%d个字符:",i);
	    scanf("%s",&HT[i].ch);
		printf("请输入该字符的频度：");
        scanf("%d",&HT[i].weight);
		HT[i].num=i;
		HT[i].parent=NULL;//将每个节点的指针均初始化为空
		HT[i].lchild=NULL;
		HT[i].rchild=NULL;
	}
	for(i=n+1;i<=m;++i)
	{
		Select(HT,i-1);
		//在HT[1...n]中选择parent为0，且weight最小的两个节点，其序号分别是S1,S2
		HT[S1].parent=i,HT[S2].parent=i;//开始构造哈夫曼树
		HT[i].lchild=S1,HT[i].rchild=S2;
		HT[i].weight=HT[S1].weight+HT[S2].weight;
		HT[i].parent=NULL;
		HT[i].num=i;
		HT[i].ch=' ';

	}
	//printf("%s   %s    %s     %s     %s",HT[i].num,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    if((out1=fopen("hfmTree.txt","w"))==NULL)//建立文件hfmTree.txt以存储哈夫曼树
	{
		printf("文件错误\n ！");
	}
    fputs("fuhao     num       weight    parent    lchild    rchild    \n",out1);
	for(i=1;i<=m;i++)//将哈夫曼树存入hfmTree.txt文件
	{
		
	    fprintf(out1,"%-10c%-10d%-10d%-10d%-10d%-10d\n",HT[i].ch,HT[i].num,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);  	 
	}
	fclose(out1);
	printf("哈夫曼树已构造完成,并已存入hfmTree.txt文件!\n");
	return OK;

}



int Encoding(HuffmanTree HT,int n)
{
	int i,start,c,f;
	char ch,infile[20];
    FILE *in,*out2,*out3;
    if(n==0)         //未建立哈夫曼树  
	{  
        printf("请先建立哈夫曼树！\n");  
        return NULL;  
	} 

	Huffmancode HC=(Huffmancode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量
	char* 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);//释放工作空间
	for(i=1;i<=n;i++) printf("%s\n",HC[i]);
   if((out3=fopen("CodeFile.txt","w"))==NULL)//建立CodeFile.txt文件以存储对正文的编码
	{
		printf("文件错误！\n ");
	} 
	if((in=fopen("ToBeTran.txt","r"))==NULL)//打开需要编码的文件ToBeTran.txt
	{
		printf("\n 打不开此ToBeTran.txt文件！");
		
	}
    ch=fgetc(in);
    while(ch!=EOF)//对正文中的逐个字符进行编码
	{	    
		putchar(ch);
	    for(i=1;i<=n;++i)
		{
		    if(ch==HT[i].ch) 
			{
				fprintf(out3,"%s",HC[i]);//将编码结果写进CodeFile.txt文件				
			}
			else continue;
		}

		ch=fgetc(in);	
	}
    fclose(out3);//关闭文件
	printf("编码已完成并存入CodeFile.txt文件！");
    return OK;

	
}
int Decoding(HuffmanTree HT,int n)
{
	int c,f;
	char infile[20],ch;
    FILE *in,*out;
    if(n==0)         //未建立哈夫曼树  
	{  
        printf("请先建立哈夫曼树！\n");  
        return NULL;  
	} 

    if((out=fopen("TextFile.txt","w"))==NULL)//建立文件以储存编码
	{
		printf("\n 建立文件失败！");		
	}
    
	printf("请输入需要译码的文件名(默认文件为CodeFile.txt)：");
	scanf("%s",infile);
    if((in=fopen(infile,"r"))==NULL)
	{
		printf("\n请检查您是否建树或编码！");
		return NULL;
	}
    ch=fgetc(in);
    c=2*n-1;
    f=c;
    while(ch!=EOF)//对正文中的逐个字符进行译码
	{
		if(ch=='0')
		{
			f=HT[c].lchild;
			c=f;
			if(HT[f].lchild==0 && HT[f].rchild==0)
			{
				fprintf(out,"%c",HT[f].ch);
				c=2*n-1;
				f=c;
			}
		}
		if(ch=='1')
		{
			f=HT[c].rchild;
			c=f;
			if(HT[f].lchild==0 && HT[f].rchild==0)
			{
				fprintf(out,"%c",HT[f].ch);
				c=2*n-1;
				f=c;
			}
		}
       ch=fgetc(in);
	
	}
    fclose(out);
	printf("译码已完成并存入TextFile.txt文件!");
	return OK;

}

int Print()
{
    char infile[20],ch,i=0;
    FILE *in,*out;
	printf("请输入存放编码的文件名(默认为CodeFile.txt)：");
    scanf("%s",infile);
	if((in=fopen(infile,"r"))==NULL)
	{
		printf("\n 此文件不存在，请先建立！");
		return NULL;
	}
    if((out=fopen("CodePrin.txt","w"))==NULL)
	{
		printf("\n 建立文件失败！");		
	}
	ch=fgetc(in);
	while(ch!=EOF)
	{
		++i;
		putchar(ch);
        fprintf(out,"%c",ch);
		if(i==50)
		{
			printf("\n");
		    fputs("\n",out);
			i=0;
		}
        ch=fgetc(in);
	}
	fclose(out);
	fclose(in);
	return OK;
}
int TreePrinting (HuffmanTree HT,int n)
{
	FILE *out;
	int m;
	m=2*n-1;
    if(n==0)         //未建立哈夫曼树  
	{  
        printf("请先建立哈夫曼树！\n");  
        return NULL;  
	} 
	if((out=fopen("TreePrint.txt","w"))==NULL)//建立文件hfmTree.txt以存储哈夫曼树
	{
		printf("文件错误\n ！");
	}
	printf("fuhao     num       weight    parent    lchild    rchild    \n");
    fputs("fuhao     num       weight    parent    lchild    rchild    \n",out);
	for(i=1;i<=m;i++)//将哈夫曼树存入hfmTree.txt文件
	{
		
	    fprintf(out,"%-10c%-10d%-10d%-10d%-10d%-10d\n",HT[i].ch,HT[i].num,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); 
		printf("%-10c%-10d%-10d%-10d%-10d%-10d\n",HT[i].ch,HT[i].num,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); 
	}
	fclose(out);
	return OK;
}

int Select(HuffmanTree HT,int n)
{
	int i,j,min1,min2;
    min1=32767;
	min2=32767;
	for(i=1;i<=n;i++)
	{
		if(HT[i].weight<min1 && HT[i].parent==NULL)
		{
			min1=HT[i].weight;
			S1=i;
		}
	}
	for(j=1;j<=n;j++)
	{
		if(HT[j].weight<min2 && HT[j].parent==NULL && j!=S1)
		{
			min2=HT[j].weight;
			S2=j;
		}
	}
	return OK;
}