C++詞典索引樹實現

我得到段錯誤在我insert上線功能：C++詞典索引樹實現

current->isWord = true;

一切編譯罰款，沒有警告或錯誤（g++ -Wall -Wextra）。我的main函數只調用一次insert函數，它不起作用。這是我的代碼;這是我.h和.cpp文件之間的混合體：

const int alphabetSize = 26; 

struct Node 
{ 
    bool isWord; 
    Node* child[alphabetSize]; 
}; 

Dictionary::Dictionary() 
{ 
    initNode(head); //Node* head; is defined in my .h file under private: 
} 

bool Dictionary::isPrefix(string s) 
{ 
    Node* current = endOfString(s, false); 
    if (current == NULL) 
    { 
     return false; 
    } 
    else 
    { 
     return true; 
    } 
} 

bool Dictionary::isWord(string s) 
{ 
    Node* current = endOfString(s, false); 
    if (current == NULL) 
    { 
     return false; 
    } 
    else 
    { 
     return current->isWord; 
    } 
} 

void Dictionary::insert(string s) 
{ 
    Node* current = endOfString(s, true); 
    current->isWord = true; //segfault here 
} 

//initializes a new Node 
void Dictionary::initNode(Node* current) 
{ 
    current = new Node; 
    current->isWord = false; 
    for (int i = 0; i < alphabetSize; i++) 
    { 
     current->child[i] = NULL; 
    } 
} 

//returns a pointer to the Node of the last character in the string 
//isInsert tells it whether it needs to initialize new Nodes 
Node* Dictionary::endOfString(string s, bool isInsert) 
{ 
    Node* current = head; 
    Node* next = head; 
    for (unsigned int i = 0; i < s.length(); i++) 
    { 
     if (isalpha(s[i]) == true) 
     { 
      int letter = (tolower(s[i]) - 'a'); 
      next = current->child[letter]; 
      if (next == NULL) 
      { 
       if (isInsert == false) 
       { 
        return NULL; 
       } 

       initNode(next); 
       current->child[letter] = next; 
      } 
      current = current->child[letter]; 
     } 
    } 

    return current; 
}

來源

2013-04-09 Paulrevere21

爲什麼在insert（）中沒有NULL檢查？ – iammilind 2013-04-09 03:51:58

@iammilind：因爲它像其他時間一樣將'true'傳遞給'endOfString'而不是'false'。 – icktoofay 2013-04-09 03:52:45

@icktoofay，如果在'Dictionary :: endOfString（..）'方法中'head'爲NULL並且s.length（）= 0，會發生什麼？我們還需要在這種情況下進行NULL檢查。 – iammilind 2013-04-09 03:57:32

initNode創建一個新的Node並初始化它，但它被丟棄。因爲current是按值傳遞的，所以在函數內部修改它時，更改不會傳播到initNode之外。直接的解決方法是通過引用：

void Dictionary::initNode(Node*& current)

來源

2013-04-09 03:55:20 icktoofay

真棒，簡單的修復，謝謝 – Paulrevere21 2013-04-09 04:42:52

的問題是在這裏：

//initializes a new Node 
void Dictionary::initNode(Node* current) 
{ 
    current = new Node; 
    current->isWord = false; 
    for (int i = 0; i < alphabetSize; i++) 
    { 
     current->child[i] = NULL; 
    } 
}

current是按值傳遞的，所以當你改變的方法current要變更副本傳入的內容，而不是外部變量。嘗試傳遞一個Node** current這是一個指針指向你的指針，所以你可以編輯原始變量。你會這樣稱呼它; initNode(&next);和您將取消引用當前的方法以編輯原始變量。

來源

2013-04-09 03:55:02 Patashu

C++詞典索引樹實現

回答

相關問題