spy 发表于 2015-3-27 18:13:40

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

#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;//HuffmanTree是向量类型

typedef struct
{
    char ch;//存储字符
    char bits;//存放编码位串
}CodeNode;

typedef CodeNode HuffmanCode;

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中2N-1个结点里的三个指针均置为空(即置为-1), 权值置为0

    int i;

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

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

    int i;

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

void SelectMin(HuffmanTree T, int loc, int *p1, int *p2)
{
    //在当前森林T的所有结点中, 选取权最小和次小的两个根结点T,T作为合并对象, 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.parent==-1)
      {
            *p1 = T[*p1].weight<=T.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.parent==-1)
      {
            if( T.weight == T[*p1].weight )
            {
                if(++cnt>1)//最小值出现两次
                {
                  *p2 = i;
                  break;
                }

                continue;
            }

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

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

    int i, p1, p2;

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

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

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

      T.weight = T.weight + T.weight;
    }

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

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

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

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

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

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

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

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

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

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

citian3094 发表于 2015-5-19 18:35:43

谢谢分享！！！

逆战时代 发表于 2015-5-21 20:06:56

顶。。。。。。。。。。

逆战时代 发表于 2015-5-22 10:21:08

看看
页: [1]
查看完整版本: 简单的huffman树的实现，就差解码部分，真心不好写