所以我知道在互联网上找人调试我的代码是无耻的,但我已经把我豌豆大小的大脑榨干了,我仍然不能解决这个问题(我的橡皮鸭已经逃离了我的办公桌,以获得一些和平)。开个玩笑,我在pset5上遇到了麻烦:speller,来自cs50。事情是这样的,在完成了所有繁琐的编码过程并最终能够编译我的代码 * 没有错误 * 之后,我当然得到了恼人的segfault。
现在是“有趣和有趣”的部分:当执行cs50教学人员提供的check50函数时,我得到所有的绿色刻度,就好像我的代码正在工作...这很让人困惑
下面是我的代码:
// 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;
// Choose number of buckets in hash table
const unsigned int N = 150001; //Bigger than word count for enough buckets (Not concerned about memory space)
// Hash table
node *table[N];
// Variable with the amount of words in the dictionary
int count = 0;
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// hash word for value in table
int hash_value = hash(word);
// access list at hash value and compare words (strcompare)
node *p = table[hash_value];
// loop to end of linked list
while (p != NULL)
{
if (strcasecmp(word, p->word) == 0)
{
return true;
}
p = p->next;
}
return false;
}
// Hashes word to a number
/*CREDIT: JR(joseph28robinson) from website medium.com for helping with HASH TABLE theory*/
unsigned int hash(const char *word)
{
long x = 0;
// Improve this hash function
for (int i = 0, n = strlen(word); i < n; i++)
{
// I am unsure if the subtraction of 'A' is needed
x += toupper(word[i]);
}
return x % N;
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// Open file
FILE *dict_file = fopen(dictionary, "r");
if (dictionary == NULL)
{
// Could not open dictionary
return false;
}
// Buffer for reading file
char new_word[LENGTH + 1];
// Scan file for every word and create a new node for each one
// (NOT SURE WHY ==1 instead of != EOF /*CREDIT: Creig Estey comment from stackoverflow.com*/)
while (fscanf(dict_file, "%s", new_word) == 1)
{
// Get word's hash value
int hash_value = hash(new_word);
// Malloc space for node
node *p = malloc(sizeof(node));
if (p == NULL)
{
return false;
}
// Fill in new node's variables
strcpy(p->word, new_word);
// TODO: Check for available space in hash's table hash_value node or create linked list
if (table[hash_value] == NULL)
{
// First item in bucket so pointer to NULL
p->next = NULL;
}
else
{
// Not first item in bucket so pointer to first item in list (LINKED LIST THEORY)
p->next = table[hash_value];
}
// Point bucket to new node
table[hash_value] = p;
// Update size of dict
count++;
}
// Close file
fclose(dict_file);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// No need to insert if function to check if dict loaded since count is already set to 0 (it will return 0 if not loaded)
return count;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// Iterate through all buckets of hash table
for (int i = 0; i < N; i++)
{
// Access hash's table bucket
node *p = table[i];
// Loop through all items (linked list) in bucket
while (p != NULL)
{
// Use trav pointer not to orphan list
node *trav = p;
// Point to next element in list
p = p->next;
// Free trav
free(trav);
}
// End of loop condition to return true
if (p == NULL && i == N - 1)
{
return true;
}
}
return false;
}
我已经尝试使用调试器,并且在处理内存时检查了每一个可能的(据我所知)NULL返回。我假设问题就在这里,尽管在这一点上我不太确定。
1条答案
按热度按时间5uzkadbs1#
阅读字典文件时,代码中存在潜在问题:
如果字典中有一个单词超过
LENGTH
个字符,fscanf()
将导致缓冲区溢出,试图将其存储到new_word
中。您应该将最大字符数传递给
fscanf()
或使用自定义函数读取单词:然后你可以用以下代码替换
while
循环:哈希函数可以改进:
char
值在传递给toupper()
时必须转换为(unsigned char)
,因为此函数仅针对正值定义,并且EOF
和char
可能在目标平台上签名。此外,hash
应该是无符号的,以避免溢出问题和模运算的负结果: