赫夫曼树和赫夫曼编码

用C语言实现赫夫曼树的建立及赫夫曼编码的求解
代码如下:
#include<stdio.h>  
#include<malloc.h>
#include<string.h>
int m,s1,s2;
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树
typedef char *HuffmanCode; //动态分配数组存储赫夫曼编码表
void Select(HuffmanTree HT,int n)
{
    int i,j,temp;
    for(i = 1;i <= n;i++)
    if(!HT[i].parent){s1 = i;break;}
    for(j = i+1;j <= n;j++)
    if(!HT[j].parent){s2 = j;break;}
    for(i = 1;i <= n;i++)
    if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
    for(j = 1;j <= n;j++)
    if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
    if(s1>s2)
    {
        temp=s1;
        s1=s2;
        s2=temp;
    }
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n)
{                                                         // w存放n个字符的权值(均>0),构造赫夫曼树HT,
    int i, j;                                             // 并求出n个字符的赫夫曼编码HC
    char *cd;
    if (n<=1) return;
    m = 2 * n - 1;
    HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
    for (i=1; i<=n; i++)//初始化
    {
    HT[i].weight=w[i-1];
    HT[i].parent=0;
    HT[i].lchild=0;
    HT[i].rchild=0;
    }
    for (i=n+1; i<=m; i++) //初始化
    {
        HT[i].weight=0;
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    puts("\n赫夫曼树的构造过程如下所示:");
    printf("HT初态:\n 结点\tweight\tparent\tlchild\trchild");
    for (i=1; i<=m; i++)
    printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild);
    for (i=n+1; i<=m; i++)   // 建赫夫曼树
    {                        // 在HT[1..i-1]中选择parent为0且weight最小的两个结点,
        Select(HT, i-1);     // 其序号分别为s1和s2。
        HT[s1].parent = i; HT[s2].parent = i;
        HT[i].lchild = s1; HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        printf("\nselect: s1=%d s2=%d\n", s1, s2);
        printf(" 结点\tweight\tparent\tlchild\trchild");
        for (j=1; j<=i; j++)
        printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
    }
    //-----------从叶子到根逆向求每个字符的赫夫曼编码 ------
    cd = (char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(i=1;i<=n;i++)
    {
        int start=n-1;
        for(unsigned int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向的逆向过程
        {  
            if(HT[f].lchild==c) cd[--start]='0';
            else cd[--start]='1';
        }
        HC[i] = (char * )malloc((n-start)*sizeof(char));
        for(int j=start;j<=n;j++)   HC[i][j-start]=cd[j];
    }
    free(cd);
} // HuffmanCoding
void main()
{
    HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
    puts("请输入结点数:");
    scanf("%d",&n);
    HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
    w = (int *)malloc(n*sizeof(int));
    printf("请输入%d个结点的权值\n",n);
    for(i = 0;i < n;i++)
    scanf("%d",&w[i]);
    HuffmanCoding(HT,HC,w,n);
    puts("\n各结点的赫夫曼编码为:");
    for(i = 1;i <= n;i++)
    printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
}



[本日志由 somarange 于 2007-11-21 05:01 PM 编辑]
文章来自: 本站原创
引用通告: 查看所有引用 | 我要引用此文章
Tags: 数据结构 C语言
相关日志:
评论: 0 | 引用: 0 | 查看次数: -
发表评论
昵 称:
密 码: 游客发言不需要密码.
内 容:
验证码: 验证码
选 项:
虽然发表评论不用注册,但是为了保护您的发言权,建议您注册帐号.