CS50 pset5 speller line 54 条件跳转错误

Question

当我编译和运行我的代码时，它看起来有点像代码工作，但是当我运行 Valgrind 和 help50 时，它说 “==1295== 条件跳转或移动取决于未初始化的值” 我不知道如何解决这个问题。 Help50 告诉我要关注代码的第 54 行，但我不明白哪里出了问题，之前它可以工作，现在是一个错误。我不明白的是错误是什么/

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

// 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 = 10000;
int i = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    char lword[LENGTH+1];
    for(i = 0; i < strlen(word); i++)
    {
        lword[i] = word[i];
        lword[i] = tolower(lword[i]);
    }
    node *current;
    int hashnum = hash(lword);
    if(table[hashnum] == NULL)
    return false;
    current = table[hashnum];
    while(current->next != NULL)
    {
        if(strcmp(current->word, word) == 0)
        return true;
        else
        current = current->next;
    }
    return false;
}

// Hashes word to a number
// Hash function from cs50.stackexchange
unsigned int hash(const char *word)
{
    int n;
    unsigned int hash_value = 0;
    for (i = 0, n = strlen(word); i < n; i++)
    {
         hash_value = (hash_value << 2) ^ word[i];
    }
    return hash_value % N; //N is size of hashtable
}
// Loads dictionary into memory, returning true if successful else false
// adopted from github user
int word_count = 0;
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }
    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) != EOF)
    {
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            free(new_node);
            return false;
        }
        strcpy(new_node->word, word);
        int h = hash(new_node->word);
        node *head = table[h];
        if (head == NULL)
        {
            table[h] = new_node;
            word_count++;
        }
        else
        {
            new_node->next = table[h];
            table[h] = new_node;
            word_count++;
        }
    }
    fclose(file);
    return true;
}


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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for(i=0;i<10000;i++)
    {
        for(i = 0; i < 10000; i++)
    {
        while(table[i] != NULL)
        {
            char *retval = NULL;
            if (table[i]->next == NULL)
            {
                retval = table[i]->word;
                free(table[i]);
                return retval;
            }
            else
            {
                node * current = table[i];
                while (current->next->next != NULL)
                {
                    current = current->next;
                }
                retval = current->next->word;
                free(current->next);
                current->next = NULL;
            }
        }
    }
    }
return true;
}

Answer 1

你有很多问题。导致 valgrind 基于未初始化值的条件移动的主要问题是您未能初始化 load() 中的 ->next 指针 NULL，例如：

        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
//             free(new_node);                  /* not necessary */
            return false;
        }
        strcpy(new_node->word, word);
        new_node->next = NULL;                  /* must initialize NULL */

这将解决 valgrind 问题。

C 不是 C++。 const unsigned int N = 10000; 不会创建整数常量，导致 node *table[N]; 成为指向 node 的指针的 VLA（可变长度数组）而不是指向 node 的指针数组。这是导致错误的问题：

error: variably modified ‘table’ at file scope

（不清楚您是如何通过 VLA 使用 gcc 进行编译的。参见 C11 Standard - 6.7.6.2 Array declarators(p2)）

相反，您需要 #define N 的值，使用全局 enum 或将 table 的声明移动到块或函数作用域。（注意，N 应该至少 ten-times 保持散列冲突的数量——以及散列 table 负载因子 [buckes_used/total_buckets] 下面 0.7)

类型很重要

您的哈希函数声明为：

unsigned int hash(const char *word)

它 returns 键入 unsigned int，您不应将结果分配给 int。而取模会使返回的值保持在正整数值范围内，那是在玩火。

//     int hashnum = hash(lword);
    unsigned int hashnum = hash(lword);

在其他情况下，如果第 31 位是 1，您对 int 的赋值将导致该值为负数——如果用作数组索引，则会导致 未定义的行为.

unload() 函数比必要的复杂得多。您有一个全局数组 table 用作您的散列 table。唯一需要释放的是桶中非空的所有节点。所以你只需要遍历每个桶并检查它是否为空。如果不是，则遍历以释放每个节点的桶元素开头的列表，例如：

bool unload(void)
{
//     for(size_t i=0; i<10000;i++)       /* you have a constant -- use it */
    for(size_t i=0; i<N;i++)
    {
        node *n = table[i];
        while (n) {
            node *victim = n;
            n = n->next;
            free (victim);
        }
    }
    
    word_count = 0;
    
    return true;
}

不必要的代码

有几个地方你的代码没有错，但涉及到额外的复制或不必要的调用free()等。例如在check()中，没有必要分配给lword[i]只是转小写后重新赋值。只需转换为小写并分配：

    for (size_t i = 0; i <= strlen(word); i++)
        lword[i] = tolower(word[i]);
//     {
//         lword[i] = word[i];
//         lword[i] = tolower(lword[i]);
//     }

在load()中，如果new_node的分配失败，则不需要free(new_node);，如前所示。为什么？当 malloc() 失败时，它 returns NULL。没有分配任何东西。尽管 free(NULL); 是无害的（free() 会为您检查），但根本没有必要。

导致内存使用

如果您进行了所有更改，您的代码现在运行不会出现内存错误，并且会释放它分配的内存，例如

$ valgrind ./bin/speller texts/lalaland.txt > test/lalaland.txt
==28984== Memcheck, a memory error detector
==28984== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==28984== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==28984== Command: ./bin/speller texts/lalaland.txt
==28984==
==28984==
==28984== HEAP SUMMARY:
==28984==     in use at exit: 0 bytes in 0 blocks
==28984==   total heap usage: 143,095 allocs, 143,095 frees, 8,022,392 bytes allocated
==28984==
==28984== All heap blocks were freed -- no leaks are possible
==28984==
==28984== For counts of detected and suppressed errors, rerun with: -v
==28984== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

我没有检查所有答案的正确性，但 lalaland.txt 的答案似乎是正确的。

检查一下，如果您还有其他问题，请告诉我。

CS50 pset5 speller line 54 条件跳转错误

CS50 pset5 speller line 54 conditional jump error

c

cs50