我运行了check50，得到了一张皱眉的脸，因为“拼写检查不区分大小写”和“正确处理大多数基本单词”。
我该怎么解决这个问题呢？这和我的哈希函数有关吗？
#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 words in dictionary
int word_count = 0;
// Number of buckets in hash table
const unsigned int N = 26;
// Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
unsigned int n = hash(word);
node *cursor = table[n];
while (cursor != NULL)
{
if (strcasecmp(word, cursor->word) == 0)
{
return true;
}
cursor = cursor->next;
}
return false;
}
// Hashes word to a number
// Function credit to staff on CS50 reddit page
unsigned int hash(const char *word)
{
unsigned int hash_value = 0;
for (int i = 0, n = strlen(word); i < n; i++)
{
hash_value = (hash_value << 2) ^ word[i];
}
return hash_value % N;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// Open dictionary and check for memory issue
//Function guide credit to CS50 Guide by Anvea on YouTube
FILE *dict = fopen(dictionary, "r");
char word[LENGTH + 1];
// Check for memory issue with dict
if (dict == NULL)
{
printf("Dictionary is null\n");
unload();
return false;
}
while (fscanf(dict, "%s", word) != EOF)
{
node *n = malloc(sizeof(node));
if (n == NULL)
{
return false;
}
strcpy(n->word, word);
word_count++;
// Index word using hash function
int dict_index = hash(word);
// Insert into hash table if already empty
if (table[dict_index] == NULL)
{
n->next = NULL;
}
// Insert work as new node if not empyty
else
{
n->next = table[dict_index];
}
table[dict_index] = n;
}
// Close dictionary file
fclose(dict);
// Indicate success
return true;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
return word_count;
return 0;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
for (int i = 0; i < N; i++)
{
node *cursor = table[i];
while (cursor)
{
node *tmp = cursor;
cursor = cursor->next;
free(tmp);
}
}
return true;
}字符串
1条答案
按热度按时间rks48beu1#
一些问题...
1.所有的字典单词都是，每行一个。所以，哈希是在字符上完成的。
1.在
check中，它在混合大小写文本上调用hash，因此它可以为某些单词（例如）Won't this work?和No, it won't.生成不同的哈希值1.在
check中，我们需要在 * 调用hash之前 * 对字符串进行重命名，这样我们就可以得到 * 相同的 * 哈希值/索引。作为一个有益的副作用，我们可以用strcmp替换strcasecmp（这样更快）。1.在
load中，当table[n]是NULL时，* 没有 * 需要有特殊情况，所以我们可以简化它。1.虽然我没有检查这一点，但在
hash中执行<<可能会产生一个不均匀分布的哈希值，从而减慢check中的搜索速度。1.因为字典文件是[保证]所有的行和每行一个条目，在
load中，我们可以用fgets替换fscanf[剥离换行符]，因为fgets快得多。1.在
gcc8.3.1中，编译器标记了node *table[N];，因为：const unsigned int N = 26;与C++不同，这在C中是不允许的--它需要一个文字常量，而不仅仅是const。1.* 风格说明：* 永远不要做（例如）：
x -> y而不是x->y。下面是更正后的代码。我已经检查了所有可能的输入文件和字典。它带有bug和修复的注解：
字符串
在上面的代码中，我使用了
cpp条件来表示旧代码和新代码：型
注意：这可以通过
unifdef -k运行文件来清理。以下是清理后的版本（通过
unifdef -k运行，并进行了一些注解清理）：型
虽然上面的代码[现在]是正确的，但它可以进一步改进。
对于一些额外的修复和加速，请参阅我的cs50拼写答案：cs50 pset5 Speller optimisation
以下是您的[固定]版本与我的[优化]版本之间
check函数的运行时间比较：型