第一篇：c語(yǔ)言構(gòu)建哈夫曼樹(shù)(附運(yùn)行結(jié)果圖)[本站推薦]

#include #include #include

int m,s1,s2;

typedef struct {

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)

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)造哈夫曼樹(shù)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哈夫曼樹(shù)的構(gòu)造過(guò)程如下所示：”);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);for(i=n+1;i<=m;i++){ // 建哈夫曼樹(shù)

// 在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=%dn”, 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);

}

//------無(wú)棧非遞歸遍歷哈夫曼樹(shù)，求哈夫曼編碼

cd =(char *)malloc(n*sizeof(char));// 分配求編碼的工作空間

p = m;cdlen = 0;

for(i=1;i<=m;++i)// 遍歷哈夫曼樹(shù)時(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] ='