Huffman编码/译码问题

本文主要是介绍Huffman编码/译码问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Huffman编码/译码

问题描述

利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译码系统。

基本要求

一个完整的系统应具有以下功能:
(1) I:初始化(Initialization)。从终端读入字符集大小n，及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree中。
(2) C:编码(Coding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmtree中读 入)，对文件tobetrans中的正文进行编码，然后将结果存入codefile中。
(3) D:译码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译 码，结果存入文件textfile中。
(4) P:印代码文件(Print)。将文件codefile以紧凑格式显示在终端上，每行50个代 码。同时将此字符形式的编码文件写入文件codeprint中。
(5) T:印哈夫曼树(Tree print)。将已在内存中的哈夫曼树以直观的方式 树或凹入表行式)显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。
测试数据：
用下表中给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码: “THIS PROGRAM IS MY FAVORITE”.

实现提示
(1) 文件codefile的基类型可以设为子界型 bit=0…1。
(2) 用户界面可以设计为"菜单"方式: 显示上述功能符号，再加上"E"，表示结束运行End，请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了"E"为止。
(3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，哈符曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmtree可能早己建好。

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

typedef struct HT{
    int val;
    char word;
    bool bitt[30];
    struct HT *left, *right;
};

struct HT *Huffman_Tree[30], *roott;

bool Huff[30][30];
char Huffq[30][30];

int nn = 30, HuffLen[30];

void Build_Tree(int n, struct HT *root, int k) {
    struct HT *q = (struct HT*) malloc(sizeof(struct HT));
    q->left = NULL;
    q->right = NULL;
    q->val = 0;
    if (Huffq[n][k] == '\0') {
        if (n == 26) {
            root->word = ' ';
        }
        else {
            root->word = n + 'A';
        }
    }
    else if (Huffq[n][k] == '0') {
        if (root->left == NULL) {
            q->word = '*';
            root -> left = q;
            Build_Tree(n, q, k + 1);
        }
        else {
            Build_Tree(n, root->left, k + 1);
        }
    }
    else if (Huffq[n][k] == '1') {
        if (root->right == NULL) {
            q->word = '*';
            root -> right = q;
            Build_Tree(n, q, k + 1);
        }
        else {
            Build_Tree(n, root->right, k + 1);
        }
    }
}

void Readhfmtree() {
    char s[30];
    FILE *fp = NULL;
    fp = fopen("../hfmtree.txt", "r");
    if (fp == NULL) {
        printf("The document does not exist\n");
    }
    int sum = 0;
    while(!feof(fp)) {
        memset(s, '\0', sizeof(s));
        fgets(s, 30, fp);
        for (int i = 2; i < strlen(s); i++) {
            if (s[i] == '\n') {
                break;
            }
            Huffq[sum][i - 2] = s[i];
        }
        sum++;
    }
    fclose(fp);
    roott = (struct HT*) malloc(sizeof(struct HT));
    roott->left = NULL;
    roott->right = NULL;
    roott->word = '*';
    roott->val = 0;
    for (int i = 0; i < 27; i++) {
        Build_Tree(i, roott, 0);
    }
}

void sortt(int n) {
    for (int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            if (Huffman_Tree[i]->val < Huffman_Tree[j]->val) {
                struct HT *temp = Huffman_Tree[i];
                Huffman_Tree[i] = Huffman_Tree[j];
                Huffman_Tree[j] = temp;
            }
        }
    }
}

void Build_Bitt(struct HT *root, int k) {
    if (root == NULL) {
        return;
    }
    if (root->word >= 'A' && root->word <= 'Z') {
        memcpy(Huff[root->word - 'A'], root->bitt, k + 1);
        HuffLen[root->word - 'A'] = k;
    }
    else if (root->word == ' ') {
        memcpy(Huff[26], root->bitt, k + 1);
        HuffLen[26] = k;
    }
    if (root -> left != NULL) {
        memcpy(root->left->bitt, root->bitt, k + 1);
        root->left->bitt[k + 1] = false;
        Build_Bitt(root->left, k + 1);
    }
    if (root -> right != NULL) {
        memcpy(root->right->bitt, root->bitt, k + 1);
        root->right->bitt[k + 1] = true;
        Build_Bitt(root->right, k + 1);
    }
}

