Trie 实现运行时错误

Question

我正在尝试用 C++ 实现 Trie，但出现运行时错误...

这是我的代码：

#include <bits/stdc++.h>
using namespace std;

struct trie{
    bool word = false;
    trie* adj [26];
    trie(){}

    void add(char* s){
        trie* t = this;

        while(s){
            if(t->adj[s[0] - 'a'] == NULL){
                trie nova = create(s);
                t->adj[s[0] - 'a'] = &nova;
                return;
            }
            else{
                t = t->adj[s[0] - 'a'];
            }
            s++;
        }
    }

    trie create(char* s){
        trie t;
        trie* point = &t;
        while(s){
            point->adj[s[0] - 'a'] = new trie();
            point = point->adj[s[0] - 'a'];
            s++;
        }
        point->word = true;
        return t;
    }

    void seek(){
        trie* t = this;
        run(t, "");
    }

    void run(trie* t, string s){
        if(t->word){
            cout<<s<<"\n";
        }
        for(int i = 0; i < 26; i++){
            if(t->adj[i] != NULL){
                run(t->adj[i], s + char('a' + i));
            }
        }
    }
};

int main(){
    trie t;
    t.add("ball");
    t.add("balloon");
    t.add("cluster");
    t.seek();
}

它是这样工作的：

假设我要添加一个词；
如果单词的字母不在 trie 中
```
 if(t->adj[s[0] - 'a'] == NULL)
```
- 使用 void create 创建新的 trie 并将 t->adj[s[0] - 'a'] 设置为新的 trie
否则转到下一个字母并重复该过程
```
 t = t->adj[s[0] - 'a'];
```

我做错了什么？我是新手使用指针，我想我一定是错误地使用了其中一个（或多个）...有什么问题吗？

Answer 1

在您的代码中发现了几个问题。

一个问题在于堆栈局部变量 trie nova 在超出范围时被删除。

代码

...
if(t->adj[s[0] - 'a'] == NULL){
    trie nova = create(s);
    t->adj[s[0] - 'a'] = &nova; // address points to memory on stack
    return;
} // nova is deleted. t->adj[s[0] - 'a'] is pointing to trash now.
...

要处理它，您应该使用指针和 new 运算符。

...
if(t->adj[s[0] - 'a'] == NULL){
    trie* novaPtr = create(s + 1);
    t->adj[s[0] - 'a'] = novaPtr; 
    return;
} 
...

trie* create(char* s){
    trie *t = new trie();
    trie* point = t;
    while(*s){
        point->adj[s[0] - 'a'] = new trie(); // allocate memory on heap
        point = point->adj[s[0] - 'a'];
        s++;
    }
    point->word = true;
    return t; // the pointer on heap memeroy is returned.
}

正如@bkVnet 所注意到的，您还应该检查整个地方的 while 循环中的字符串终止。 while(*s) - 意思是 s 没有指向 '[=17=]' 符号而不是 while(s).

您应该在结构构造函数中使用 NULL 初始化您的 adj 指针。那么在 if(t->adj[s[0] - 'a'] == NULL).

NULL

构建代码。

trie() {
    for (int i = 0; i < 26; i++) adj[i] = NULL;
}

第 create(s); 行存在逻辑错误，应删除一个字符 - create(s + 1).

Full working code example

Trie 实现运行时错误

Trie implementation runtime error

c++

pointers

trie