#include
#include
#include
#include
#include
#include
#include
#include
#include
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)
{
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=n*2-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號未用
for(p=*HT+1,i=1;i<n;++i,++p,++w)
{
(*p).weight = *w; //對每個weight初始化
(*p).parent = 0; //對每個parent初始化
(*p).lchild = 0; //對每個lchild初始化
(*p).rchild = 0; //對每個rchild初始化
}
for(;i<m;++i,++p)
(*p).parent = 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 = (*HT)[s2].parent =i;
(*HT)[i].lchild = s1;
(*HT)[i].rchild = s2;
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
}
//求哈夫曼編碼
HC = (HuffmanCode)malloc((n+1)*sizeof(char));//分配n個字符編碼
//的頭指針向量【第0個不用】
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';
else
cd[--start] = '1';
}
(*HC)[i] = (char*)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]); //複製:從cd輔助編碼(串)到HC
}
free(cd); //釋放工作空間
}
int min(HuffmanTree t,int i)
{
int j,flag;
unsigned int k = UINT_MAX;
for(j=1;j<=i;j++)
{
if(t[j].weight<k && t[j].parent ==0) //循環查找最小的值
k = t[j].weight,flag = j;
}
t[flag].parent = 1; //對已經查找出來的最小值進行標記 .parent為1
return flag;
}
void select(HuffmanTree t,int i,int *s1,int *s2)
{
int j;
*s1 = min(t,i);
*s2 = min(t,i);
if(*s1>*s2)
{
j = *s1;
*s1 = *s2;
*s2 = j; //s1為最小的兩個值中序號小的那個
}
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
printf("請輸入權值的個數(>1):");
int n,i,*w;
scanf("%d",&n);
w = (int*)malloc(n*sizeof(int));
printf("請依次輸入%d個權值(整數):\n",n);
for(i=0;i<=n-1;i++)
scanf("%d",w+i);
HuffmanCoding(&HT,&HC,w,n);
for(i = 1;i<=n; i++)
puts(HC[i]);
}