Trie Implementation in C++

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

이있는 문제의 나머지 코드, 내가 너에게 맡긴다. 런업 콜 스택의 원인.

EDIT OP는 추가 분석을 요청합니다. 일반적으로 그렇게하지는 않지만 확장 할 수있는 매우 간단한 응용 프로그램입니다.

이

은 여러 곳에서 이루어집니다 :

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

그것은 질문을 구걸한다 : "왜 우리는 단지 우리가 신속하게 가을 무시하고 어쨌든 문자를 사용하여 인덱스를 요청 않았다"을 이것은 add()과 getPhone()에서 이루어집니다. 배열 children[] 내의 모든 peek에 대해 계산 한 후에 index을 사용해야합니다.

또한 initialize() 함수는 수정되거나 완전히 코드가 포함 된 생성자 기반 솔루션을 위해 완전히 제거해야합니다. 마지막으로,이 트 리가 생성 된 단어의 사용 횟수를 추적하고 각 레벨에 참여하는 접두사가 참여하는 것으로 가정하면 나는 왜 이 필요 한 가를 모르겠다. 단어와 접두사 카운터 모두를 카운터하지만 카운터를 업데이트하려면 재귀 적으로 괜찮은 add()의 경우 뒤쪽에 재발생 할 때이를 범프해야합니다.