Trie数据结构的实现

Question

我是个编程新手。我正在尝试实现Trie dataStructure。但是每当我尝试在trie中插入一个字符串时，就会出现分段错误。

下面是Node类

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;
        }
};

这是trie类

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试图插入的“字符串”只由字符'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?
        // ...
    }
    // ...
}