huffman.c

huffman完整源代码C语言实现

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <math.h> 
#define N 100 

typedef struct { 
	double probobility; /*某结点出现的概率*/
	int lnode; 
	int rnode; 
} node;			/* node为此结构的别名*/
node tree[N]; 		/* tree[]可通过.操作符使用node结构中的元素*/
int p = 0, total = 0; 	/* p记录叶子编号（例如tree[p]表示第p个叶子）；total为树的总叶子结点数*/
char stk[N], q = 0; 	/* stk[i]为第i结点的编码（即code，例如000001）；q为某结点编码后的长度（即Length）*/
int used[N],node_len[N];/* used[]为已使用的元素（结点）;node_len[i]为第i子树的长度（从根部开始）*/

void print_code() 
{ 
	int i = 0; 
	for (i = 0; i < q; i++) 
		printf("%c", stk[i]); 
} 

void print_avg_len() 
{ 
	int i; 
	double avg_len=0; 	/*avg_len为经huffman编码后树的平均长度*/
	for(i=0;i<total;i++) 
		avg_len+=tree[i].probobility * (double)node_len[i]; 
	printf("The average length is %f\n",avg_len); 
}

int find_min() 		/*从剩下的子树或前两最小概率结点组成的新结点中找出概率最小的一个*/
{ 
	int i_min = 0, i; 
	while (used[i_min] && i_min < p) 
		i_min++; 
	for (i = 0; i < p; i++) 
		if (!used[i] 
		    && tree[i].probobility <= tree[i_min].probobility) 
			i_min = i; 
	return i_min; 
} 
 
 void create_tree() 
{ 
	int  n1, n2; 
	node newnode; 
	while (1) { 
		if (tree[p - 1].probobility == 1) 
			break; 
		n1 = find_min(); 
		used[n1] = 1; 		/*标记为已使用*/
		n2 = find_min(); 
		used[n2] = 1; 
		newnode.probobility = 	/*创造一个新结点*/
		    tree[n1].probobility + tree[n2].probobility; 
		newnode.lnode = n1; 
		newnode.rnode = n2; 
		tree[p++] = newnode; 	/*把新结点加入未用队列中*/
	}
} 
 
 void traverse_tree(int i) 		/*遍历树*/
{ 
	if (tree[i].lnode == -1 && tree[i].rnode == -1) { 		/*如果是叶子结点则输出*/
		printf("%-f\t\t|", tree[i].probobility); 
		print_code(); 
		printf("\t\t|%-d\n",q); 
		node_len[i]=q; 
		return; 
	} 
	stk[q++] = '0'; 						/*如果不是叶子结点则递归*/
	traverse_tree(tree[i].rnode); 	/*如果是右子树则输出0，并递归直到叶子结点*/
	q--; 
	stk[q++] = '1'; 
	traverse_tree(tree[i].lnode); 	/*如果是左子树则输出1，并递归直到叶子结点*/
	q--;
} 

int main() 
{ 
	int i = 0,tmp_total=0; 
	double check = 0; 
	node x; 
	memset(tree, 0, sizeof(tree)); 		/*把tree[]所指的前sizeof(tree)个字节设置为0（即将初始tree[]指向0）*/
	memset(used, 0, sizeof(used)); 
	memset(node_len,0,sizeof(node_len)); 
	printf("How many symbols?:\n"); 
	scanf("%d", &total); 
	if (total <= 0 || total > N / 2) { 
		printf("can't accept\n"); 
		return 1; 
	} 
	printf("enter their posibilities\n"); 
	tmp_total=total; 
	while (tmp_total--) { 
		scanf("%lf", &x.probobility); 
		if (x.probobility < 0 || x.probobility > 1) { 
			printf("illegle\n"); 
			return 2; 
		} 
		check += x.probobility; 
		x.lnode = -1; 			/*x的左子树为空*/
		x.rnode = -1; 			/*x的右子树为空*/
		tree[p++] = x; 
	} 
	if (fabs(check - 1) > 1e-15) 		/*概率总和check必须为1，根据机器精度可有些微偏差*/
	{ 
		printf("error,the sum should be 1\n"); 
		return 2; 
	} 
	create_tree(); 
	printf("Proboblility\t\t|Code\t\t|Length\n"); 
	traverse_tree(p - 1); 
	print_avg_len(); 
	return 0;
}


/*简单测试结果:
How many symbols?:
6
enter ther posibilities
0.25 0.05 0.15 0.05 0.05 0.45
Proboblility            |Code           |Length
0.050000                |00000          |5
0.050000                |00001          |5
0.050000                |0001           |4
0.150000                |001            |3
0.250000                |01             |2
0.450000                |1              |1
The average length is 2.100000

*/