用不同的方式实现了Huffman编码算法：1、使用链表结构。2、使用《数据结构》 ...

#include <stdio.h>
#include <malloc.h>

int w[4] = {6, 3, 1, 1};

typedef struct
{
    int weight;
    int LChild, RChild, parent;
}HTNode;

typedef struct
{
    HTNode *nodes;
}HuffmanTree;

typedef struct
{
    int *bit;
    int start;
    int weight;
}Code;

void seleteMin(HuffmanTree &T, int n, int &loc1, int &loc2)
{
    int i, s1 = 10000, s2 = 10000;
    for(i = 0; i <= n; i++)
        if(T.nodes[i].parent == -1)
        {
            if(T.nodes[i].weight < s1)
            {
                s1 = T.nodes[i].weight;
                loc2 = loc1;
                loc1 = i;
            }
            else if(T.nodes[i].weight < s2)
            {
                s2 = T.nodes[i].weight;
                loc2 = i;
            }
        }
}
void CreateHuffmanTree(HuffmanTree &T, int *w, int n)
{
    int i, loc1, loc2;
    T.nodes = (HTNode *)malloc((2 * n - 1) * sizeof(HTNode));
    for(i = 0; i < n; i++)
    {
        T.nodes[i].weight = w[i];
        T.nodes[i].parent = T.nodes[i].LChild = T.nodes[i].RChild = -1;
    }
    for(i = n; i < 2 * n - 1; i++)
    {
        seleteMin(T, i - 1, loc1, loc2);
        T.nodes[loc1].parent = T.nodes[loc2].parent = i;
        T.nodes[i].parent = -1;
        T.nodes[i].LChild = loc1;
        T.nodes[i].RChild = loc2;
        T.nodes[i].weight = T.nodes[loc1].weight + T.nodes[loc2].weight;
        printf("%d %d\n", T.nodes[loc1].weight, T.nodes[loc2].weight);
    }
}

void HuffmanCode(HuffmanTree &T, int n, Code huffCode[])
{
    int i, j, child, parent, t;
    for(i = 0; i < n; i++)
    {
        huffCode[i].bit = (int *)malloc(n * sizeof(int));
        huffCode[i].start = n;
        child = i;
        parent = T.nodes[child].parent;
        t = 0;
        while(parent != -1)
        {
            if(T.nodes[parent].LChild == child) huffCode[i].bit[--huffCode[i].start] = 0;
            else huffCode[i].bit[--huffCode[i].start] = 1;
            t++;
            child = parent;
            parent = T.nodes[child].parent;
        }
        for(j = 0; j < t; j++) printf("%d", huffCode[i].bit[huffCode[i].start + j]);
        puts("");
    }
}

int main()
{
    HuffmanTree T;
    Code huffCode[100];
    CreateHuffmanTree(T, w, 4);
    HuffmanCode(T, 4, huffCode);
    return 0;
}
//结果
//构建HuffmanTree
1    1
3    2
6    5
//翻译HuffmanCode
1
01
000
001