c - 字典未正确加载和拼写检查单词

Question

我正在研究一个 pset，我们必须使用散列表尽可能高效地实现加载、散列、大小、检查和卸载功能，以使 TIME IN 加载、TIME IN 检查、TIME IN 大小和 TIME IN卸载全部最小化。当我用给定的文本测试它时，我收到以下消息： 单词拼写错误：17187 字典中的单词：1 文本中的单词：17756 加载时间：0.00 检查时间：0.01 时间大小：0.00 卸载时间：0.00总时间：0.01 字典无法正常工作，因为我没有根据条件实现哈希和检查，但我不知道如何。检查必须不区分大小写，并且只会传递包含（大写或小写）字母字符和可能的撇号的单词。

// 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 = 17576; // for the first 3 letters so 26*26*26

// Hash table
node *table[N];

unsigned int hash_value; // initialise positive int value
unsigned int word_counter; // initialise positive int word counter

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    //Hash the word to obtain the hash value;
    hash_value = hash(word);
    //Access linked list at the given index in the hash table, we are creating a trav pointer to the head of list indexed via the hash function
     for (node *cursor = table[hash_value]; cursor!= NULL; cursor = cursor->next)
     {
       if (strcasecmp(word, cursor->word) == 0)
        {
    return true;
        }
     }
   return false;
}

// Hashes word to a number
// hash function was taken from : stackexchange.com
unsigned int hash(const char *word)
{

    for (hash_value = 0; *word != '\0'; word++)
    {
    hash_value = *word + 31 * hash_value;
    }

    return hash_value % N;
}


// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{

    // TODO
    //allocate memory for all node buckets
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    //Open dictionary
    FILE *file = fopen(dictionary, "r");
if (file == NULL) // check if file is not empty)
    {
        printf("Error, empty file\n");
        return 1;
    }
    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) != EOF)
    {
        //create a new node
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL) // check if enough memory
        {
return false;
        }
        else
        {
        strcpy(new_node->word, word); //copies word into new_node->word;
        hash_value= hash(word);
        //Insert the node into the hash table
        new_node->next = table[hash_value];
        /set the head to the new pointer, so it is inserted in front
        table[hash_value] = new_node;
        word_counter ++;
        }
        fclose(file);
        }
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    if (word_counter > 0)
    {
       return word_counter;
    }
    else
    {
        return 0;
    }
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // loop through all buckets ( ie all indexes of the array of linked lists)
    for (int i = 0; i < N; i++)
    {
        node *cursor = table[i]; // place cursor to each bucket
        while (cursor!= NULL) //
        {

            node *tmp = cursor->next; // create a tmp equal to cursor
            free(cursor);
            cursor = tmp;

        }
        return true;

    }
    return false;
}

标签： c