[数据结构与算法]数据结构C语言实现哈夫曼编码、译码

简单实现哈夫曼编码译码过程，简单易懂`

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>

typedef struct{
	char ch;	//字符 
	int weight;		//权值 
	int parent,lchild,rchild;	//双亲、左孩子、右孩子的下标 
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void weight(HuffmanTree &HT,char filename[])	//统计每个字符出现的频度 
{
	FILE *fp;
	char ch;
	int i;
	fp = fopen(filename,"r");		//以只读模式打开文本文件 
	if((fp =fopen(filename,"r"))==NULL){		//判断文件是否存在并做出选择 
		printf("can't open file\n");
		getchar();
		exit(0);
	}
	while(!feof(fp)){	//利用ASCII码对应的数值来进行统计 
		ch = fgetc(fp);
		i = ch-'a'+1;
		if(i>=1&&i<=26){
			HT[i].weight++;
		}
		else if(i==-64){
			HT[27].weight++;
		}
	}	
	fclose(fp);
}

void select(HuffmanTree HT,int num,int &s1,int &s2)	//选择双亲域为0且权值最小的两个结点 
{
	int i;
	s1 = s2 = 0;
	HT[0].weight = 100000;
	for(i=1;i<=num;i++){
		if(HT[i].weight<HT[s1].weight&&HT[i].parent==0){	//选择第一个最小的结点 
			s1 = i;
		}
	}
	for(i=1;i<=num;i++){
		if(HT[i].weight<HT[s2].weight&&HT[i].parent==0&&i!=s1){		//选择次小结点 
			s2 = i;
		}
	}
}

void createHuffman(HuffmanTree &HT,char filename[])	//建立哈夫曼树 
{
	int m,i,s1,s2;
	int n = 27;
	m = 2*n - 1;
	HT = new HTNode[m+1];
	for(i=1;i<=n;i++){	//对有字符的结点进行初始化 
		HT[i].ch = 'a'+i-1;
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
		HT[i].weight = 0;
	}
	for(i=n+1;i<=m;i++){	//对无字符的结点进行初始化 
		HT[i].ch = '#';
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
		HT[i].weight = 0;
	}
	HT[27].ch = ' ';
	weight(HT,filename);	//将统计的权值录入结点中 
	for(i=n+1;i<=m;i++){
		select(HT,i-1,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;	//计算双亲结点的权重 
	}
}


void createHuffmanCode(HuffmanTree HT,HuffmanCode &HC)	//根据哈夫曼树生成哈夫曼编码 
{
	int i,c,f,start,n;
	n = 27;
	char *cd;
	HC = new char*[n+1];
	cd = new char[n];	//分配一个临时的数组空间存放编码 
	cd[n-1] = '\0';
	for(i=1;i<=n;i++){	//从叶子结点向上找，因此从后向前向临时数组中存放 
		start = n-1;
		c = i;
		f = HT[i].parent;
		while(f!=0){
			--start;
			if(HT[f].lchild==c)	//左孩子录入0 
			cd[start] = '0';
			else
			cd[start] = '1';	//右孩子录入1 
			c = f;
			f = HT[f].parent;
		}
		HC[i] = new char[n-start];
		strcpy(HC[i],&cd[start]);
	}
	delete cd;
}

void code(HuffmanCode HC,char filename[])	//生成编码后的文件 
{
	FILE *fp1,*fp2;
	int i;
	char ch;
	fp1 = fopen(filename,"r");		//以只读模式打开文本文件 
	if((fp1 =fopen(filename,"r"))==NULL){		//判断文件是否存在并做出选择 
		printf("can't open file\n");
		getchar();
		exit(0);
	}
	fp2 = fopen("code.txt","w");
	if((fp2 =fopen("code.txt","w"))==NULL){		//判断文件是否存在并做出选择 
		printf("can't open file\n");
		getchar();
		exit(0);
	}
		while(!feof(fp1)){	//遍历文件的字符，向文件中写入对应编码的字符串 
		ch = fgetc(fp1);
		i = ch-'a'+1;
		if(i>=1&&i<=26){
			fputs(HC[i],fp2);
		}
		else if(i==-64){
			fputs(HC[27],fp2);
		}
	}
	fclose(fp1);
	fclose(fp2);
}

void print(HuffmanTree HT,HuffmanCode HC)	//输出字符出现的次数和相应的哈夫曼编码 
{	
	printf("字符 出现次数   编码\n"); 
	for(int i=1;i<=27;i++)
	{
		printf("%c	%d	%s\n",HT[i].ch,HT[i].weight,HC[i]);
	}
}

void decode(HuffmanTree HT,char filename[])	//打印输出译码结果 
{
	FILE *fp;
	fp = fopen(filename,"r");
	char ch;
	int n = 27;
	int m = 2*n-1;
	int f;
	while(!feof(fp)){	//遍历译码文件，0向左1向右向哈夫曼树遍历至叶子结点 
		f = m;
		while(HT[f].ch=='#'&&!feof(fp)){
			ch = fgetc(fp);
			if(ch=='0'){	//向右 
				f = HT[f].lchild;
			}
			else{	//向左 
				f = HT[f].rchild;
			}
		}
		if(ch!=EOF){
			printf("%c",HT[f].ch);
		}
	}
	fclose(fp);
}

void decodefile(HuffmanTree HT,char filename[])	//生成译码文件 
{
	FILE *fp1,*fp2;
	fp1 = fopen(filename,"r");
	fp2 = fopen("decode.txt","w");
	char ch;
	int n = 27;
	int m = 2*n-1;
	int f;
	while(!feof(fp1)){	//遍历译码文件，0向左1向右向哈夫曼树遍历至叶子结点，并将字符写入新建的文件中 
		f = m;
		while(HT[f].ch=='#'&&!feof(fp1)){
			ch = fgetc(fp1);
			if(ch=='0'){
				f = HT[f].lchild;
			}
			else{
				f = HT[f].rchild;
			}
		}
		if(ch!=EOF){
			fputc(HT[f].ch,fp2);
		}
	}
	fclose(fp1);
	fclose(fp2);
}

void huffmancodefile(HuffmanTree HT,HuffmanCode HC)	//生成哈夫曼编码文件 
{
	FILE *fp;
	int i;
	int n = 27;
	fp = fopen("huffmancodetree.txt","w");
	if((fp =fopen("huffmancodetree.txt","w"))==NULL){		//判断文件是否存在并做出选择 
		printf("can't open file\n");
		getchar();
		exit(0);
	} 
	fprintf(fp,"字符	编码\n");
	for(i=1;i<=n;i++){
		fprintf(fp,"%c	%s\n",HT[i].ch,HC[i]);
		fflush(fp);
	}
	fclose(fp);
	printf("哈夫曼编码文件已写入\n"); 
}

void huffmanfile(HuffmanTree HT)	//生成哈夫曼树文件 
{
	FILE *fp;
	int i;
	int n = 27;
	int m = 2*n-1;
	fp = fopen("huffmantree.txt","w");
	if((fp =fopen("huffmantree.txt","w"))==NULL){		//判断文件是否存在并做出选择 
		printf("can't open file\n");
		getchar();
		exit(0);
	} 
	fprintf(fp,"字符	权值	左孩子	右孩子	双亲\n");
	for(i=1;i<=m;i++){
		fprintf(fp,"%c	%d	%d	%d	%d\n",HT[i].ch,HT[i].weight,HT[i].lchild,HT[i].rchild,HT[i].parent);
		fflush(fp);
	}
	fclose(fp);
	printf("哈夫曼树文件已写入\n"); 
}


int main()
{
	int choose;
	char filename[30];		//定义字符串数组用来保存文件名称 
	char filename1[30];
	HuffmanTree HT;
	HuffmanCode HC;
	while(1){
		printf("系统菜单\n");
		printf("1、生成哈夫曼编码\n");
		printf("2、查看编码\n");
		printf("3、生成哈夫曼树文件\n");
		printf("4、生成哈夫曼编码文件\n");
		printf("5、生成编码文件\n");
		printf("6、生成译码文件\n");
		printf("7、查看译码内容\n");
		printf("8、退出\n");
		printf("\n");
		printf("请选择功能：");
		scanf("%d",&choose);
		getchar(); 
		switch(choose){
			case 1:
				printf("请输入需编码文件的位置：");
				gets(filename);
				createHuffman(HT,filename);
				createHuffmanCode(HT,HC);
				printf("完成编码\n"); 
				break;
			case 2:
				print(HT,HC);
				break;
			case 3:
				huffmanfile(HT);
				break;
			case 4:
				huffmancodefile(HT,HC);
				break;
			case 5:
				code(HC,filename);
				printf("编码文件已生成\n"); 
				break;
			case 6:
				printf("请输入编码文件\n");
				gets(filename1);
				decodefile(HT,filename1);
				printf("译码文件已生成\n"); 
				break;
			case 7:
				printf("请输入编码文件\n");
				gets(filename1);
				decode(HT,filename1);
				printf("\n"); 
				break; 
			case 8:
				exit(0);
			default:
				printf("请输入正确的序号\n");		 
		}
		system("pause");	//暂停 
		system("cls");		//清屏 
		
	}
	return 0;
}