CS50 Speller 中的分段错误。为什么？
Segmentation fault in CS50 Speller. Why?
我正在研究 CS50 pset5 Speller，但我一直收到分段错误。 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 file\n");
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;
}
您的代码中存在多个问题：
如果 N 是常量表达式，则 node *table[N]; 不能仅定义为全局对象。 N 被定义为 const unsigned int，但 N 在 C 中不是常量表达式（尽管它在 C++ 中）。你的程序编译只是因为编译器接受它作为不可移植的扩展。使用宏或枚举。- 一旦在
check() 中分配，您就覆盖 cursor。本函数无需分配节点
hash() 函数应该为仅大小写不同的单词生成相同的散列。hash()函数只使用word中的第一个字母。hash()函数可以return一个散列值>=N.fscanf(file, "%s", word) 应防止缓冲区溢出。- 在
unload() 中取消引用之前不检查 cursor 是否为非空
这是修改后的版本：
// 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] != '[=10=]'; 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 file\n");
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;
}
我正在研究 CS50 pset5 Speller，但我一直收到分段错误。 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 file\n");
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;
}
您的代码中存在多个问题：
-
如果
node *table[N];不能仅定义为全局对象。N被定义为const unsigned int，但N在 C 中不是常量表达式（尽管它在 C++ 中）。你的程序编译只是因为编译器接受它作为不可移植的扩展。使用宏或枚举。- 一旦在
check()中分配，您就覆盖cursor。本函数无需分配节点 hash()函数应该为仅大小写不同的单词生成相同的散列。hash()函数只使用word中的第一个字母。hash()函数可以return一个散列值>=N.fscanf(file, "%s", word)应防止缓冲区溢出。- 在
unload() 中取消引用之前不检查
N 是常量表达式，则 cursor 是否为非空
这是修改后的版本：
// 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] != '[=10=]'; 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 file\n");
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;
}