由於Trie中的字符串結構導致程序崩潰

我正在實現一個trie，它將在達到單詞末尾時打印定義。我使用字符串進行定義。但是，當我將定義分配給字符串。由於Trie中的字符串結構導致程序崩潰

#include <bits/stdc++.h> 
#define ALPHABET_SIZE 26 
#define CHAR_TO_INDEX(c) ((int)c - (int)'0') 
using namespace std; 
typedef struct trienode{ 

string definition;   //For Definition of the word 
bool isLeaf; 
struct trienode *children[ALPHABET_SIZE]; 

}node; 
node* getnode() 
{ 
    int i; 
    node *t=new node(); 
    t->isLeaf=false; 
    for(i=0;i<26;i++) 
    { 
     t->children[i]=NULL; 
    } 
    return t; 
} 
void insert(node *root,string s) 
{ 
    node *crawler=root; 
    int level,index,length=s.length(); 
    for(level=0;level<length;level++) 
    { 
     index= CHAR_TO_INDEX(s[level]); 
     if(crawler->children[index]==NULL) 
     { 
      crawler->children[index]=getnode(); 
     } 
     crawler=crawler->children[index]; 
    } 
    crawler->definition= "Definition of" + s; //Here is the code crashing,when I am assigning the definition 
    crawler->isLeaf=true; 
}

來源

2016-06-25 tesla

請發表[mcve]。 – PaulMcKenzie

您可能會傳遞不完全大寫的字符串。 – sameerkn

你的代碼有很多問題。

越大，我看到，即（我想）導致崩潰的問題，是在下面的行

#define CHAR_TO_INDEX(c) ((int)c - (int)'0')

的CHAR_TO_INDEX()宏旨在從索引值0返回到9時c是代表數字的字符（從0到9）。

的問題是，你用它來獲得0-25的數，當是c和a或z（我想）A和Z之間。

舉例：當c是r,(int)'r' - (int)'0')是114 - 48 = 66。因此，您嘗試在children的插槽66中只訪問26個插槽。

要解決這個問題，你可以通過這種方式

#define CHAR_TO_INDEX(c) (c - (int)'a')

改寫CHAR_TO_INDEX()並調用它以這種方式

index = CHAR_TO_INDEX(std::tolower(s[level]));

但我認爲這是一個壞主意，使用宏，所以我建議你用一些檢查來定義一個簡單的函數;像這樣

int charToIndec (int ch) 
{ 
    if ((ch < int(`a`)) || (ch > int(`z`))) 
    ; // throw something 

    return ch - int(`a`); 
}

其他建議，沒有特別的命令......

您使用C++，不是C;所以trienode不需要該typedef;你可以簡單地寫

struct trienode { 
    string definition; //For Definition of the word 
    bool isLeaf; 
    trienode *children[ALPHABET_SIZE]; 
};

，並簡單地用結構作爲trienode

還是那句話：你使用C++，不是C;所以我不明白你爲什麼寫一個函數getnode()應該是（恕我直言）的構造函數trienode;像

trienode() : definition(""), isLeaf(false) 
{ 
    for (int i = 0 ; i < ALPHABET_SIZE ; ++i) 
     children[i] = NULL; 
}

應該以這種方式

crawler->children[index]= new trienode;

可以使用在任何情況下，你已經定義ALPHABET_SIZE爲26;請記住隨處使用它而不是26（當26是children的尺寸時）;所以用getnode()替代26與ALPHABET_SIZE

包括;什麼是bits/stdc++.h？在不知道它，我甚至不知道它是否包含C++標準。建議：使用標準包括。

最後的建議：您使用new作爲節點;記得要delete分配的節點;如果您可以使用C++ 11編譯器，請考慮假設使用std::unique_ptr來避免此需求。

對不起，我的英語不好。

來源

2016-06-25 12:05:33 max66

由於Trie中的字符串結構導致程序崩潰

回答

相關問題