标题:哈夫曼编码遇到权值相同的结点怎么办
取消只看楼主
EMMMM
Rank: 1
等 级:新手上路
帖 子:32
专家分:0
注 册:2017-9-16
结帖率:75%
已结贴  问题点数:14 回复次数:0 
哈夫曼编码遇到权值相同的结点怎么办
我写的哈夫曼编码遇到权值相同的结点,其中会有一个随机的结点不输出他的编码(直接输出一个空行),这是为什么?要怎么解决呢?
代码:
#include<stdio.h>
#include<stdlib.h>
#define MAX 500

typedef struct List{
    char c;
int d;
char t[10];
}List;

List L[500];

typedef struct BTree{
    int data;
struct BTree* left;
struct BTree* right;
}BTree;

BTree* CreateBTree(int n) {
    int i, j;
    BTree **b, *q = NULL;
    b = (BTree**)malloc(n * sizeof(BTree));
    for (i = 0; i<n; i++) {//初始化b
        b[i] = (BTree*)malloc(sizeof(BTree));
        b[i]->data = L[i].d;
        b[i]->left = b[i]->right = NULL;
    }
    for (i = 1; i<n; i++) {//建立哈夫曼树
        int k1 = -1, k2 = 0;//k1表示最小权值结点下标,k2为次最小的下标
        for (j = 0; j<n; j++) {//k1初指向第一棵,k2指向第二棵
            if (b[j] != NULL&&k1 == -1) {
                k1 = j;
                continue;
            }
            if (b[j] != NULL) {
                k2 = j;
                break;
            }
        }
        for (j = k2; j<n; j++) {//从森林中求出最小权值树和次最小
            if (b[j] != NULL) {
                if (b[j]->data<b[k1]->data) {
                    k2 = k1;
                    k1 = j;
                }
                else if(b[j]->data<b[k2]->data)
                    k2 = j;
            }
        }
        q = (BTree*)malloc(sizeof(BTree));
        q->data = b[k1]->data + b[k2]->data;
        q->left = b[k1];
        q->right = b[k2];
        b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置
        b[k2] = NULL;
    }
    free(b);//删除动态建立的数组b
    return q;
}

void HuffMan(BTree* FBT, int len, int n) {//len初始值为0
    static char a[10];//保存每个叶子的编码
    if (FBT != NULL) {
        if (FBT->left == NULL&&FBT->right == NULL) {
            int i;
            for (i = 0; i<n; i++)
                if (FBT->data == L[i].d)
                    break;
            for (int j = 0; j<len; j++)
                L[i].t[j] = a[j];
        }
        else {//向左右子树递归调用,并把编码保存到数组中
            a[len] = '0';
            HuffMan(FBT->left, len + 1, n);
            a[len] = '1';
            HuffMan(FBT->right, len + 1, n);
        }
    }
}

int main() {
    int n;
    BTree* Huf;
    printf("输入结点个数:\n");
    scanf("%d", &n);
    getchar();
    for (int i = 0; i<n; i++) {
        printf("");
        printf("输入结点以及其频率,中间以逗号隔开,例如:c,3\n");
        scanf("%c,%d", &L[i].c, &L[i].d);
        getchar();
    }
    Huf = CreateBTree(n);
    HuffMan(Huf, 0, n);
    for (int i = 0; i<n; i++)
    {
        printf("本行结果为频度:%d\n",L[i].d);
        printf("本行结果为字符:%c\n",L[i].c);
        printf("本行结果为编码:%s\n",L[i].t);
    }
    return 0;
}
搜索更多相关主题的帖子: 结点 int data NULL for 
2018-07-06 09:47



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-488415-1-1.html




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

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