Блог

Я очень новичок в программировании, и я пытался закончить курс cs50, не просто копируя чужой код и пытаясь понять, почему мой не будет работать. В настоящее время я застрял в pset5 (уже пару дней), код компилируется нормально, но не работает, и valgrind возвращает:

 Process terminating with default action of signal 11 (SIGSEGV)
==1697==  Access not within mapped region at address 0x0
==1697==    at 0x401A86: hash (dictionary.c:53)
==1697==    by 0x401B71: load (dictionary.c:78)
==1697==    by 0x4012BE: main (speller.c:40)
 

вот мой код:

 // Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <strings.h>
#include "dictionary.h"

/*
** Global variable that indicates the number of words loaded in the dictionary
*/
unsigned int loadedWords = 0;

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH   1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = 54;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    if (table[hash(word)]->next == NULL)
    {
        return false;
    }
    else if (strcasecmp(word, table[hash(word)]->word) == 0)
    {
        return true;
    }
    else
    {
        return check(table[hash(word)]->next->word);
    }
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    char lowerCaseWord[LENGTH   1];
    for (int i = 0; word[i]; i  )
    {
        lowerCaseWord[i] = tolower(word[i]);
    }
    unsigned int hashNumber = ((int)word[0]   (int)word[1]) % 53;
    return hashNumber;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        printf("Could not openn");
        return false;
    }
    char word[LENGTH   1];
    while (fscanf(file, "%s", word) != EOF)
    {
        node *buffer = malloc(sizeof(node));
        if (buffer == NULL)
        {
            return false;
        }
        strcpy(buffer->word, word);
        buffer->next = table[hash(word)]->next;
        table[hash(word)]->next = buffer;
        loadedWords   ;
    }
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    return loadedWords;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < N - 1; i  )
    {
        while (table[i] != NULL)
        {
            node *tmp = table[i]->next;
            free(table[i]);
            table[i] = tmp;
        }
    }
    return true;
}
 

Может кто-нибудь, пожалуйста, указать, почему это не будет работать и / или как это исправить? Я не ищу полного решения проблемы, я просто хотел бы знать, в чем моя ошибка или в чем моя логика неверна. Спасибо.

что касается инструкции OPs: код компилируется нормально,

вот выходные данные компилятора. Что ясно показывает, что опубликованный код НЕ компилируется,

 gcc -ggdb3 -Wall -Wextra -Wconversion -pedantic -std=gnu11 -c "untitled1.c" -o "untitled1.o" 

untitled1.c:26:7: error: variably modified ‘table’ at file scope
   26 | node *table[N];
      |       ^~~~~

untitled1.c: In function ‘check’:

untitled1.c:31:15: warning: implicit declaration of function ‘hash’ [-Wimplicit-function-declaration]
   31 |     if (table[hash(word)]->next == NULL)
      |               ^~~~

untitled1.c: At top level:

untitled1.c:46:14: error: conflicting types for ‘hash’
   46 | unsigned int hash(const char *word)
      |              ^~~~

untitled1.c:31:15: note: previous implicit declaration of ‘hash’ was here
   31 |     if (table[hash(word)]->next == NULL)
      |               ^~~~

untitled1.c: In function ‘hash’:

untitled1.c:51:28: warning: conversion from ‘int’ to ‘char’ may change value [-Wconversion]
   51 |         lowerCaseWord[i] = tolower(word[i]);
      |                            ^~~~~~~

untitled1.c:53:31: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
   53 |     unsigned int hashNumber = ((int)word[0]   (int)word[1]) % 53;
      |                               ^

untitled1.c:48:10: warning: variable ‘lowerCaseWord’ set but not used [-Wunused-but-set-variable]
   48 |     char lowerCaseWord[LENGTH   1];
      |          ^~~~~~~~~~~~~

untitled1.c: In function ‘unload’:

untitled1.c:92:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘unsigned int’ [-Wsign-compare]
   92 |     for (int i = 0; i < N - 1; i  )
      |                       ^

Compilation failed.
 

что касается:

 char lowerCaseWord[LENGTH   1];
for (int i = 0; word[i]; i  )
{
    lowerCaseWord[i] = tolower(word[i]);
}
 

массив lowerCaseWord[] нигде не используется, поэтому этот блок кода можно удалить

Вы продолжаете обращаться к следующему указателю в первом узле списка, прежде чем узнаете, пуст ли этот список. Позвольте мне объяснить. table представляет собой массив указателей. node *table[N]; Это определение создает массив из N указателей на узел. Когда вы индексируете в таблицу, вы получаете обратно указатель. Так table[2] же как и указатель, и он может быть или не быть нулевым в зависимости от того, было ли что-либо добавлено в этот список. Оно, безусловно, равно НУЛЮ, прежде чем load добавит к нему что-либо.

В проверке у вас есть эта строка:

 if (table[hash(word)]->next == NULL) // possible seg fault
 

Что, если возвращаемый хэш индекса приводит к пустому списку? Тогда это становится NULL->next

Использование оператора arrow разыменовывает указатель, а разыменование NULL является незаконным. Вы хотите проверить, является ли текущий указатель узла нулевым, следующий на данный момент не имеет значения.

Использование рекурсии здесь также является плохой идеей. Было бы быстрее и эффективнее использовать память, чтобы просто перебирать каждый узел в списке.

Вы допускаете ту же ошибку в своей функции загрузки:

 buffer->next = table[hash(word)]->next; // why next?
table[hash(word)]->next = buffer; // why next?
 

запись в buffer->next здесь правильная. Вы только что вызвали malloc, чтобы выделить для него место, поэтому вы записываете в следующий указатель в этом узле. Но тогда вы принимаете значение table[hash(word)]->next вместо просто table[hash(word)]

Похоже, вы не понимаете, с чего начинается список. Попытка чтения next никогда не переходит к первому узлу в списке.