哈弗曼树的建立

  • Z时代
  • 2024-01-10
  • 分类：IT

建立代码；

static int s1, s2;
typedef struct {
    unsigned int weight; //结点的权值
    unsigned int parent; //结点的亲
    unsigned int lchild; //左孩子
    unsigned int rchild; //右孩子
    char data;  //数据
} HTnode, *Huffmantree;
typedef char **Huffmancode;

/*
 TODO: 查询两个权值最小的节点，赋值给s1，s2
 功能描述：在ht[1]~ht[n]的范围内选择两个parent为0且weight最小的结点，其序号赋值给s1，s2
 参数说明：ht-Huffmantree型树
       n-int型 表示节点数
 返回值说明：无
 */
void selectMin(Huffmantree ht, int n)
{
    int min = 0, i;
    // 选最小；
    for (i = 0; i < n; i++)
    {
        if ((ht + i)->parent == 0)
        {
            min = i;
            break;
        }
    }
    for (i = 0; i < n; i++)
    {
        if ((ht + i)->parent == 0)
            if ((ht + i)->weight < (ht + min)->weight)
                min = i;
    }
    s1 = min;
    //选次小
    for (i = 0; i < n; i++)
    {
        if ((ht + i)->parent == 0 && i != s1)
        {
            min = i;
            break;
        }
    }
    for (i = 0; i < n; i++)
    {
        if ((ht + i)->parent == 0 && i != s1)
            if ((ht + i)->weight < (ht + min)->weight)
                min = i;
    }
    s2 = min;
}

/*
 TODO: 建立哈弗曼树。
 功能描述：根据键盘输入创建哈弗曼树，期间调用selectMin函数实现，给生成的父结点的data赋值为减号-，打印输出用以下格式。
       printf("%c%4d%4d%4d%4d\n", ht[i].data,ht[i].weight, ht[i].parent, ht[i].lchild,ht[i].rchild);
 参数说明：ht-Huffmantree型树
       n-int型 表示节点数
       w-int型指针 表示权值
       d-char型指针 表示节点数据
 返回值说明：Huffmantree型树
 */
Huffmantree createHuffmanTree(Huffmantree ht, int *w, int n, char *d) {
    int i, m;
    // 申请空间；
    m = 2 * n-1;
    ht = (Huffmantree)malloc(sizeof(HTnode)*m+1); // 从i=1开始写入；
    //对n个结点进行初始化 ;
    for (i = 1 ; i < n+1 ; i++)
    {
        (ht + i)->data = d[i-1];
        (ht + i)->weight = w[i-1]; 
        (ht + i)->lchild = 0;
        (ht + i)->rchild = 0;
        (ht + i)->parent = 0;
    }
    // 对剩余的结点初始化
    for (i = n+1; i < m+1; i++)
    {
        (ht + i)->weight = 0;
        (ht + i)->lchild = 0;
        (ht + i)->rchild = 0;
        (ht + i)->parent = 0;
    }
    //添加结点；
    for (i = n+1; i < m+1; i++)
    {
        selectMin(ht, i);
        (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;  //权重相加；
        (ht + i)->data = '-';
    }
    for(i=1;i<m+1;i++)
        printf("%c%4d%4d%4d%4d\n", ht[i].data, ht[i].weight , ht[i].parent, ht[i].lchild, ht[i].rchild);
    return ht;
}

函数的调用：

Huffmantree ht = NULL;   //输入一个哈夫曼树型指针；
    Huffmancode hc = NULL;   //字符指针；
    int *w = NULL;
    char *d = NULL;
    int i;
    int n;
    printf("请输入节点数\n");
            scanf_s("%d", &n);  //申请空间；
            w = (int *)malloc(n * sizeof(int));
            d = (char*)malloc(n * sizeof(char));
            printf("请输入节点的权值以及字符，先输入权值后输入字符并且两者之间无空格\n");
            for (i = 0; i < n; i++) {
                scanf_s("%d%c", &w[i], &d[i]);
            }
            printf("输出哈夫曼树的存储结构\n");
            ht = createHuffmanTree(ht, w, n, d);
        printf("哈弗曼编码已建立！\n");

实际输出
QQ图片20200511151455.png
标准答案：
A 2 8 0 0
B 3 8 0 0
C 4 9 0 0
D 5 9 0 0
E 6 10 0 0
F 7 11 0 0
G 8 11 0 0

  • 5 10 1 2

  • 9 12 3 4

  • 11 12 5 8

  • 15 13 6 7

  • 20 13 9 10

  • 35 0 11 12

除了斜体加粗部分其余的均相同，那个大神来解释一下问题出在哪？？？

回答：

今天查看了一下所有的用例发现对所有选择出的s1 和s2 进行比较 s1始终为最小值就能得出想要的果
添加代码：

int tem=0;
if(s1>s2)
{
   tem =s1;
   s1=s2;
   s2=tem;
}

操作令人迷惑，这样还是构建的哈夫曼树有什么好处啊，感觉只是将左孩子位接 序号小的 右孩子接序号大的；？？？

以上是 哈弗曼树的建立 的全部内容， 来源链接： utcz.com/p/194265.html

回到顶部