数据结构实验5：哈夫曼编码

哈夫曼编码实现文本压缩

1、输入字符串，输出字符串的哈夫曼编码；

   输入文本文件（英文），输出哈夫曼编码文件

2、附加：解压缩

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma warning(disable : 4996)
#define _CRT_SECURE_NO_DEPRECATE
using namespace std;

int choice; // 1输入字符串,2文件
int n;      //各字符的序号
string txt;
unordered_map hashmap;                                                     //计数，算出权重
priority_queue, vector>, greater>> heap; //堆，用于后面取最小的两个权重,第一位是权重，第二位是序号
unordered_map char_to_num;                                                 //字符和编号的映射
char num_to_char[10010];                                                              //下标为该位置存储字符的序号
string code;
vector> match;

typedef struct
{
    unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;
typedef char **HuffmanCode;

string readFileIntoString(char *filename)
{
    ifstream ifile(filename); //将文件读入到ostringstream对象buf中
    ostringstream buf;
    char ch;
    while (buf && ifile.get(ch))
        buf.put(ch); //返回与流对象buf关联的字符串
    return buf.str();
}

void Prepare() //一切准备工作
{
    for (auto x : txt)
    {
        if (++hashmap[x] == 1) //计数加1,并判断是否第一次出现
        {
            num_to_char[++n] = x; //第一次出现，就为这个字符编上序号,从1开始
            char_to_num[x] = n;
        }
    }
    for (int i = 1; i <= n; i++) //执行完上面的遍历之后，cnt即为总的字符种类数
    {
        char c = num_to_char[i]; //此编号对应字符
        int weight = hashmap[c]; //字符的权重
        heap.push({weight, i});  //入堆
    }
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC)
{
    if (n <= 1)
        return;
    int m = 2 * n - 1;
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
    int i = 1;
    for (HuffmanTree p = HT + 1; i <= m; i++, p++) //前n个默认为原数组中的字符
        *p = {0, 0, 0};
    for (int i = n + 1; i <= m; i++) //建立哈夫曼树
    {
        auto least1 = heap.top(); //取最小权重的
        heap.pop();
        auto least2 = heap.top(); //第二小的
        heap.pop();
        HT[least1.second].parent = i;
        HT[least2.second].parent = i;
        HT[i].lchild = least1.second;
        HT[i].rchild = least2.second;
        heap.push({least1.first + least2.first, i}); // i的权重和序号入堆
    }
    HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //分配n个字符编码的头指针向量
    char *cd = (char *)malloc(n * sizeof(char));        //分配求编码的工作空间
    cd[n - 1] = '';
    for (int i = 1; i <= n; i++)
    {
        int start = n - 1;
        for (int c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
        {
            if (HT[f].lchild == c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
        }
        HC[i] = (char *)malloc((n - start) * sizeof(char));
        strcpy(HC[i], &cd[start]);
    }
    free(cd);
}

void Transform(HuffmanCode &HC) //文本转换为编码
{
    for (auto x : txt)
        code += HC[char_to_num[x]];
    if (choice == 1)
        cout << code << endl;
    if (choice == 2) //文件的话
    {
        std::ofstream OsWrite("huffmancode.txt");
        OsWrite << code;
        // OsWrite << std::endl;
        OsWrite.close();
    }
}

int Search(int x) //二分查找
{
    int l = 0, r = match.size() - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (match[mid].first >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (match[l].first == x)
        return match[l].second;
    else
        return 0;
}

void Translate(HuffmanCode &HC) //解压缩
{
    for (int i = 1; i <= n; i++)
    {
        int temp = 0; //编码转换为二进制值
        for (int j = 0; HC[i][j] != ''; j++)
        {
            temp <<= 1;
            temp += int(HC[i][j]);
        }
        match.push_back({temp, i});
    }
    sort(match.begin(), match.end());

    char *fn = (char *)"huffmancode.txt";
    string allcode = readFileIntoString(fn);
    string res;
    for (int i = 0; i < allcode.size(); i++)
    {
        int temp = 0;
        while (1)
        {
            temp <<= 1;
            temp += int(allcode[i]);
            int idex = Search(temp); //返回的是字符对应的序号
            if (idex)
            {
                res += num_to_char[idex];
                break;
            }
            else
                i++;
        }
    }
    std::ofstream OsWrite("translate.txt");
    OsWrite << res;
    // OsWrite << std::endl;
    OsWrite.close();
}

int main()
{
    cin >> choice;
    if (choice == 1)
    {
        cin.ignore(); //清空缓冲区
        getline(cin, txt);
    }
    if (choice == 2)
    {
        char *fn = (char *)"source.txt";
        txt = readFileIntoString(fn);
    }
    Prepare();
    HuffmanTree HT;
    HuffmanCode HC;
    HuffmanCoding(HT, HC);
    Transform(HC);
    if (choice == 2)
        Translate(HC); //解压
    system("pause");
    return 0;
}