Trie数据结构的实现

Question

我是编程新手。我正在尝试实现 Trie 数据结构。但是每当我尝试将字符串插入到 trie 中时，就会出现分段错误。

这里是节点class

class Node{
    public:
        Node *key[2];
        Node *parent;
        bool EOW;
        Node1(){
            this->key[0]=NULL;
            this->key[1]=NULL;
            this->parent = NULL;
            this->EOW = false;
        }
};

这是特里树 class

class Trie{
    public:
        Node *root;
        Trie(){
            root =  new Node();
        }

        void insertUtil(Node *root, char a[]);
        void insert(char a[]){
            // cout << root <<endl;
            // cout << root->key[0];
            insertUtil(root, a);
        }
};

这是 insertUtil 函数

void Trie::insertUtil(Node *root, char a[]){
    Node *temp = root;
    for(int idx=0;idx<5;idx++){
        cout << idx <<endl;
        int tmp_chr = a[idx]-'0';
        if(!(temp->key[1])){
            temp->key[a[idx]-'0'] = new Node();
            temp->key[a[idx]-'0']->parent = temp;
        }
        temp = temp->key[a[idx]-'0'];
    }
    temp->EOW = -1;
}

int main(){
    Trie t1;
    char b[5];
    cin >> b;
    t1.insert(b);
    cout << '*';
    cin >> b;
    t1.insert(b);
    cin >> b;
    t1.insert(b);
    cin >> b;
    t1.insert(b);
}

Answer 1

Node 的成员 key 声明为

Node *key[2];

所以它是一个包含两个指针的数组，并在 Trie::insertUtil、

中给出了这一行

int tmp_chr = a[idx]-'0';  // A variable ignored in the following code, BTW.

我假设 OP 试图插入的 "strings" 仅由字符 '0' 和 '1'.

组成

请注意，在发布的代码中，使用的 C 字符串中所需的空终止符被简单地忽略了，这本身就是一个错误，可以通过使用适当的 std::string 轻松修复。

另一个问题在同一个循环中：

for(int idx = 0; idx < 5; idx++)
{   //           ^^^^^^^                   It should stop before the null-terminator
    // (...)
    int tmp_chr = a[idx]-'0'; //           Are you sure that there are only '0' or '1'?
    if( !(temp->key[1]) )
    { //           ^^^                     1 is wrong, here, it should be temp->key[tmp_chr]
        temp->key[a[idx]-'0'] = new Node();
        //        ^^^^^^^^^^               Why not use tmp_chr here and in the following?
        // ...
    }
    // ...
}

Trie数据结构的实现

Implementation of Trie data structure

c++

data-structures

string-matching

trie