| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
ADSL如何秒变专线,公网IP盒子了解一下千里之行 始于足下
共有 642 人关注过本帖
标题:赫夫曼树的建立问题
只看楼主 加入收藏
liuzeyu12a
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2019-3-10
结帖率:0
  已结贴   问题点数:20  回复次数:6   
赫夫曼树的建立问题
请大佬根据我的代码把树建立以下,我根据自己代码建立的树,


然而解码的时候发现对应不上
附上代码,代码可以运行。。就是树的解码对应不上?
我这边代码运行的结果是:



无能为了了  发现自己好菜,
程序代码:
#include "stdafx.h"
#include<string.h>
#include<malloc.h>  //malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>

#define TRUE 1
#define FALSE 1
#define OK 1
#define ERROR 1
#define INFEASIBLE -1

typedef int Status;
typedef int Boolean;


/************************************************************************/
/* 最优二叉树简称:哈夫曼树                                                                     */
/************************************************************************/
//哈夫曼树结构
; typedef struct{
    unsigned int weight;          //权重
    unsigned int parent, lchild, rchild;  //树的双亲节点,和左右孩子

}HTNode, *HuffmanTree;

typedef char**  HuffmanCode;

//返回i个节点中权值最小的树的根节点的序号,供select()调用
int Min(HuffmanTree T, int i){
    int j, flag;
    unsigned int k = UINT_MAX;  //%d-->UINT_MAX = -1,%u--->非常大的数
    for (j = 1; j <= i; j++)
        if (T[j].weight <k && T[j].parent == 0)
            k = T[j].weight, flag = j;                  //
    T[flag].parent = 1;    //将parent标志为1避免二次查找

    return flag;   //返回
}

void Select(HuffmanTree T, int i, int& s1, int& s2){
    //在i个节点中选取2个权值最小的树的根节点序号,s1为序号较小的那个
    int j;
    s1 = Min(T, i);
    s2 = Min(T, i);
    if (s1 > s2){
        j = s1;
        s1 = s2;
        s2 = j;
    }
}

//HuffmanCode代表的树解码二进制值
void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n){
    //w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
    int m, i, s1, s2, start;
    unsigned c, f;
    char* cd;
    //分配存储空间
    HuffmanTree p;
    if (n <= 1)
        return;
    //n个字符(叶子节点)有2n-1个树节点,所以树节点m
    m = 2 * n - 1;
    HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode));  //0号元素未用
    //这一步是给哈夫曼树的叶子节点初始化
    for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)
    {
        (*p).weight = *w;
        (*p).lchild = 0;
        (*p).rchild = 0;
        (*p).parent = 0;
    }
    //这一步是给哈夫曼树的非叶子节点初始化
    for (; i <= m; ++i, ++p){
        (*p).parent = 0;
    }
    /************************************************************************/
    /* 做完准备工作后 ,开始建立哈夫曼树
    /************************************************************************/
    for (i = n + 1; i <= m; i++)
    {
        //在HT[1~i-1]中选择parent=0且weigh最小的节点,其序号分别为s1,s2
        Select(HT, i - 1, s1, s2);  //传引用
        HT[s1].parent = HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    /************************************************************************/
    /* 从叶子到根逆求每个叶子节点的哈夫曼编码                                          */
    /************************************************************************/
    //分配n个字符编码的头指针向量,([0]不用)
    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));  //生成一个块内存存储字符
        //为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]);  //从cd赋值字符串到cd
    }
    free(cd);  //释放资源
}

//函数声明
int Min(HuffmanTree T, int i); //求i个节点中的最小权重的序列号,并返回
void Select(HuffmanTree T, int i, int& s1, int& s2); //从两个最小权重中选取最小的(左边)给s1,右边的给s2
void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n);//哈夫曼编码与解码

int main(){

    HuffmanTree HT;
    HuffmanCode HC;

    int *w, n, i;
    printf("请输入权值的个数(>1):");
    scanf_s("%d", &n);

    w = (int*)malloc(n*sizeof(int));
    printf("请依次输入%d个权值(整形):\n", n);

    for (i = 0; i <= n - 1; i++)
    {
        scanf_s("%d", w + i);
    }
    HuffmanCoding(HT, HC, w, n);

    for (i = 1; i <= n; i++)
    {
        puts(HC[i]);
    }
    return 0;
}




[此贴子已经被作者于2019-3-12 17:19编辑过]

附件: 您没有浏览附件的权限,请 登录注册
搜索更多相关主题的帖子: include int 哈夫曼 parent 节点 
2019-03-10 11:58
liuzeyu12a
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2019-3-10
  得分:0 
没大佬会的吗
2019-03-10 13:18
林月儿
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:湖南
等 级:版主
威 望:132
帖 子:1919
专家分:8443
注 册:2015-3-19
  得分:10 
什么对不上

知命以下无敌
2019-03-10 13:25
liuzeyu12a
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2019-3-10
  得分:0 
回复 3楼 林月儿
比如说的我程序上面的叶子节点5 ,对应的解码是0001  ,而我画的树叶子节点对应的解码是0001,我画的树也是按照代码的思路画出来的,想不通为什么就是对应不上
2019-03-10 21:13
俺是你大爷
Rank: 2
等 级:论坛游民
帖 子:57
专家分:35
注 册:2019-3-12
  得分:10 
你实在CSDN上发的麽,C币...
2019-03-12 13:13
liuzeyu12a
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2019-3-10
  得分:0 
对啊  直接copy过来的
2019-03-12 17:17
快速回复:赫夫曼树的建立问题
数据加载中...
 
   



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

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