dict-encoder.cpp

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

// 字典編碼
class DictionaryEncoding {
private:
     // 记录字典的大小
    int size;
    // 字典内容
    char dict[1024][1024];
    // 将一个字符追加到一个字符串末尾
    void add_char_to_string(char* string, char chr);
public:
    DictionaryEncoding();
    // 输出字典内容
    void print_dict();
    // 向字典添加内容
    void add_string(char* string);
    // 清空字典
    void clean_dict();
    // 初始化字典內容
    void init_dict(char* string);
    // 判斷輸入的字符串是否在字典中
    int is_in_dict(char* string);
    // 獲取輸入的字符串下標
    int index_of(char* string);
    // 使用字典編碼壓縮輸入的字符串
    void encode(char* string);
};

DictionaryEncoding::DictionaryEncoding() {}

void DictionaryEncoding::print_dict() {
    // 輸出字典的內容，用于調試。
    int i;
    for(i=0;i<size;++i) {
        printf("%s\n", dict[i]);
    }
}

void DictionaryEncoding::add_string(char* string) {
    // 將字符串添加到字典中
    strcpy(dict[size], string);
    size += 1;
}

void DictionaryEncoding::clean_dict() {
    // 清空字典內容，每次進行編碼之前都要清空字典。
    size = 1;
    dict[0][0] = '\0';
}

void DictionaryEncoding::init_dict(char* string) {
    // 根據輸入的字符串，初始化字典內容，將字符串里的字符保存到字典中。
    int i;
    char chr[2];
    i = 0;
    while((chr[0] = string[i]) != '\0') {
        chr[1] = '\0';
        if (!is_in_dict(chr)) {
            add_string(chr);
        }
        i += 1;
    }
}

int DictionaryEncoding::is_in_dict(char* string) {
    // 判斷字符串是否存在于字典內。
    int i;
    for(i=0; i<size; ++i) {
        if (strcmp(dict[i], string) == 0) {
            return 1;
        }
    }
    return 0;
}

int DictionaryEncoding::index_of(char* string) {
    // 返回字符串在字典的位置（下標），如果不存在返回 -1
    int i;
    for(i=0; i<size; ++i) {
        if (strcmp(dict[i], string) == 0) {
            return i;
        }
    }
    return -1;
}

void DictionaryEncoding::add_char_to_string(char* string, char chr) {
    // 將單個字符追加到字符串末尾。
    // strcat 只能將兩個字符串連接起來。
    int len = strlen(string);
    string[len] = chr;
    string[len + 1] = '\0';
}

void DictionaryEncoding::encode(char* string) {
    // 對輸入的字符做字典編碼壓縮
    clean_dict();
    init_dict(string);
    int i, idx;
    char chr;
    char temp[100] = "";
    char output[100] = "";
    char prefix[100] = "";
    i = 0;
    while((chr = string[i]) != '\0') {
        strcpy(temp, prefix);
        add_char_to_string(temp, chr);
        if (is_in_dict(temp)) {
            add_char_to_string(prefix, chr);
        } else {
            idx = index_of(prefix);
            if (idx == -1) {
                printf("Error\n");
                exit(1);
            }
            add_char_to_string(output, (idx + 48));
            add_char_to_string(prefix, chr);
            add_string(prefix);
            prefix[0] = chr;
            prefix[1] = '\0';
        }
        i += 1;
    }
    printf("%s\n", output);
}

int main(int argc, char* argv[]) {
    char str[100];
    DictionaryEncoding encoder;
    printf("请输入待压缩字符串：");
    scanf("%s", str);
    encoder.encode(str);
    return 0;
}