用c语言写电文的编码和译码 任务：从键盘接收一串电文字符，输出对应的哈夫曼编码。同时，能翻译由哈夫曼编码生成的代码串，输出对应的电文字符串。 ①构造一棵哈夫曼树；②实现哈夫曼编码，并用哈夫曼编码生成的代码串进行译码；③程序中字符和权值是可变的，实现程序的灵活性。

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

#define MAX_CHAR 256

typedef struct MinHeapNode{
    char data;
    int freq;
    struct MinHeapNode *left, *right;
}MinHeapNode;

typedef struct MinHeap{
    int size;
    int capacity;
    MinHeapNode **array;
}MinHeap;

typedef struct HuffmanCode{
    char data;
    char *code;
}HuffmanCode;

MinHeapNode *newNode(char data, int freq){
    MinHeapNode *node = (MinHeapNode*)malloc(sizeof(MinHeapNode));
    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->capacity = capacity;
    heap->array = (MinHeapNode**)malloc(capacity * sizeof(MinHeapNode*));
    return heap;
}

void swap(MinHeapNode **a, MinHeapNode **b){
    MinHeapNode *t = *a;
    *a = *b;
    *b = t;
}

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){
        swap(&heap->array[idx], &heap->array[smallest]);
        minHeapify(heap, smallest);
    }
}

int isSizeOne(MinHeap *heap){
    return heap->size == 1;
}

MinHeapNode *extractMin(MinHeap *heap){
    MinHeapNode *min = heap->array[0];
    heap->array[0] = heap->array[heap->size - 1];
    --heap->size;
    minHeapify(heap, 0);
    return min;
}

void insertMinHeap(MinHeap *heap, MinHeapNode *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 printArray(int arr[], int n){
    int i;
    for(i = 0; i < n; ++i)
        printf("%d", arr[i]);
    printf("\n");
}

int isLeaf(MinHeapNode *node){
    return !node->left && !node->right;
}

void generateCodes(MinHeapNode *root, int arr[], int top, HuffmanCode *codes[]){
    if(root->left){
        arr[top] = 0;
        generateCodes(root->left, arr, top + 1, codes);
    }
    if(root->right){
        arr[top] = 1;
        generateCodes(root->right, arr, top + 1, codes);
    }
    if(isLeaf(root)){
        int i;
        for(i = 0; i < top; ++i);
        HuffmanCode *code = (HuffmanCode*)malloc(sizeof(HuffmanCode));
        code->data = root->data;
        code->code = (char*)malloc(top * sizeof(char));
        memcpy(code->code, arr, top * sizeof(char));
        codes[root->data] = code;
    }
}

int findFrequency(char data[], int n, char c){
    int i, count = 0;
    for(i = 0; i < n; ++i){
        if(data[i] == c)
            ++count;
    }
    return count;
}

void encode(char data[], int n, HuffmanCode *codes[]){
    int i;
    for(i = 0; i < n; ++i){
        printf("%s", codes[data[i]]->code);
    }
    printf("\n");
}

void decode(MinHeapNode *root, char *str, int n){
    MinHeapNode *node = root;
    int i;
    for(i = 0; i < n; ++i){
        if(str[i] == '0')
            node = node->left;
        else
            node = node->right;
        if(isLeaf(node)){
            printf("%c", node->data);
            node = root;
        }
    }
}

void destroyCodes(HuffmanCode *codes[]){
    int i;
    for(i = 0; i < MAX_CHAR; ++i){
        if(codes[i]){
            free(codes[i]->code);
            free(codes[i]);
        }
    }
}

int main(){
    char data[MAX_CHAR];
    printf("Enter input data: ");
    fgets(data, MAX_CHAR, stdin);
    int n = strlen(data);
    if(data[n - 1] == '\n')
        data[n - 1] = '\0';
    n = strlen(data);
    int freq[MAX_CHAR] = {0};
    int i;
    for(i = 0; i < n; ++i){
        freq[data[i]]++;
    }
    MinHeap *heap = createMinHeap(MAX_CHAR);
    for(i = 0; i < MAX_CHAR; ++i){
        if(freq[i] > 0)
            insertMinHeap(heap, newNode(i, freq[i]));
    }
    while(!isSizeOne(heap)){
        MinHeapNode *left = extractMin(heap);
        MinHeapNode *right = extractMin(heap);
        MinHeapNode *node = newNode('$', left->freq + right->freq);
        node->left = left;
        node->right = right;
        insertMinHeap(heap, node);
    }
    MinHeapNode *root = extractMin(heap);
    HuffmanCode *codes[MAX_CHAR] = {0};
    int arr[MAX_CHAR] = {0};
    generateCodes(root, arr, 0, codes);
    printf("Huffman Codes:\n");
    printf("----------------\n");
    for(i = 0; i < MAX_CHAR; ++i){
        if(codes[i]){
            printf("%c : %s\n", i, codes[i]->code);
        }
    }
    printf("----------------\n");
    printf("Encoded Data:\n");
    printf("----------------\n");
    encode(data, n, codes);
    printf("----------------\n");
    char code[MAX_CHAR];
    printf("Enter code: ");
    fgets(code, MAX_CHAR, stdin);
    n = strlen(code);
    if(code[n - 1] == '\n')
        code[n - 1] = '\0';
    n = strlen(code);
    printf("Decoded Data:\n");
    printf("----------------\n");
    decode(root, code, n);
    printf("\n");
    destroyCodes(codes);
    return 0;
}