c语言 - CS50 拼写检查器中的分段错误.为什么?

Question

我正在研究CS50 pset5拼写器，但不断收到分段错误错误。Debug50 表明问题出在load函数的实现中n->next = table[index];行，即第 110 行。我试图修改，但我无法弄清楚为什么它会出错。在我的代码下面，有人可以帮助我吗？

// Implements a dictionary's functionality
#include <stdbool.h>
#include <strings.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.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 = 150000;
// Nodes counter
int nodes_counter = 0;
// Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// TODO
int hash_value = hash(word);
node *cursor = malloc(sizeof(node));
if (cursor != NULL)
{
cursor = table[hash_value];
}
if (strcasecmp(cursor->word, word) == 0) // If word is first item in linked list
{
return 0;
}
else // Iterate over the list by moving the cursor
{
while (cursor->next != NULL)
{
if (strcasecmp(cursor->word, word) == 0) // If word is found
{
return 0;
}
else
{
cursor = cursor->next;
}
}
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// Adaptation of FNV function, source https://www.programmingalgorithms.com/algorithm/fnv-hash/c/
const unsigned int fnv_prime = 0x811C9DC5;
unsigned int hash = 0;
unsigned int i = 0;
for (i = 0; i < strlen(word); i++)
{
hash *= fnv_prime;
hash ^= (*word);
}
return hash;
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// Open Dictionary File (argv[1] or dictionary?)
FILE *file = fopen(dictionary, "r");
if (file == NULL)
{
printf("Could not open filen");
return 1;
}
// Read until end of file word by word (store word to read in word = (part of node)?)
char word[LENGTH + 1];
while(fscanf(file, "%s", word) != EOF)
{
// For each word, create a new node
node *n = malloc(sizeof(node));
if (n != NULL)
{
strcpy(n->word, word);
//Omitted to avoid segmentation fault n->next = NULL;
nodes_counter++;
}
else
{
return 2;
}
// Call hash function (input: word --> output: int)
int index = hash(word);
// Insert Node into Hash Table
n->next = table[index];
table[index] = n;
}
return false;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// Return number of nodes created in Load
if (nodes_counter > 0)
{
return nodes_counter;
}
return 0;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// TODO
for (int i = 0; i < N; i++)
{
node *cursor = table[i];
while (cursor->next != NULL)
{
node *tmp = cursor;
cursor = cursor->next;
free(tmp);
}
}
return false;
}

Answer 1

代码中存在多个问题：

• 如果node *table[N];是常量表达式，则不能仅将其定义为全局对象N。N被定义为const unsigned int，但N在C中不是一个常量表达式(尽管它是在C++中)。程序编译只是因为编译器接受它作为非可移植扩展。使用宏或枚举。
• 一旦在check()中分配cursor，您就会覆盖它。无需在此函数中分配节点。
• hash()函数应为仅在大小写不同的单词生成相同的哈希。
• hash()函数仅使用word中的第一个字母。
• hash()函数可以返回哈希值>=N。
• fscanf(file, "%s", word)应防止缓冲区溢出。
• 在取消引用cursor之前，不要检查它是否为非 nullunload()

这是一个修改版本：

// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.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
enum { N = 150000 };
// Nodes counter
int nodes_counter = 0;
// Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word) {
int hash_value = hash(word);
// Iterate over the list by moving the cursor
for (node *cursor = table[hash_value]; cursor; cursor = cursor->next) {
if (strcasecmp(cursor->word, word) == 0) {
// If word is found
return true;
}
}
// If word is not found
return false;
}
// Hashes word to a number
unsigned int hash(const char *word) {
// Adaptation of FNV function, source https://www.programmingalgorithms.com/algorithm/fnv-hash/c/
unsigned int fnv_prime = 0x811C9DC5;
unsigned int hash = 0;
for (unsigned int i = 0; word[i] != ''; i++) {
hash *= fnv_prime;
hash ^= toupper((unsigned char)word[i]);
}
return hash % N;
}
// Loads dictionary into memory, returning true if successful, else a negative error number
int load(const char *dictionary) {
// Open Dictionary File (argv[1] or dictionary?)
FILE *file = fopen(dictionary, "r");
if (file == NULL) {
printf("Could not open filen");
return -1;
}
// Read until end of file word by word (store word to read in word = (part of node)?)
char word[LENGTH + 1];
char format[10];
// construct the conversion specifier to limit the word size
//    read by fscanf()
snprintf(format, sizeof format, "%%%ds", LENGTH);
while (fscanf(file, format, word) == 1) {
// For each word, create a new node
node *n = malloc(sizeof(node));
if (n == NULL) {
fclose(file);
return -2;
}
strcpy(n->word, word);
n->next = NULL;
nodes_counter++;
// Call hash function (input: word --> output: int)
int index = hash(word);
// Insert Node into Hash Table
n->next = table[index];
table[index] = n;
}
fclose(file);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void) {
// Return number of nodes created in Load
return nodes_counter;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void) {
for (int i = 0; i < N; i++) {
node *cursor = table[i];
table[i] = NULL;
while (cursor != NULL) {
node *tmp = cursor;
cursor = cursor->next;
free(tmp);
}
}
return true;
}