#define INT_MAX 10000
#define ENCODING_LENGTH 1000
#include "stdio.h"
#include "string.h"
#include "malloc.h"
typedef enum{none,left_child,right_child}Which;//標記是左孩子還是右孩子
typedef char Elemtype;//元素類型
typedef struct TNode{
    Elemtype letter; 
    int weight;
    int parent;
    Which sign;
    char *code;
}HTNode,*HuffmanTree;
int n;
char coding[50];//儲存代碼
char str[ENCODING_LENGTH];//保存要翻譯的句子
void InitTreeNode(HuffmanTree &HT){//初始前N個結點,后M-N個結點置空
    int i;int w;char c;
    int m=2*n-1;
    HuffmanTree p;
    HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
    printf("Input %d database letter and weight:",n);
	printf("(For example:a1b2c3d4)\n");
    p=HT;
    getchar();
    for (i=1;i<=n;i++){
        scanf("%c%d",&c,&w);
        p->code='\0';
        p->letter=c;
        p->parent=0;
        p->sign=none;
        p->weight=w;
        p++;
    }
    for (;i<=m;i++,p++){
        p->code='\0';
        p->letter=' ';
        p->parent=0;
        p->sign=none;
        p->weight=0;
    }
}//INITTREENODE
void Select(HuffmanTree HT,int end,int *s1,int *s2){//在0~END之間,找出最小和次小的兩個結點序號,返回S1,S2
int i;
int min1=INT_MAX;
int min2;
for (i=0;i<=end;i++){//找最小的結點序號
     if (HT[i].parent==0&&HT[i].weight<min1){ 
         *s1=i;
         min1=HT[i].weight;
}
}
     min2=INT_MAX;
      for(i=0;i<=end;i++){//找次小結點的序號
          if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){
              *s2=i;
              min2=HT[i].weight;
          }
      }
}
void HuffmanTreeCreat(HuffmanTree &HT){//建立HUFFMAN樹
    int i;int m=2*n-1;
    int s1,s2;
    for(i=n;i<m;i++){
        Select(HT,i-1,&s1,&s2);
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[s1].sign=left_child;
        HT[s2].sign=right_child;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
}

void HuffmanTreeCode(HuffmanTree HT){//HUFFMAN譯碼
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
int p;int s;
for (i=0;i<n;i++){
     p=i;
     s=n-1;
    while (HT[p].parent!=0){//從結點回溯,左孩子為0,右孩子為1
        if (HT[p].sign==left_child)
              temp[--s]='0';
        else if (HT[p].sign==right_child)
            temp[--s]='1';
        p=HT[p].parent;
    }
    HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配結點碼長度的內存空間
    strcpy(HT[i].code,temp+s);
    printf("%s\n",HT[i].code);    
}
}
void GetCodingSen(char *sentence){//輸入要編碼的句子
    int l;
	getchar();
	printf("Please input your letters.");
	printf("(For example:abcd)\n");
    gets(sentence);
    l=strlen(sentence);
    sentence[l]='\0';
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT){//將句子進行編碼
int i=0;int j;
while(sen[i]!='\0'){
    for(j=0;j<n;j++){
        if (HT[j].letter==sen[i]) //字母吻合則用代碼取代
        {strcat(coding,HT[j].code);
        break;
        }
    }
    i++;
    if (sen[i]==32) i++;
}
printf("The codes refered to the letters is:\n");
printf("(Following up-steps,you will see:110111100.110:a 111:b 10:c 0:d)");
printf("\n%s",coding);
}
void main(){
	printf("This project accomplishs the turn between letter and code.\n");
    HTNode hnode;
    HuffmanTree huff;
    huff=&hnode;
    printf("Input the letter for coding number:");
	printf("(For example:4)\n");
    scanf("%d",&n);
    InitTreeNode(huff);
    HuffmanTreeCreat(huff);
    HuffmanTreeCode(huff);
    GetCodingSen(str);
    HuffmanTreeEncoding(str,huff);
	getchar();
}