Obtention d'une erreur de segmentation lors de l'accès au membre struct dans C

Question

J'essaie d'implémenter un trie pour stocker des mots dans C, mais j'obtiens une erreur de segmentation lorsque j'essaie d'accéder à un membre struct.

Le code est ci-dessous:

#include <stdbool.h> 
#include <ctype.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

#define ALPHABET_SIZE 27 
#define SIZE 45 

//Trie data structure declaration 
typedef struct _dictionary { 
    bool is_word; 
    char letter; 
    struct _dictionary *children[ALPHABET_SIZE]; 
} dicto; 

dicto *DICT; 

//Function prototypes 
void insert(char *string); 
int toIndex(char s); 

int main() { 
    FILE *fp = fopen("small", "r"); 
    if (fp == NULL) { 
     printf("Could not open file\n"); 
     return 1; 
    } 

    char word[46]; 

    while (fgets(word, sizeof(word), fp)) { 
     insert(word); 
     if (feof(fp)) { 
      return 0; 
     } 
    } 
    return 2; 
} 

//Inserts word into trie 
void insert(char *string) { 
    dicto *trav; //Pointer to walk through the trie 
    trav = DICT; 
    for (int n = 0; n = strlen(string); n++) { 
     if (trav->children[toIndex(string[n])] == NULL) { 
      trav->children[toIndex(string[n])] = malloc(sizeof(DICT)); 
      trav->letter = string[n]; 
      trav = trav->children[toIndex(string[n])]; 
     } else { 
      trav->letter = string[n]; 
      trav = trav->children[toIndex(string[n])]; 
     } 

     if (trav->letter == '\0') { 
      trav->is_word = true; 
     } 
    } 
    return; 
} 

/** 
* Output alphabetic index from given input 
*/ 
int toIndex(char s) { 
    s = toupper(s); 
    int index = s - 65; 
    return index; 
} 

J'ai essayé de débogage avec Valgrind et GDB. La sortie de Valgrind est:

==1979== Memcheck, a memory error detector 
==1979== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al. 
==1979== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info 
==1979== Command: ./test_function1 
==1979== 
==1979== Invalid read of size 4 
==1979== at 0x8048684: insert (in /home/test_function1) 
==1979== by 0x80485F7: main (in /home/test_function1) 
==1979== Address 0xffffff00 is not stack'd, malloc'd or (recently) free'd 
==1979== 
==1979== 
==1979== Process terminating with default action of signal 11 (SIGSEGV) 
==1979== Access not within mapped region at address 0xFFFFFF00 
==1979== at 0x8048684: insert (in /home/test_function1) 
==1979== by 0x80485F7: main (in /home/test_function1) 
==1979== If you believe this happened as a result of a stack 
==1979== overflow in your program's main thread (unlikely but 
==1979== possible), you can try to increase the size of the 
==1979== main thread stack using the --main-stacksize= flag. 
==1979== The main thread stack size used in this run was 8388608. 
==1979== 
==1979== HEAP SUMMARY: 
==1979==  in use at exit: 344 bytes in 1 blocks 
==1979== total heap usage: 2 allocs, 1 frees, 4,440 bytes allocated 
==1979== 
==1979== LEAK SUMMARY: 
==1979== definitely lost: 0 bytes in 0 blocks 
==1979== indirectly lost: 0 bytes in 0 blocks 
==1979==  possibly lost: 0 bytes in 0 blocks 
==1979== still reachable: 344 bytes in 1 blocks 
==1979==   suppressed: 0 bytes in 0 blocks 
==1979== Reachable blocks (those to which a pointer was found) are not shown. 
==1979== To see them, rerun with: --leak-check=full --show-leak-kinds=all 
==1979== 
==1979== For counts of detected and suppressed errors, rerun with: -v 
==1979== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0) 
Segmentation fault (core dumped) 

Et en exécutant GDB, ressemble à l'erreur provient de la ligne 54:

if (trav->children[toIndex(string[n])] == NULL) 

Aucune idée sur ce qui pourrait se produire.

Answer 1

Il y a plusieurs problèmes dans votre code:

• tests feof(fp) ne fait pas ce que vous pensez, il est en fait inutile que fgets() retournera NULL à la fin du fichier.

• la boucle for (int n = 0; n = strlen(string); n++) ne se termine que n est recalculée que la longueur de la chaîne à chaque itération, utilisez plutôt:

  for (int n = 0, len = strlen(string); n < len; n++) { 
  

• lorsque vous allouez un nouveau nœud, vous devez initialiser la structure, sinon vous pouvez avoir un comportement indéfini car le bloc de mémoire renvoyé par malloc() n'est pas initialisé. Utilisez calloc() à la place. La fonction toIndex() ne renvoie pas nécessairement une valeur comprise entre 0 et 26. Vous ne devriez pas coder en dur la valeur de 'A' et vous devriez tester si le caractère est bien une lettre.

Voici une version modifiée:

#include <stdbool.h> 
#include <ctype.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

#define ALPHABET_SIZE 27 
#define SIZE 45 

//Trie data structure declaration 
typedef struct _dictionary { 
    bool is_word; 
    char letter; 
    struct _dictionary *children[ALPHABET_SIZE]; 
} dicto; 

dicto *DICT; 

//Function prototypes 
void insert(char *string); 
int toIndex(char s); 

int main(void) { 
    char word[SIZE + 1]; 
    FILE *fp = fopen("small", "r"); 
    if (fp == NULL) { 
     printf("Could not open file\n"); 
     return 1; 
    } 

    while (fgets(word, sizeof(word), fp)) { 
     insert(word); 
    } 
    return 0; 
} 

//Inserts word into trie 
void insert(char *string) { 
    dicto *trav = DICT; //Pointer to walk through the trie 

    for (int n = 0, len = strlen(string); n < len; n++) { 
     int index = toIndex(string[n]); 
     if (trav->children[index] == NULL) { 
      trav->children[index] = malloc(sizeof(DICT)); 
     } 
     trav->letter = string[n]; 
     trav = trav->children[index]; 
    } 
    trav->is_word = true; 
} 

/** 
* Output alphabetic index from given input (assuming ASCII) 
*/ 
int toIndex(char c) { 
    if (c >= 'a' && c <= 'z') 
     return c - 'a'; 
    if (c >= 'A' && c <= 'Z') 
     return c - 'A'; 
    return 26; /* not a letter */ 
} 

Answer 2

Ceci est juste une réponse rapide concernant l'un des problèmes possibles avec le code dans la question. Je n'ai pas lu le tout.

Après l'affectation suivante, la mémoire est pleine de données indésirable:

trav->children[toIndex(string[n])] = malloc(sizeof(dicto)); 

Vous seriez mieux soit en utilisant calloc (qui garantit la mémoire à remis à zéro):

trav->children[toIndex(string[n])] = calloc(sizeof(dicto), 1); 

ou zéro les données vous-même:

trav->children[toIndex(string[n])] = malloc(sizeof(dicto)); 
memset(trav->children[toIndex(string[n])], 0, sizeof(dicto)); 

Si vous conservez les données indésirables dans la mémoire, que e La condition suivante peut être fausse même si elle doit être vraie:

if(trav->children[toIndex(string[n])] == NULL) 

P.S.

En outre, sizeof(DICT) est la taille du pointeur , pas la structure . Vous pouvez envisager sizeof(*DICT) ou sizeof(dicto).