前言
无套路，均已上机通过，求个关注求个赞，提供答疑解惑服务。
功能
请自行设计一段报文，长度不少于 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;
}
