在 C++ 中实现 Trie 时出现分段错误
Getting a segmentation fault while implementing Trie in c++
改天又出现了另一个我不明白的段错误,我第一次尝试实施尝试,事实证明这是一个相当大的挑战,我认为如果有人能告诉我什么会很有帮助我做错了,我想也可能会帮助我更好地理解 OOP,因为我认为错误与此有关。
The fault happens while searching and I wasn't able to understand it using the debugger myself.
代码如下:
#include <vector>
#include <iostream>
using std::string, std::cout, std::vector;
class TrieNode {
private:
bool isLeaf;
vector<TrieNode*> ar = vector<TrieNode*>(26);
public:
TrieNode() {
isLeaf = false;
for(int i = 0; i < 26; i++) ar[i] = nullptr;
}
void insert(TrieNode *root, string key) {
TrieNode *crawl = root;
for(int i = 0; i < key.size(); i++) {
if(!crawl->ar[key[i]]) {
crawl->ar[key[i]] = new TrieNode();
}
crawl = crawl->ar[key[i]];
}
crawl->isLeaf = true;
}
bool search(TrieNode *root, string key) {
TrieNode *crawl = root;
for(int i = 0; i < key.size(); i++) {
if(!crawl->ar[key[i]]) {
return false;
}
crawl = crawl->ar[key[i]];
}
return crawl->isLeaf;
}
};
int main() {
TrieNode* head = new TrieNode();
head->insert(head, "hello");
cout << head->search(head, "hello");
}
如果您的字符串总是小写,请将您的 ar[key[i]]
设为 ar[key[i]-'a']
。
基本上,key[i]是['a'-'z']范围内的一个字符。当它被隐式转换为 int 时,它不在 [0,25] 的范围内,而是等于它们的 ascii 值。
改天又出现了另一个我不明白的段错误,我第一次尝试实施尝试,事实证明这是一个相当大的挑战,我认为如果有人能告诉我什么会很有帮助我做错了,我想也可能会帮助我更好地理解 OOP,因为我认为错误与此有关。
The fault happens while searching and I wasn't able to understand it using the debugger myself.
代码如下:
#include <vector>
#include <iostream>
using std::string, std::cout, std::vector;
class TrieNode {
private:
bool isLeaf;
vector<TrieNode*> ar = vector<TrieNode*>(26);
public:
TrieNode() {
isLeaf = false;
for(int i = 0; i < 26; i++) ar[i] = nullptr;
}
void insert(TrieNode *root, string key) {
TrieNode *crawl = root;
for(int i = 0; i < key.size(); i++) {
if(!crawl->ar[key[i]]) {
crawl->ar[key[i]] = new TrieNode();
}
crawl = crawl->ar[key[i]];
}
crawl->isLeaf = true;
}
bool search(TrieNode *root, string key) {
TrieNode *crawl = root;
for(int i = 0; i < key.size(); i++) {
if(!crawl->ar[key[i]]) {
return false;
}
crawl = crawl->ar[key[i]];
}
return crawl->isLeaf;
}
};
int main() {
TrieNode* head = new TrieNode();
head->insert(head, "hello");
cout << head->search(head, "hello");
}
如果您的字符串总是小写,请将您的 ar[key[i]]
设为 ar[key[i]-'a']
。
基本上,key[i]是['a'-'z']范围内的一个字符。当它被隐式转换为 int 时,它不在 [0,25] 的范围内,而是等于它们的 ascii 值。