C语言统计一句话中各个字母的个数,将各字母作为节点,各字母出现的次数作为权值,构建哈夫曼树,并打印各个字母所对应的哈夫曼编码
时间: 2024-02-25 16:52:45 浏览: 24
下面是一个C语言程序,可以实现统计一句话中各个字母的个数,构建哈夫曼树并打印哈夫曼编码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 1000
typedef struct Node {
char data;
int freq;
struct Node *left, *right;
} Node;
typedef struct MinHeap {
int size;
Node **array;
} MinHeap;
Node *newNode(char data, int freq)
{
Node *node = (Node *) malloc(sizeof(Node));
node->data = data;
node->freq = freq;
node->left = node->right = NULL;
return node;
}
MinHeap *createMinHeap(int capacity)
{
MinHeap *heap = (MinHeap *) malloc(sizeof(MinHeap));
heap->size = 0;
heap->array = (Node **) malloc(capacity * sizeof(Node *));
return heap;
}
void swapNode(Node **a, Node **b)
{
Node *temp = *a;
*a = *b;
*b = temp;
}
void minHeapify(MinHeap *heap, int idx)
{
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < heap->size && heap->array[left]->freq < heap->array[smallest]->freq) {
smallest = left;
}
if (right < heap->size && heap->array[right]->freq < heap->array[smallest]->freq) {
smallest = right;
}
if (smallest != idx) {
swapNode(&heap->array[smallest], &heap->array[idx]);
minHeapify(heap, smallest);
}
}
int isSizeOne(MinHeap *heap)
{
return heap->size == 1;
}
Node *extractMin(MinHeap *heap)
{
Node *temp = heap->array[0];
heap->array[0] = heap->array[heap->size - 1];
heap->size--;
minHeapify(heap, 0);
return temp;
}
void insertMinHeap(MinHeap *heap, Node *node)
{
heap->size++;
int i = heap->size - 1;
while (i && node->freq < heap->array[(i - 1) / 2]->freq) {
heap->array[i] = heap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
heap->array[i] = node;
}
void buildMinHeap(MinHeap *heap)
{
int n = heap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; i--) {
minHeapify(heap, i);
}
}
void printCodes(Node *root, int arr[], int top)
{
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (!root->left && !root->right) {
printf("%c: ", root->data);
for (int i = 0; i < top; i++) {
printf("%d", arr[i]);
}
printf("\n");
}
}
void huffmanCodes(char data[], int freq[], int size)
{
MinHeap *heap = createMinHeap(size);
for (int i = 0; i < size; i++) {
insertMinHeap(heap, newNode(data[i], freq[i]));
}
buildMinHeap(heap);
while (!isSizeOne(heap)) {
Node *left = extractMin(heap);
Node *right = extractMin(heap);
Node *node = newNode('$', left->freq + right->freq);
node->left = left;
node->right = right;
insertMinHeap(heap, node);
}
int arr[MAX_LEN], top = 0;
printCodes(heap->array[0], arr, top);
}
void countLetters(char sentence[], int freq[], int size)
{
for (int i = 0; i < size; i++) {
if (sentence[i] >= 'A' && sentence[i] <= 'Z') {
freq[sentence[i] - 'A']++;
} else if (sentence[i] >= 'a' && sentence[i] <= 'z') {
freq[sentence[i] - 'a']++;
}
}
}
int main()
{
char sentence[MAX_LEN];
int freq[26] = {0};
printf("请输入一句英语句子:\n");
fgets(sentence, MAX_LEN, stdin);
int len = strlen(sentence);
countLetters(sentence, freq, len);
huffmanCodes("abcdefghijklmnopqrstuvwxyz", freq, 26);
return 0;
}
```
这个程序中定义了一个 `Node` 结构体表示哈夫曼树的节点,包含了字符数据、出现频率以及左右子节点。还定义了一个 `MinHeap` 结构体表示最小堆,用于构建哈夫曼树。程序中使用了最小堆来实现哈夫曼树的构建,具体实现细节可以参考代码中的注释。
程序首先读入一个字符串,然后统计其中各个字母出现的次数。接着调用 `huffmanCodes` 函数,将各个字母作为节点,各字母出现的次数作为权值,构建哈夫曼树,并打印各个字母所对应的哈夫曼编码。
注意,由于哈夫曼编码的长度不确定,因此在实现中需要使用动态数组或链表等数据结构来存储编码。在这个程序中,我们使用了一个长度为 `MAX_LEN` 的数组 `arr` 来存储哈夫曼编码,其中 `top` 变量表示当前编码的长度。