哈夫曼编码译码器打印树形项目

Question

现在只需将代码中直接写入的文档改为通过读取文档内容再统计字符或权重，但回答时请发全部代码
【问题描述】
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传送数据预先编码，在接收端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
文件file.txt中有短文：多行可改，有标点，小写即可
试编写一个哈夫曼编/译码系统。
【基本要求】
一个完整的系统应具有以下功能：
获取字符权重。读取file.txt文件，统计文本文件中字符种类及个数，得到字符权重。
构建哈夫曼树。根据字符个数n及其权值，建立哈夫曼树，并将它存于文件HfmTree.txt中。
编码。利用已建好的哈夫曼树求出每个字符的哈夫曼编码，然后将结果存入文件CodeFile.txt中。
加密。利用哈夫曼编码对短文进行加密，以紧凑格式显示在终端上，每行50个字符，最后将结果存入文件TextFile.txt中。
译码。读取TextFile.txt文件编码，进行译码，并显示结果。
打印哈夫曼树。将哈夫曼树以直观的方式（树或凹入表示）显示在终端上，同时写入文件TreePrint.txt中。
【参考资料】
打印树形的代码https://blog.csdn.net/Ice__Clean/article/details/121078026
3天内

#include <iostream>
#include "huffman.h"

using namespace std;
int len;
int couter=0;
void menu()
{
    printf("****************************\n");
    printf("---------欢迎使用系统-------\n");
    printf("***     获取字符权重    *** \n");
    printf("***     构建哈夫曼树    *** \n");
    printf("***     编码            *** \n");
    printf("***     加密            *** \n");
    printf("***     译码            *** \n");
    printf("***     打印哈夫曼树    *** \n");
    printf("***     退出            *** \n");
    printf("****************************\n");
}

int main()
{
    int i;
    int n;
    int select=1;//用户选择的功能
    huffmanTree *p;
    huffmanTree *pp;
    FILE *a;
    huffmanTree *ppp=(huffmanTree*)malloc(1000*sizeof(huffmanTree));
    FILE *file;
    // 初始化功能
    // 1.把文件写入
    char str[200]="there are moments in life when you miss someone so much that you just want to pick them from your dreams and hug them for real!";
    file=fopen("file.txt","wb");
    fwrite(str,sizeof(char),127,file);
    fclose(file);
    // 2.读取权值
    p= getCharPowerHuffman();
    // 3.创建哈夫曼树
    pp=createHuffman(couter,p);
    menu();

    while(select)
    {
        printf("请输入您的选择：");
        scanf("%d",&select);
        switch(select)
        {
        case 1:
            for(i=0; i<couter; i++)
            {
                printf("%c：%d \n",(p+i)->character,(p+i)->weight);
            }
            printf("\n");
            break;
        case 2:
            printfHuffmanTree(pp);
            //写入文件
            writeFile(pp);
            break;
        case 3:
            codeHuffman(pp,couter);//编码
            break;
        case 4:
            encryptHuffman();//加密
            break;
        case 5:
            decodingHuffman();//
            break;
        case 6:
            printHuffman(pp);//打印哈夫曼树
            break;
        case 0:
            break;
        }
    }
    return 0;
}
#include "huffman.h"
extern int couter;
extern int len;

void codeHuffman(huffmanTree *pp,int couter){
    hafcode HC;//定义储存哈夫曼编码
    int i;
    int m =couter;
    int n = 2*m-1;

    CODE *p=(CODE*)malloc(m*sizeof(CODE));

    HC=(hafcode)malloc((m+1)*sizeof(char*));
    char *cd =(char*)malloc(m*sizeof(char));
    cd[m-1]='\0';
    int start,chi,f=0;
    for (i=0; i<m; i++)//循环结构
    {
        start = m-1;
        chi=i;
        f=(pp+chi)->parent-1;//把f拉回其儿子的父结点
        while(f>0)
        {   int lchild=(pp+f)->leftChild-1;
            start--;
            if(lchild==chi)
            {
                cd[start]='0';//左0
            }
            else if((pp+f)->rightChild-1==chi)
            {
                cd[start]='1';//右1
            }
            chi=f;//父结点变为儿子结点 深度遍历
            f=((pp+chi)->parent)-1;
        }
        HC[i]=(char*)malloc((m-start)*sizeof(char));
        strcpy(HC[i],&cd[start]);//储存的编码赋值给HC[]数组
    }

    // 将编码与字母保存起来再存到文件
    for (i = 0; i <m ; i++)
    {
        (p+i)->s=(pp+i)->character;
         strcpy((p+i)->number,HC[i]);
    }
    FILE *fp2;
    fp2 = fopen("CodeFile.txt", "wb");
    fwrite(p,sizeof(CODE),m,fp2);
    fclose(fp2);
    free(cd);
    // 打印显示的内容
    for(i=0; i<m; i++)
    {
        printf("%s:",(p+i)->number);
        printf("%c\n",(p+i)->s);
    }
    free(p);
}
#include "huffman.h"
extern int couter;

