1

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

1 に答える 1

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

それは次のような疑問を投げかけます: 「なぜ、すぐに無視して char を使用するインデックスを要求したのでしょうか?」これは および で行われadd()ますgetPhone()。配列index内のすべてのピークに対して計算した後に使用する必要があります。children[]

また、initialize()そのコードが真に属するコンストラクターベースのソリューションを優先して、関数を改良するか、完全に破棄する必要があります。最後に、このトライが生成された単語の使用回数と各レベルが参加している接頭辞を追跡することになっている場合、単語と接頭辞の両方のカウンターが必要な理由はわかりませんが、どちらの場合でもカウンターを更新するには、再帰的な適切なカウンターを使用するadd()必要がありますそれらを逆再帰でぶつけます。

于 2013-04-20T19:31:28.157 に答える