我已经部分完成了cs50的pset5,但是每次尝试运行程序时,由于某种原因,我都会遇到段错误。
在load
函数中,我打开词典文件并通过调用init_table()
初始化哈希表。然后,我使用fscanf
扫描词典文件,为词典中的每个单词创建一个node *n
,然后将单词从dict_word
复制到此节点中。然后,我使用hash
函数(基于djb2)存储该节点单词的索引。
如果是table[index] == NULL
,则将table[index]
和名为head
的节点都设置为等于节点n
,然后将下一个地址设置为等于NULL
。否则,我将下一个节点设置为table[index]
,将table[index]
设置为当前节点n
。
我尚未释放任何内存,因为这将在另一个名为unload
的函数中完成,但是我怀疑我当前的问题可能是由于不同的原因。任何帮助将不胜感激。
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.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 (A-Z)
const unsigned int N = 5381;
// Hash table
node *table[N];
// initialize hash table (set all values to NULL)
// reference video: https://youtu.be/2Ti5yvumFTU
void init_table()
{
for (int i = 0; i < N; i++)
{
table[i] = NULL;
}
}
// Hashes word to a number
// hash function: djb2
// retrieved from http://www.cse.yorku.ca/~oz/hash.html
unsigned int hash(const char *word)
{
unsigned int hash_value = N;
int c;
while ((c = *word++))
{
hash_value = ((hash_value << 5) + hash_value) + c; /* hash * 33 + c */
}
return hash_value;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// open dictionary file, check if NULL
FILE *dict_file = fopen(dictionary, "r");
if (dict_file == NULL)
{
return false;
}
init_table();
// create char for each dictionary word (max length + nul)
char dict_word[LENGTH + 1];
// create beginning node that serves as first item in linked list
node *head;
// scan until end of file
while (fscanf(dict_file, "%s", dict_word) != EOF)
{
// create a node n for each word and copy string into it
node *n = malloc(sizeof(node));
if (n == NULL)
{
return false;
}
strcpy(n->word, dict_word);
// hash the word and store as index (which tells which linked list to use)
int index = hash(n->word);
// if table[index] is NULL, set it and head as node n, set next node as NULL
if (table[index] == NULL)
{
head = table[index] = n;
n->next = NULL;
}
// otherwise set next node as table[index], table[index] as current node n
else
{
n->next = head;
table[index] = n;
}
}
return true;
}
EDIT:在阅读Boris Lipschitz的答案之后,我已经意识到了这个问题,并且进一步学习了如何使用调试器来解决它。我修改了const unsigned int N = 5381
并将N
的值更改为25
,以表示字母表中每个字母的存储桶(尽管我稍后可能会更改此值以优化程序)。对于我的hash
函数,就像鲍里斯(Boris)所说的,没有什么可以阻止hash_value
越过N
,因此我将return hash_value;
更改为return hash_value % N;
,这将使我的输出在适当的范围内我桌子的范围。
hash
函数中绝对没有阻止它达到5381或更高的值。然后使用它访问table
...动臂,分段错误。
反问:为什么不只在调试器中运行代码?您会比我们中任何人都可以更快地知道答案的方式。