huffman.c

哈夫曼编码：输入一个文本文件（英文文本）

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

typedef struct huffman_node 
{
	int data;
	int lchild;
	int rchild;
	int parent;
}bnode;  //定义二叉链表结点结构

void SelectIJ(int k, bnode node[], int *i, int *j)
{
	int s,low,hig;
	low=100000000000000;
	hig=100000000000001;
	*i=1000;
	*j=1001;
	for(s=0;s<k;s++){
		if(node[s].parent==0){
			if(node[s].data<low){
				hig=low;*j=*i;
				low=node[s].data;*i=s;}
			else if(node[s].data<hig)
			{hig=node[s].data;*j=s;}
			
		}

	}
}

void HuffmanTree(int n, bnode node[],int w[])
{
	int i,j,k;
	for (i=0;i<n;i++){
		node[i].data=w[i]; 
		node[i].lchild=node[i].rchild=0;
	}
	for (i=0;i<2*n-1;i++) node[i].parent=0;
	for (k=n;k<2*n-1;k++){
		SelectIJ(k,node,&i,&j);//查找最小的i,j
		node[k].data=node[i].data+node[j].data;
		node[k].lchild=i;  node[k].rchild=j;
		node[i].parent=node[j].parent=k;
	}
}

void main()
{
	FILE *fp;
	int weight[26];
	int record[20];


	int i,j,h;
	int ch;
	int n;
	int p;
	int m;

	bnode *node;
	unsigned long code;

	for(i=0; i<26; i++)
	{
		weight[i] = 0;
	}

	if( (fp = fopen("StrayBirds.txt","r")) == NULL )
		return;

	do {
		ch = fgetc(fp);

		if (!( ((ch>=97)&&(ch<=122)) ||
			   ((ch>=65)&&(ch<=90 ))	 )
		   )
		{
			continue;
		}
		if( (ch>=97)&&(ch<=122) )
		{
			ch -= 32;
		}
        putchar(ch);
		weight[ch-65]++;
	} while(feof(fp)==0);

	printf("\n");

	n = 0;
	for(i=0; i<26; i++)
	{
		if(weight[i] > 0) 
		{
			n++;
			printf("%c  %d \n", i+65, weight[i]);
		}
	}

	node = (bnode *)malloc((2*26-1) * sizeof(bnode));

	//建立哈夫曼树
	HuffmanTree(26, node, weight);


	//哈夫曼编码
	for (i=0; i<26; i++)
	{
		printf("Now processing %c -----", i+65);
		n=0;
		h=i;
		p=node[i].parent;

		while(p){
			record[n]=(node[p].lchild==h);
		    h=p;	
		    p=node[p].parent;
			n++;
		}
		for(m=n-1;m>-1;m--) printf("%d",record[m]);
		

		printf("\n");
	}

	free(node);
	fclose(fp);
}