исправить ошибку сегментации в TrieE C ++ - PullRequest
Новая
       6

исправить ошибку сегментации в TrieE C ++

0 голосов
/ 11 февраля 2019

Я использую Trie-реализацию для хранения и поиска слов на языке программирования C ++.При использовании функции search () я получаю ошибку сегментации при поиске определенного слова.Кажется, что ошибка произошла при проверке, если структура имеет значение null.

вот сообщение об ошибке: 

Program received signal SIGSEGV, Segmentation fault.
0x000055555555b2ff in search (this=0x55555577ee70, 
wordlist=0x55555577ef00, word="a1g6os") at test.cc:30
            if (!pCrawl->children[index])

вот исходный код: 

#include <bits/stdc++.h> 
using namespace std; 
const int ALPHABET_SIZE = 26; 

struct TrieNode { 
struct TrieNode *children[ALPHABET_SIZE]; 

bool isEndOfWord; 
}; 



struct TrieNode *getNode(void) { 
    struct TrieNode *pNode =  new TrieNode; 
     pNode->isEndOfWord = false; 

    for (int i = 0; i < ALPHABET_SIZE; i++) 
        pNode->children[i] = NULL; 

    return pNode; 
} 



void insert(struct TrieNode *root, string key) { 
    struct TrieNode *pCrawl = root; 

    for (int i = 0; i < key.length(); i++) { 
        int index = key[i] - 'a'; 
        if (!pCrawl->children[index]) 
            pCrawl->children[index] = getNode(); 

        pCrawl = pCrawl->children[index]; 
   } 

   // mark last node as leaf 
   pCrawl->isEndOfWord = true; 
} 

// Returns true if key presents in trie, else 
// false 
bool search(struct TrieNode *root, string key) { 
    struct TrieNode *pCrawl = root; 

    for (int i = 0; i < key.length(); i++) { 
        int index = key[i] - 'a'; 
        if (!pCrawl->children[index]) 
             return false; 

        pCrawl = pCrawl->children[index]; 
    } 

    return (pCrawl != NULL && pCrawl->isEndOfWord); 
} 

int main() { 
    string keys[] = {"the", "a", "there", 
                "answer", "any", "by", 
                 "bye", "their" }; 
    int n = sizeof(keys)/sizeof(keys[0]); 

    struct TrieNode *root = getNode(); 

    for (int i = 0; i < n; i++) 
        insert(root, keys[i]); 

    // Search for different keys 
    search(root, "a1g6os")? cout << "Yes\n" : 
                     cout << "No\n"; 
    return 0; 
}

1 Ответ

0 голосов
/ 12 февраля 2019

@ Некоторые программист чувак и @JohnnyJohansson указали причину.Живой тест показал, где код читает массив за пределами.На самом деле исправить это легко, когда вы понимаете, что происходит.Ниже приведен фиксированный код, если вы не можете понять его самостоятельно.Прямой тест этого здесь segfault.stensal.com 

#include<iostream>
using namespace std; 
const int ALPHABET_SIZE = 75; // increase the range

struct TrieNode { 
struct TrieNode *children[ALPHABET_SIZE]; 

bool isEndOfWord; 
}; 



struct TrieNode *getNode(void) { 
    struct TrieNode *pNode =  new TrieNode; 
     pNode->isEndOfWord = false; 

    for (int i = 0; i < ALPHABET_SIZE; i++) 
        pNode->children[i] = NULL; 

    return pNode; 
} 



void insert(struct TrieNode *root, string key) { 
    struct TrieNode *pCrawl = root; 

    for (int i = 0; i < key.length(); i++) { 
        int index = key[i] - '0';  // lower the low bound
        if (!pCrawl->children[index]) 
            pCrawl->children[index] = getNode(); 

        pCrawl = pCrawl->children[index]; 
   } 

   // mark last node as leaf 
   pCrawl->isEndOfWord = true; 
} 

// Returns true if key presents in trie, else 
// false 
bool search(struct TrieNode *root, string key) { 
    struct TrieNode *pCrawl = root; 

    for (int i = 0; i < key.length(); i++) { 
        int index = key[i] - '0';  // lower the low bound
        if (!pCrawl->children[index]) 
             return false; 

        pCrawl = pCrawl->children[index]; 
    } 

    return (pCrawl != NULL && pCrawl->isEndOfWord); 
} 

int main() { 
    string keys[] = {"the", "a", "there", 
                "answer", "any", "by", 
                 "bye", "their" }; 
    int n = sizeof(keys)/sizeof(keys[0]); 

    struct TrieNode *root = getNode(); 

    for (int i = 0; i < n; i++) 
        insert(root, keys[i]); 

    // Search for different keys 
    search(root, "a1g6os")? cout << "Yes\n" : 
                     cout << "No\n"; 
    return 0; 
}
...