字典树

admin

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstring>   // for memset
#include <string>

using namespace std;

const int maxn = 100;
const int maxc = 26;

struct Trie {
    int ch[maxn][maxc];
    int tot;        // 当前最大的节点索引（根为 0）
    int cnt[maxn];

    void init() {
        tot = 0;                     // 根节点为 0
        // 将所有边初始化为 -1，计数初始化为 0
        memset(ch, -1, sizeof(ch));
        memset(cnt, 0, sizeof(cnt));
    }

    // 接受 const char*，或者可以重载接受 std::string
    void insert(const char *str) {
        int p = 0;
        for (int i = 0; str[i]; ++i) {
            int c = str[i] - 'a';
            if (c < 0 || c >= maxc) {
                // 忽略非小写字母（也可以处理或抛出错误）
                continue;
            }
            if (ch[p][c] == -1) {
                // 创建新节点，编号为 ++tot
                ch[p][c] = ++tot;
                cout<<tot<<endl;
            }
            p = ch[p][c];
        }
        cnt[p]++;
    }

    int find(const char *str) const {  // 返回字符串 str 的出现次数
        int p = 0;
        for (int i = 0; str[i]; ++i) {
            int c = str[i] - 'a';
            if (c < 0 || c >= maxc) return 0;
            if (ch[p][c] == -1) {
                return 0;
            }
            p = ch[p][c];
        }
        return cnt[p];
    }

    void erase(const char *str) {
        int p = 0;
        for (int i = 0; str[i]; ++i) {
            int c = str[i] - 'a';
            if (c < 0 || c >= maxc) return;
            if (ch[p][c] == -1) {
                return;
            }
            p = ch[p][c];
        }
        if (cnt[p] > 0) {
            --cnt[p];
        }
    }

    void print() {
        // 打印从 0 到 tot 的每个节点的 26 条边
        for (int i = 0; i <= tot; ++i) {
            cout << "node " << i << ": ";
            for (int j = 0; j < maxc; ++j) {
                cout << ch[i][j] << (j + 1 == maxc ? "" : " ");
            }
            cout<<"      " << cnt[i]<< endl;
        }
    }
};

int main() {
    Trie name;
    name.init();

    // 使用字面量时传入 const char* 不会有警告
    name.insert("barty");
    name.insert("bar");
    name.insert("islands");
    name.print();

    cout << "islands: " << name.find("islands") << endl;
    cout << "bar: " << name.find("bar") << endl;

    // 示例删除
    name.erase("bar");
    cout << "bar after erase: " << name.find("bar") << endl;

    return 0;
}