void Initialization() {
    char ch;
    int q;
    getchar();
    printf("input the letter and its val\n");
    for (int i = 0; i < 27; ++i) {
        scanf("%c %d", &ch, &q);
        struct HT *ht = (struct HT*)malloc(sizeof(struct HT));
        ht->word = ch;
        ht->val = q;
        ht->left = NULL;
        ht->right = NULL;
        memset(ht->bitt, false, sizeof(ht->bitt));
        getchar();
        if (ch == ' ') {
            Huffman_Tree[26] = ht;
        }
        else {
            Huffman_Tree[ch - 'A'] = ht;
        }
    }
    sortt(27);
    int m = 27;
    while(m != 1) {
        struct HT *ht = (struct HT *)malloc(sizeof(struct HT));
        ht->left = Huffman_Tree[m - 2];
        ht->right = Huffman_Tree[m - 1];
        ht->word = '*';
        ht->val = ht->left->val + ht->right->val;
        memset(ht->bitt, false, sizeof(ht->bitt));
        Huffman_Tree[m - 2] = ht;
        sortt(m);
        m--;
    }
    Build_Bitt(Huffman_Tree[0], 0);
    FILE *fp = NULL;
    fp = fopen("../hfmtree.txt","w");
    if (fp == NULL) {
        printf("Document Error");
    }
    for (int i = 0; i < 27; i++) {
        char s[30];
        memset(s, '\0', sizeof(s));
        if (i == 27 - 1) {
            s[0] = ' ';
        }
        else {
            s[0] = 'A' + i;
        }
        s[1] = ' ';
        for (int j = 1; j <= HuffLen[i]; ++j) {
            if (Huff[i][j] == false) {
                s[j + 1] = '0';
            }
            else {
                s[j + 1] = '1';
            }
        }
        fprintf(fp, s);
        fprintf(fp, "\n");
    }
    fclose(fp);
}

void Coding() {
    char s[300];
    memset(s, '\0', sizeof(s));
    gets(s);
    FILE *fp = NULL;
    fp = fopen("../codefile.txt","w");
    if (fp == NULL) {
        printf("Document Error");
    }
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            fprintf(fp, Huffq[s[i] - 'A']);
        }
        else if (s[i] == ' ') {
            fprintf(fp, Huffq[26]);
        }
        else {
            char ch[2];
            ch[0] = s[i];
            ch[1] = '\0';
            fprintf(fp, ch);
        }
    }
    fprintf(fp, "\n");
    fclose(fp);
};

void Decoding() {
    char s1[3000], s2[3000];
    FILE *fp1 = NULL, *fp2 = NULL;
    fp1 = fopen("../codefile.txt","r");
    fp2 = fopen("../textfile.txt","w");
    if (fp2 == NULL) {
        printf("Document Error");
    }
    if (fp1 == NULL) {
        printf("Document Not exist");
    }
    while (!feof(fp1)) {
        memset(s1, '\0', sizeof(s1));
        memset(s2, '\0', sizeof(s2));
        fgets(s1, 3000, fp1);
        struct HT *q = roott;
        int sum = 0;
        for (int i = 0; i < strlen(s1); ++i) {
            if (s1[i] == '0') {
                q = q->left;
            }
            else if (s1[i] == '1') {
                q = q->right;
            }
            else {
                s2[sum++] = s1[i];
            }
            if (q->word != '*') {
                s2[sum++] = q->word;
                q = roott;
            }
        }
        fprintf(fp2, s2);
        fprintf(fp2, "\n");
    }
    fclose(fp2);
    fclose(fp1);
}

void Print() {
    char s[1000];
    FILE *fp = NULL;
    fp = fopen("../codefile.txt","r");
    if (fp == NULL) {
        printf("Document Not exist");
    }
    while(!feof(fp)) {
        memset(s, '\0', sizeof(s));
        fgets(s, 1000, fp);
        for (int i = 0; i < strlen(s); ++i) {
            printf("%c", s[i]);
            if ((i + 1) % 50 == 0) {
                printf("\n");
            }
        }
    }
    fclose(fp);
}

void Tree_Print() {
    FILE *fp;
    fp = fopen("../treeprint.txt","w");
    if (fp == NULL) {
        printf("Document Error");
    }
    int sum = 30;
    char s[50];
    for (int i = 0; i < 27; ++i) {
        memset(s, '\0', sizeof(s));
        if (i == 26) {
            s[0] = ' ';
        }
        else {
            s[0] = 'A' + i;
        }
        s[1] = ' ';
        for (int j = 0; j < sum - strlen(Huffq[i]) * 2; ++j) {
            s[j + 2] = '=';
        }
        fprintf(fp, s);
        fprintf(fp,"\n");
        printf("%s\n",s);
    }
    fclose(fp);
}

int main() {
    char c;
    while (1) {
        printf(" 1.Initialization\n 2.Coding\n 3.Decoding\n 4.Print\n 5.Tree print\n");
        printf("input the number of the instruction to use the instructions, or input e/E to exit\n");
        scanf("%c",&c);
        if (c == 'E' || c == 'e') {
            break;
        }
        else {
            if (c == '1') {
                Initialization();
            }
            else if (c == '2') {
                Readhfmtree();
                getchar();
                Coding();
            }
            else if (c == '3') {
                Readhfmtree();
                Decoding();
            }
            else if (c == '4') {
                Print();
            }
            else if (c == '5') {
                Readhfmtree();
                Tree_Print();
            }
        }
    }
    return 0;
}

这篇关于Huffman编码/译码问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！