#include <stdio.h>
#include <stdlib.h>
typedef struct {
	unsigned int weight;
	unsigned int parent, lchild, rchild;
	char c;
} HTNode, *HuffmanTree;

void Select (HuffmanTree HT, int n, int *s1, int *s2) {
	int i, t1, t2, w1=HT[1].weight, w2=HT[1].weight;
	for (i=2;i<=n;++i)
	if (HT[i].weight<w1 && HT[i].parent==0)
		{w1=HT[i].weight; t1=i;}
	for (i=2;i<=n;++i)
	if (HT[i].weight<w2 && i!=t1 && HT[i].parent==0)
		{w2=HT[i].weight; t2=i;}
	s1=&t1;s2=&t2;
}

void HuffmanCode(HuffmanTree HT, int n) {
	int i, start, d, f, t;
	char ch, *cd;
	cd=NULL;
	FILE *fp, *fq;
	if ((fp=fopen("file1","rb"))==NULL)
		printf ("file1 can't be opened!\n");
	if ((fq=fopen("file2","ab"))==NULL)
		printf ("file2 can't be opened!\n");
	ch=fgetc(fp);
	while (ch!=EOF) {
		for (i=1;i<=n;++i)	
			if (ch==HT[i].c) break;
		start=n+1;
		for (d=i,f=HT[i].parent;f!=0;d=f,f=HT[f].parent)
			if (HT[f].lchild==d) cd[--start]='0';
			else cd[--start]='1';
		for (t=start;t<=n;++t)
			fputc(cd[t],fq);
		ch=fgetc(fq);
	}
	fclose(fp);
	fclose(fq);
}

void HuffmanDecode(HuffmanTree HT, int n) {
	int i, m, root;
	char ch;
	FILE *fp, *fq;
	if ((fp=fopen("file3","rb"))==NULL)
		printf ("file3 can't be opened!\n");
	if ((fq=fopen("file4","ab"))==NULL)
		printf ("file4 can't be opened!\n");
	m=2*n-1;
	for (i=1;i<=m;++i)
		if (HT[i].parent==0) root=i;
	ch=fgetc(fp);
	while (ch!=EOF) {
		if (ch=='0') root=HT[root].lchild;
		else	root=HT[root].rchild;
		if (HT[root].lchild==0 && HT[root].rchild==0) {
			fputc(HT[root].c,fq);
			root=i;
		}
		ch=fgetc(fp);
	}
	fclose(fp);
	fclose(fq);
}

int main() {
	HuffmanTree HT;
	int i, n, m ,w[128]={0}, d[128]={0}, *s1, *s2;
	char ch, a[128]={0};
	s1=(int *)malloc(sizeof(int));
	s2=(int *)malloc(sizeof(int));
	FILE *fp;
	if ((fp=fopen("file1","rb"))==NULL)
		printf("file1 can't be opened!\n");
	ch = fgetc(fp);
	while (ch!=EOF) {
		for (i=0;i<128;++i)
			if (i==ch) d[i]++;
		ch=fgetc(fp);
	}
	for (i=0,n=0;i<128;++i)
		if (d[i])	{w[n]=d[i];a[n]=i;n++;}
	m=2*n-1;
	HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for (i=1;i<=n;++i)	{HT[i].weight=w[i];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].c=a[i];}
	for (;i<=m;++i)		{HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].c=-1;}
	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;
	}
	free(s1);free(s2);
	fclose(fp);
	HuffmanCode(HT,n);
	HuffmanDecode(HT,n);
	return 0;
}