Erreur de segmentation de l'implémentation Trie C++

Question

J'implémente une structure de données trie simple en C++ en utilisant struct et pointters. Quand je passe une chaîne à ajouter à trie, cela donne une erreur de segmentation dans la fonction addString().

struct node { 
    char ch; 
    node *link[26]; 

    node() : link(){} 
}; 

node head; 


void addString(node *n, string s) { 
    if (!s.length()) return; 

    if (!n -> link[(int)s[0] - 97]) { 
     node m; 
     m.ch = s[0]; 
     n -> link[(int)s[0] - 97] = &m; 
    } 
    addString(n -> link[(int)s[0] - 97], s.substr(1)); 
} 

int main(){ 
    addString(&head, "red"); 
    return 0; 
} 

J'ai essayé les instructions de débogage et même imprimé et mis en correspondance les valeurs d'adresse du noeud nouvellement créé et celui passé récursivement, ils étaient identiques. PS J'utilise un nœud de tête comme état epsilon.

Answer 1

Vous utilisez des adresses d'objets alloués sur la pile. node m; est sur la pile. Il sera supprimé dès que vous quittez un bloc if dans lequel il est déclaré. Et vous affectez son adresse à un nœud n -> link[(int)s[0] - 97] = &m; qui vit plus longtemps que cela.

Answer 2

n -> link[(int)s[0] - 97] = &m; 

vous stockez l'adresse de m alors qu'il est détruit à la fin de son champ d'application.

Vous devez repenser votre projet en gérant correctement la mémoire.

Answer 3

Il y a deux problèmes qui pourraient expliquer une erreur de segmentation:

• le premier est que vous ajoutez un pointeur vers un objet local m dans votre tableau de liens. Dès que vous revenez de la fonction, le pointeur se balancera et vous aurez UB. Allouer correctement m: node *m = new node; Mieux: utiliser unique_ptr au lieu de pointeurs bruts.

• Vous supposez que la chaîne ne contient que des lettres minuscules entre 'a' et 'z'. Si la chaîne contient autre chose, vous allez sortir des limites et peut provoquer une corruption de la mémoire et UB. Vous devez avoir au moins un assert()

Voici un petit correctif pour résoudre les problèmes, en fonction de votre structure actuelle et de l'approche:

struct node { 
    ... 
    node(char c=0) : link(), ch(c) {} 
    ~node() { for (int i=0;i<26; i++) delete link[i]; } 
}; 
... 
void addString(node *n, string s) { 
    if (!s.length()) return; 
    size_t c = tolower(s[0]); 
    if (c<'a' || c>'z') return; // char not ok-> do like end of string 
    if (!n -> link[c-'a']) { 
     n -> link[c-'a'] = new node(c); 
    } 
    addString(n -> link[c-'a'], s.substr(1)); 
}  

Notez que lorsque vous utilisez des pointeurs dans un struct, vous avez être très prudent sur le rule of 3. Cependant, cela ne vous fera pas de mal, car vous ne copiez pas encore de nœuds.

Online demo