Get-Seg-Fehler beim Zugriff auf Strukturelement in C

Question

Ich versuche, einen Trie zum Speichern von Wörtern in C zu implementieren, aber ich bekomme einen Segmentierungsfehler beim Versuch, ein Strukturelement zugreifen.

Der Code ist unten:

#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; 
} 

ich Debuggen es mit Valgrind und GDB ausprobiert habe. Die Ausgabe von Valgrind ist:

==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) 

Und von GDB läuft, sieht aus wie der Fehler kommt aus der Leitung 54:

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

keine Ahnung, was passiert sein könnte.

Answer 1

Es gibt mehrere Probleme im Code:

• Prüfung feof(fp) nicht tun, was Sie denken, es ist eigentlich unnötig, da fgets()NULL am Ende der Datei zurück.

• die Schleife for (int n = 0; n = strlen(string); n++) nie als n endet, wenn die Länge der Zeichenfolge bei jeder Iteration neu berechnet wird, verwenden Sie stattdessen:

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

• , wenn Sie einen neuen Knoten zuordnen, können Sie die Struktur initialisieren müssen, sonst Sie haben möglicherweise ein nicht definiertes Verhalten, da der von malloc() zurückgegebene Speicherblock nicht initialisiert ist. Verwenden Sie stattdessen calloc().

• Die Funktion toIndex() gibt nicht unbedingt einen Wert im Bereich 0 bis 26 zurück. Sie sollten den Wert 'A' nicht fest codieren und Sie sollten testen, ob das Zeichen tatsächlich ein Buchstabe ist.Hier

ist eine modifizierte Version:

#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

Dies ist nur eine schnelle Antwort auf eines der möglichen Probleme mit dem Code in der Frage. Ich habe die ganze Sache nicht gelesen.

Nach der folgenden Zuordnung ist der Speicher voll von Junk-Daten:

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

Sie wäre besser dran, entweder mit calloc (die den Speicher garantiert werden auf Null gesetzt):

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

Oder löschen Sie die Daten selbst:

Wenn Sie die Junk-Daten im Speicher halten, th Die folgende Bedingung könnte falsch sein, selbst wenn sie wahr sein sollte:

P.S.

Auch ist sizeof(DICT) die Größe des Zeiger, nicht die Struktur. Sie könnten sizeof(*DICT) oder sizeof(dicto) betrachten.