CS50 Speller segfault

rfbsl7qr  于 2023-10-16  发布在  其他
关注(0)|答案(1)|浏览(106)

我不明白为什么会出现分段错误。我对哈希表的理解是,你为输入(在这种情况下是一个字符串)计算一个哈希值,并使用该值作为表的索引,允许你立即检查输入是否存在,而无需实际搜索它。下面是我的hash函数代码:

typedef struct node
{
    char word[LENGTH + 1];
}
node;
// set a size for the hash table
const unsigned int N = 100049;

// Hash table
node *table[N];

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

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{

    unsigned int hash_value = 7;
    for (int i = 0; word[i] != '\0'; i++)
    {
       hash_value = word[i] * hash_value;
    }

    return hash_value % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    for (int j = 0; j < N; j++)
    {
        table[j] = NULL;
    }
    FILE *infile = fopen(dictionary, "r");
    if (infile == NULL)
    {
        return false;
    }

    char *word = NULL;
    while (fscanf(infile, "%s", word) != EOF)
    {
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            return false;
        }

        int hash_value = hash(word);
        table[hash_value] = new_node;
        strcpy(new_node->word, word);
        wordc ++;

    }

    fclose (infile);

    return true;
}

它编译得很好,但使用小字典和小文本,我得到了一个分割错误(核心转储)错误。
thanks in advance

5kgi1eie

5kgi1eie1#

代码至少存在以下问题:

fscanf()调用无效

下面的代码通过"%s"传递了一个无效的指针来存储 string,导致了 undefined behavior(UB)。

char *word = NULL;
while (fscanf(infile, "%s", word) != EOF  // Bad
  ...

相反,传递一个指向可存储内存的有效指针。
另外,不要使用"%s",因为它缺少 width。使用 width

#define STR_EVALUATE(x)   #x
#define STRINGIFY(x)      STR_EVALUATE(x)
char word[LENGTH + 1];
while (fscanf(infile, "%" STRINGIFY(LENGTH) "s", word) == 1) {
  ...

未完成测试

代码只测试 some 指针是否在哈希表中。代码也应该检查它是否是一个匹配的字符串。

// if (table[hash(word)] != NULL) {
size_t index = hash(word)
if (table[index] != NULL && strcmp(table[index], word) != 0) { 
  ...

缺点:hash应该返回size_t
缺点:hash不应该返回与anagrams相同的值

相关问题