Trie Implementation in C++

Question

Я пытаюсь реализовать trie, как показано на странице TopCoder. Я немного модифицирую его, чтобы хранить номера телефонов пользователей. Я получаю ошибку сегментации. Может кто-нибудь указать на ошибку.

#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); 
// ---------------------^^^^^^ 

Остальная часть вопросов в этом код, который я оставляю вам, но это причиной вашего вызова вызова.

EDIT OP запросить дальнейший анализ, и, хотя я обычно этого не делаю, это было довольно простое приложение для расширения.

Это делается в нескольких местах:

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

Напрашивается вопрос: «Почему мы просто попросить индекса, который мы быстро игнорируемых и использовать символ в любом случае» Это делается в add() и getPhone(). Вы должны использовать index после вычисления его для всех подглядывающих в пределах children[] массивов.

Кроме того, функция initialize() должна быть обновлена ​​или полностью выброшена в пользу решения на основе конструктора, где этот код действительно принадлежит. Наконец, если это три должно отслеживать количество использованных слов и префиксы, на которых участвует каждый уровень, я не понимаю, зачем вам и слов и префиксных счетчиков, но в любом случае для обновления счетчиков ваш рекурсивный порядочный в add() должны ударить их по спине.