huffmanTree * createHuffman(int n,huffmanTree *p)
{
    int countNumber,t;
    int i,j,h;
    int a,b,m;
    m=2*n-1;//
    countNumber =m;
    t=(countNumber+1)/2;
    h=t;
    // 初始化哈夫曼树
    for(i=0; i<n; i++)
    {
        (p+i)->lchild=NULL;
        (p+i)->rchild=NULL;
        (p+i)->leftChild=0;
        (p+i)->rightChild=0;
    }
    // 生成哈夫曼树
    for(i=0,j=h; i<t-1; i++,h++)
    {
        select(p,t+i,a,b);
        (p+h)->weight=(p+a)->weight+(p+b)->weight;
        (p+h)->leftChild=a+1;
        (p+h)->rightChild=b+1;
        (p+h)->lchild=p+a;
        (p+h)->rchild=p+b;
    }

    return p;
}
void printfHuffmanTree(huffmanTree *p)
{
    // 把哈夫曼树打印出来
    int i=0;
    while(1)
    {
        printf("%d %d %d %d\n",(p+i)->weight,(p+i)->parent,(p+i)->leftChild,(p+i)->rightChild);
        if((p+i)->parent==0)
        {
            break;
        }
        i++;
    }
}
void select(huffmanTree *p,int number,int &a,int &b)
{
    // 进行两次对比，分别挑出最小的两个赋值给a和b
    int i,j;
    int t=0;
    for(j=0; j<2; j++)
    {
        for(i=0; i<number; i++)
        {
            if((p+i)->parent==0)
            {
                t=i;
                break;
            }
        }
        for(i=0; i<number; i++)
        {
            if((p+i)->parent!=0)
            {
                continue;
            }
            if((p+i)->weight<(p+t)->weight)
            {
                t=i;
            }
        }
        (p+t)->parent=number+1;
        if(j==0)
        {
            a=t;
        }
        if(j==1)
        {
            b=t;
        }
    }
}
void writeFile(huffmanTree *p)
{
    // 把哈夫曼编码写入到文件当中去
    FILE *a;
    int t;
    t = 2*couter-1;
    a=fopen("HfmTree.txt","wb");//wb 只写方式打开或新建一个二进制文件，只允许写数据。
    fwrite(p,sizeof(huffmanTree),t,a);//写入格式(指向数组或结构体的指针,单个数组里面内容的大小,数量,文件指针)
    fclose(a);
}
#include "huffman.h"
char seekS(CODE *p,char *s,int len)
{
    // 循环比例，根据s的值找到其对应的字符
    int i;
    for(i=0; i<len; i++)
    {
        if(strcmp((p+i)->number,s)==0)
        {
            return (p+i)->s;
        }
    }
    return '-';
}
void decodingHuffman(){
    int i,j;
    int len,len2;
    // 读取TextFile.txt
    FILE* filetwo;
    filetwo=fopen("TextFile.txt","rb");
    fseek(filetwo, 0, SEEK_END);// 使用完之后切记让指针回到初始位置
    len2 = ftell(filetwo);
    fseek(filetwo, 0, SEEK_SET);// 回到开头（很关键，不然无法fread）
    len2 = len2 / sizeof(char);// 获取存入了几个数据
    char pp[len2];
    fread(pp,sizeof(char),len2,filetwo);
    fclose(filetwo);

    // 读取CodeFile.txt
    FILE *fp2;
    fp2 = fopen("CodeFile.txt", "rb");
    fseek(fp2, 0, SEEK_END);// 使用完之后切记让指针回到初始位置
    len = ftell(fp2);
    fseek(fp2, 0, SEEK_SET);// 回到开头（很关键，不然无法fread）
    len = len / sizeof(CODE);// 获取存入了几个数据

    // 开辟空间存放从文件读取的内容
    CODE *p=(CODE*)malloc(len*sizeof(CODE));
    fread(p,sizeof(CODE),len,fp2);
    fclose(fp2);
    char ss[10];// 依次读取记录内容
    int t=0;// 记录读取到哪里
    int sss;//记录返回出来的源码
    for(i=0;i<len2;i++){
        ss[t++]=pp[i];
        if(t>=2){
            ss[t]='\0';
            sss=seekS(p,ss,len);
            if(sss!='-'){
                t=0;
                printf("%c",sss);
            }
        }
    }
    printf("\n");
}
#include "huffman.h"
char* seekNumber(CODE *p,char s,int len)
{
    // 循环遍历，根据s的值找到其对应的编码
    char *strr = (char *)malloc(20*sizeof(char));
    int i;
    for(i=0; i<len; i++)
    {
        if((p+i)->s==s)
        {
            strcpy(strr,(p+i)->number);
            break;
        }
    }
    return strr;
}
void encryptHuffman()
{
    int i,j;
    int len,len2;
    FILE *fp2;
    fp2 = fopen("CodeFile.txt", "rb");
    fseek(fp2, 0, SEEK_END);// 使用完之后切记让指针回到初始位置
    len = ftell(fp2);
    fseek(fp2, 0, SEEK_SET);// 回到开头（很关键，不然无法fread）
    len = len / sizeof(CODE);// 获取存入了几个数据

    // 开辟空间存放从文件读取的内容
    CODE *p=(CODE*)malloc(len*sizeof(CODE));
    char *pp=(char*)malloc(600*sizeof(char));// 存放加密的编码
    fread(p,sizeof(CODE),len,fp2);
    fclose(fp2);
    // 读取短文
    char s[200];
    int couter=0; //计数的换行器
    int coutermore=0;
    FILE *file;
    file=fopen("file.txt","rb");// 以只读模式打开文件

    fseek(file, 0, SEEK_END);// 使用完之后切记让指针回到初始位置
    len2 = ftell(file);
    fseek(file, 0, SEEK_SET);// 回到开头（很关键，不然无法fread）
    len2 = len2 / sizeof(char);// 获取存入了几个数据

    fread(s,sizeof(char),len2,file);
    fclose(file);// 关闭文件

    char *ss;
    // 循环遍历短文
    for(i=0; i<len2; i++)
    {
            ss = seekNumber(p,s[i],len);
            for(j=0; j<strlen(ss); j++)
            {
                if(couter==50)
                {
                    couter=0;
                    printf("\n");
                }
                printf("%c",ss[j]);
                pp[coutermore]=ss[j];
                couter++;
                coutermore++;
            }
    }
    printf("\n");
    pp[coutermore]='\0';
    FILE* filetwo;
    filetwo=fopen("TextFile.txt","wb");
    fwrite(pp,sizeof(char),coutermore+1,filetwo);
    fclose(filetwo);
}
#include "huffman.h"
extern int len;
extern int couter;
int test(huffmanTree H[],int couter,char alphabet)
{
// 返回1或者-1，-1表示该字符第一次出现，i表示其已经存在直接累加即可
    int i;
    for(i=0; i<couter; i++)
    {
        if(H[i].character==alphabet)
        {
            return i;
        }
    }
    return -1;
}
huffmanTree* getCharPowerHuffman()
{
    // 返回CharacterRate数组，里面存放着字母及其对应的权值
    char s[200];
    int i;
    huffmanTree *H=(huffmanTree*)malloc(100*sizeof(huffmanTree));
    // 初始化H
    for(i=0; i<100; i++)
    {
        H[i].character=' ';
        H[i].weight=0;
        H[i].parent=0;
        H[i].leftChild=0;
        H[i].rightChild=0;
    }

    //第二个单词为累加
    FILE *file;
    file=fopen("file.txt","r");// 以只读模式打开文件

    fseek(file, 0, SEEK_END);// 使用完之后切记让指针回到初始位置
    len = ftell(file);
    fseek(file, 0, SEEK_SET);// 回到开头（很关键，不然无法fread）
    len = len / sizeof(char);// 获取存入了几个数据

    fread(s,sizeof(char),len,file);
    fclose(file);// 关闭文件
    // 调试实例there are moments
    // 开始计算频率
    for(i=0; i<len; i++)
    {
            if(test(H,couter,s[i])==-1)
            {
                H[couter].weight=1;
                H[couter].character=s[i];
                couter++;
            }
            else
            {
                H[test(H,couter,s[i])].weight++;
            }
    }
    return H;
}
#include "huffman.h"

