Huffmanアルゴリズム(欲張りアルゴリズム)By ACReaper

#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef struct huffman{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;
int n;
char buf[MAX_LEN];
void HuffmanCoding(HuffmanTree &HT,int w[],int len_w);
void writeHC(HuffmanTree &HT,HTNode &leaf,int i,char buf[],int &cur);
int min(HuffmanTree &T,int &len_w);
int main(){
	HuffmanTree HT;
	while(scanf("%d",&n) != EOF){
		int *pw = (int *)malloc( (n + 1) * sizeof(int));
		if(!pw){
			printf("Memory Error!,Please Try Again.");
			continue;
		}
		for(int i = 1; i <= n; i++){//  n        (      a -- z)
			scanf("%d",pw + i);
		}
		HuffmanCoding(HT,pw,n);//  huffman  ,    HC 
		free(pw);
	}
	return 0;
}
void HuffmanCoding(HuffmanTree &HT,int w[],int len_w){
	int m = 2 * len_w - 1;
	HT = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));
	if(!HT){
		printf("Something Error in Build HuffmanTree!");
		exit(-1);
	}
	/*                ,          */
	for(int i = 1 ; i <= len_w; i++){//        
		HT[i].weight = w[i];//1 -- len_w     
		HT[i].parent = 0;
		HT[i].lchild = HT[i].rchild = 0;
	}
	
	for(int i = len_w + 1; i <= m; i++){//        ,    2   ,      
		HT[i].weight = 0;
		HT[i].parent = 0;
		HT[i].lchild = HT[i].rchild = 0; 
	} 
	
	/*    ,  huffman */ 
	int search_area = len_w;//        
	int start = len_w + 1;//          
	for(;;){
		int min1 = min(HT,search_area);
		int min2 = min(HT,search_area);
		if(min1 == min2){//      ,huffman      
			HT[min1].parent = 0;//   parent    2 
			break;
		}
		HT[start].weight = HT[min1].weight + HT[min2].weight;
		HT[start].lchild = min2;
		HT[start].rchild = min1;
		HT[min1].parent = HT[min2].parent = start;
		search_area++;
		start++;  
		len_w--;
	} 
	int cur = 0;
	for(int i = 1; i <= n;i++){
		writeHC(HT,HT[i],i,buf,cur);
		cur = 0;
	}
	free(HT);
	
}
int min(HuffmanTree &T,int &len_w){//len_w         
	int m;
	for(int i = 1; i <= len_w; i++){
		if(T[i].parent == 0){
			m = i;
			break;
		}
	}
	for(int i = 1; i <= len_w;i++){
		if(T[m].weight > T[i].weight && T[i].parent == 0){
			m = i;
		}
	}
	T[m].parent = -1;
	return m;
}
void writeHC(HuffmanTree &HT,HTNode &leaf,int i,char buf[],int &cur){
	if(leaf.parent == 0){
		buf[cur] = '\0'; 
		for(int i = cur - 1; i >=0 ; i--)
			printf("%c",buf[i]);
		printf("
"); 
		return;
	}else{
		if(HT[leaf.parent].lchild == i){
			buf[cur++] = '1';
			writeHC(HT,HT[leaf.parent],leaf.parent,buf,cur);
		}
		if(HT[leaf.parent].rchild == i){
			buf[cur++] = '0';
			writeHC(HT,HT[leaf.parent],leaf.parent,buf,cur);
		}
	}
}