//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :4  (4_4)                   *
//*PROGRAM          :哈夫曼樹                   *
//*CONTENT          :構造哈夫曼樹,哈夫曼編碼    *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{unsigned int weight;  //結點權值
 unsigned int parent,lchild,rchild; //結點的父指針，左右孩子指針
}HTNode,*HuffmanTree;       //動態分配數組存儲哈夫曼樹
typedef char **HuffmanCode; //動態分配數組存儲哈夫曼編碼表
void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成一棵哈夫曼樹
void HuffmanCoding(HuffmanTree,HuffmanCode &,int );       //對哈夫曼樹進行編碼
void PrintHuffmanCode(HuffmanCode,unsigned int*,int);     //顯示哈夫曼編碼
void Select(HuffmanTree,int,int&,int&); //在數組中尋找權值最小的兩個結點
void main()
{HuffmanTree HT;  //哈夫曼樹HT
 HuffmanCode HC;  //哈夫曼編碼表HC
 int n,i;         //n是哈夫曼樹葉子結點數
 unsigned int *w; //w存放葉子結點權值   
 char j='y';
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //程序解說
 printf("本程序將演示構造哈夫曼樹.\n");
 printf("首先輸入葉子結點數目.\n例如:8\n");
 printf("然后輸入每個葉子結點的權值.\n");
 printf("例如:5 29 7 8 14 23 3 11\n");
 printf("程序會構造一棵哈夫曼樹并顯示哈夫曼編碼.\n");
 printf("  5---0110\n 29---10\n  7---1110\n  8---1111\n 14---110\n");
 printf(" 23---00\n  3---0111\n 11---010\n");
 while(j!='N'&&j!='n')
      {printf("請輸入葉子結點數目:");
       scanf("%d",&n);   //輸入葉子結點數
       if(n<=1) {printf("該數不合理!\n");continue;}
       w=(unsigned int*)malloc(n*sizeof(unsigned int)); //開辟空間存放權值
       printf("請輸入各葉子結點的權值:\n");
       for(i=0;i<n;i++) scanf("%d",&w[i]);   //輸入各葉子結點權值
       CreateHuffmanTree(HT,w,n);       //生成哈夫曼樹
       HuffmanCoding(HT,HC,n);          //進行哈夫曼編碼
       PrintHuffmanCode(HC,w,n);        //顯示哈夫曼編碼
       printf("哈夫曼樹構造完畢，還要繼續嗎?(Y/N)");
       scanf(" %c",&j);
     }
}

void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)
{//w存放n個結點的權值，將構造一棵哈夫曼樹HT
 int i,m;
 int s1,s2;
 HuffmanTree p;
 if(n<=1) return;
 m=2*n-1;  //n個葉子結點的哈夫曼樹，有2*n-1個結點
 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //開辟2*n各結點空間，0號單元不用
 for(p=HT+1,i=1;i<=n;++i,++p,++w) //進行初始化
       {p->weight=*w;
	p->parent=0;
	p->lchild=0;
	p->rchild=0;
       }
 for(;i<=m;++i,++p)
       {p->weight=0;
	p->parent=0;
	p->lchild=0;
	p->rchild=0;
       }
 for(i=n+1;i<=m;++i)  //建哈夫曼樹
    {Select(HT,i-1,s1,s2);  
        //從HT[1...i-1]中選擇parent為0且weight最小的兩個結點，其序號分別為s1和s2
     HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2結點的父指針parent
     HT[i].lchild=s1; HT[i].rchild=s2; //修改i結點的左右孩子指針
     HT[i].weight=HT[s1].weight+HT[s2].weight; //修改權值
    }
}
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{//將有n個葉子結點的哈夫曼樹HT進行編碼， 所編的碼存放在HC中
 //方法是從葉子到根逆向求每個葉子結點的哈夫曼編碼
 int i,c,f,start;
 char *cd;
 HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n個編碼的頭指針向量
 cd=(char *)malloc(n*sizeof(char));  //開辟一個求編碼的工作空間
 cd[n-1]='\0';           //編碼結束符
 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';        //若是左孩子編為'0'
	else cd[--start]='1';                        //若是右孩子編為'1' 
     HC[i]=(char *)malloc((n-start)*sizeof(char));   //為第i個編碼分配空間
     strcpy(HC[i],&cd[start]);         //將編碼從cd復制到HC中
    }
 free(cd); //釋放工作空間
}
void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)
{//顯示有n個葉子結點的哈夫曼樹的編碼表
 int i;
 printf("HuffmanCode is :\n");
 for(i=1;i<=n;i++)
   {printf(" %3d---",w[i-1]);
    puts(HC[i]);
   }
 printf("\n");
}
void Select(HuffmanTree HT,int t,int&s1,int&s2)
{//在HT[1...t]中選擇parent不為0且權值最小的兩個結點，其序號分別為s1和s2 
 int i,m,n;
 m=n=10000;  
 for(i=1;i<=t;i++)
   {if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n))
	if(m<n)
	    {n=HT[i].weight;s2=i;}
	else {m=HT[i].weight;s1=i;}

   }
 if(s1>s2)  //s1放較小的序號
      {i=s1;s1=s2;s2=i;}
}