#include<string.h> 
#include<stdlib.h> 
#include<stdio.h> 

int m,s1,s2; 

typedef struct { 
unsigned int weight; 
unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹 
typedef char *HuffmanCode; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表 

void Select(HuffmanTree HT,int n) { 
int i,j; 
for(i = 1;i <= n;i++) 
if(!HT[i].parent){s1 = i;break;} 
for(j = i+1;j <= n;j++) 
if(!HT[j].parent){s2 = j;break;} 
for(i = 1;i <= n;i++) 
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; 
for(j = 1;j <= n;j++) 
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j; 
} 

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC[], int *w, int n) { 
// 算法6.13 
// w存放n個(gè)字符的權(quán)值(均>0)，構(gòu)造哈夫曼樹HT， 
// 并求出n個(gè)字符的哈夫曼編碼HC 
int i, j; 
char *cd; 
int p; 
int cdlen; 

if (n<=1) return; 
m = 2 * n - 1; 
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號(hào)單元未用 
for (i=1; i<=n; i++) { //初始化 
HT[i].weight=w[i-1]; 
HT[i].parent=0; 
HT[i].lchild=0; 
HT[i].rchild=0; 
} 
for (i=n+1; i<=m; i++) { //初始化 
HT[i].weight=0; 
HT[i].parent=0; 
HT[i].lchild=0; 
HT[i].rchild=0; 
} 
puts("\n哈夫曼樹的構(gòu)造過程如下所示："); 
printf("HT初態(tài):\n 結(jié)點(diǎn) weight parent lchild rchild"); 
for (i=1; i<=m; i++) 
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight, 
HT[i].parent,HT[i].lchild, HT[i].rchild); 
printf(" 按任意鍵，繼續(xù) ..."); 
getchar(); 
for (i=n+1; i<=m; i++) { // 建哈夫曼樹 
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)， 
// 其序號(hào)分別為s1和s2。 
Select(HT, i-1); 
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; 
printf("\nselect: s1=%d s2=%d\n", s1, s2); 
printf(" 結(jié)點(diǎn) weight parent lchild rchild"); 
for (j=1; j<=i; j++) 
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight, 
HT[j].parent,HT[j].lchild, HT[j].rchild); 
printf(" 按任意鍵，繼續(xù) ..."); 
getchar(); 
} 

//------無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼 
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間 
p = m; cdlen = 0; 
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時(shí)用作結(jié)點(diǎn)狀態(tài)標(biāo)志 
HT[i].weight = 0; 
while (p) { 
if (HT[p].weight==0) { // 向左 
HT[p].weight = 1; 
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; } 
else if (HT[p].rchild == 0) { // 登記葉子結(jié)點(diǎn)的字符的編碼 
HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); 
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復(fù)制編碼(串) 
} 
} else if (HT[p].weight==1) { // 向右 
HT[p].weight = 2; 
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; } 
} else { // HT[p].weight==2，退回退到父結(jié)點(diǎn)，編碼長(zhǎng)度減1 
HT[p].weight = 0; p = HT[p].parent; --cdlen; 
} 
} 
} // HuffmanCoding 
void main() { 
HuffmanTree HT;HuffmanCode *HC;int *w,n,i; 
puts("輸入結(jié)點(diǎn)數(shù):"); 
scanf("%d",&n); 
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); 
w = (int *)malloc(n*sizeof(int)); 
printf("輸入%d個(gè)結(jié)點(diǎn)的權(quán)值\n",n); 
for(i = 0;i < n;i++) 
scanf("%d",&w[i]); 
HuffmanCoding(HT,HC,w,n); 
puts("\n各結(jié)點(diǎn)的哈夫曼編碼:"); 
for(i = 1;i <= n;i++) 
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]); 
getchar(); 
}