C语言报文哈夫曼编码系统_请自行设计一段报文,统计报文中字母种类数

前言

无套路，均已上机通过，求个关注求个赞，提供答疑解惑服务。

功能

请自行设计一段报文，长度不少于 30（例如 ABAACEGZBBZ…），统计报文中字母种类数（不少于 8类）和各类字母出现的次数（频率，每个字母频率尽量不相同），设计最经济的编码方案使得报文传输时间最短，并计算报文使用该编码方案后的优化率。

运行截图

所有代码

//
// Created by Administrator on 2023/12/26.
//

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

typedef struct HuffmanTreeNode {
    char data;
    int repeatCount;
    struct HuffmanTreeNode *lNode;
    struct HuffmanTreeNode *rNode;
} HuffmanTreeNode, *HuffmanTree;

/**
 * 插入排序
 * @param forest
 * @param size
 */
static void sort(HuffmanTreeNode *forest[], int size) {
    for (int unOrderListIterator = 2; unOrderListIterator <= size; ++unOrderListIterator) {
        HuffmanTreeNode *sortedData = forest[unOrderListIterator - 1];
        if (sortedData == NULL) {
            continue;
        }
        int orderListIterator;
        for (orderListIterator = unOrderListIterator - 1; orderListIterator >= 1 && (forest[orderListIterator - 1] == NULL || sortedData->repeatCount < forest[orderListIterator - 1]->repeatCount); --orderListIterator) {
            forest[orderListIterator + 1 - 1] = forest[orderListIterator - 1];
        }
        forest[orderListIterator + 1 - 1] = sortedData;
    }
}

/**
 * 构造哈夫曼树
 * @param count 数据列表
 * @param repeatCountList 权值列表
 * @param size 大小
 * @param reCompare 权值逆序比较
 * @param weightSum 权值相加
 * @return
 */
HuffmanTree huffmanTreeNodeConstructor(int count[], int size) {
    HuffmanTreeNode *forest[size];
    int treeCount = 0;
    for (int i = 0; i < 256; ++i) {
        if (count[i] != 0) {
            HuffmanTreeNode *node = (HuffmanTreeNode *) malloc(sizeof(HuffmanTreeNode));
            node->data = (char) i;
            node->repeatCount = count[i];
            node->lNode = NULL;
            node->rNode = NULL;
            forest[treeCount++] = node;
        }
    }
    sort(forest, size);
    for (; treeCount != 1;) {
        HuffmanTreeNode *node = (HuffmanTreeNode *) malloc(sizeof(HuffmanTreeNode));
        node->lNode = forest[0];
        forest[0] = NULL;
        treeCount--;
        node->rNode = forest[1];
        forest[1] = NULL;
        treeCount--;
        node->data = ' ';
        node->repeatCount = node->lNode->repeatCount + node->rNode->repeatCount;
        forest[0] = node;
        treeCount++;
        sort(forest, size);
    }
    return forest[0];
}

/**
 * 是否是叶子结点
 * @param node
 * @return
 */
static int isLeafNode(HuffmanTreeNode *node) {
    return node->lNode == NULL && node->rNode == NULL;
}

/**
 * 哈夫曼编码
 * @param tree
 * @param target
 * @param compare
 * @return
 */
char *huffmanCoding(HuffmanTree tree, char target) {
    if (tree != NULL) {
        char *lr = huffmanCoding(tree->lNode, target);
        char *rr = huffmanCoding(tree->rNode, target);
        if (lr != NULL) {
            char *code = (char *) calloc(strlen(lr) + 2, sizeof(char));
            strcat(code, "0");
            strcat(code, lr);
            return code;
        } else if (rr != NULL) {
            char *code = (char *) calloc(strlen(rr) + 2, sizeof(char));
            strcat(code, "1");
            strcat(code, rr);
            return code;
        } else if (tree->lNode != NULL && isLeafNode(tree->lNode) && tree->lNode->data == target) {
            return "0";
        } else if (tree->rNode != NULL && isLeafNode(tree->rNode) && tree->rNode->data == target) {
            return "1";
        } else {
            return NULL;
        }
    } else {
        return NULL;
    }
}

/**
 * 统计重复字符的个数
 * @param str
 * @param count
 */
int countChars(char *str, int count[]) {
    int len = strlen(str);
    int total = 0;
    for (int i = 0; i < len; i++) {
        if (count[str[i]] == 0) {
            total++;
        }
        count[str[i]]++;
    }
    return total;
}

int main() {
    while (1) {
        char *str = (char *) calloc(100, sizeof(char));
        printf("请输入报文：");
        scanf("%s", str);
        int count[256] = {0};
        int total = countChars(str, count);
        HuffmanTree tree = huffmanTreeNodeConstructor(count, total);
        for (int i = 0; i < 256; ++i) {
            if (count[i] != 0) {
                printf("字符%c的哈夫曼编码为：%s\n", (char) i, huffmanCoding(tree, (char) i));
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149