我在哈佛 cs50 类(class)的 pset5 中实现加载和卸载函数时遇到问题。当我运行它时,出现段错误,当我运行 valgrind 时,它告诉我在加载时分配的所有节点都没有被释放。
几天来我一直在尝试解决这个问题,我已经为我的卸载函数尝试了几种不同的实现,但没有任何效果。我认为错误可能出在我的加载函数中。有人可以帮我解决这个问题吗?
/****************************************************************************
* dictionary.c
*
* Computer Science 50
* Problem Set 5
*
* Implements a dictionary's functionality.
***************************************************************************/
#include <stdbool.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include "dictionary.h"
#define HASHTABLE_SIZE 5000
// create word counter for size
int wordCount = 0;
// linked link struct
typedef struct node
{
// word's length + NULL character
char word[LENGTH + 1];
struct node* next;
}
node;
// Hashtable array
node* hashtable[HASHTABLE_SIZE];
// hash function from study.cs50.net
int hash_function(char* key)
{
// initialize index to 0
int index = 0;
// sum ascii values
for (int i = 0; key[i] != 0; i++)
{
index += toupper(key[i]) - 'A';
}
return index % HASHTABLE_SIZE;
}
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
// create variable to hold word
char temp[LENGTH + 1];
// convert every character in word to lowercase
for (int i = 0, n = strlen(word); i < n; i++)
{
if (isalpha(word[i]))
{
temp[i] = tolower(word[i]);
}
}
// get hashed word's index
int hash_index = hash_function(temp);
// find head of that index
node* head = hashtable[hash_index];
// traverse through linked list
for (node* cur = head; cur != NULL; cur = cur->next)
{
// find if linnked list contains word
if (strcmp(cur->word, word) == 0)
{
return true;
}
}
return false;
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char* dictionary)
{
// // open file
FILE* file = fopen(dictionary, "r");
// check if file exists
if (file == NULL)
{
return false;
}
// word length plus NULL character
char word[LENGTH + 1];
// iterate through every word of the dictionary
while (fscanf(file, "%s\n", word) != EOF) // Source: http://stackoverflow.com/questions/6275558/question-about-whileeof
{
node* new_node = malloc(sizeof(node));
if (new_node == NULL)
{
return false;
}
wordCount++;
strcpy(new_node->word, word); // Source: cs50 reddit
int hash_index = hash_function(new_node->word);
// check whether node should be head
if (hashtable[hash_index] == NULL)
{
hashtable[hash_index] = new_node;
new_node->next = NULL;
}
else
{
new_node->next = hashtable[hash_index];
hashtable[hash_index] = new_node;
}
}
// close file
fclose(file);
return false;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
return wordCount;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
// go through all of the indexes in the hashtable
for (int i = 0; i < HASHTABLE_SIZE; i++)
{
node* head = hashtable[i];
while (head != NULL)
{
node* ptr = head->next;
free(head);
head = ptr;
}
}
return true;
}
最佳答案
您的unload
功能很好。您的代码的问题是 check
函数,特别是您尝试将输入转换为小写的部分:
char temp[LENGTH + 1];
for (int i = 0, n = strlen(word); i < n; i++)
{
if (isalpha(word[i]))
{
temp[i] = tolower(word[i]);
}
}
这里有两个问题。首先,temp
不是以 null 结尾的。其次,检查 isalpha
意味着您可以保留未初始化的字符:如果您的输入是,比方说,"I'm"
,temp
将保留'I'
, garbage, 'm'
, garbage 当它应该容纳 'I'
、'\''
、'm'
、'\0'
、垃圾。
或者,您可以过滤掉不需要的字符。在这种情况下,您需要两个索引:一个用于源词,另一个用于过滤后的词。
但您甚至不需要这个额外的步骤,因为您的哈希函数会再次将输入转换为 toupper
。
说到您的哈希函数:您可能想选择一个更好的函数。当前的值没有很好地分布在 5000 个槽中。 (当你添加 0 到 25 之间的最多 20 个数字时,你怎么会达到 5000?)
散列还有另一个问题:如果你输入一个数字,贡献的“字母”是负数,因为在 ASCII 中,数字的值从 48 到 57,你减去 'A'
的值>,65,来自他们。通常,您的哈希函数应返回一个无符号值。
关于c - 为什么我的节点都没有被释放? (cs50 pset5 段错误) C,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33030592/