haffmantree
#include <cstdio>
#include <iostream>
#include <malloc.h>
#include <cstring>
using namespace std;
#define INF 0xffffff
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode ,*HuffmanTree;
typedef char * * HuffmanCode;
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w,int n)
{
    int i,j,m,s1,s2,start;
    char *cd;
    unsigned int c,f;
    if(n<=1)return ;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    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;
    }
    int min1=INF,min2=INF;
    for(i=n+1;i<=m;++i)
    {
       for(j=1;j<=i-1;j++)
       {
           if(HT[j].parent==0&&HT[j].weight<min1)
           {
               min1=HT[j].weight;
               s1=j;
           }
       }
       for(j=1;j<=i-1;j++)
       {
           if(HT[j].parent==0&&HT[j].weight<min2&&s1!=j)
           {
               min2=HT[j].weight;
               s2=j;
           }
       }
       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;
       min1=INF;
       min2=INF;
    }
    for(i=1;i<=m;i++)
    {
        printf("%5d %5d %5d %5d\n",HT[i].weight,HT[i].lchild,HT[i].rchild,HT[i].parent);
    }
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
    cd=(char*)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(i=1;i<=n;i++)
    {
        start=n-1;
        for(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));
        strcpy(HC[i],&cd[start]);
        printf("%d 's haffmancode is :%s\n",w[i-1],HC[i]);
    }
    free(cd);
}
int main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    int w[100]={0},n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&w[i]);
    }
    HuffmanCoding(HT,HC,w,n);
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议