用数组实现哈夫曼编解码

简单的版本，用数组实现的。

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

#define N 10        //要编码的字符个数

typedef char KeyType;    // 被编码字符的类型,假定为字符
typedef enum{ NONE, LEFT_CHILD, RIGHT_CHILD } WHICH ; //定义节点是双亲的左孩子还是右孩子。
// NONE表示未知

typedef struct node
{
    KeyType key;
    int weight;              //权重或者出现的概率
    int parent;              //我们用数组存储树，这里用下标标是双亲。-1表示没有双亲。
    WHICH sign;              //说明该节点使是左孩子还是右孩子
    char *code;              //对编码采用01串存储，以便输出；也可以在设定一个int，来存储编码
                           //这样解码要快，解码程序比较简单，这里就不写了。
} HuffmanNode;

//定义一个HUFFMAN树类型，数组表示，长度是N+N-1 = 2N-1
typedef HuffmanNode HuffmanTree[N+N-1];

//为了测试方便，这里用随机数的方法初始化一个HUFFMAN树。
void init( HuffmanTree T)
{
    int i;
    char j=’A';
    //初始化存储关键字的部分。
    for(i=0; i<N; i++)
    {
        T.key = j++;
        T.parent = -1 ; //-1表示没有双亲。
        T.sign=NONE;
        T.weight = (rand() % 100);    //暂不考虑总的概率和为1，用权值代之
    }

    for(;i<N+N-1; i++)
    {
        T.parent = -1;
        T.sign=NONE;
        T.weight=0;
    }
}

//从HT[0]..HT[N+i-1]中找出最小，次小
void SelectMin(HuffmanTree T, int start, int end, int *pmin1, int *pmin2)
{
    int i;
    int min1=INT_MAX;//最小
    int min2;    //次小。
    
    //找出最小
    for(i=start; i<=end; i++)
    {
        if( T.sign == NONE && T.weight < min1)
        {
             *pmin1 = i;
             min1 = T.weight;
        }
    }

    //找次小
    min2=INT_MAX;
    for(i=start; i<=end; i++)
    {
        if( (*pmin1 != i) &&  (T.sign == NONE) && (T.weight < min2) )
        {
             *pmin2 = i;
             min2 = T.weight;
        }
    }
}

// 进行HUFFMAN树构造
void CreateHuffmanTree(HuffmanTree T)
{
    
    int i;
    int min1, min2;    //记录权值最小，次小的两个节点下标


    for(i=N; i<2*N-1; i++)
    {
        SelectMin(T, 0, i-1, &min1, &min2);    //从HT[0]..HT[i-1]中找出最小，次小
        
        T.weight = T[min1].weight + T[min2].weight;
        T[min1].parent = i;
        T[min1].sign = LEFT_CHILD;
        T[min2].parent = i;
        T[min2].sign = RIGHT_CHILD;
    }
}

//生成将每个节点的编码，按01字符串的方式生成。
void EncodeHuffman( HuffmanTree T)
{
    char temp[N];        //临时串,树高会大于N。
    int s;
    
    int i, p;
    temp[N-1]=’\0′;

    //左孩子0，右孩子1
    for(i=0; i<N; i++)
    {
        p = i;
        s = N-1;
        while(T

.parent != -1)
        {
             if( T

.sign == LEFT_CHILD )
                 temp [--s] = ’0′;
             else if(T

.sign == RIGHT_CHILD)
                 temp [--s] = ’1′;
             
             p = T

.parent;
        }
        T.code = (char*)malloc((N-s)*sizeof(char));
        strcpy(T.code, temp+s);    //把编码复制道接点域中。
    }
}

//输出每个节点的编码情况。
void ShowCode( HuffmanTree T)
{
    int i;
    printf(” Key    Code    weigh t\n—————\n”);
    for(i=0; i<N; i++)
        printf(“%3c% 8s%8d\n”,T.key,T.code,T.weight);

}


int main()
{
    HuffmanTree T;
    init(T);    //初始化
    CreateHuffmanTree(T);
    EncodeHuffman(T);
    ShowCode(T);
    return 0;
}