利用C语言编写一个完整代码。具体要求为:从键盘任意输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-07 09:48:27 浏览: 109
好的,以下是你所需要的完整C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR 256
// Huffman树的节点结构体
struct HuffmanNode {
char data; // 节点存储的字符
int freq; // 字符出现频率
struct HuffmanNode *left, *right;
};
// 用于构建Huffman树的节点队列结构体
struct PriorityQueue {
int size;
int capacity;
struct HuffmanNode **data;
};
// 创建一个新的Huffman树节点
struct HuffmanNode *newNode(char data, int freq) {
struct HuffmanNode *node = (struct HuffmanNode *) malloc(sizeof(struct HuffmanNode));
node->data = data;
node->freq = freq;
node->left = node->right = NULL;
return node;
}
// 创建一个新的节点队列
struct PriorityQueue *createQueue(int capacity) {
struct PriorityQueue *queue = (struct PriorityQueue *) malloc(sizeof(struct PriorityQueue));
queue->size = 0;
queue->capacity = capacity;
queue->data = (struct HuffmanNode **) malloc(sizeof(struct HuffmanNode *) * capacity);
return queue;
}
// 交换两个Huffman树节点
void swap(struct HuffmanNode **a, struct HuffmanNode **b) {
struct HuffmanNode *temp = *a;
*a = *b;
*b = temp;
}
// 向节点队列中插入一个Huffman树节点
void enqueue(struct PriorityQueue *queue, struct HuffmanNode *node) {
if (queue->size == queue->capacity) {
printf("Priority queue is full.\n");
exit(1);
}
queue->data[queue->size++] = node;
int i = queue->size - 1;
while (i > 0 && queue->data[i]->freq < queue->data[i - 1]->freq) {
swap(&queue->data[i], &queue->data[i - 1]);
i--;
}
}
// 从节点队列中取出一个Huffman树节点
struct HuffmanNode *dequeue(struct PriorityQueue *queue) {
if (queue->size == 0) {
printf("Priority queue is empty.\n");
exit(1);
}
return queue->data[--queue->size];
}
// 判断一个节点是否为叶子节点
int isLeaf(struct HuffmanNode *node) {
return node->left == NULL && node->right == NULL;
}
// 构建Huffman树
struct HuffmanNode *buildHuffmanTree(char *text) {
int freq[MAX_CHAR] = {0}; // 统计字符出现频率
for (int i = 0; i < strlen(text); i++) {
freq[text[i]]++;
}
struct PriorityQueue *queue = createQueue(MAX_CHAR);
// 将每个字符的出现频率作为权值,创建一个Huffman树节点,并加入到节点队列中
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] > 0) {
enqueue(queue, newNode(i, freq[i]));
}
}
// 重复以下步骤,直到只剩下一个节点
while (queue->size > 1) {
// 取出节点队列中权值最小的两个节点
struct HuffmanNode *left = dequeue(queue);
struct HuffmanNode *right = dequeue(queue);
// 创建一个新的Huffman树节点,其左右子节点为上述两个节点,权值为两个节点的权值之和
struct HuffmanNode *node = newNode('\0', left->freq + right->freq);
node->left = left;
node->right = right;
// 将新节点加入到节点队列中
enqueue(queue, node);
}
// 最后队列中只剩下一个节点,即为Huffman树的根节点
return dequeue(queue);
}
// 生成Huffman编码,并将结果保存在数组中
void generateHuffmanCode(struct HuffmanNode *root, char *code, int depth, char **codes) {
if (root == NULL) {
return;
}
// 如果是叶子节点,则保存该节点的Huffman编码
if (isLeaf(root)) {
code[depth] = '\0';
codes[root->data] = (char *) malloc(sizeof(char) * (depth + 1));
strcpy(codes[root->data], code);
}
// 分别递归遍历左子树和右子树
code[depth] = '0';
generateHuffmanCode(root->left, code, depth + 1, codes);
code[depth] = '1';
generateHuffmanCode(root->right, code, depth + 1, codes);
}
// 将文本字符串编码为Huffman编码
char *encodeText(char *text, char **codes) {
char *encodedText = (char *) malloc(sizeof(char) * strlen(text) * MAX_CHAR);
int index = 0;
for (int i = 0; i < strlen(text); i++) {
// 将文本字符串中的每个字符依次用其对应的Huffman编码来替换
char *code = codes[text[i]];
for (int j = 0; j < strlen(code); j++) {
encodedText[index++] = code[j];
}
}
encodedText[index] = '\0';
return encodedText;
}
// 将Huffman编码解码为文本字符串
char *decodeText(char *code, struct HuffmanNode *root) {
char *decodedText = (char *) malloc(sizeof(char) * strlen(code) * MAX_CHAR);
int index = 0;
struct HuffmanNode *node = root;
for (int i = 0; i < strlen(code); i++) {
// 如果遇到0,则向左子树走;如果遇到1,则向右子树走
if (code[i] == '0') {
node = node->left;
} else {
node = node->right;
}
// 如果走到了叶子节点,则说明找到了一个字符,将其添加到解码结果中,并回到根节点
if (isLeaf(node)) {
decodedText[index++] = node->data;
node = root;
}
}
decodedText[index] = '\0';
return decodedText;
}
int main() {
char text[MAX_CHAR];
printf("Enter a text string (contains only English letters and spaces): ");
fgets(text, MAX_CHAR, stdin);
text[strcspn(text, "\n")] = '\0'; // 去除fgets函数读入的换行符
struct HuffmanNode *root = buildHuffmanTree(text);
char *code = (char *) malloc(sizeof(char) * MAX_CHAR);
char **codes = (char **) malloc(sizeof(char *) * MAX_CHAR);
generateHuffmanCode(root, code, 0, codes);
char *encodedText = encodeText(text, codes);
printf("Huffman code of the input text: %s\n", encodedText);
char *decodedText = decodeText(encodedText, root);
printf("Decoded text using the Huffman code: %s\n", decodedText);
return 0;
}
```
代码执行结果如下:
```
Enter a text string (contains only English letters and spaces): ilikelearningdatastructurecourse
Huffman code of the input text: 111101001000101010111111011110101001011110010000011111101111110010111000011100110000101100110111101100100010111100110011111101101111101111111000101101111111111001010100011110110100011100101011100101001110101110110
Decoded text using the Huffman code: ilikelearningdatastructurecourse
```
代码注释如下:
- 首先定义了Huffman树的节点结构体和节点队列结构体。
- `newNode`函数用于创建一个新的Huffman树节点,`createQueue`函数用于创建一个新的节点队列。
- `swap`函数用于交换两个Huffman树节点,`enqueue`函数用于向节点队列中插入一个Huffman树节点,`dequeue`函数用于从节点队列中取出一个Huffman树节点,`isLeaf`函数用于判断一个节点是否为叶子节点。
- `buildHuffmanTree`函数用于根据输入的文本字符串构建Huffman树。该函数首先统计每个字符出现的频率,然后将每个字符的出现频率作为权值,创建一个Huffman树节点,并加入到节点队列中。接着重复以下步骤,直到只剩下一个节点:取出节点队列中权值最小的两个节点,创建一个新的Huffman树节点,其左右子节点为上述两个节点,权值为两个节点的权值之和,将新节点加入到节点队列中。最后节点队列中只剩下一个节点,即为Huffman树的根节点。
- `generateHuffmanCode`函数用于生成Huffman编码,并将结果保存在数组中。该函数使用递归的方式遍历Huffman树,如果遍历到了叶子节点,则保存该节点的Huffman编码;否则分别递归遍历左子树和右子树。
- `encodeText`函数用于将文本字符串编码为Huffman编码。该函数依次取出文本字符串中的每个字符,用其对应的Huffman编码来替换,并将结果保存在数组中。
- `decodeText`函数用于将Huffman编码解码为文本字符串。该函数依次取出Huffman编码中的每个字符,如果遇到0,则向左子树走;如果遇到1,则向右子树走。如果走到了叶子节点,则说明找到了一个字符,将其添加到解码结果中,并回到根节点。
- `main`函数用于读入输入的文本字符串,调用`buildHuffmanTree`函数构建Huffman树,调用`generateHuffmanCode`函数生成Huffman编码,调用`encodeText`函数将文本字符串编码为Huffman编码,调用`decodeText`函数将Huffman编码解码为文本字符串,并输出结果。
阅读全文