哈夫曼的c语言实现代码

我们设置一个结构数组 HuffNode 保存哈夫曼树中各结点的信息。根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有 2n-1 个结点，所以数组 HuffNode 的大小设置为 2n-1 。HuffNode 结构中有 weight, lchild, rchild 和 parent 域。其中，weight 域保存结点的权值, lchild 和 rchild 分别保存该结点的左、右孩子的结点在数组 HuffNode 中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过 parent 域的值来确定。初始时 parent 的值为 -1。当结点加入到树中去时，该结点 parent 的值为其父结点在数组 HuffNode 中的序号，而不会是 -1 了。

求叶结点的编码：
该过程实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的 0、1 序列，因此先得到的分支代码为所求编码的低位，后得到的分支代码为所求编码的高位码。我们可以设置一个结构数组 HuffCode 用来存放各字符的哈夫曼编码信息，数组元素的结构中有两个域：bit 和 start。其中，域 bit 为一维数组，用来保存字符的哈夫曼编码， start 表示该编码在数组 bit 中的开始位置。所以，对于第 i 个字符，它的哈夫曼编码存放在 HuffCode[i].bit 中的从 HuffCode[i].start 到 n 的 bit 位中。
复制代码 代码如下:

#include

#define MAXBIT      100
#define MAXVALUE  10000
#define MAXLEAF     30
#define MAXNODE    MAXLEAF*2 -1

typedef struct
{
    int bit[MAXBIT];
    int start;
} HCodeType;       
typedef struct
{
    int weight;
    int parent;
    int lchild;
    int rchild;
} HNodeType;       

void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
{
   
    int i, j, m1, m2, x1, x2;
   
    for (i=0; i<2*n-1; i++)
    {
        HuffNode[i].weight = 0;
        HuffNode[i].parent =-1;
        HuffNode[i].lchild =-1;
        HuffNode[i].lchild =-1;
    }

   
    for (i=0; i    {
        printf ("Please input weight of leaf node %d: n", i);
        scanf ("%d", &HuffNode[i].weight);
    }

   
    for (i=0; i    {
        m1=m2=MAXVALUE;    
        x1=x2=0;
       
        for (j=0; j        {
            if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
            {
                m2=m1;
                x2=x1;
                m1=HuffNode[j].weight;
                x1=j;
            }
            else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
            {
                m2=HuffNode[j].weight;
                x2=j;
            }
        }
           
        HuffNode[x1].parent  = n+i;
        HuffNode[x2].parent  = n+i;
        HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
        HuffNode[n+i].lchild = x1;
        HuffNode[n+i].rchild = x2;

        printf ("x1.weight and x2.weight in round %d: %d, %dn", i+1, HuffNode[x1].weight, HuffNode[x2].weight); 
        printf ("n");
    }
}

int main(void)
{
    HNodeType HuffNode[MAXNODE];           
    HCodeType HuffCode[MAXLEAF],  cd;      
    int i, j, c, p, n;
    printf ("Please input n:n");
    scanf ("%d", &n);
    HuffmanTree (HuffNode, n);

    for (i=0; i < n; i++)
    {
        cd.start = n-1;
        c = i;
        p = HuffNode[c].parent;
        while (p != -1)  
        {
            if (HuffNode[p].lchild == c)
                cd.bit[cd.start] = 0;
            else
                cd.bit[cd.start] = 1;
            cd.start--;       
            c=p;                   
            p=HuffNode[c].parent;   
        }

       
        for (j=cd.start+1; j        { HuffCode[i].bit[j] = cd.bit[j];}
        HuffCode[i].start = cd.start;
    }

   
    for (i=0; i    {
        printf ("%d 's Huffman code is: ", i);
        for (j=HuffCode[i].start+1; j < n; j++)
        {
            printf ("%d", HuffCode[i].bit[j]);
        }
        printf ("n");
    }
    getch();
    return 0;
}