huffman tree.cpp

数据结构中的Huffman编码/译码源程序

#include<stdio.h>
#include<stdlib.h>
typedef struct {
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode,*HuffmanTree;
typedef char  * * HuffmanCode;

void Select(HuffmanTree pht, int pos, int *x1, int *x2)
{    
	int  m1=MAXINT, m2=MAXINT,j;	/* 相关变量赋初值 */
	for (j=1; j<pos; j++)	/* 找两个最小权的无父结点的结点 */
	{
		if (pht->HT[j].weight<m1 && HT->HT[j].parent==0)
		{ 	
			m2=m1;
			x2=x1;
			m1=pht->HT[j].weight;
			x1=j;
		}
		else if 
			(pht->HT[j].weight<m2 && pht->HT[j].parent == 0)
		{
			m2=pht->HT[j].weight;
			x2=j;
		}
	}
}


void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){
//w存放n个字符的权值（均>0），构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC。
	int m,i;
	HuffmanCode p;
    if(n<=1) return;
    m=2*n-1;
    HT= (HuffmanTree) malloc ((m+1)*sizeof(HTNode));
    for (p=HT,i=1; i<=n; ++i,++p,++w) *p={*w, 0, 0, 0};
    for (; i<=m; ++i,++p) *p={0,0,0,0};
    for (i=n+1; i<=m; ++i){  //建哈夫曼树
        Select(HT, i-1, s1, s2);
        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;
    }
	//从叶子到根逆向求每个字符的哈夫曼编码
	HC=(HuffmanCode) malloc ((n+1)*siezof(char *));
    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));
        strcpt (HC[i], &cd[start]);
    }
    free(cd);
}