ZBLOG

注册 原创投稿

函数SelectTwoMin(int upbound, HuffmanTree HT, int &s1, int &s2)是从1到upbound中找出father为0的节点赋给s1,s2,（为了保证答案唯一，请让s1的节点编号小于s2），函数HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)是构造哈夫曼树以及计算哈夫曼编码。保证输入的权重值小于1000。 函数接口定义： void Sele

作者：golang云原生栏目：公开2023-11-12 03:08823

根据题目要求，我们需要实现两个函数SelectTwoMin和HuffmanCoding。下面是完整的代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int weight;
    int parent;
    int lchild;
    int rchild;
} HTNode, *HuffmanTree;

typedef char ** HuffmanCode;

void SelectTwoMin(int upbound, HuffmanTree HT, int &s1, int &s2) {
    // 初始化s1和s2为最大值
    s1 = s2 = upbound;
    
    for (int i = 1; i <= upbound; ++i) {
        if (HT[i].parent == 0) { // 找到father为0的节点
            if (i < s1) {
                s2 = s1;
                s1 = i;
            } else if (i < s2) {
                s2 = i;
            }
        }
    }
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
    if (n <= 1)
        return;

    int m = 2 * n - 1; // 哈夫曼树总节点数
    
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); // 分配内存空间

    for (int i = 1; i <= n; ++i) { // 初始化叶子节点
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }

    for (int i = n + 1; i <= m; ++i) { // 初始化非叶子节点
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }

    for (int i = n + 1; i <= m; ++i) { // 构建哈夫曼树
        int s1, s2;
        SelectTwoMin(i - 1, HT, 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;
    }

    HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); // 分配内存空间

    char *code = (char *)malloc(n * sizeof(char));
    
    code[n - 1] = '\0'; // 哈夫曼编码结束符
    
    for (int i = 1; i <= n; ++i) {
        int start = n - 1;

        int c, f;
        
        for (c = i, f=HT[i].parent; f != 0; c=f, f=HT[f].parent) {
            if (HT[f].lchild == c)
                code[--start] ='0';
            else
                code[--start] ='1';
       }
       
       HC[i] =(char *)malloc((n-start)*sizeof(char));
       strcpy(HC[i], &code[start]);
   }
   
   free(code);
}

int main() {
    HuffmanTree ht;
    HuffmanCode hc;

    int n;
    scanf("%d", &n);
    
    int *w = (int *) malloc (n * sizeof(int));
    
    for(int i = 0; i < n; ++i)
        scanf("%d", &w[i]);

    HuffmanCoding(ht, hc, w, n);
    
    for (int i = 1; i <= 2 * n - 1; ++i) {
        printf("%d %d %d %d\n",
               ht[i].weight, ht[i].parent, ht[i].lchild, ht[i].rchild);
    }

    for (int i = 1; i <= n; ++i)
        printf("%s\n", hc[i]);

    free(w);
    free(ht);
    
   for (int i = 1; i <= n; ++i)
       free(hc[i]);
  
   return 0;
}

注意：在上述代码中，我们使用了动态内存分配来创建哈夫曼树和哈夫曼编码的数据结构，所以在程序结束时要记得释放相应的内存空间。


内容由零声教学AI助手提供，问题来源于学员提问

本站部分文章来源于网络，版权归原作者所有，如有侵权请联系站长删除。
转载请注明出处：https://golang.0voice.com/?id=10182

golang云原生 golang云原生 管理员
分享：
扫描分享到社交APP
上一篇
下一篇

相关推荐

发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论，快来说点什么吧~

golang云原生

golang云原生

  • 24377文章
  • 0评论
  • 2粉丝
  • 0被赞
最近发布
热门排行
热评文章
猜您喜欢
热门标签
Copyright ©2022    湖南零声信息科技有限公司    版权所有     湘ICP备18009867号-1          证照中心 

联系我们

在线咨询： 点击这里给我发消息

微信号：3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号？
简单注册快人一步