【c++、数据结构课设】哈夫曼树

时间过的真快，转眼之间一个学期即将结束，想必这个时候大家都在准备各科的课设作业，本期内容是我的数据结构课设，希望能给大家带来帮助，如果有任何不足或需要改进的地方，欢迎各位提出宝贵的意见。

屏幕录制2023-12-24 13.43.01

课设要求

哈夫曼树应用 题目描述及功能要求

  1. 从文件 Text.txt 中读取一大段文字(字符)，统计其中不同字符出现频度(百分比)，将这些字符 以及对应频度统计结果存于文件 Freq.txt 中。从 Freq.txt 文件中读取频度并按此频度创建哈夫曼树。
  2. 建立哈夫曼树并将它存于文件HuffTree.txt中(以顺序存储方式，结点结构(权值，双亲，左，右). 将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上;(可以以树的凹入表示法在屏幕上显示 哈夫曼树)。
  3. 利用已经建好的哈夫曼树(如不在内存，则从文件 HuffTree.txt 中读入)，给各字符进行哈夫曼编 码，并将编码结果存于另一个文件 HuffCode.txt 中。
  4. 输出该哈夫曼树的 WPL 值。
  5. 从键盘另外输入一段字符，所出现的字符，将输入的正文内容进行哈夫曼编码，如果某字符并没 有在哈夫曼编码表中，则该字符原样不变，若存在则进行二进制编码替换，将所得编码结果也保存在文 件 HuffEncoding.txt 中，同时也显示在终端上。
  6. 将二进制编码的结果从文件 HuffEncoding.txt 中读出再进行解码，显示出第 5 步中输入的那段字 符。

过程

1.数据结构

因为每个字符只能是哈夫曼树的叶子结点，所以要标记一下叶子结点。


typedef struct node {
    //权重
    int weight;
    //左右孩子,双亲
    node *lchild, *rchild, *parent;
    //叶子结点标志 false 叶子结点 true 非叶子结点
    bool flag;
} HuffmanNode;


typedef struct tree {
    //根结点
    HuffmanNode *head;
    //叶子结点个数
    int count;
} HuffmanTree;

//叶子结点数组
HuffmanNode *CH[26];

//哈夫曼编码结果
int HuffmanCode[26];

//WPL
int W;

//每个字符的权重
int weight[26];

//权重总和
int total;

//标记元素是否已经在哈夫曼树上
int status[26];


//每个字符的哈夫曼编码
int HuffmanCodes[26][26];

//
HuffmanTree *tree = new HuffmanTree;

2.主要函数

菜单


void menu() {

    cout << "-----------------------------------------------------------------------" << endl;
    cout << "|                                                                      |" << endl;
    cout << "|                            欢 迎 回 来                                 |" << endl;
    cout << "|                                                                      |" << endl;
    cout << "-----------------------------------------------------------------------" << endl;
    cout << endl;

    while (true) {
        int op;
        cout << "* 1.哈夫曼树的应用" << endl << "* 2.退出" << endl;
        cin >> op;
        if (op == 1) Huffmantree();
        else if (op == 2)bye();
        else cout << "输出有误！！！" << endl;
    }
}

退出函数

void bye() {
    ::exit(0);
}

接下来就是核心部分了

欢迎界面

void welcome() {
    cout << "-----------------------------------------------------------------------" << endl;
    cout << "|                                                                      |" << endl;
    cout << "|                        哈 夫 曼 树 应 用                               |" << endl;
    cout << "|                                                                      |" << endl;
    cout << "-----------------------------------------------------------------------" << endl;
    cout << endl;
};

初始化

void init(int flag){

    tree->count = 0;
    total = 0;
    W=0;
    if (flag)generateWeight(tree, flag);
    memset(status, 0, sizeof status);
    memset(HuffmanCodes, -1, sizeof HuffmanCodes);

}

哈夫曼树主函数


void Huffmantree() {
    //初始化

   init(0);

    //欢迎界面
    welcome();
    //生成权重
    generateWeight(tree, 0);

    //打印权重
    printWeight();
    sleep(1);

    //生成哈夫曼树
    generate(tree);

    //哈夫曼树写入文件
    writeTree(tree->head);

    //打印哈夫曼树
    printTree(0, tree->head);

    sleep(1);

    //哈夫曼编码
    code(tree, 0);


    //重新获取权重
    generateWeight(tree, 0);
    //计算WPL
    show();
    WPL(tree->head, 0);
    cout << " = " << W << endl;

    //从键盘读入字符，生成哈夫曼树
    //初始化
   init(1);
    //生成哈夫曼树
    generate(tree);

    //哈夫曼编码
    code(tree, 1);

    //输入文本
    Input();



    //解码
    decode(tree->head);
    sleep(1);
    cout<<endl;

}

生成权重

因为字符可以从文件读取，也可以从键盘读取，所以提供了两种选择，flag=0是从文件读，flag=1是从键盘读

（从文件读数据）
在这里插入图片描述


void generateWeight(HuffmanTree *t, int flag) {
    if (!flag) {
        cout << "正在努力读取文件..." << endl;
        sleep(1);
        fstream in;
        in.open("/Users/yuwei/Desktop/c++/practice/Text.txt", ios::in);
        memset(weight, 0, sizeof weight);

        char c;
        while (c = in.get()) {
            //weight=0,说明改字符第一次出现，
            if (weight[c - 'a'] == 0)t->count++;
            weight[c - 'a']++;

            //字符总数
            total++;
        }
        in.close();
    } else {
        cout << "请输入字符" << endl;
        memset(weight, 0, sizeof weight);

        string ch;
        cin >> ch;
        for (char c: ch) {
            if (c) {
                //weight=0,说明改字符第一次出现，
                if (weight[c - 'a'] == 0)t->count++;

                weight[c - 'a']++;

                //字符总数
                total++;
            }

        }

    }


}

打印权重

在这里插入图片描述


void printWeight() {

    //将权重存入文件中
    fstream out;
    out.open("/Users/yuwei/Desktop/c++/practice/Freq.txt", ios::out);

    cout << "-----------------------------------------------------------------------" << endl;
    cout << "                         权   重                                        " << endl;
    cout << "-----------------------------------------------------------------------" << endl;

    //第一行：字符
    for (int i = 0; i < 26; i++) {
        if (weight[i] != 0) {
            //在终端显示
            printf("%c\t", 'a' + i);
            // 写入文件
            out.put('a' + i);
            out.put('\t');
        }
    }

    cout << endl;
    out.put('\n');
    //第二行：权重
    for (int i = 0; i < 26; i++) {
        if (weight[i] != 0) {
            cout << weight[i] << "\t";
            //权重可能大于10，不能当作一个字符，必须转成字符串
            string s = to_string(weight[i]);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        }

    }
    cout << endl;
    out.put('\n');
    //第三行：比例
    for (int i = 0; i < 26; i++) {
        if (weight[i] != 0) {
            cout << (weight[i] * 100) / total << "%\t";
            string s = to_string((weight[i] * 100) / total);
            for (char c: s) {
                out.put(c);
            }
            out.put('%');
            out.put('\t');
        }
    }

    cout << endl << endl;
    out.close();

}

生成哈夫曼树


void generate(HuffmanTree *t) {
    cout << "努力构建哈夫曼树ing...";
    cout << endl;
    //间隔1s
    sleep(1);

    cout << "-----------------------------------------------------------------------" << endl;
    cout << "                         哈 夫 曼 树                                     " << endl;
    cout << "-----------------------------------------------------------------------" << endl;

    for (int i = 0; i < 26; i++) {
        //生成叶子结点
        CH[i] = new HuffmanNode;
        CH[i]->weight = 'a' + i;
        CH[i]->flag = false;

        CH[i]->lchild = CH[i]->rchild = nullptr;
        //如果weight为0说明改字符未出过，所以赋值为0x3ffff，作为标记
        if (!weight[i])weight[i] = 0x3ffff;
    }
    //f：未选结点中最小的权值最小的结点id，s：未选结点中最小的权值第二小的结点id
    int f, s;
    //进行t-》count-1次就能构造一颗哈夫曼树，比如只有两个字符，只须一步就能构造哈夫曼树
    for (int i = 1; i < t->count; i++) {

        //find ：查找未选结点中最小的权值最小的结点id
        f = find();
        //加入哈夫曼树，更新status
        status[f] = 1;
        s = find();
        //用第weight[s]来储存新生成的结点
        weight[s] = weight[f] + weight[s];
        HuffmanNode *tem = new HuffmanNode;
        //更新根结点
        t->head = tem;
        //更新左右孩子
        tem->lchild = CH[f];
        tem->rchild = CH[s];
        //更新双亲
        CH[f]->parent = CH[s]->parent = tem;
        tem->weight = weight[s];
        //非叶子结点
        tem->flag = true;
        //将新结点加入CH中
        CH[s] = tem;
    }

}

find()

查找未选结点中最小的权值最小的结点id


int find() {
    int min = -1;
    //找到第一个未加入哈夫曼树结点的id
    while (status[++min]);
    for (int i = 0; i < 26; i++) {
        if (!status[i]) {
            if (weight[i] < weight[min])min = i;
        }
    }
    return min;
}

哈夫曼树写入文件

n代表null
请添加图片描述
如果是叶子结点，则会在后面加上对应的字符



void writeTree(HuffmanNode *n) {

    if (n == nullptr) return;
    fstream out;
    out.open("/Users/yuwei/Desktop/c++/practice/HuffTree.txt", ios::app);


    out.write("parent: ", 8);
    //权重可能大于10，不能当作一个字符，必须转成字符串
    if (n->parent) {
        string s = to_string(n->parent->weight);
        for (char c: s) {
            out.put(c);
        }
        out.put('\t');
    } else {
        out.write("n", 1);
        out.put('\t');
    }

    out.write("weight: ", 8);
    //非叶子结点
    if (n->flag) {

        string s = to_string(n->weight);
        for (char c: s) {
            out.put(c);
        }
        out.put('\t');
    } else {
        string s = to_string(weight[n->weight - 'a']);
        for (char c: s) {
            out.put(c);
        }
        out.put('\t');
    }

    //左右孩子

    out.write("lchild: ", 8);
    //非叶子结点

    if (n->lchild) {

        //左孩子非叶子结点
        if (n->lchild->flag) {
            string s = to_string(n->lchild->weight);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        } else {
            string s = to_string(weight[n->lchild->weight - 'a']);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        }
    } else {
        out.write("n", 1);
        out.put('\t');
    }

    //右孩子
    out.write("rchild: ", 4);
    //非叶子结点

    if (n->rchild) {

        //左孩子非叶子结点
        if (n->rchild->flag) {
            string s = to_string(n->rchild->weight);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        } else {
            string s = to_string(weight[n->rchild->weight - 'a']);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        }
    } else {
        out.write("n", 1);
        out.put('\t');
    }



    if (!n->flag) {
        //如果是叶子结点
        out.write("char: ", 6);
        out.put(n->weight);
    }
    out.put('\n');
    out.close();

    writeTree(n->lchild);
    writeTree(n->rchild);


}

打印哈夫曼树

采用以树的凹入表示法在屏幕上显示 哈夫曼树
请添加图片描述


void printTree(int num, HuffmanNode *head) {

    if (head == nullptr)return;
    //按照中序顺序便利
    printTree(num + 1, head->lchild);
    //树的凹入表示法在屏幕上显示 哈夫曼树
    for (int i = 0; i < 15 - 3 * num; i++)cout << "  ";
    if (head->flag)cout << head->weight;
    else printf("%c", head->weight);
    for (int i = 0; i <= 3 * num; i++) {
        cout << "--";
    }
    cout << endl;
    printTree(num + 1, head->rchild);

}

哈夫曼编码

请添加图片描述


void code(HuffmanTree *t, int flag) {
    cout << "哈夫曼树编码中ing...";
    cout << endl;
    sleep(1);
    if (!flag)
        //将结果写进文件
        write(0, 0, t->head);
    else
        print(0, 0, t->head);
    cout << "-----------------------------------------------------------------------" << endl;
    cout << "                         编 码 完 成                                    " << endl;
    cout << "-----------------------------------------------------------------------" << endl;
}


void write(int i, int v, HuffmanNode *t) {
    if (t == nullptr)return;

    HuffmanCode[i] = v;

    write(i + 1, 0, t->lchild);
    //如果是叶子结点则写入文件中
    if (!t->flag) {
        fstream out;
        out.open("/Users/yuwei/Desktop/c++/practice/HuffCode.txt", ios::app);
        out.put(t->weight);
        out.put(':');
        for (int j = 1; j <= i; j++)
            //数字转字符
            out.put(HuffmanCode[j] + '0');
        out.put('\n');
        out.close();

    }
    write(i + 1, 1, t->rchild);
}

计算WPL



void WPL(HuffmanNode *n, int i) {
    if (n == nullptr)return;

    WPL(n->lchild, i + 1);

    if (!n->flag) {
        W += i * weight[n->weight - 'a'];
        cout << i << " * " << weight[n->weight - 'a'] << " + ";
    }
    WPL(n->rchild, i + 1);

}

从键盘读入字符构造哈夫曼编码

在这里插入图片描述


    //哈夫曼编码
    code(tree, 1);

输入文本进行编码

在这里插入图片描述


void Input() {

    cout << "请输入文本" << endl;
    string ch;
    cin >> ch;
    fstream out;
    out.open("/Users/yuwei/Desktop/c++/practice/HuffEncoding.txt", ios::out);

    for (char c: ch) {

        if (c) {

            //不等于-1说明该字符的编码存在
            if (HuffmanCodes[c - 'a'][0] != -1) {
                for (int j = 0; HuffmanCodes[c - 'a'][j] != -1; j++) {
                    out.put(HuffmanCodes[c - 'a'][j] + '0');
                    cout << HuffmanCodes[c - 'a'][j];
                }
            } else {
                cout << c;
                out.put(c);
            }
        }
    }
    out.close();

    cout << "编码完成！！！";
    cout << endl;
    sleep(1);

}

解码

在这里插入图片描述


void decode(HuffmanNode *head) {
    cout << "努力解码中ing" << endl;
    sleep(1);
    fstream in;
    in.open("/Users/yuwei/Desktop/c++/practice/HuffEncoding.txt", ios::in);
    char c;
    HuffmanNode *tem = new HuffmanNode ;
   tem = head;
   c=in.get();
    while ((c>'a'&&c<'z')||c=='0'||c=='1'){

        if (c == '0') {
           if(tem){
               tem = tem->lchild;
               findChar(&tem);
           }

        } else if (c == '1') {
         if(tem){
             tem = tem->rchild;
             findChar(&tem);
         }

        } else cout << c;
        c=in.get();
    }
in.close();

}


void findChar(HuffmanNode **n) {

    if ((*n)->flag)return;
        //叶子结点直接输出结果
    else {
        printf("%c", (*n)->weight);
        //找到字符后，再从头开始
        (*n) = tree->head;
    }
}

完整代码

#include <iostream>
#include <unistd.h>
#include <cstdio>
#include <fstream>
#include <string>

using namespace std;

typedef struct node {
    //权重
    int weight;
    //左右孩子,双亲
    node *lchild, *rchild, *parent;
    //叶子结点标志 false 叶子结点 true 非叶子结点
    bool flag;
} HuffmanNode;


typedef struct tree {
    //根结点
    HuffmanNode *head;
    //叶子结点个数
    int count;
} HuffmanTree;

//叶子结点数组
HuffmanNode *CH[26];

//哈夫曼编码结果
int HuffmanCode[26];

//WPL
int W;

//每个字符的权重
int weight[26];

//权重总和
int total;

//标记元素是否已经在哈夫曼树上
int status[26];


//每个字符的哈夫曼编码
int HuffmanCodes[26][26];

//
HuffmanTree *tree = new HuffmanTree;

// 欢迎界面
void welcome();

//生成权重，flag:0:从文件读取字符，1：从键盘读入
void generateWeight(HuffmanTree *t, int flag);

//打印哈夫曼树, num是层数
void printTree(int num, HuffmanNode *head);

//将哈夫曼树写入文件
void writeTree(HuffmanNode *n);

//计算WPL显示界面
void show();


void WPL(node *head, int i);

//哈夫曼树核心函数
void Huffmantree();


void bye();

//flag:0 编码结果写入文件，flag：1编码结果存入数组
void code(HuffmanTree *t, int flag);

//打印权重
void printWeight();

//查找未选结点中最小的权值最小的结点id
int find();

//将编码结果写入文件 ， num ：层数 v：编码值
void write(int num, int v, HuffmanNode *n);

//将编码结果写入二维数组 ， num ：层数 v：编码值
void print(int i, int v, HuffmanNode *t);

//从键盘输入内容，并将结果存入文件中
void Input();

//生成哈夫曼树
void generate(HuffmanTree *t);

//解码
void decode(HuffmanNode *head);

//根据哈夫曼编码找字符
void findChar(HuffmanNode **n);
//初始化
void init(int flag);
void menu() {

    cout << "-----------------------------------------------------------------------" << endl;
    cout << "|                                                                      |" << endl;
    cout << "|                            欢 迎 回 来                                 |" << endl;
    cout << "|                                                                      |" << endl;
    cout << "-----------------------------------------------------------------------" << endl;
    cout << endl;

    while (true) {
        int op;
        cout << "* 1.哈夫曼树的应用" << endl << "* 2.退出" << endl;
        cin >> op;
        if (op == 1) Huffmantree();
        else if (op == 2)bye();
        else cout << "输出有误！！！" << endl;
    }
}

void welcome() {
    cout << "-----------------------------------------------------------------------" << endl;
    cout << "|                                                                      |" << endl;
    cout << "|                        哈 夫 曼 树 应 用                               |" << endl;
    cout << "|                                                                      |" << endl;
    cout << "-----------------------------------------------------------------------" << endl;
    cout << endl;
};
void init(int flag){

    tree->count = 0;
    total = 0;
    W=0;
    if (flag)generateWeight(tree, flag);
    memset(status, 0, sizeof status);
    memset(HuffmanCodes, -1, sizeof HuffmanCodes);

}

void Huffmantree() {
    //初始化

   init(0);

    //欢迎界面
    welcome();
    //生成权重
    generateWeight(tree, 0);

    //打印权重
    printWeight();
    sleep(1);

    //生成哈夫曼树
    generate(tree);

    //哈夫曼树写入文件
    writeTree(tree->head);

    //打印哈夫曼树
    printTree(0, tree->head);

    sleep(1);

    //哈夫曼编码
    code(tree, 0);


    //重新获取权重
    generateWeight(tree, 0);
    //计算WPL
    show();
    WPL(tree->head, 0);
    cout << " = " << W << endl;

    //从键盘读入字符，生成哈夫曼树
    //初始化
   init(1);
    //生成哈夫曼树
    generate(tree);

    //哈夫曼编码
    code(tree, 1);

    //输入文本
    Input();



    //解码
    decode(tree->head);
    sleep(1);
    cout<<endl;

}


void bye() {
    ::exit(0);
}

void printWeight() {

    //将权重存入文件中
    fstream out;
    out.open("/Users/yuwei/Desktop/c++/practice/Freq.txt", ios::out);

    cout << "-----------------------------------------------------------------------" << endl;
    cout << "                         权   重                                        " << endl;
    cout << "-----------------------------------------------------------------------" << endl;

    //第一行：字符
    for (int i = 0; i < 26; i++) {
        if (weight[i] != 0) {
            //在终端显示
            printf("%c\t", 'a' + i);
            // 写入文件
            out.put('a' + i);
            out.put('\t');
        }
    }

    cout << endl;
    out.put('\n');
    //第二行：权重
    for (int i = 0; i < 26; i++) {
        if (weight[i] != 0) {
            cout << weight[i] << "\t";
            //权重可能大于10，不能当作一个字符，必须转成字符串
            string s = to_string(weight[i]);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        }

    }
    cout << endl;
    out.put('\n');
    //第三行：比例
    for (int i = 0; i < 26; i++) {
        if (weight[i] != 0) {
            cout << (weight[i] * 100) / total << "%\t";
            string s = to_string((weight[i] * 100) / total);
            for (char c: s) {
                out.put(c);
            }
            out.put('%');
            out.put('\t');
        }
    }

    cout << endl << endl;
    out.close();

}

void generate(HuffmanTree *t) {
    cout << "努力构建哈夫曼树ing...";
    cout << endl;
    //间隔1s
    sleep(1);

    cout << "-----------------------------------------------------------------------" << endl;
    cout << "                         哈 夫 曼 树                                     " << endl;
    cout << "-----------------------------------------------------------------------" << endl;

    for (int i = 0; i < 26; i++) {
        //生成叶子结点
        CH[i] = new HuffmanNode;
        CH[i]->weight = 'a' + i;
        CH[i]->flag = false;

        CH[i]->lchild = CH[i]->rchild = nullptr;
        //如果weight为0说明改字符未出过，所以赋值为0x3ffff，作为标记
        if (!weight[i])weight[i] = 0x3ffff;
    }
    //f：未选结点中最小的权值最小的结点id，s：未选结点中最小的权值第二小的结点id
    int f, s;
    //进行t-》count-1次就能构造一颗哈夫曼树，比如只有两个字符，只须一步就能构造哈夫曼树
    for (int i = 1; i < t->count; i++) {

        //find ：查找未选结点中最小的权值最小的结点id
        f = find();
        //加入哈夫曼树，更新status
        status[f] = 1;
        s = find();
        //用第weight[s]来储存新生成的结点
        weight[s] = weight[f] + weight[s];
        HuffmanNode *tem = new HuffmanNode;
        //更新根结点
        t->head = tem;
        //更新左右孩子
        tem->lchild = CH[f];
        tem->rchild = CH[s];
        //更新双亲
        CH[f]->parent = CH[s]->parent = tem;
        tem->weight = weight[s];
        //非叶子结点
        tem->flag = true;
        //将新结点加入CH中
        CH[s] = tem;
    }

}

void printTree(int num, HuffmanNode *head) {

    if (head == nullptr)return;
    //按照中序顺序便利
    printTree(num + 1, head->lchild);
    //树的凹入表示法在屏幕上显示 哈夫曼树
    for (int i = 0; i < 15 - 3 * num; i++)cout << "  ";
    if (head->flag)cout << head->weight;
    else printf("%c", head->weight);
    for (int i = 0; i <= 3 * num; i++) {
        cout << "--";
    }
    cout << endl;
    printTree(num + 1, head->rchild);

}

int find() {
    int min = -1;
    //找到第一个未加入哈夫曼树结点的id
    while (status[++min]);
    for (int i = 0; i < 26; i++) {
        if (!status[i]) {
            if (weight[i] < weight[min])min = i;
        }
    }
    return min;
}

void code(HuffmanTree *t, int flag) {
    cout << "哈夫曼树编码中ing...";
    cout << endl;
    sleep(1);
    if (!flag)
        //将结果写进文件
        write(0, 0, t->head);
    else
        print(0, 0, t->head);
    cout << "-----------------------------------------------------------------------" << endl;
    cout << "                         编 码 完 成                                    " << endl;
    cout << "-----------------------------------------------------------------------" << endl;
}

void write(int i, int v, HuffmanNode *t) {
    if (t == nullptr)return;

    HuffmanCode[i] = v;

    write(i + 1, 0, t->lchild);
    //如果是叶子结点则写入文件中
    if (!t->flag) {
        fstream out;
        out.open("/Users/yuwei/Desktop/c++/practice/HuffCode.txt", ios::app);
        out.put(t->weight);
        out.put(':');
        for (int j = 1; j <= i; j++)
            //数字转字符
            out.put(HuffmanCode[j] + '0');
        out.put('\n');
        out.close();

    }
    write(i + 1, 1, t->rchild);
}

void writeTree(HuffmanNode *n) {

    if (n == nullptr) return;
    fstream out;
    out.open("/Users/yuwei/Desktop/c++/practice/HuffTree.txt", ios::app);


    out.write("parent: ", 8);
    //权重可能大于10，不能当作一个字符，必须转成字符串
    if (n->parent) {
        string s = to_string(n->parent->weight);
        for (char c: s) {
            out.put(c);
        }
        out.put('\t');
    } else {
        out.write("n", 1);
        out.put('\t');
    }

    out.write("weight: ", 8);
    //非叶子结点
    if (n->flag) {

        string s = to_string(n->weight);
        for (char c: s) {
            out.put(c);
        }
        out.put('\t');
    } else {
        string s = to_string(weight[n->weight - 'a']);
        for (char c: s) {
            out.put(c);
        }
        out.put('\t');
    }

    //左右孩子

    out.write("lchild: ", 8);
    //非叶子结点

    if (n->lchild) {

        //左孩子非叶子结点
        if (n->lchild->flag) {
            string s = to_string(n->lchild->weight);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        } else {
            string s = to_string(weight[n->lchild->weight - 'a']);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        }
    } else {
        out.write("n", 1);
        out.put('\t');
    }

    //右孩子
    out.write("rchild: ", 4);
    //非叶子结点

    if (n->rchild) {

        //左孩子非叶子结点
        if (n->rchild->flag) {
            string s = to_string(n->rchild->weight);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        } else {
            string s = to_string(weight[n->rchild->weight - 'a']);
            for (char c: s) {
                out.put(c);
            }
            out.put('\t');
        }
    } else {
        out.write("n", 1);
        out.put('\t');
    }



    if (!n->flag) {
        //如果是叶子结点
        out.write("char: ", 6);
        out.put(n->weight);
    }
    out.put('\n');
    out.close();

    writeTree(n->lchild);
    writeTree(n->rchild);


}

//
void print(int i, int v, HuffmanNode *t) {
    if (t == nullptr)return;
    HuffmanCode[i] = v;

    print(i + 1, 0, t->lchild);
    //如果是叶子结点则写入文件中
    if (!t->flag) {
        for (int j = 1; j <= i; j++) {
            //数字转字符
            HuffmanCodes[t->weight - 'a'][j - 1] = HuffmanCode[j];
        }

    }
    print(i + 1, 1, t->rchild);

}

void Input() {

    cout << "请输入文本" << endl;
    string ch;
    cin >> ch;
    fstream out;
    out.open("/Users/yuwei/Desktop/c++/practice/HuffEncoding.txt", ios::out);

    for (char c: ch) {

        if (c) {

            //不等于-1说明该字符的编码存在1
            if (HuffmanCodes[c - 'a'][0] != -1) {
                for (int j = 0; HuffmanCodes[c - 'a'][j] != -1; j++) {
                    out.put(HuffmanCodes[c - 'a'][j] + '0');
                    cout << HuffmanCodes[c - 'a'][j];
                }
            } else {
                cout << c;
                out.put(c);
            }
        }
    }
    out.close();

    cout << "编码完成！！！";
    cout << endl;
    sleep(1);

}


void WPL(HuffmanNode *n, int i) {
    if (n == nullptr)return;

    WPL(n->lchild, i + 1);

    if (!n->flag) {
        W += i * weight[n->weight - 'a'];
        cout << i << " * " << weight[n->weight - 'a'] << " + ";
    }
    WPL(n->rchild, i + 1);

}

void show() {
    cout << "努力计算WPLing...";
    cout << endl;
    sleep(1);

    cout << "-----------------------------------------------------------------------" << endl;
    cout << "                           W  P  L                                     " << endl;
    cout << "-----------------------------------------------------------------------" << endl;

    cout << "WPL: ";
}

void generateWeight(HuffmanTree *t, int flag) {
    if (!flag) {
        cout << "正在努力读取文件..." << endl;
        sleep(1);
        fstream in;
        in.open("/Users/yuwei/Desktop/c++/practice/Text.txt", ios::in);
        memset(weight, 0, sizeof weight);

        char c;
        while (c = in.get()) {
            //weight=0,说明改字符第一次出现，
            if (weight[c - 'a'] == 0)t->count++;
            weight[c - 'a']++;

            //字符总数
            total++;
        }
        in.close();
    } else {
        cout << "请输入字符" << endl;
        memset(weight, 0, sizeof weight);

        string ch;
        cin >> ch;
        for (char c: ch) {
            if (c) {
                //weight=0,说明改字符第一次出现，
                if (weight[c - 'a'] == 0)t->count++;

                weight[c - 'a']++;

                //字符总数
                total++;
            }

        }

    }


}

void decode(HuffmanNode *head) {
    cout << "努力解码中ing" << endl;
    sleep(1);
    fstream in;
    in.open("/Users/yuwei/Desktop/c++/practice/HuffEncoding.txt", ios::in);
    char c;
    HuffmanNode *tem = new HuffmanNode ;
   tem = head;
   c=in.get();
    while ((c>'a'&&c<'z')||c=='0'||c=='1'){

        if (c == '0') {
           if(tem){
               tem = tem->lchild;
               findChar(&tem);
           }

        } else if (c == '1') {
         if(tem){
             tem = tem->rchild;
             findChar(&tem);
         }

        } else cout << c;
        c=in.get();
    }
in.close();

}

void findChar(HuffmanNode **n) {

    if ((*n)->flag)return;
        //叶子结点直接输出结果
    else {
        printf("%c", (*n)->weight);
        //找到字符后，再从头开始
        (*n) = tree->head;
    }
}

int main() {
    menu();
}

小结

本课设用到的知识
树的创建和遍历
哈夫曼树的构建和应用
c++文件的读写
在这里插入图片描述

再次感谢你的阅读，希望本文对你有所帮助。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/269441.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【GoLang】Go语言几种标准库介绍(一)

【GoLang】Go语言几种标准库介绍(一)

你见过哪些令你膛目结舌的代码技巧&#xff1f; 文章目录 你见过哪些令你膛目结舌的代码技巧&#xff1f;前言几种库bufio&#xff08;带缓冲的 I/O 操作&#xff09;特性示例 bytes (实现字节操作)特性示例 总结专栏集锦写在最后 前言 随着计算机科学的迅猛发展&#xff0c;编…
阅读更多...
前端---vscode 的基本使用

前端---vscode 的基本使用

1. vscode 的基本介绍 全拼是 Visual Studio Code (简称 VS Code) 是由微软研发的一款免费、开源的跨平台代码编辑器&#xff0c;目前是前端(网页)开发使用最多的一款软件开发工具。 2. vscode 的安装 下载网址: Download Visual Studio Code - Mac, Linux, Windows选择对应…
阅读更多...
（企业 / 公司项目）如何使用分布式任务调度框架Quartz集成 和 SpringBoot自带的定时任务集成？

（企业 / 公司项目）如何使用分布式任务调度框架Quartz集成 和 SpringBoot自带的定时任务集成？

SpringBoot自带的定时任务 首先在你的微服务项目中创建一个新的模块&#xff0c;定时调度模块 pom.xml里面关联公共模块common的依赖其他不需要改变 然后启动类别删&#xff0c;启动项目是否报错&#xff0c;写一个简单的测试类访问路径是否成功 package com.jiawa.train.bat…
阅读更多...
C语言：字符串字面量及其保存位置

C语言：字符串字面量及其保存位置

相关阅读 C语言https://blog.csdn.net/weixin_45791458/category_12423166.html?spm1001.2014.3001.5482 虽然C语言中不存在字符串类型&#xff0c;但依然可以通过数组或指针的方式保存字符串&#xff0c;但字符串字面量却没有想象的这么简单&#xff0c;本文就将对此进行讨论…
阅读更多...
【Linux】僵尸与孤儿 进程等待

【Linux】僵尸与孤儿 进程等待

目录 一&#xff0c;僵尸进程 1&#xff0c;僵尸进程 2&#xff0c;僵尸进程的危害 二&#xff0c;孤儿进程 1&#xff0c;孤儿进程 三&#xff0c;进程等待 1&#xff0c;进程等待的必要性 2&#xff0c;wait 方法 3&#xff0c;waitpid 方法 4&#xff0c;回收小结…
阅读更多...
华为OD机试 - 学生方阵 - 矩阵（Java 2023 B卷 200分）

华为OD机试 - 学生方阵 - 矩阵（Java 2023 B卷 200分）

目录 专栏导读一、题目描述二、输入描述三、输出描述1、输入2、输出 四、解题思路1、题目解析2、解体思路 五、Java算法源码再重新读一遍题目&#xff0c;看看能否优化一下~ 六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导…
阅读更多...
阶段十-物业项目

阶段十-物业项目

可能遇到的错误&#xff1a; 解决jdk17javax.xml.bind.DatatypeConverter错误 <!--解决jdk17javax.xml.bind.DatatypeConverter错误--><dependency><groupId>javax.xml.bind</groupId><artifactId>jaxb-api</artifactId><version>…
阅读更多...
使用 fixture 机制重构 appium_helloworld

使用 fixture 机制重构 appium_helloworld

一、前置说明 在 pytest 基础讲解 章节，介绍了 pytest 的特性和基本用法，现在我们可以使用 pytest 的一些机制，来重构 appium_helloworld 。 appium_helloworld 链接: 编写第一个APP自动化脚本 appium_helloworld ，将脚本跑起来 代码目录结构： pytest.ini 设置： [pyt…
阅读更多...
IntelliJ IDEA插件

IntelliJ IDEA插件

插件安装目录&#xff1a;C:\Users\<username>\AppData\Roaming\JetBrains\IntelliJIdea2021.2\plugins aiXcoder Code Completer&#xff1a;代码补全 Bookmark-X&#xff1a;书签分类 使用方法&#xff1a;鼠标移动到某一行&#xff0c;按ALT SHIFT D
阅读更多...
机器学习之实验过程01

机器学习之实验过程01

import pandas as pd import numpy as np import matplotlib.pyplot as plt data_path /home/py/Work/labs/data/SD.csv # 请确保您的数据文件路径是正确的 df pd.read_csv(data_path) df.head() # 创建散点图 # 创建散点图 plt.figure(figsize(10, 6)) plt.scatter…
阅读更多...
C语言字符串处理提取时间(ffmpeg返回的时间字符串)

C语言字符串处理提取时间(ffmpeg返回的时间字符串)

【1】需求 需求&#xff1a;有一个 “00:01:33.90” 这样格式的时间字符串&#xff0c;需要将这个字符串的时间值提取打印出来&#xff08;提取时、分、秒、毫秒&#xff09;。 这个时间字符串从哪里来的&#xff1f; 是ffmpeg返回的时间&#xff0c;也就是视频的总时间。 下…
阅读更多...
Go_defer详解

Go_defer详解

defer 1. 前言 defer语句用于延迟函数的调用&#xff0c;每次defer都会把一个函数压入栈中&#xff0c;函数返回前再把延迟的函数取出并执行。 为了方便描述&#xff0c;我们把创建defer的函数称为主函数&#xff0c;defer语句后面的函数称为延迟函数。 延迟函数可能有输入…
阅读更多...
零基础入门网络安全必看的5本书籍（附PDF)

零基础入门网络安全必看的5本书籍（附PDF)

