Trie在C ++中的实现 [英] Trie Implementation in C++

问题描述

我正在尝试执行 TopCoder上显示的字符串页面。我修改它一点，以存储用户的电话号码。我得到分段错误。可能有人请指出错误。

I am trying to implement the trie as shown on the TopCoder page. I am modifying it a bit to store the phone numbers of the users. I am getting segmentation fault. Can some one please point out the error.

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

在进行建议更改后添加了一个新函数：

Added a new function after making suggested changes:

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

推荐答案

更改this：

add(root->children[ch], name++, data);
// ---------------------^^^^^^

向此：

add(root->children[ch], ++name, data);
// ---------------------^^^^^^

这段代码中的其他问题我留给你，但这是你运行调用栈的原因。

The remainder of the issues in this code I leave to you, but that is the cause of your run up call-stack.

EDIT OP要求进一步分析，虽然我通常不这样做，但这是一个非常简单的应用程序，可以扩展。

EDIT OP ask for further analysis, and while I normally don't do so, this was a fairly simple application on which to expand.

这在几个地方完成：

 int index = getIndex(ch);
 root = root->children[ch];
 ... etc. continue using ch instead of index

它提出了一个问题： em>为什么我们只是要求一个索引，我们立即忽略并使用char？这是在 add（）和 getPhone（）。对于 children [] 数组中的所有查看，应该使用 index 。

It begs the question: "Why did we just ask for an index that we promptly ignore and use the char anyway?" This is done in add() and getPhone(). You should use index after computing it for all peeks inside children[] arrays.

此外， initialize（）函数需要被修改或彻底抛出以支持基于构造函数的解决方案， 。最后，如果这个trie应该跟踪生成的单词的使用计数和每个级别正在加入的前缀，我不清楚为什么你需要两个单词和前缀计数器，但在任何一种情况下更新在 add（）中递归的计数器应该在反向递归上反映。

Also, the initialize() function needs to be either revamped or outright thrown out in favor of a constructor-based solution, where that code truly belongs. Finally, if this trie is supposed to be tracking usage counts of words generated and prefixes each level is participating in, I'm not clear why you need both words and prefix counters, but in either case to update the counters your recursive decent in add() should bump them up on the back-recurse.

这篇关于Trie在C ++中的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！