CS50 拼写器 : Unload executes 80, 000,000+ 免费

Question

这是哈佛大学 CS50 中的 pset 5。它主要包括加载字典，检查所选文本中的每个单词是否在加载的字典中找到，然后卸载(释放所有分配的内存)。所有其他功能都可以工作，但是当涉及到卸载时，它只是执行，如上所述，超过 80,000,000 次释放，而在程序中只有 143,094 个 malloc，我是一个新手，所以这对我来说是令人兴奋的。下面是卸载的相关函数。

编辑 (1):以下是有关变量哈希表的一些上下文。

typedef struct node
{
    char word[LENGTH+2];
    struct node *next;
}
node;

node *hashtable[264636] = { NULL };

我将每个元素初始化为 NULL，以便在卸载时我可以轻松跳过哈希函数中未生成键的索引值。

//LOAD FUNCTION: Loads the dictionary into a hash table. Djb2 function used. 

bool load(const char *dictionary)
{
    head = malloc(sizeof(node));
    head->next = NULL;
    if (head == NULL)
    {
        unload();
        return false;
    }
    opntr = fopen(dictionary, "r");

    while (fscanf(opntr, "%s", WORD) != EOF)
    {
        wnode = malloc(sizeof(node));
        if (wnode == NULL)
        {
            unload();
            return false;
        }
        strcpy(wnode->word, WORD);
        wnode->next = head; 
        head = wnode; 
        unsigned long key = hash(wnode->word);
        hashtable[key] = wnode;
        wnode = wnode->next;
    }
    return true;
}

// Checks whether the input word is somewhere within the dictionary

bool check(const char *word)
{
    char dword[strlen(word) + 1];
    strcpy(dword, word);
    for (int c = 0; c < strlen(dword); c++)
    {
        dword[c] = tolower(dword[c]);
    }
    int key_w;
    key_w = hash(dword);
    node *cursor = hashtable[key_w];
    while (cursor != NULL)
    {
        if (strcmp(cursor->word, dword) == 0)
        {
            return true;
        }
        cursor = cursor->next; 
    }
    return false;
}

// Unloads memory allocated (?) to store the dictionary

bool unload(void)
{
    for (int in = 0; in < 264636; in++)
    {
        node *fhead = hashtable[in];             
        while (fhead != NULL)
        {
            node *fcursor = fhead->next;
            free(fhead);
            fhead = fcursor;
        }
    }
    return true;
}

Answer 1

如果有人觉得它有帮助，问题出在加载函数内。分配的节点被错误地更新，因此散列表数组的元素不是独立的链表，并且每次我们想要添加节点时，我都不必要地使用头节点来指向列表的第一个元素。相反，为了将新节点添加到哈希表数组中的相应元素，我们使用该元素本身作为链表的头，并对其进行排列，使其指向添加的每个节点，从而成功地跟踪链表的开头链接列表。哈希表中的每个元素最初都指向 NULL，以便我们可以找到每个链表的末尾。

int null()
{
    for (int i = 0; i < 264636; i++)
    {
        hashtable[i]->next = NULL;
    }
    return 0;
}

bool load(const char *dictionary)
{

    opntr = fopen(dictionary, "r");
    while (fscanf(opntr, "%s", WORD) != EOF)
    {
        wnode = malloc(sizeof(node));
        if (wnode == NULL)
        {
            unload();
            return false;
        }
        strcpy(wnode->word, WORD);
        unsigned long key = hash(wnode->word);
        wnode->next = hashtable[key]; 
        hashtable[key] = wnode; 
    }
    return true;
}