lz78 c++代码

以下是LZ78压缩算法的C++代码实现：

#include <iostream>
#include <map>
#include <string>

using namespace std;

// 压缩函数
void compress(string input) {
    map<string, int> dict; // 字典表
    string w = "";
    char c;
    int code = 0;
    for (int i = 0; i < input.length(); i++) {
        c = input[i];
        if (dict.find(w + c) != dict.end()) {
            w = w + c;
        } else {
            if (w == "") code = 0;
            else code = dict[w];
            cout << code << " " << c << endl;
            dict[w + c] = dict.size() + 1;
            w = "";
        }
    }
    if (w != "") {
        code = dict[w];
        cout << code << endl;
    }
}

// 解压函数
void decompress(string input) {
    map<int, string> dict; // 字典表
    string w = "";
    int code = 0;
    char c;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == ' ') {
            code = stoi(w);
            w = "";
            c = input[++i];
            if (code == 0) cout << c;
            else cout << dict[code] << c;
            dict[dict.size() + 1] = dict[code] + c;
        } else {
            w += input[i];
        }
    }
    if (w != "") {
        code = stoi(w);
        cout << dict[code];
    }
}

int main() {
    string input = "ababcbababaaaaaabaaa";
    cout << "原始字符串：" << endl << input << endl << endl;
    
    cout << "压缩结果：" << endl;
    compress(input);
    cout << endl;
    
    string compressed = "0 a\n1 b\n2 c\n4 b\n5 a\n6 a\n7 a\n3 5\n3 5\n3 6\n";
    cout << "压缩字符串：" << endl << compressed << endl << endl;
    
    cout << "解压结果：" << endl;
    decompress(compressed);
    cout << endl;
    
    return 0;
}

在这个实现中，压缩函数和解压函数都使用了一个 `map` 类型的字典表来存储字符和对应的编码或解码结果。在压缩函数中，我们使用了一个 `string` 类型的 `w` 来存储当前的字符串，每次读取一个新字符 `c` 时，如果 `w+c` 在字典表中已经存在，则将 `w+c` 赋值给 `w` 继续读取下一个字符；否则，我们输出 `w` 的编码和字符 `c`，并将 `w+c` 加入字典表中。在解压函数中，我们同样使用了一个 `string` 类型的 `w` 来存储当前的字符串，每次读取一个新的编码 `code` 和字符 `c` 时，如果 `code` 为 0，则直接输出 `c`；否则，我们输出 `dict[code]+c`，并将 `dict[code]+c` 加入字典表中。