编写完整的C语言代码：根据给定的n个字符及其权值设计各字符的哈夫曼编码。键盘输入一段英文句子统计句子中出现的英文字母数目不含标点符号以及各个英文字母的出现次数及频率。然后设计各个英文字母的哈夫曼编码的码字。选定一个英文字母序列根据上述哈夫曼编码方法得到码字序列后再对码字序列译码

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

#define MAX_TREE_HT 100

// 定义哈夫曼树的结构体 struct MinHeapNode { char data; unsigned freq; struct MinHeapNode *left, *right; };

struct MinHeap { unsigned size; unsigned capacity; struct MinHeapNode **array; };

// 创建一个哈夫曼树的节点 struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* node = (struct MinHeapNode*) malloc(sizeof(struct MinHeapNode)); node->left = node->right = NULL; node->data = data; node->freq = freq; return node; }

// 创建一个最小堆 struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap = (struct MinHeap*) malloc(sizeof(struct MinHeap)); minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**) malloc(minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap; }

// 交换两个节点 void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; }

// 最小堆的下滤操作 void minHeapify(struct MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq) smallest = left; if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } }

// 判断堆是否只剩下一个节点 int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); }

// 取出最小节点 struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; }

// 插入一个节点 void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; }

// 构建哈夫曼树 struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, top; struct MinHeap minHeap = createMinHeap(size); for (int i = 0; i < size; ++i) { insertMinHeap(minHeap, newNode(data[i], freq[i])); } while (!isSizeOne(minHeap)) { left = extractMin(minHeap); right = extractMin(minHeap); top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } return extractMin(minHeap); }

// 打印哈夫曼编码 void printCodes(struct MinHeapNode* 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 countLetters(char sentence[], int *letterCount, int *letterFreq) { int len = strlen(sentence); for (int i = 0; i < len; i++) { if ((sentence[i] >= 'a' && sentence[i] <= 'z') || (sentence[i] >= 'A' && sentence[i] <= 'Z')) { letterCount[sentence[i] - 'A']++; } } for (int i = 0; i < 26; i++) { if (letterCount[i] > 0) { letterFreq[i] = letterCount[i] * 1.0 / len * 100; } } }

int main() { int n; printf("请输入字符总数n："); scanf("%d", &n); char data[n]; int freq[n]; printf("请依次输入n个字符和它们的权值：\n"); for (int i = 0; i < n; i++) { scanf(" %c %d", &data[i], &freq[i]); } struct MinHeapNode* root = buildHuffmanTree(data, freq, n); int arr[MAX_TREE_HT], top = 0; printf("\n哈夫曼编码如下：\n"); printCodes(root, arr, top);

getchar(); // 清空输入缓冲区

printf("\n请输入一段英文句子：");
char sentence[100];
fgets(sentence, 100, stdin);

int letterCount[26] = {0};
int letterFreq[26] = {0};
countLetters(sentence, letterCount, letterFreq);

printf("\n英文字母数目和出现次数如下：\n");
for (int i = 0; i < 26; i++) {
    if (letterCount[i] > 0) {
        printf("%c: %d\n", i + 'A', letterCount[i]);
    }
}

printf("\n英文字母出现频率如下：\n");
for (int i = 0; i < 26; i++) {
    if (letterFreq[i] > 0) {
        printf("%c: %d%%\n", i + 'A', letterFreq[i]);
    }
}

printf("\n请输入一个英文字母序列：");
char letters[100];
fgets(letters, 100, stdin);

printf("\n哈夫曼编码后的码字序列如下：\n");
for (int i = 0; i < strlen(letters); i++) {
    if ((letters[i] >= 'a' && letters[i] <= 'z') || (letters[i] >= 'A' && letters[i] <= 'Z')) {
        for (int j = 0; j < n; j++) {
            if (data[j] == letters[i]) {
                for (int k = 0; k < top; k++) {
                    printf("%d", arr[k]);
                }
                printf(" ");
                break;
            }
        }
    }
}

printf("\n\n请输入哈夫曼编码后的码字序列：");
char code[100];
fgets(code, 100, stdin);

printf("\n码字序列译码后得到的英文字母序列如下：\n");
int i = 0;
while (i < strlen(code)) {
    struct MinHeapNode* node = root;
    while (node->left || node->right) {
        if (code[i] == '0') {
            node = node->left;
        } else if (code[i] == '1') {
            node = node->right;
        }
        i++;
    }
    printf("%c", node->data);
}

return 0;