C语言实现输入超过10字符的字符串后再输入这些字符的频度,输出这些字符的哈夫曼编码
时间: 2023-06-19 10:05:44 浏览: 209
要实现输入超过10字符的字符串后再输入这些字符的频度,可以使用一个字符数组来存储输入的字符串,然后使用一个整型数组来记录每个字符出现的频度。具体实现可以参考下面的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100 // 字符串最大长度
// 哈夫曼树节点
typedef struct node {
char ch; // 字符
int freq; // 频度
struct node *left; // 左子节点
struct node *right; // 右子节点
} Node;
// 哈夫曼编码表项
typedef struct {
char ch; // 字符
char *code; // 编码
} CodeTableItem;
// 创建哈夫曼树
Node *createHuffmanTree(Node *nodes[], int count) {
while (count > 1) {
// 找到频度最小的两个节点
int min1 = 0, min2 = 1;
if (nodes[min1]->freq > nodes[min2]->freq) {
min1 = 1;
min2 = 0;
}
for (int i = 2; i < count; i++) {
if (nodes[i]->freq < nodes[min1]->freq) {
min2 = min1;
min1 = i;
} else if (nodes[i]->freq < nodes[min2]->freq) {
min2 = i;
}
}
// 合并两个节点
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->ch = '\0';
newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
nodes[min1] = newNode;
nodes[min2] = nodes[count - 1];
count--;
}
return nodes[0];
}
// 生成哈夫曼编码表
void createCodeTable(Node *root, char *prefix, int depth, CodeTableItem *codeTable, int *count) {
if (root->left == NULL && root->right == NULL) {
// 叶子节点,添加编码表项
CodeTableItem item;
item.ch = root->ch;
item.code = (char *) malloc((depth + 1) * sizeof(char));
strncpy(item.code, prefix, depth);
item.code[depth] = '\0';
codeTable[*count] = item;
(*count)++;
} else {
// 非叶子节点,继续递归
prefix[depth] = '0';
createCodeTable(root->left, prefix, depth + 1, codeTable, count);
prefix[depth] = '1';
createCodeTable(root->right, prefix, depth + 1, codeTable, count);
}
}
// 查找字符的哈夫曼编码
char *findCode(CodeTableItem *codeTable, int count, char ch) {
for (int i = 0; i < count; i++) {
if (codeTable[i].ch == ch) {
return codeTable[i].code;
}
}
return NULL;
}
int main() {
char str[MAX_LEN + 1]; // 输入的字符串
int freq[256] = {0}; // 每个字符出现的频度
int len = 0; // 字符串长度
while (1) {
printf("请输入一个字符串:");
fgets(str + len, MAX_LEN - len + 1, stdin); // 读取剩余的字符
len = strlen(str);
if (str[len - 1] == '\n') {
str[len - 1] = '\0'; // 去掉换行符
len--;
}
if (len >= MAX_LEN) {
break; // 字符串已达到最大长度,退出循环
}
}
for (int i = 0; i < len; i++) {
freq[(unsigned char) str[i]]++; // 统计频度
}
// 创建哈夫曼树
Node *nodes[256];
int nodeCount = 0;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
Node *node = (Node *) malloc(sizeof(Node));
node->ch = (char) i;
node->freq = freq[i];
node->left = NULL;
node->right = NULL;
nodes[nodeCount] = node;
nodeCount++;
}
}
Node *root = createHuffmanTree(nodes, nodeCount);
// 生成哈夫曼编码表
CodeTableItem codeTable[256];
int codeCount = 0;
char prefix[256] = "";
createCodeTable(root, prefix, 0, codeTable, &codeCount);
// 输出编码表和编码后的字符串
printf("编码表:\n");
for (int i = 0; i < codeCount; i++) {
printf("%c: %s\n", codeTable[i].ch, codeTable[i].code);
}
printf("编码后的字符串:\n");
for (int i = 0; i < len; i++) {
char *code = findCode(codeTable, codeCount, str[i]);
printf("%s", code);
}
printf("\n");
// 释放内存
for (int i = 0; i < nodeCount; i++) {
free(nodes[i]);
}
for (int i = 0; i < codeCount; i++) {
free(codeTable[i].code);
}
return 0;
}
```
上述代码中,我们使用字符数组 `str` 来存储输入的字符串,使用整型数组 `freq` 来记录每个字符出现的频度。当输入的字符串长度超过10时,程序会停止读取输入,并统计每个字符的频度。然后,我们根据频度创建哈夫曼树,再根据哈夫曼树生成哈夫曼编码表,最后使用哈夫曼编码表对输入字符串进行编码,并输出编码后的字符串和哈夫曼编码表。
需要注意的是,由于 C 语言中没有字符串类型,因此我们要使用字符数组来存储字符串,并使用字符串操作函数来处理字符数组。此外,由于字符数组中可能包含任意字符,因此我们需要使用无符号字符类型 `unsigned char` 来表示字符,以保证程序的正确性。
阅读全文