//改变光标位置
void gotoxy(int x, int y)
{
    // 更新光标位置
    COORD pos;
    HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
    pos.X = x;
    pos.Y = y;
    SetConsoleCursorPosition(hOutput, pos);
}
// 获取树的深度
int BiTreeDepth(huffmanTree *T)
{
    if (T == NULL) return 0;

    int depthLeft, depthRight;
    depthLeft = BiTreeDepth(T->lchild);
    depthRight = BiTreeDepth(T->rchild);
    return 1 + (depthLeft > depthRight ? depthLeft : depthRight);
}
// 分割树
int BreakBiTree(BiTree& T, BiTree& L, BiTree& R)
{
    if (T == NULL) return 0;
    L = T->lchild;
    R = T->rchild;

    return 1;
}
int Traverse_R(BiTree T, int depth, int right, int tap,FILE *file)
{
    if (T == NULL) return 1;

    // 获取一次树的初始高度，用于计算相对偏移数量
    static int treeDepth = BiTreeDepth(T);
    // 记录当前光标位置，用于在递归中记录当前递归时树的位置
    int x, y;
    // 拆分树，将树的左右子树拆分开来
    BiTree L, R;
    BreakBiTree(T, L, R);

    // 计算父树的偏移量
    int tap1 = tap * pow(LENLENLEN, treeDepth - depth);
    // 计算子树的偏移量
    int tap2 = right * (pow(LENLENLEN, treeDepth - depth));
    // 计算半偏移量
    int tap3 = pow(LENLENLEN, treeDepth - depth - 1);

    // 获取根的坐标
    // x 计算方法为：父偏移量 + 子偏移量 + 半偏移量 - 1
    // y 计算方法为：目前打印的层数 * 2
    x = tap1 + tap2 + tap3 - 1;
    y = depth * LENLENLEN;

    // 打印根的位置
    gotoxy(x * LENLENLEN, y);
    printf("%d", T->weight);
        fprintf(file,"%d", T->weight);
    // 在打印子树时，当前层数+1
    depth++;
    // 计算子树的父偏移量
    tap = tap * LENLENLEN + (right == 1 ? LENLENLEN: 0);
    if (L == NULL && R == NULL) return 1;
    else if (R == NULL)
    {
        // 打印左子树的位置
        gotoxy(x * LENLENLEN - tap3, y + 1);
        printf("┏");
        fprintf(file,"┏");
        for (int i = 0; i < tap3-1; i++) {printf("━");fprintf(file,"━");}
        printf("┛");
        fprintf(file,"┛");
        Traverse_R(L, depth, 0, tap,file);
    }
    else if (L == NULL)
    {
        // 打印右子树的位置
        gotoxy(x * LENLENLEN, y + 1);
        printf("┗");
        fprintf(file,"┗");
        for (int i = 0; i < tap3-1; i++) {printf("━"); fprintf(file,"━");}
        printf("┓");
         fprintf(file,"┓");
        Traverse_R(R, depth, 1, tap,file);
    }
    else
    {
        // 打印左右子树的位置
        gotoxy(x * LENLENLEN - tap3, y + 1);
        printf("┏");
        fprintf(file,"┏");
        for (int i = 0; i < tap3 - 1; i++){ printf("━");fprintf(file,"━");}
        printf("┻");
        fprintf(file,"┻");
        for (int i = 0; i < tap3 - 1; i++) {printf("━");fprintf(file,"━");}
        printf("┓");
        fprintf(file,"┓");
        Traverse_R(L, depth, 0, tap,file);
        Traverse_R(R, depth, 1, tap,file);
    }
}
void printHuffman(BiTree T)
{
    FILE *file;
    file=fopen("TreePrint.txt","w+");
    Traverse_R(T+44, 0, 0, 0,file);
    printf("\n");
    fprintf(file,"\n");
    fclose(file);
}

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

