Может кто-нибудь помочь мне найти segfault здесь?

Question

EDIT: Итак, оказывается, что «index» не возвращался к 0. Ну тогда. Это фиксировало один segfault. Но все равно получается другой segfault. Работаю над этим.

node* new_node(void){ 
    node* ptr = malloc(sizeof(node)); 
    for (int i = 0; i<27; i++) { 
     ptr->next[i] = NULL; 
    } 
    return ptr; 
} 
bool load(const char* dictionary) 
{ 
    FILE* dict = fopen(dictionary, "r"); 
    node* ptr = new_node; 
    char word[LENGTH+1]; 
    int index = 0; 
    for (int c = fgetc(dict); c!=EOF; c = fgetc(dict)){ 
     if(c!='\n'){ 
      word[index]=c; 
      index++; 
     } 
     else { 
      for(int x=0; x<=index; x++){ 
       int ch = (word[x] == '\'') ? 26 : tolower(word[x])-'a'; 
       if (ptr->next[ch] == NULL){ 
        ptr->next[ch] = new_node; 
       } 
       ptr = ptr->next[ch]; 
      } 
      ptr->end=true; 
     } 
    } 
    return true; 
} 

Я пытаюсь реализовать структуру Trie данных для словаря, но моя программа, кажется, где-то в сегментации этой функции. Похоже, что я не могу прикрепить его даже с помощью GDB, так кто-то может мне помочь?

Узел определяется как таковой:

typedef struct node{ 
    bool end; 
    struct node* next[27]; 
} node; 

Файл словаря:

a 
aaa 
aaas 
aachen 
aalborg 
aalesund 
aardvark 
aardvark's 
aardvarks 
aardwolf 

(...)

Answer 1

У вас есть много проблем в вашем коде:

• При выделении памяти с malloc, она неиницализированные. инициализируйте его непосредственно после его выделения, так что указатели NULL действительно равны нулю. (calloc, двоюродный брат аллаллока, инициализирует всю память до нуля.)

• Когда петля над словом, вы должны и не включать index:

  for (int x = 0; x < index; x++) ... 
  

• Когда вы нашли конец слова, вы должны сбросить index 0. В противном случае, вы будете добавлять к старому слову и переполнению буфера. (Вероятно, вы также должны применять верхнюю границу «index».)

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

• Как есть, ваш твой является локальным для вашей функции. Верните корневой узел, чтобы другие функции могли использовать trie, или NULL при сбое.

Исправить это, и у вас будет функция без сбоев. (Он по-прежнему утечки памяти и не может построить правильно синтаксического дерева.)

node *load(const char *dictionary) 
    { 
     FILE *dict = fopen(dictionary, "r"); 
     node *head = calloc(1, sizeof(node)); 

     char word[LENGTH + 1]; 
     int index = 0; 

     for (int c = fgetc(dict); c != EOF; c = fgetc(dict)) { 
      if (c != '\n') { 
       word[index] = c; 
       index++; 
      } else { 
       node *ptr = head; 

       for (int x = 0; x < index; x++) { 
        int ch = (word[x] == '\'') ? 26 : tolower(word[x]) - 'a'; 
        if (ptr->next[ch] == NULL) { 
         ptr->next[ch] = calloc(1, sizeof(node)); 
        } 
        ptr = ptr->next[ch]; 
       } 
       ptr->end = true; 
       index = 0; 
      } 
     } 

     return head; 
    } 

Answer 2

Линия:

node* ptr = new_node; 

и

ptr->next[ch] = new_node; 

не вызывают функцию, но назначают адрес функции ptr. Вызовите функцию вместо этого.

Эта проблема может быть предотвращена, если предупреждения компилятора: -Wall и -Wextra были включены.

---

Нет проверок границ на массиве word. Используйте значение LENGTH, чтобы проверить, находится ли индекс в границах перед его использованием.

Неясно, что делает оператор if внутри цикла for. Кажется, что каждый раз, когда найдена новая строка, весь массив word добавляется в дерево, но index не сбрасывается, поэтому один и тот же массив добавляется несколько раз. В какой-то момент index будет указывать за пределы, вызывая неопределенное поведение. Вы должны сбросить index после использования массива word.

Answer 3

Вы забыли перезагрузить index в 0 в начале цикла.

Вы должны также использовать calloc(1, sizeof(node)) вместо malloc(sizeof(node)), чтобы избежать неинициализации памяти. Я предлагаю вам использовать valgrind, чтобы помочь вам отслеживать проблемы такого рода в вашем коде.

Answer 4

Вы должны фильтровать знаки препинания \ недопустимые символы немного больше. Любой символ за пределами [a-z|A-Z|\n|\\] приведет к сбою программы из-за

int ch = (word[x] == '\'') ? 26 : tolower(word[x])-'a'; 
if (ptr->next[ch] == NULL){ 

Учитывая, что вы открываете файл, может быть пространство где-то или какой-то неожиданный характер. Вам нужно что-то вроде

if(c!='\n'){ 
     int num = (c == '\'') ? 26 : tolower(c)-'a'); 
     if(num >=0 && num < 27) 
     { 
      word[index]=c; 
      index++; 
     } 
    }