简单的huffman树的实现，就差解码部分，真心不好写

spy

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

#define N 6  //叶子数目
#define M 2*N-1  //树中结点总数

typedef struct  //结点类型
{
    float weight;  //权值, 不妨设权值均大于0
    int lchild, rchild, parent;  //左右孩子及双亲指针
}HTNode;

typedef HTNode HuffmanTree[M];  //HuffmanTree是向量类型

typedef struct
{
    char ch;  //存储字符
    char bits[N+1];  //存放编码位串
}CodeNode;

typedef CodeNode HuffmanCode[N];

void InitHuffmanTree(HuffmanTree);
void InputWeight(HuffmanTree);
void SelectMin(HuffmanTree, int, int *, int *);
void CreateHuffmanTree(HuffmanTree);
void CharSetHuffmanEncoding(HuffmanTree, HuffmanCode);

int main()
{
    HuffmanTree tree;
    HuffmanCode table;

    InitHuffmanTree(tree);
    InputWeight(tree);
    CreateHuffmanTree(tree);
    CharSetHuffmanEncoding(tree, table);

    return 0;
}

void InitHuffmanTree(HuffmanTree T)
{
    //将T[0...M-1]中2N-1个结点里的三个指针均置为空(即置为-1), 权值置为0

    int i;

    for(i=0; i<M; i++)
    {
        T[i].weight = 0;
        T[i].lchild = -1;
        T[i].rchild = -1;
        T[i].parent = -1;
    }
}

void InputWeight(HuffmanTree T)
{
    //读入N个叶子的权值存于向量的前N个分量(即T[0...N-1])中, 它们是初始森林中N个独立的根结点上的权值

    int i;

    for(i=0; i<N; i++)
    {
        scanf("%f", &T[i].weight);
    }
}

void SelectMin(HuffmanTree T, int loc, int *p1, int *p2)
{
    //在当前森林T[0...i-1]的所有结点中, 选取权最小和次小的两个根结点T[p1],T[p2]作为合并对象, 0<=p1, p2<=i-1

    int i, cnt=0;

    *p1 = 0;
    while(T[*p1].parent!=-1)
    {
        (*p1)++;
    }
    *p2 = *p1;

    //求权值最小的位置
    for(i=*p1+1; i<=loc; i++)
    {
        if(T[i].parent==-1)
        {
            *p1 = T[*p1].weight<=T[i].weight ? *p1 : i;
        }
    }

    //求权值次小的位置
    for(i=*p2+1; i<=loc; i++)
    {
        if(T[*p2].weight == T[*p1].weight)
        {
            if(++cnt>1)
            {
                break;
            }

            (*p2)++;
            while(T[*p2].parent!=-1)
            {
                (*p2)++;
                i++;
            }

            continue;
        }

        if(T[i].parent==-1)
        {
            if( T[i].weight == T[*p1].weight )
            {
                if(++cnt>1)  //最小值出现两次
                {
                    *p2 = i;
                    break;
                }

                continue;
            }

            *p2 = T[*p2].weight<=T[i].weight ? *p2 : i;
        }
    }
}

void CreateHuffmanTree(HuffmanTree T)
{
    //构造哈夫曼树, T[M-1]为其根结点
    //对森林中的树共进行N-1次合并, 所产生的新结点依次放入向量T的第i个分量中(N<=i<=M-1)

    int i, p1, p2;

    for(i=N; i<M; i++)
    {
        //在T[0...i-1]中选择两个权最小的根结点, 其序号分别为p1和p2

        SelectMin(T, i-1, &p1, &p2);

        T[p1].parent = T[p2].parent = i;
        T[i].lchild = p1;  //最小权的根结点是新结点的左孩子
        T[i].rchild = p2;  //次最小权的根结点是新结点的右孩子

        T[i].weight = T[p1].weight + T[p2].weight;
    }

    for(i=0; i<M; i++)
    {
        printf("%.2f ", T[i].weight);
    }
    putchar('\n');
}

void CharSetHuffmanEncoding(HuffmanTree T, HuffmanCode H)
{
    //根据哈夫曼树T求哈夫曼编码表H

    int c, p, i;  //c和p分别指示T中孩子和双亲的位置
    char cd[N+1];  //临时存放编码
    int start;  //指示编码在cd中的起始位置

    cd[N] = '\0';  //编码结束符

    for(i=0; i<N; i++)  //依次求叶子T[i]的编码
    {
        while( ( H[i].ch=getchar() )==' ' || H[i].ch=='\n' );//读入叶子T[i]对应的字符

        start = N;  //编码起始位置的初值
        c = i;  //从叶子T[i]开始上溯

        while((p=T[c].parent)>=0)  //直至上溯到T[c]是树根位置
        {
            //若T[c]是T[p]的左孩子, 则生成代码0; 否则生成代码1
            cd[--start] = (T[p].lchild==c) ? '0' : '1';
            c = p;
        }

        strcpy(H[i].bits, &cd[start]);  //复制编码位串
    }

    for(i=0; i<N; i++)
    {
        printf("%s ", H[i].bits);
    }

    for(i=0; i<N; i++)
    {
        printf("%c ", H[i].ch);
    }
    putchar('\n');
}

citian3094

谢谢分享！！！

逆战时代

顶。。。。。。。。。。

逆战时代

看看