huffman-verifafgwgh.c

Huffman source code. you can do text encoding.

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

#define MAX 256

int freq[MAX];
static char sen[MAX]="ABCDEFGHIJKLMNUAAANNNDDNXYBBBUBCCCCCCZCCCCDDMDLMD ";

typedef struct _huf
{
	int count;		// 后档
	char data;		// 巩磊
	struct _huf *left,*right;
} huf;

huf *head[MAX];
int nhead;
huf *huf_head;
unsigned code[256];
int len[256];



/* 巩磊喊 后档甫 备秦辑 freq 硅凯俊 历厘 */
void get_freq(void)
{
	int i;
	for(i=0;i<MAX;i++)
		freq[i]=0;			// 檬扁拳
	for(i=0;i<MAX;i++)
		if(sen[i]!='\0')
			freq[sen[i]]++;		// 荤侩后档甫 备窃.
}

/* 弥家 后档荐甫 茫绰 窃荐 */
int find_minimum(void)
{
	int mindex,i;
	mindex=0;
	for(i=1;i<nhead;i++)
	{
		if(head[i]->count < head[mindex]->count)
			mindex=i;
	}
	return mindex;			// struct郴俊 乐绰 后档甫 爱绊 弥家狼 后档甫 茫绰促.
}

/* freq 硅凯肺 倾橇父 飘府甫 备己窍绰 窃荐 */
void construct_tree(void)
{
	int i,m;
	huf *h,*h1,*h2;
	
	// 檬扁 窜拌狼 畴靛甫 积己茄促.
	for(i=nhead=0;i<MAX;i++)
	{
		if(freq[i]!=0)
		{
			if((h=(huf *)malloc(sizeof(huf))) == NULL)
			{
				printf("\nError : out of memory.");
				exit(1);
			}
			h->count=freq[i];
			h->data=i;
			h->left=h->right=NULL;
			head[nhead++]=h;
		}
	}

	/* 积己等 畴靛甸阑 倾橇父 飘府肺 父靛绰 窜拌 */
	while(nhead>1)
	{
		m=find_minimum();		// 捞 弥家蔼栏肺 飘府甫 瞒肥瞒肥 备己茄促.
		h1=head[m];
		head[m]=head[--nhead];
		m=find_minimum();
		h2=head[m];
		if((h=(huf*)malloc(sizeof(huf))) == NULL)
		{
			printf("\nError : out of memory.");
			exit(1);
		}
		// 困俊辑 备茄 滴俺狼 弥家后档甫 爱绰 畴靛甫 爱绊 滴俺狼 后档狼 钦阑
		// 爱绰 畴靛甫 积己窍咯 捞 畴靛狼 谅,快俊 弥家后档甫 爱绰 畴靛甫 嘿咯 飘府甫 父电促.
		h->count=h1->count+h2->count;
		h->data=0;
		h->left=h1;
		h->right=h2;
		head[m]=h;
	}
	huf_head=head[0];
}

/* 倾橇父 飘府 力芭 */
void destruct_tree(huf *h)
{
	if(h!=NULL)
	{
		destruct_tree(h->left);
		destruct_tree(h->right);
		free(h);
	}
}

/* 林绢柳 巩磊凯狼 荤侩后档甫 拳搁俊 免仿窍绰 窃荐 */
void show_freq(void)
{
	int i;
	for(i=0 ; i<MAX ; i++)
	{
		if(freq[i]==0)
			continue;
		printf("\t %c \t %d\n",i,freq[i]);
	}
}

/* 倾橇父飘府俊辑 内靛甫 掘绢晨. code硅凯苞 len硅凯 汲沥 */
void _make_code(huf *h,unsigned c, int l)
{
	if(h->left != NULL || h->right !=NULL)
	{
		c<<=1;
		l++;
		// 犁蓖龋免阑 荤侩窍咯 阿 畴靛甸狼 内靛蔼苞 内靛狼 辨捞甫 10柳荐狼 屈怕肺 历厘茄促.
		_make_code(h->left,c,l);
		c|=1u;
		_make_code(h->right,c,l);
		c >>= 1;
		l--;
	}
	else
	{
		code[h->data]=c;
		len[h->data]=l;
	}
}

/* _make_code()狼 涝备 窃荐 */
void make_code(void)
{
	int i;
	for(i=0;i<256;i++)
		code[i]=len[i]=0;		// 内靛客 内靛狼 辨捞狼 檬扁拳.
	_make_code(huf_head,0u,0);
}

 
#define bi_max_code 14       // 倾橇父 飘府甫 备己窍咯 内靛甫 备秦焊搁 弊 辨捞啊 措帆 14甫 逞瘤 臼绰促.

/* 内靛狼 辨捞 吝 啊厘 变 辨捞甫 茫绰 窃荐 */
int code_leng(void)
{
	int i,max=0;
	for(i=0 ; i<MAX ; i++)
		if(max<len[i])
			max=len[i];
	return max;
}

/* 倾橇父 拘绵窃荐 */
void huffman_comp()
{
	char ch;
	int i,j,bi_code[bi_max_code],temp,max;


	get_freq();
	construct_tree();
	make_code();
	max=code_leng();

	printf("Frequency --->>>\n");
	show_freq();
	
	printf("\n\nNext Page>>> \n");
	ch=getchar();
	system("cls");

	printf("Code from Huffman tree --->>>\n\tChar\tCode\tCode length\n");
	for(i=0 ; i<MAX ; i++)
	{
		if(len[i]!=0)
		{
			temp=code[i];		// 内靛狼 函版阑 阜扁 困秦辑 函荐荤侩
			for(j=1 ; j<=len[i]; j++)
			{
				// 阿 内靛狼 蔼阑 0苞 1阑 荤侩窍咯 内靛辨捞父怒 硅凯俊 持绰促.
				bi_code[len[i]-j]=temp%2;
				temp/=2;
			}
			printf("\t %c\t",i);
			if(max>len[i])
				for(j=0;j<max-len[i];j++)
					printf(" ");
			for(j=0 ; j<len[i];j++)
				printf("%d",bi_code[j]);
			printf("\t     %d\n",len[i]);
		}
	}
	destruct_tree(huf_head);
}

/* 皋牢 窃荐 */
void main(void)
{
//	int sen_leng = strlen(sen);
	huffman_comp();
}