CS50 第 5 周拼写器解决方案

Question

我对这段代码运行了 check 50，得到了所有绿色的表情符号，包括表示该程序没有内存错误的表情符号。

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

#include "dictionary.h"

int total_words = 0;

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// TODO: Choose number of buckets in hash table
const unsigned int N = 45;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    int hash_val;
    node *ptr = NULL;

    hash_val = hash(word);

    ptr=table[hash_val];

    while(ptr != NULL)
    {
        if(strcasecmp(word, ptr->word) == 0)
        {
            return true;
        }
        ptr=ptr->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    return toupper(word[0]) - 'A';
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    int state = 1;
    char buffer[LENGTH+1];
    int hash_val;
    int i = 0;
    node *ptr = NULL;

    FILE *file = fopen(dictionary, "r");
    if(file == NULL)
    {
        fclose(file);
        return false;
    }
    while(state != 0)
    {
        state = fscanf(file,"%s",buffer);
        if(state != 1)
        {
            break;
        }

        node *n = malloc(sizeof(node));

        if(n == NULL)
        {
            fclose(file);
            unload();
            return false;
        }

        n->next = NULL;
        i = 0;

        while(buffer[i] != '\0')
        {
            n->word[i] = buffer[i];
            i++;
        }
        n->word[i] = buffer[i];

        hash_val = hash(n->word);

        n->next = table[hash_val];
        table[hash_val] = n;

    }


    for(int j = 0; j<26; j++)
    {

        ptr=table[j];
        while(ptr != NULL)
        {
        total_words++;
        ptr=ptr->next;
        }
    }

    fclose(file);
    return true;

}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    int fake = 0;
    node *ptr = NULL;
    node *temp = NULL;

    for(int j = 0; j<26; j++)
    {
        temp=table[j];

        if(temp != NULL)
        {
            ptr = temp->next;
            free(temp);
            temp = ptr;
        }
        free(temp);
    }

    return true;
}

但是当我在上面运行 valgrind 时，它给了我这个错误消息

==2682== HEAP SUMMARY:
==2682==     in use at exit: 8,010,184 bytes in 143,039 blocks
==2682==   total heap usage: 143,096 allocs, 57 frees, 8,023,256 bytes allocated
==2682== 
==2682== 8,008,728 bytes in 143,013 blocks are indirectly lost in loss record 1 of 2
==2682==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2682==    by 0x109A36: load (dictionary.c:83)
==2682==    by 0x1092BB: main (speller.c:40)
==2682== 
==2682== 8,010,184 (1,456 direct, 8,008,728 indirect) bytes in 26 blocks are definitely lost in loss record 2 of 2
==2682==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2682==    by 0x109A36: load (dictionary.c:83)
==2682==    by 0x1092BB: main (speller.c:40)
==2682== 
==2682== LEAK SUMMARY:
==2682==    definitely lost: 1,456 bytes in 26 blocks
==2682==    indirectly lost: 8,008,728 bytes in 143,013 blocks
==2682==      possibly lost: 0 bytes in 0 blocks
==2682==    still reachable: 0 bytes in 0 blocks
==2682==         suppressed: 0 bytes in 0 blocks
==2682== 
==2682== For lists of detected and suppressed errors, rerun with: -s
==2682== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Valgrind 给了我这条消息，因为我只释放了每个链表中的前 2 个节点，但 check50 说没问题。这是他们的检查算法中的错误还是可以泄漏拼写器的内存，因为我很确定它不是。

Answer 1

由于未提供所有代码，我无法测试此解决方案。

unload

功能不正确。

1. for

   循环仅到达26，但应该到达

   N

2. 它仅对给定

   free

   中链表的 first 元素执行

   table[j]

   操作。

   if

   应该是

   while

3. 最后一个

   free

   不正确

---

这是更正后的代码。它注释有错误和修复：

// Unloads dictionary from memory, returning true if successful, else false
bool
unload(void)
{
    // TODO
    int fake = 0;
    node *ptr = NULL;
    node *temp = NULL;

// NOTE/BUG: there are N hash buckets, not just 26
#if 0
    for (int j = 0; j < 26; j++) {
#else
    for (int j = 0; j < N; j++) {
#endif
        temp = table[j];

// NOTE/BUG: this only frees the _first_ element of the linked list
#if 0
        if (temp != NULL) {
#else
        while (temp != NULL) {
#endif
            ptr = temp->next;
            free(temp);
            temp = ptr;
        }

// NOTE/BUG: this free is extraneous. it is harmless because temp will be NULL
#if 0
        free(temp);
#endif

// NOTE/FIX: we should clear this if we wish to reuse/refill the hash table
#if 1
        table[j] = NULL;
#endif
    }

    return true;
}

---

在上面的代码中，我使用

cpp

条件来表示旧代码与新代码：

#if 0
// old code
#else
// new code
#endif

#if 1
// new code
#endif

注意：这可以通过运行文件来清理

unifdef -k

---

这是一个稍微清理过的版本：

// Unloads dictionary from memory, returning true if successful, else false
bool
unload(void)
{
    // TODO
    node *ptr;
    node *temp;

    for (int j = 0; j < N; j++) {
        for (temp = table[j];  temp != NULL;  temp = ptr) {
            ptr = temp->next;
            free(temp);
        }
        table[j] = NULL;
    }

    return true;
}

---

有关一些其他指导/建议，请参阅我的 cs50 拼写器答案：cs50 pset5 拼写器优化