| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 871 人关注过本帖
标题:赫夫曼树的创建和赫夫曼编码 麻烦大家来看看。(为什么动态空间创建失败)
取消只看楼主 加入收藏
dengluoy
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:127
专家分:165
注 册:2013-2-5
结帖率:94.44%
收藏
 问题点数:0 回复次数:0 
赫夫曼树的创建和赫夫曼编码 麻烦大家来看看。(为什么动态空间创建失败)
程序代码:
//自作赫夫曼树
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 20
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}CTNode;
typedef char ** HuffCrrent;
void select(CTNode *HT,int *h1,int *h2,int n)
{
    int i,j;
    for(i =1;i<=n;i++)
        if(!HT[i].parent)
        {
            *h1 = i;
            break;
        }
    for(j =i+1;j<=n;j++)
        if(!HT[j].parent)
        {   
            *h2 = j;
            break;
        }
    for(i =1;i<=n;i++)
        if(HT[*h1].weight > HT[i].weight && !HT[i].parent && HT[i].weight!=HT[*h2].weight)
            *h1 = i;

    for(j = 1;j<=n;j++)
        if(HT[*h2].weight > HT[j].weight && !HT[j].parent && HT[j].weight!=HT[*h1].weight)
            *h2 = j;
    if(*h1 > *h2)
    {
        int temp;
        temp = *h1;
        *h1 = *h2;
        *h2 = temp;
    }
}
void Huffman(CTNode *HT,HuffCrrent *HC,int *w,int n)
{
    int m,i,s1,s2;
    int j;
    unsigned int c;
//    CTNode *p;
    char *cd;
    if(n<1)
        return ;
    m = 2 * n-1;
    HT = (CTNode *)malloc(sizeof(CTNode ) * m +1);
    for(i =1 ;i<=n;i++)
    {
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].rchild = 0;
        HT[i].lchild = 0;
    }
    for(i = n+1;i<=m;i++)
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    printf("\n--------------------------------------------------------------");
    printf("\n赫夫曼树的构造过程如下所示:\n");
    printf("HT初态:\n");
    printf(" 节点 weight parent lchild rchild");
    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++)
    {
        select(HT,&s1,&s2,i-1);
        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",s1,s2);
        printf("\n 节点 weight parent lchild rchild");
        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);
    }
    int start = 0;
    int f =0;
    (*HC) = (char **)malloc(sizeof(char *) *n);   //创建失败
    cd = (char *)malloc(sizeof(char ) * n);   //创建失败
    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(sizeof(char));
        strcpy((*HC)[i],&cd[start]);
    }
    free(cd);
}
int main(void)
{
    CTNode *HT = NULL;
    HuffCrrent HC = NULL;
    int n,i,*w;
    printf("程序开始 、\n");
    printf("请输入节点的个数:");
    scanf("%d",&n);
    w = (int *)malloc(sizeof(int) * n);
    printf("\n请输入%d节点的权值:",n);
    for(i =0;i<n;i++)
    {
        scanf("%d",&w[i]);
    }
    Huffman(HT,&HC,w,n);
    printf("\n赫夫曼编码如下:");
    printf("\n 节点 权值 编码");
    for(i = 1;i<=n;i++)
    {
        printf("\n %2d%4d%6s",i,w[i-1],HC[i]);
    }
    puts("");
    return 0;
}
搜索更多相关主题的帖子: include parent 动态 空间 
2013-06-13 12:03
快速回复:赫夫曼树的创建和赫夫曼编码 麻烦大家来看看。(为什么动态空间创建失 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.027370 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved