#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#define N 10

typedef struct{
    unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char * * HuffmanCode; //字符指針的指針

void Select(HuffmanTree HT,int k,int &s1,int &s2)
{
	//printf("i-1=%d   ",k);
	int i;
	unsigned int min;
    s1=s2=0;
	int flag=0;
	while (s1==0 || s2==0)
	{
		for (i=1;i<=k;i++) //用于從1-k中選擇第一個parent為零的節點
		{
			if (HT[i].parent==0 && i!=s1)
			{
				min=HT[i].weight;
				if (s1==0)
					s1=i;
	            else
			        s2=i;
				//printf("第一個parent為0的節點是%d:%d",i,HT[i].weight);
			    break;
			}
		}
        
	    for(i=1;i<=k;i++)//求得weight值最小并且parent為0的節點
		{
			if ((HT[i].weight<min) && HT[i].parent==0 && i!=s1)
			{
				min=HT[i].weight;
				if (flag==0)
					s1=i;
	            else
			        s2=i;
			}
		}
		flag=1;
	}//while
	//printf("%d-%d\n",s1,s2);
}//Select


void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int * w,int n)
{
	int i;
	int s1,s2;
	char * cd;
	int start;
	if (n<1)
		return;
	int m=2*n-1; //生成哈夫曼樹的節點總數
    HuffmanTree p;

	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //給m+1個節點分配內存單元，0號單元未用
	
	printf("初始化。。\n");
	Sleep(1000);
	p=HT+1;
	for(i=1;i<=n;++i)  //葉子節點初始化
	{
		p->lchild=0;
		p->parent=0;
		p->rchild=0;
		p->weight=*w;
		//printf("%d",*w);
		p++;
		w++;
	}
	/*
	printf("\n");
	for(p=HT+1,i=1;i<=n;++i,++p)  //葉子節點初始化
	{
		printf("節點%d:左孩子:%d,右孩子:%d,權重:%d,父節點%:%d\n",i,p->lchild,p->rchild,p->weight,p->parent);
	}
	*/
	for (i=n+1;i<=m;++i)//根節初始化
	{
		p->lchild=0;
		p->parent=0;
		p->rchild=0;
		p->weight=0;
		++p;
	}
    p=HT+n;
	/*
	for(i=n+1;i<=m;++i)
	{
		printf("節點%d:左孩子:%d,右孩子:%d,權重:%d,父節點%:%d\n",i,p->lchild,p->rchild,p->weight,p->parent);
		++p;
	}
    */
	printf("建立哈夫曼樹。。。。\n");
	Sleep(1000);
	for (i=n+1;i<=m;++i)//建哈夫曼樹，確定n-1個內部節點
	{
		Select(HT,i-1,s1,s2); //從1到i-1中選擇weight最小的并且parent為零的節點
		//printf("第%d次選擇%d-%d\n",i-n,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;
		HT[i].parent=0;
	}
    //哈夫曼樹建立完畢！
	printf("開始編碼。。。\n");
	Sleep(1000);
	HC= (HuffmanCode) malloc ((n+1)*sizeof(char *)); //分配指針數組的空間
	cd = (char*) malloc (n*sizeof(char)); //工作空間，用于臨時存放編碼
	cd[n-1]='\0';
    unsigned int c,f;
	for (i=1;i<=n;++i)
	{
		start=n-1;
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
			if (HT[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		HC[i]=(char*) malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
		printf("%d:",HT[i].weight);
	    puts(HC[i]); //輸出編碼
	}
	free(cd);
}//HuffmanCoding

void main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int weight[N]={15,8,3,9,8,6,4,7,13,10};
	HuffmanCoding(HT,HC,weight,N);

}