Huffman_Code.c

/*
HW3-2 HHuffman 
106502030
*/ 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10000
char s[N];
int n;
int cnt[128];

typedef struct HuffmanTree{
	char data;
	int weight;
	int fa;//father
	int lson,rson;// left,right son
	int id;
}HT;

HT ht[N];

struct Queue{
	char head;
	int weight;
	int id;
}q[N],p[N];
void swap(struct Queue *a,struct Queue *b){
	struct Queue tmp=*a;
	*a=*b;
	*b=tmp;
}
int smaller(struct Queue *q,int i,int j){
	if((q[i].weight<q[j].weight)||(q[i].weight==q[j].weight&&q[i].head<q[j].head))return 1;
	return 0;
}

void sort(struct Queue *q,int left,int right){ //implementation in quicksort

	if(left>=right)return ;
	
	// choose the rightmost to be pivot
	int pivot=right;
	
	//printf("%d %d\n",pivot,right);
	
	int front=left,i;
	for(i=left;i<right;i++){
		//q[i] smaller or equal q[pivot]
		//if(q[i].weight<q[pivot].weight||(q[i].weight==q[pivot].weight&&q[i].head<q[pivot].head))
		if(smaller(q,i,pivot)==1)
			swap(&q[front],&q[i]),
			front++;
	}
	// put pivot back to the right place
	swap(&q[front],&q[right]);
	// front is the new pivot index
	sort(q,left,front-1);
	sort(q,front+1,right);
	
}
struct huffman_code{
	char *code;
	int len;
	char id;
}Hcode[N];

void huffman_encode(int len){

	char *code;
	code=(char *)malloc(len+1);
	code[len]='\0';
	int i,k,cur,fa; // current node , parent node
	for(i=0;i<len;i++){
		k=len;
		for(cur=i,fa=ht[i].fa;fa;cur=fa,fa=ht[fa].fa){
			if(ht[fa].lson==cur)
				code[--k]='0';
			else code[--k]='1';
		}
		//puts(code);
		Hcode[i].code=(char *)malloc(len-k);
		//printf("%d~%d\n",k,len);
		Hcode[i].len=len-k;
		Hcode[i].id=ht[i].data;
		strcpy(Hcode[i].code,&code[k]);
	}
	free(code);
	
}
void swap_code(struct huffman_code *a,struct huffman_code *b){
	struct huffman_code tmp=*a;
	*a=*b;
	*b=tmp;
}
void sort_code(struct huffman_code *hc,int left,int right){
	if(left>=right)return ;
	int pivot=right;
	int front=left,i;
	for(i=left;i<right;i++){
		if(hc[i].len<hc[pivot].len||(hc[i].len==hc[pivot].len&&hc[i].id<hc[pivot].id))
			swap_code(&hc[front],&hc[i]),
			front++;
	}
	swap_code(&hc[front],&hc[right]);
	sort_code(hc,left,front-1);
	sort_code(hc,front+1,right);
}
int main(){
	scanf("%d%*c",&n);
	int i;
	while(n--){
		scanf("%[^\n]%*c",&s);
		for(i=0;s[i];i++){
			cnt[s[i]]++;
		}			
	}
	
	
	int top=0;
	for(i='A';i<='z';i++)
		if(cnt[i]){
			q[top].head='A'+i-65;
			q[top++].weight=cnt[i];
		}
	

	//for(i='A';i<='z';i++)
	//	printf("%d: %d\n",i,cnt[i]);
	
	//for(i=0;i<top;i++)
	//	printf("%c %d\n",q[i].head,q[i].weight);	
	sort(q,0,top-1);
	//for(i=0;i<top;i++)
	//	printf("%c: %d ",q[i].head,q[i].weight);
	//puts("");
	
	for(i=0;i<top;i++)
		q[i].id=i;
	for(i=0;i<top;i++){
		ht[i].data=q[i].head;
		ht[i].weight=q[i].weight;
		ht[i].lson=-1;
		ht[i].rson=-1;
		ht[i].fa=-1;
		ht[i].id=i;
	}
	int l=0,r=top-1;
	// the key of head here is for order of sort
	char key='z'+1;
	for(i=top;i<top+top-1;i++){
		
		int new_w=q[l].weight+q[l+1].weight;
		char new_c=q[l].head;
		r++;
		q[r].weight=new_w;
		q[r].head=new_c;
		q[r].id=i;
		
	//	printf("%d\n",i);
		
		ht[i].id=i;
		ht[i].data=new_c;
		ht[i].weight=new_w;
		ht[i].lson=q[l].id;
		ht[i].rson=q[l+1].id;
		ht[q[l].id].fa=i;
		ht[q[l+1].id].fa=i;
		
		
		l+=2;
		//printf("%d %d\n",l,r);
		int j;
	//	for(j=0;j<=r;j++)
	//		printf("%c: %d ",q[j].head,q[j].weight);
	//	puts("");
		j=r;
		while(l<j){
			if(q[j-1].weight>q[j].weight)
				swap(&q[j-1],&q[j]),
				j--;
			else break;
		}
		
	//	for(j=l;j<=r;j++)
	//		printf("%c: %d ",q[j].head,q[j].weight);
	//	puts("");
	}
	
	//for(i=0;i<2*top-1;i++)
	//	printf("data: %d id: %d weight: %d lson: %d rson: %d fa: %d\n",ht[i].data,ht[i].id,ht[i].weight,ht[i].lson,ht[i].rson,ht[i].fa);

	huffman_encode(top);
	sort_code(Hcode,0,top-1);
	for(i=0;i<top;i++){
		printf("%c: %s\n",Hcode[i].id,Hcode[i].code);
	}
	
	int psum=0,qsum=0;
	for(i=0;i<top;i++){
		psum+=Hcode[i].len*cnt[Hcode[i].id];
		//printf("%d %d\n",Hcode[i].len,cnt[Hcode[i].id]);
		qsum+=cnt[Hcode[i].id];
	}
	qsum*=8;
	double ans=(1.-1.*psum/qsum)*100.;
	printf("Compression ratio: %.2lf%%\n",ans);
	
}


/*
3
I have a pen.
I have an apple.
UMMMM~ APPLE PEN.
*/