c++ - C++ 中的 Trie 实现

Question

我正在尝试实现 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;
     }
 }

Answer 1

改变这个:

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() 中递归体面的计数器应该在反向递归上增加它们。