// Huffuman.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "float.h"
#include "stdlib.h"
#include "string.h"
//兩種結構體的定義
struct hufnode
{
	long wei;//權值
	struct hufnode *lch;//左節點指針
    struct hufnode *rch;//右節點指針
	struct hufnode *prt;//父節點指針
	char ch;//該字符
	char code[30];//該節點的Haffuman編碼
};

struct Input//用于對輸入數據統計的結構體
{
	long total;
	char ch;
	//struct Input * Inext;
};


static void myselect(struct hufnode *p,int k,int *i,int *j);

struct hufnode *hufm (int n,int m,struct Input w[]);



int main(int argc, char* argv[])
{
	long a[128];
	struct hufnode * p=NULL,*q=NULL,*t=NULL,*bh=NULL;
	int i,j=0,n=0,j1;
	char c=' ';
	
    for(i=0;i<128;i++)//數組初始化
	{
		a[i]=0;
	}
    
	printf("請任意輸入字符,并以'.'結束:\n");

	scanf("%c",&c);
	while(c!='.')//以'.'輸入為結束
	{
        a[c]++;
		scanf("%c",&c);
	}

	for(i=0;i<128;i++)//統計有輸入的字符個數
	{
		if(a[i]!=0) n++;

	}
	struct Input *w=(struct Input *)malloc(n*sizeof(struct Input));
	for(i=0;i<128;i++)
	{
		if(a[i]!=0)
		{
			w[j].ch=i;
			w[j].total=a[i];
			j++;
		}
	}

	bh=hufm(n,2*n-1,w);
    t=(bh-2*n+2);


	for(j=0;j<n;j++)//求Huffuman編碼的反序
	{
        p=t+j;q=p;i=0;
		while(q!=bh)
		{
			if(q->prt->lch==q)  p->code[i++]='0';
			else p->code[i++]='1';
			q=q->prt;
		}
		p->code[i]='\0';
	}
	
	for(i=0;i<n;i++)//將Huffuman編碼字符串反序排列得到真正的Huffuman編碼
	{
		char chm[10];j=0;
		strcpy(chm,(t+i)->code);
		while( (t+i)->code[j++]!='\0') ;
		for(j1=j-2;j1>=0;j1--)
		{
            (t+i)->code[j-2-j1]=chm[j1];
		}
       (t+i)->code[j-1]='\0';
	}
    
	printf("您輸入的字母的Haffuman編碼為：\n");
	for(i=0;i<n;i++)
	{
		if((t+i)->ch==' ') printf("空格  %s\n",(t+i)->code);
		else if((t+i)->ch==10) printf("回車  %s\n",(t+i)->code);
		else printf("%c    %s\n",(t+i)->ch,(t+i)->code);
	}

	return 0;
}


static void myselect(struct hufnode *p,int k,int *i,int *j)
{
   int m,n=0;
   while( (n<k)&&( (p+n)->prt!=NULL )  ) n=n+1;
   m=(p+n)->wei;
   *i=n;
   while(n<k)
   {
	   if(  ( ((p+n)->wei)<m )&&( (p+n)->prt==NULL )  )
	   {
		   *i=n;m=(p+n)->wei;
	   }
	   n=n+1;
   }
   n=0;
   while( (n<k)&&( (p+n)->prt!=NULL )|| (n==(*i))  ) n=n+1;
   m=(p+n)->wei;*j=n;
   while(n<k)
   {
	   if(  ( ((p+n)->wei)<m )&&( (p+n)->prt==NULL )&& (  n!=(*i))  )
	   {
		   *j=n;m=(p+n)->wei;
	   }
	   n=n+1;
   }
   if((*i)>(*j)) { n=(*i);*i=(*j);*j=n;}
   return;
 
}

struct hufnode *hufm (int n,int m,struct Input w[])
{
   struct hufnode *p,*bh;
   int k,i,j;
   p=(struct hufnode*)malloc(m*sizeof(struct hufnode));
   for(k=0;k<m;k++)
   {
	   (p+k)->prt=NULL; 
	   (p+k)->lch=NULL; 
	   (p+k)->rch=NULL;
   }
   for(k=0;k<n;k++)
   {
	   (p+k)->wei=w[k].total;
       (p+k)->ch=w[k].ch;
   }
   for(k=n;k<m;k++)
   {
	   myselect(p,k,&i,&j);
	   (p+i)->prt=(p+k); (p+j)->prt=(p+k);
	   (p+k)->lch=(p+i); (p+k)->rch=(p+j);
	   (p+k)->wei=(p+i)->wei+(p+j)->wei;
   }
   bh=p+m-1;
   return (bh); 
}