书中自有黄金屋&#xff0c;书中自有颜如玉。很多人学习一门技术都会看大量的书籍&#xff0c;经常也有朋友询问&#xff1a;零基础刚入门&#xff0c;应该看哪些书&#xff1f;应该怎么学&#xff1f;等等问题。今天就整理了5本零基础入门网络安全必看书籍&#xff0c;希望能帮…
阅读更多...
WebGL开发地理和地球科学应用

WebGL开发地理和地球科学应用

使用WebGL开发地理和地球科学应用可以为学生提供交互式、沉浸式的学习体验&#xff0c;帮助他们理解地球表面的地理特征、地球科学原理以及环境变化。以下是开发地理和地球科学应用的一般步骤&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外…
阅读更多...
微信小程序~如何设置页面的背景色

微信小程序~如何设置页面的背景色

微信小程序~如何设置页面的背景色 众所周知&#xff0c;微信小程序每个页面由.json&#xff0c;.scss&#xff0c;.ts&#xff0c;.wxml这四个文件组成。 有的小伙伴会发现&#xff0c;需要给页面加背景色的时候&#xff0c;只需在此页面的.scss文件中写个page{background-colo…
阅读更多...
Java设计模式-桥接模式

Java设计模式-桥接模式

目录 一、手机操作问题 二、传统方法 三、基本介绍 四、原理类图 五、使用桥接模式解决手机问题 一、手机操作问题 现在对不同手机类型的不同品牌实现操作编程( 比如 : 开机、关机、上网&#xff0c;打电话等) &#xff0c; 如图: 二、传统方法 传统方案解决手机操作问题分…
阅读更多...
2024如果创业适合干什么，普通人如何创业

2024如果创业适合干什么，普通人如何创业

五行学说是中国古代哲学中的一部分&#xff0c;将世界万物归纳为五种元素&#xff0c;分别是金、木、水、火和土。每个年份的五行组合不同&#xff0c;代表着特定的能量和属性。2024年什么生意好做。 一&#xff0c;物联网科技行业&#xff1a;庚子年的金属性与现代物联网科技的…
阅读更多...
【JUnit技术专题】「入门到精通系列」手把手+零基础带你玩转单元测试，让你的代码更加“强壮”（夯实功底篇）

【JUnit技术专题】「入门到精通系列」手把手+零基础带你玩转单元测试，让你的代码更加“强壮”（夯实功底篇）

手把手零基础带你玩转单元测试&#xff0c;让你的代码更加“强壮” 前言介绍JUnit是什么&#xff1f;JUnit和xUnit之间的关系 JUnit的基本概念JUnit的特点什么是一个单元测试用例 JUnit的用法JUnit的最佳实践案例分析创建一个类创建 Test Case 类创建 Test Runner 类 JUnit总体…
阅读更多...
第11章 GUI Page436 使用缓冲DC， wxBufferedPaintDC

第11章 GUI Page436 使用缓冲DC， wxBufferedPaintDC

所谓“缓冲DC”&#xff0c;是指将所有图元都先划到一个人眼看不到的“设备上下文”之上&#xff0c;最后再一次性复制到真正的屏幕DC之上&#xff0c;这样我们就看不到中间画的过程了&#xff0c;也就不会感到闪烁了。 注意&#xff0c;这时不能解除ScrolledWindow1的背景擦除…
阅读更多...
千帆起航：探索百度智能云千帆AppBuilder在AI原生应用开发中的革新之路

千帆起航：探索百度智能云千帆AppBuilder在AI原生应用开发中的革新之路

千帆起航&#xff1a;探索百度千帆AppBuilder在AI原生应用开发中的革新之路 1.揭开帷幕&#xff0c;大模型第二次战役 自从 ChatGPT 横空出世后&#xff0c;一石激起千层浪&#xff0c;人工智能也正在从感知理解走向生成创造&#xff0c;这是一个关键里程碑。生成式大模型完成…
阅读更多...
最新文章

Copyright @ 2022~2023