我正在尝试实现 TopCoder 中所示的 trie页。我正在对其进行一些修改以存储用户的电话号码。我遇到段错误。有人可以指出错误吗。
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node{
int words;
int prefix;
long phone;
struct node* children[26];
};
struct node* initialize(struct node* root) {
root = new (struct node);
for(int i=0;i<26;i++){
root->children[i] = NULL;
}
root->word = 0;
root->prefix = 0;
return root;
}
int getIndex(char l) {
if(l>='A' && l<='Z'){
return l-'A';
}else if(l>='a' && l<='z'){
return l-'a';
}
}
void add(struct node* root, char * name, int data) {
if(*(name)== '\0') {
root->words = root->words+1;
root->phone = data;
} else {
root->prefix = root->prefix + 1;
char ch = *name;
int index = getIndex(ch);
if(root->children[ch]==NULL) {
struct node* temp = NULL;
root->children[ch] = initialize(temp);
}
add(root->children[ch],name++, data);
}
}
int main(){
struct node* root = NULL;
root = initialize(root);
add(root,(char *)"test",1111111111);
add(root,(char *)"teser",2222222222);
cout<<root->prefix<<endl;
return 0;
}
在进行建议更改后添加了一个新函数:
void getPhone(struct node* root, char* name){
while(*(name) != '\0' || root!=NULL) {
char ch = *name;
int index = getIndex(ch);
root = root->children[ch];
++name;
}
if(*(name) == '\0'){
cout<<root->phone<<endl;
}
}
最佳答案
改变这个:
add(root->children[ch], name++, data);
// ---------------------^^^^^^
对此:
add(root->children[ch], ++name, data);
// ---------------------^^^^^^
我将此代码中的其余问题留给您,但这是您运行调用堆栈的原因。
编辑 OP 要求进一步分析,虽然我通常不这样做,但这是一个相当简单的应用程序,可以扩展。
这是在几个地方完成的:
int index = getIndex(ch);
root = root->children[ch];
... etc. continue using ch instead of index
它回避了一个问题:“为什么我们只是要求一个我们立即忽略并且无论如何都使用 char 的索引?”这是在 add 中完成的()
和 getPhone()
。在为 children[]
数组中的所有 peeks 计算之后,您应该使用 index
。
此外,initialize()
函数需要改进或彻底抛弃,以支持基于构造函数的解决方案,该代码真正属于该解决方案。最后,如果这个 trie 应该跟踪每个级别参与的生成的单词和前缀的使用计数,我不清楚为什么你需要 both 单词和前缀计数器,但在任何一种情况下都需要更新您在 add()
中递归体面的计数器应该在反向递归上增加它们。
关于c++ - C++ 中的 Trie 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16124056/