讨论/算法和数据结构/哈夫曼树的建立问题/
哈夫曼树的建立问题

最近在学习哈夫曼树,自己写了一段哈夫曼树的建立代码,输出的结果和预期的不相符,找了好久都没找到问题
建立代码;

 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

除了斜体加粗部分(*** 5 8***)的位置相反了其余的均相同,那个大神来解释一下问题出在哪???

展开讨论
一码当先发起于 2020-05-11

左右儿子互换不影响最终正确性吧