Структура данных - Trie C++, вставлять слова. Доступ к определению нарушения доступа

Question

Я кодирую словарь Trie как assigment, C++. Я продолжаю получать ошибку при вставке определенных букв в словах, особенно «l» и «t», если они не являются первой буквой.

Это ошибка

Необработанного исключения в 0x00EC5392 в A4Tries.exe: 0xC0000005: Access местоположения чтения нарушения 0x000032EC.

Проблема заключается в функции InsertTrie. Он разбивает на следующей строке

if (!current->branch[newkey[i] - 'a']) 

Im так путать, как работает код для нагрузок тестовых слов и затем вводит как «sdfl» или «СФО», «FFDF» разбить программу. Если кто-нибудь сможет определить проблему, я буду очень благодарен. Благодарю.

const int LETTERS = 26; 
typedef char Key[MAXLENGTH]; 
struct Trienode 
{ 
    Trienode *branch[LETTERS]; 
    EntryType *ref; 
}; 



class TrieType 
{ 
public: 
    TrieType(); 
    ~TrieType(); 
    TrieType(TrieType &originalTree); 
    void operator=(TrieType & originalTree); 
    void MakeEmpty(); 
    void InsertTrie(Key newkey, EntryType *newentry); 
    EntryType * TrieSearch(Key target); 
    bool DeleteTrie(Key delkey); 
    void PrintTrie(); 


private: 
    Trienode * root; 
}; 

TrieType::TrieType() 
{ 
    root = NULL; 

} 


TrieType::~TrieType() 
{ 


} 
TrieType::TrieType(TrieType &originalTree) 
{ 

} 

EntryType * TrieType::TrieSearch(Key target) 
{ 
    int i; 
    Trienode * current = root; 
    for (i = 0; i < MAXLENGTH && current; i++) 
     if (target[i] == '\0') 
      break; 
     else 
      current = 
      current->branch[target[i] - 'a']; 
    if (!current) 
     return NULL; 
    else 
     if (!current->ref) 
      return NULL; 

    return current->ref; 
} 


Trienode *CreateNode() 
{ 
    int ch; 
    Trienode *newnode = new Trienode; 
    for (ch = 0; ch < LETTERS; ch++) 
     newnode->branch[ch] = NULL; 

    newnode->ref = NULL; 

    return newnode; 
} 

void TrieType::InsertTrie(Key newkey, EntryType *newentry) 
{ 
    int i; 
    Trienode *current; 
    if (!root) 
     root = CreateNode(); 
    current = root; 
    for (i = 0; i < MAXLENGTH; i++) 
     if (newkey[i] == '\0') 
      break; 
     else 
     { 
      if (!current->branch[newkey[i] - 'a']) 
       current->branch[newkey[i] - 'a'] = CreateNode(); 
      current = current->branch[newkey[i] - 'a']; 
     } 
    if (current->ref != NULL) 
     cout << "\nTried to insert a duplicate key." << endl; 
    else 
     current->ref = newentry; 

} 



    const int MAXLENGTH = 10; 
class EntryType 
{ 
public: 
    EntryType(); 
    EntryType(char * key); 
    EntryType(EntryType & entry); 
    ~EntryType(); 
    bool operator== (const EntryType& item) const; 
    bool operator!= (const EntryType& item) const; 
    void EntryKey(char word[]); 
    void PrintWord(); 

private: 
    char entryKey[MAXLENGTH]; 
}; 


EntryType::EntryType() 
{ 

} 
EntryType::~EntryType() 
{ 

} 

void EntryType::EntryKey(char word[]) 
{ 
    for (int i = 0; i < 10; i++) 
    { 
     entryKey[i] = word[i]; 
    } 
} 

void EntryType::PrintWord() 
{ 
    cout << entryKey << endl; 
} 

В главном

void insert(TrieType & trie) 
{ 
    Key word; 
    cout << "Please enter the word you would like to enter: " << endl; 
    cin >> word; 

    EntryType* newEntry = new EntryType; 
    newEntry->EntryKey(word); 


    trie.InsertTrie(word, newEntry); 


} 

Answer 1

Вот почему профессиональные программисты используют assert s

{ 
     if (!current->branch[newkey[i] - 'a']) 
      current->branch[newkey[i] - 'a'] = CreateNode(); 
     current = current->branch[newkey[i] - 'a']; 
    } 

Когда newkey[i] не строчная буква, приведенный выше код устанавливает current равным мусор, то в следующий раз через цикл используются current и seg faults.

Некоторая другая часть кода должна нести ответственность за то, чтобы к тому времени, когда вы сюда попадете, у вас есть только строчные буквы. Но так как это не очевидно для тех, кто отлаживает эту часть кода, должно быть утверждение.

{ 
     assert(newkey[i]>='a' && newkey[i]<='z'); 
     if (!current->branch[newkey[i] - 'a']) 
      current->branch[newkey[i] - 'a'] = CreateNode(); 
     current = current->branch[newkey[i] - 'a']; 
    } 

Затем вы можете запустить отладочную сборку программы и либо выяснить неисправность была вызвана тем, что в других местах кода, который позволял другие символы, чем строчные буквы, чтобы добраться сюда, или вы можете увидеть, что не является проблема и лучше сосредоточиться на поиске некоторых менее вероятных дефектов.