CS50 pset5拼写行54条件跳转错误 [英] CS50 pset5 speller line 54 conditional jump error
问题描述
当我编译并运行我的代码时，看起来好像代码可以工作，但是当我使用help50运行Valgrind时，它说"== 1295 ==条件跳转或移动取决于未初始化的值".我不知道如何解决此问题.Help50告诉我专注于代码的第54行，但是我不明白什么地方出了问题，它以前一直在起作用，现在是一个错误.我不明白的是什么错误/
When I compile and run my code it sort of looks like the code works, but when I run Valgrind with help50, it says "==1295== Conditional jump or move depends on uninitialized value(s)" I don't get how to fix this problem. Help50 tells me to focus on line 54 of my code, but I don't understand what is wrong, it was working before, now it is a mistake. What I don't understand is what the mistake is/
#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;
}
推荐答案
您遇到了很多问题.导致基于未初始化值的 valgrind 条件移动的主要问题是您无法初始化-> next 指针 NULL 中的load()，例如:
You have a large number of problems. The primary problem leading to the valgrind conditional move based on uninitialized value is your failure to initialize the ->next pointer NULL in load(), e.g.:
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]; 是指向的指针的VLA(可变长度数组)节点，而不是指向 node 的指针数组.这是导致错误的问题:
C is not C++. const unsigned int N = 10000; does not create an integer constant resulting in node *table[N]; being a VLA (Variable Length Array) of pointers to node rather than an array of pointers to node. This is a problem resulting in the error:
error: variably modified ‘table’ at file scope
(it is unclear how you were able to compile with gcc with the VLA. See C11 Standard - 6.7.6.2 Array declarators(p2))
相反，您需要 #define N 的值，使用全局 enum 或移动 table 来阻止或作用域.(请注意， N 的大小至少应为原来的十倍，以保持哈希冲突次数-哈希表 Load Factor [ buckes_used/total_buckets ]在 0.7 )
Instead, you need to #define the value for N, use a global enum or move the declaration of table to block or function scope. (note, N should be at least ten-times as large to keep the number of hash collisions -- and the hash table Load Factor [buckes_used/total_buckets] below 0.7)
类型问题
您的哈希函数声明为:
unsigned int hash(const char *word)
它返回类型为 unsigned int 的类型，您不应将结果分配给 int .模将使返回的值保持在正整数值的范围内，这很麻烦.
It returns type unsigned int, you should not be assigning the result to int. While the modulo will keep the value returned in the range of positive integer values, that is playing with fire.
// int hashnum = hash(lword);
unsigned int hashnum = hash(lword);
在其他情况下，如果bit-31是 1 ，则对 int 的赋值将导致该值为负-如果用作数组索引，则结果为在未定义行为中.
In other circumstances, if bit-31 is 1, your assignment to int will result in the value being negative -- and if used as an array index, results in Undefined Behavior.
unload()函数比所需的要复杂得多.您有一个全局数组 table 用作哈希表.唯一需要释放的是存储桶中不为空的所有节点.因此，您只需要遍历每个存储桶并检查它是否为空.如果不是，则遍历以bucket元素开头的列表，以释放每个节点，例如:
The unload() function is much much more convoluted that necessary. You have a global array table used as your hash table. The only thing that needs to be freed are any nodes in buckets that are not empty. So you simply need to loop over each bucket and check if it is empty. If not, then traverse the list that starts with the bucket element freeing each node, e.g.:
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] 只是在转换为小写字母后再次分配值.只需将其转换为小写并分配:
There are several places where you code isn't wrong, but involves additional copying or unnecessary calls to free(), etc.. For example in check(), there is no need to assign to lword[i] just to assign the value again after converting to lowercase. Just convert to lowercase and assign:
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()失败时，它将返回 NULL .没有分配任何东西.尽管 free(NULL); 是无害的( free()会检查您)，但这根本没有必要.
In load(), if the allocation of new_node fails, there isn't any need to free(new_node);, as shown earlier. Why? When malloc() fails, it returns NULL. There is nothing allocated. Though free(NULL); is harmless (free() will check for you), it's simply unnecessary.
导致的内存使用量
如果您进行了所有更改，则代码现在将运行而不会出现内存错误，并将释放分配的内存，例如
If you make all of the changes, your code will now run without memory error and will free the memory it allocated, e.g.
$ 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 ，答案似乎正确.
I haven't check correctness of all answers, but for lalaland.txt the answer appears correct.
仔细检查一下，如果还有其他问题，请告诉我.
Look things over and let me know if you have further questions.
这篇关于CS50 pset5拼写行54条件跳转错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
