用c语言编程:已知通信员甲要传输一串电文,WINNIE WILL WIN,请设计电文编码并使译码唯一,要求写出C语言代码
时间: 2024-02-13 08:06:07 浏览: 128
唯一可译码源代码(c语言 含报告)
5星 · 资源好评率100%
可以使用哈夫曼编码实现电文编码和译码的唯一性。具体实现步骤如下:
1. 统计电文中每个字符出现的次数,并将其存入一个数组中。
2. 根据字符出现次数构建哈夫曼树。
3. 对哈夫曼树进行遍历,赋予每个字符对应的编码。
4. 将编码后的电文输出,并将其存入文件中。
5. 对编码后的电文进行译码。
6. 将译码后的电文输出,并将其存入文件中。
下面是一份示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHARACTERS 256
// 哈夫曼树节点
typedef struct node {
char character;
int frequency;
struct node *left;
struct node *right;
} Node;
// 哈夫曼编码
typedef struct code {
char character;
char *bits;
} Code;
// 哈夫曼树队列
typedef struct queue {
Node *node;
struct queue *next;
} Queue;
// 统计字符出现次数
void count_characters(char *text, int *frequencies) {
int i;
for (i = 0; i < strlen(text); i++) {
frequencies[(int) text[i]]++;
}
}
// 创建哈夫曼树节点
Node *create_node(char character, int frequency) {
Node *node = (Node *) malloc(sizeof(Node));
node->character = character;
node->frequency = frequency;
node->left = NULL;
node->right = NULL;
return node;
}
// 创建哈夫曼树队列节点
Queue *create_queue_node(Node *node) {
Queue *queue_node = (Queue *) malloc(sizeof(Queue));
queue_node->node = node;
queue_node->next = NULL;
return queue_node;
}
// 插入哈夫曼树队列节点
Queue *insert_queue_node(Queue *head, Queue *queue_node) {
if (head == NULL) {
head = queue_node;
} else {
Queue *current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = queue_node;
}
return head;
}
// 弹出哈夫曼树队列节点
Queue *pop_queue_node(Queue *head) {
if (head == NULL) {
return NULL;
} else {
Queue *temp = head;
head = head->next;
temp->next = NULL;
return temp;
}
}
// 创建哈夫曼树
Node *create_huffman_tree(int *frequencies) {
Queue *queue = NULL;
int i;
for (i = 0; i < MAX_CHARACTERS; i++) {
if (frequencies[i] > 0) {
Node *node = create_node(i, frequencies[i]);
queue = insert_queue_node(queue, create_queue_node(node));
}
}
while (queue != NULL && queue->next != NULL) {
Queue *first = pop_queue_node(queue);
Queue *second = pop_queue_node(queue);
Node *node = create_node('\0', first->node->frequency + second->node->frequency);
node->left = first->node;
node->right = second->node;
queue = insert_queue_node(queue, create_queue_node(node));
free(first);
free(second);
}
Node *root = NULL;
if (queue != NULL) {
root = queue->node;
free(queue);
}
return root;
}
// 遍历哈夫曼树赋予编码
void traverse_tree(Node *node, char *bits, int depth, Code *codes) {
if (node == NULL) {
return;
}
if (node->left == NULL && node->right == NULL) {
int i;
for (i = 0; i < MAX_CHARACTERS; i++) {
if (node->character == i) {
Code code = {i, (char *) malloc(sizeof(char) * (depth + 1))};
strncpy(code.bits, bits, depth);
code.bits[depth] = '\0';
codes[i] = code;
return;
}
}
}
bits[depth] = '0';
traverse_tree(node->left, bits, depth + 1, codes);
bits[depth] = '1';
traverse_tree(node->right, bits, depth + 1, codes);
}
// 哈夫曼编码
void huffman_encode(char *text, Code *codes) {
int frequencies[MAX_CHARACTERS] = {0};
count_characters(text, frequencies);
Node *root = create_huffman_tree(frequencies);
char bits[MAX_CHARACTERS] = {'\0'};
traverse_tree(root, bits, 0, codes);
int i;
for (i = 0; i < strlen(text); i++) {
printf("%s", codes[(int) text[i]].bits);
}
}
// 哈夫曼译码
void huffman_decode(char *text, Node *root) {
Node *current = root;
int i;
for (i = 0; i < strlen(text); i++) {
if (text[i] == '0') {
current = current->left;
} else {
current = current->right;
}
if (current->left == NULL && current->right == NULL) {
printf("%c", current->character);
current = root;
}
}
}
int main() {
char text[] = "WINNIE WILL WIN";
Code codes[MAX_CHARACTERS];
huffman_encode(text, codes);
Node *root = create_huffman_tree(NULL);
char bits[MAX_CHARACTERS] = {'\0'};
traverse_tree(root, bits, 0, codes);
printf("\n");
huffman_decode("0010110010111100001110011101100110000010101111100111001011111", root);
printf("\n");
return 0;
}
```
阅读全文