以下是一个C++的实现，实现了上述要求的功能：

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <queue>
#include <vector>

using namespace std;

// 哈夫曼树节点结构
struct HuffmanNode {
    char data;  // 字符
    int freq;   // 权重
    HuffmanNode* left;
    HuffmanNode* right;
    
    HuffmanNode(char ch, int f) {
        data = ch;
        freq = f;
        left = nullptr;
        right = nullptr;
    }
};

// 定义优先队列的比较函数
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 递归构建哈夫曼树
HuffmanNode* buildHuffmanTree(map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    
    // 将字符权重信息加入优先队列
    for (auto entry : freqMap) {
        HuffmanNode* node = new HuffmanNode(entry.first, entry.second);
        pq.push(node);
    }
    
    // 构建哈夫曼树
    while (pq.size() > 1) {
        HuffmanNode* a = pq.top(); pq.pop();
        HuffmanNode* b = pq.top(); pq.pop();
        
        HuffmanNode* newNode = new HuffmanNode('$', a->freq + b->freq);
        newNode->left = a;
        newNode->right = b;
        
        pq.push(newNode);
    }
    
    return pq.top();
}

// 递归获取字符的哈夫曼编码
void getHuffmanCode(HuffmanNode* root, string code, map<char, string>& codeMap) {
    if (root->left == nullptr && root->right == nullptr) {
        codeMap[root->data] = code;
        return;
    }
    
    getHuffmanCode(root->left, code + "0", codeMap);
    getHuffmanCode(root->right, code + "1", codeMap);
}

