hafumanbianyimaqi.c

给定电文进行哈夫曼编码

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

#define MAX 256//定义一个最大值

typedef struct {
	unsigned int weight;
	unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;//动态分配数组存储哈夫曼树
typedef char **HuffmanCode;//动态分配数组存储哈夫曼译码表

//- - －选择两个最小的结点,序号分别放在s1和s2中程序
void Select(HuffmanTree *HT, int n, int *s1, int *s2)
{
	int t1, t2, flag1, flag2;
	int i;

	flag1 = 0;
	flag2 = 0;//相关变量赋初值
	for (i = 1; i <= n; ++i){//用多个if语句依次寻找
		if ((*HT)[i].parent == 0){ //第一个parent为0的结点
			if (!flag1){
				t1 = i;
				flag1 = 1;
			}else if (!flag2){
				if ((*HT)[i].weight < (*HT)[t1].weight){
					t2 = t1;
					t1 = i;
				}else {
					t2 = i;
				}
				flag2 = 1;
			}else if ((*HT)[i].weight < (*HT)[t1].weight){
					t2 = t1;
					t1 = i;
			}else if ((*HT)[i].weight < (*HT)[t2].weight){
				t2 = i;
			}
		}
	}

	*s1 = t1;
	*s2 = t2;
}
//- - -哈夫曼编码程序
void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, unsigned int *w, int n)
{//w存放n个字符的权值（均大于0），构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
	HTNode *p;
	int m, s1, s2;
	int i;
	char *cd;

	if (n <= 1) return;

	m = 2*n-1;
	*HT = (HuffmanTree) malloc ((m+1) * sizeof(HTNode));//零号单元未用

	for (p = *HT+1, i=1; i <= n; ++i, ++p){
		p->weight = w[i];
		p->parent = 0;
		p->lchild = 0;
		p->rchild = 0;
	}
	for ( ; i <= m; ++i, ++p){
		p->weight = 0;
		p->parent = 0;
		p->lchild = 0;
		p->rchild = 0;
	}

	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 = i;
		(*HT)[s2].parent = i;
		(*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个字符编码的头指针向量
	cd = (char*) malloc (n * sizeof(char));//分配求编码的工作空间
	cd[n-1] = '\0';//编码结束符
	
	for (i = 1; i <= n; ++i){//逐个字符求哈夫曼编码
		int start;
		unsigned int c, f;
		
		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);//释放工作空间
}
//- - - 读取频率数据程序
void load_encoding(FILE *fdata, unsigned int w[])
{
	int i;

	for (i = 1 ; i <= MAX; ++i)
		fscanf(fdata, "%u\n", &w[i]);
}
//- - - 存储编码数据程序
void save_encoding(FILE *fencoding, HuffmanCode HC)
{
	int i;

	for (i = 1; i <= MAX; ++i)
		fprintf(fencoding, "%c:%s\n", i, HC[i]);
}
//- - -编码文件程序
void encode(FILE *in, FILE *out, HuffmanCode HC)
{
	char c;
	int i, flag;

	while ((c = fgetc(in)) != EOF){
		flag = 0;
		for (i = 1; i <= MAX; ++i){
			if (c == i){
				fprintf(out, "%s", HC[i]);
				flag = 1;
			}
		}
		if (!flag)
			fprintf(out, "%c", c);
	}		
}
//- - -对文件进行译码程序
void decode(FILE *in, FILE *out, HuffmanTree HT)
{
	char c;
	HTNode *p;

	while (!feof(in)){
		p = HT + 2*MAX-1;
		do{
			if ((c = fgetc(in)) == EOF)	return;

			if (c == '0')
				p = HT + p->lchild;
			else if (c == '1')
				p = HT + p->rchild;
		}while (p->lchild != 0 && p->rchild != 0);
		fprintf(out, "%c", p-HT);
	}
}
//- - -从给定文件中生成频率数据程序
void make_data(FILE *in,  FILE *out)
{
	char c;
	unsigned int count[256]={0};
	int i;

	while (!feof(in)){
		c = fgetc(in);
		++count[c];
	}

	for (i = 0; i < 256; ++i){
		fprintf(out, "%u\n", count[i]);
	}
}
//- - -主程序
int main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	
	unsigned int w[MAX+1]={0};
	
	FILE *fsrc, *fdata, *fencoding, *in, *out;

	/*从给定文件中生成频率数据*/
	fsrc = fopen("src.txt", "r");
	fdata = fopen("fdata.txt", "w");
	if (fsrc == NULL || fdata == NULL)
		exit (-1); 
	make_data(fsrc, fdata);
	fclose(fsrc);
	fclose(fdata); 


	/*读取频率数据*/
	fdata = fopen("fdata.txt", "r");
	if (fdata == NULL)
		exit (-1); 
	load_encoding(fdata, w);
	fclose(fdata);

	/*哈夫曼编码*/
	HuffmanCoding(&HT, &HC, w, MAX);	

	/*存储编码*/
	fencoding = fopen("fencoding.txt", "w");
	if (fencoding == NULL)
		exit (-1); 
	save_encoding(fencoding, HC);
	fclose(fencoding);

	/*编码文件*/
	in = fopen("f1.txt", "r");
	out = fopen("f2.txt", "w");
	if (in == NULL || out == NULL)
		exit (-1); 
	encode(in, out, HC);
	fclose(in);
	fclose(out);

	/*译码文件*/
	in = fopen("f2.txt", "r");
	out = fopen("f3.txt", "w");
	if (in == NULL || out == NULL)
		exit (-1); 
	decode(in, out, HT);
	fclose(in);
	fclose(out);
	
}