// 获取文件文本并统计字符权重
map<char, int> getCharFreq(string filename) {
    ifstream file(filename);
    map<char, int> freqMap;
    
    if (file.is_open()) {
        char ch;
        while (file >> noskipws >> ch) {
            if (isalpha(ch)) {
                ch = tolower(ch);
                if (freqMap.find(ch) == freqMap.end()) {
                    freqMap[ch] = 1;
                } else {
                    freqMap[ch]++;
                }
            }
        }
    }
    
    return freqMap;
}

// 将哈夫曼树打印为树形结构并写入文件
void printHuffmanTree(HuffmanNode* root, string indent, ofstream& file) {
    if (root == nullptr) return;
    
    file << indent;
    file << root->data << ": " << root->freq << endl;
    
    indent += "    ";
    printHuffmanTree(root->left, indent, file);
    printHuffmanTree(root->right, indent, file);
}

int main() {
    // 获取字符权重
    map<char, int> freqMap = getCharFreq("file.txt");
    
    // 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freqMap);
    
    // 获取哈夫曼编码
    map<char, string> codeMap;
    getHuffmanCode(root, "", codeMap);
    
    // 将哈夫曼树存入文件
    ofstream hfmTreeFile("HfmTree.txt");
    printHuffmanTree(root, "", hfmTreeFile);
    hfmTreeFile.close();
    
    // 将编码存入文件
    ofstream codeFile("CodeFile.txt");
    for (auto entry : codeMap) {
        codeFile << entry.first << ": " << entry.second << endl;
    }
    codeFile.close();
    
    // 加密并存入文件
    ifstream inputFile("file.txt");
    ofstream textFile("TextFile.txt");
    
    if (inputFile.is_open()) {
        char ch;
        int count = 0;
        while (inputFile >> noskipws >> ch) {
            if (isalpha(ch)) {
                ch = tolower(ch);
                textFile << codeMap[ch];
                count += codeMap[ch].length();
                
                if (count >= 50) {
                    textFile << endl;
                    count = 0;
                }
            }
        }
    }
    
    inputFile.close();
    textFile.close();
    
    // 译码并显示结果
    ifstream cipherFile("TextFile.txt");
    ofstream decodedFile("DecodedFile.txt");
    
    if (cipherFile.is_open()) {
        string encodedText;
        while (getline(cipherFile, encodedText)) {
            string decodedText;
            HuffmanNode* node = root;
            
            for (char ch : encodedText) {
                if (ch == '0') {
                    node = node->left;
                } else if (ch == '1') {
                    node = node->right;
                }
                
                if (node->left == nullptr && node->right == nullptr) {
                    decodedText += node->data;
                    node = root;
                }
            }
            
            decodedFile << decodedText << endl;
        }
    }
    
    cipherFile.close();
    decodedFile.close();
    
    // 打印哈夫曼树
    ofstream treePrintFile("TreePrint.txt");
    printHuffmanTree(root, "", treePrintFile);
    treePrintFile.close();
    
    return 0;
}

代码中使用了C++的STL库，通过map来统计字符权重，通过优先队列priority_queue来构建哈夫曼树。其中，HuffmanNode结构体表示哈夫曼树的节点，Compare结构体作为排序函数来比较节点的权重。

buildHuffmanTree函数用于构建哈夫曼树，通过优先队列逐步合并权重最小的两个节点，直到得到根节点。

getHuffmanCode函数递归地获取每个字符的哈夫曼编码，最终存储在map中。

getCharFreq函数用于获取文件文本并统计字符的权重。

printHuffmanTree函数用于将哈夫曼树以树形结构的格式打印，并写入文件。

最后，主函数中依次调用上述函数来实现完整的哈夫曼编/译码系统。