C语言在高级哈希表中释放内存时出现问题

我正在学习cs50，我有一个pset，我应该实现一个哈希表来加载字典中的单词来检查文本中单词的拼写，这就像一个单词拼写检查。我的想法是将每个字符的ascii数字的总和作为第一层，第一个字母作为第二层，每个总和都有一个从a到z的数组，单词被堆叠在这个数组中作为“单词”的节点和“指针”到下一个。它工作得很好，但有点慢，但当我不得不实现卸载部分来释放我分配的每个内存块时。但是valgrind说while循环中的最后几个节点并没有被释放。我不知道我做错了什么。

// Implements a dictionary's functionality

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

#include "dictionary.h"

// TODO: Choose number of buckets in hash table
const unsigned int SIZE_OF_ALPHABET = 26;
const unsigned int MAX_SUM = SIZE_OF_ALPHABET * LENGTH;

int number_of_words = 0;
// Represents a node in a hash table

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

typedef struct
{
    node *children[SIZE_OF_ALPHABET];
}
sn;

typedef struct
{
    sn *sums[MAX_SUM];
}
fn;

// Hash table
fn *root;
//node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    node *ptr;
    ptr = root->sums[hash(word)]->children[tolower(word[0]) - 'a'];
    while (ptr != NULL)
    {
        if (strcasecmp(ptr->word, word) == 0)
        {
            return true;
        }
        ptr = ptr->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    int sum = 0;
    // TODO: Improve this hash function
    for (int i = 0, l = strlen(word); i < l; i++)
    {
        if (isalpha(word[i]))
        {
            sum += tolower(word[i]) - 'a';
        }
    }

    return sum;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        return false;
    }

    //initialising the hash table

    //printf("%li\n", sizeof(fn));
    root = malloc(sizeof(fn));
    if (root == NULL)
    {
        return false;
    }

    for (int i = 0; i < MAX_SUM; i++)
    {
        root->sums[i] = malloc(26*(sizeof(node) - LENGTH + 1));
        if (root->sums[i] == NULL)
        {
            return false;
        }
        for (int j = 0; j < SIZE_OF_ALPHABET; j++)
        {
            root->sums[i]->children[j] = malloc(sizeof(node));
            if (root->sums[i]->children[j] == NULL)
            {
                return false;
            }
            root->sums[i]->children[j] = NULL;
        }
    }

    // iterate over every word and send it to be hashed
    int index = 0;
    int sum = 0;
    char c;
    while (fread(&c, sizeof(char), 1, dict))
    {
        char word[LENGTH + 1];

        if (c != '\n')
        {
            word[index] = c;
            if(isalpha(c))
            {
                sum += c - 'a';
            }
            index ++;
        }
        else
        {
            word[index] = '\0';

            // "Pushing" a node in the hash
            node *n = malloc(sizeof(node));
            if (n == NULL)
            {
                return false;
            }
            for (int i = 0; i < index + 1; i++)
            {
                n->word[i] = word[i];
            }
            //already did the same during lecture
            n->next = root->sums[sum]->children[word[0]-'a'];
            root->sums[sum]->children[word[0]-'a'] = n;

            number_of_words ++;
            sum = 0;
            index = 0;
            //free(n);
        }
    }
    fclose(dict);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    for (int i = 0; i < MAX_SUM; i++)
    {
        for (int j = 0; j < SIZE_OF_ALPHABET; j++)
        {
            node *ptr = root->sums[i]->children[j];
            if (ptr == NULL)
            {
                free(root->sums[i]->children[j]);
            }
            else
            {
                while (ptr->next != NULL)
                {
                    node *tmp = ptr;
                    ptr = ptr->next;
                    free(tmp);
                }
            }
        }
        free(root->sums[i]);
    }

    //free(root->sums);
    free(root);
    return true;
}

字符串
仅说明，请勿使用代码。

当你发现这段代码的一些问题时（并在上面的评论中发布了一些可能的解决方案），应该注意的是，这里的间接性级别与课程材料中描述的基本哈希表实现有很大的不同。问题读作XY problem。
对于问题的 X 部分：
在这个练习中，散列的目标是能够为遇到的每个 * 单词 * 生成一个整数值。如何得到这个整数值取决于您，但应该由hash函数负责。此值用于索引数组（表示哈希表），该数组使用单独的链接来处理冲突。
看一下这个实现，就好像您读了这篇注解
除了使用单词的第一个字符（或多个字符）之外，还有许多方法可以实现哈希函数。考虑一个哈希函数，它使用ASCII值的总和或单词的长度。一个好的哈希函数往往会减少“冲突”，并在哈希表“桶”中具有相当均匀的分布。
来自pset5/Speller，并且可能过于字面上的描述，试图使用它描述的两种方法（字符和第一个字符值）来产生两个单独的哈希值。在想要使用这两个值时，您最终会得到一些过度设计的东西。
一个更接近问题集意图的哈希表实现类似于下面的例子，其中哈希表被表示为一个固定长度的链表数组。字符串被散列为一个整数值，它定位一个 bucket（使用余数运算符（%）来确保索引 * 是 * 有效的）。当发生冲突时，另一个节点被预先添加到由散列值定位的链表。
当需要释放整个哈希表时，每个桶都会像普通链表一样被检查和释放。
下面是一个简单的例子，使用一个基本的REPL：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASHTABLE_SIZE 128

struct node {
    struct node *next;
    char *word;
};

static struct node *table[HASHTABLE_SIZE];

static size_t hash(const char *string)
{
    /* this is djb2 (http://www.cse.yorku.ca/~oz/hash.html),
     * but you should write your own hash function, per the instructions */
    size_t h = 5381;

    while (*string)
        h = (h << 5) + h + *string++;

    return h % HASHTABLE_SIZE;
}

static int contains(const char *string)
{
    for (struct node *n = table[hash(string)]; n; n = n->next)
        if (0 == strcmp(n->word, string))
            return 1;

    return 0;
}

static int insert(const char *string)
{
    if (contains(string))
        return 0;

    struct node *element = calloc(1, sizeof *element);

    if (!element)
        return 0;

    element->word = strdup(string);

    if (!element->word) {
        free(element);
        return 0;
    }

    unsigned long h = hash(string);

    element->next = table[h];
    table[h] = element;

    return 1;
}

static void empty(void)
{
    for (size_t i = 0; i < HASHTABLE_SIZE; i++) {
        struct node *element = table[i];

        if (element) {
            table[i] = NULL;

            while (element) {
                struct node *tmp = element;
                element = element->next;

                free(tmp->word);
                free(tmp);
            }
        }
    }
}

int main(void)
{
    char buffer[512];

    while (1) {
        printf("(< = input) (> = search) (# = dump) (. = exit): ");

        if (!fgets(buffer, sizeof buffer, stdin) || '.' == *buffer)
            break;

        buffer[strcspn(buffer, "\n")] = '\0';

        if ('#' == *buffer) {
            for (size_t i = 0; i < HASHTABLE_SIZE; i++)
                for (struct node *n = table[i]; n; n = n->next)
                    printf("%zu) %s\n", i, n->word);
        } else if ('<' == *buffer) {
            char *b = buffer + strspn(buffer, "< ");
            printf("<%s> %s!\n", b, insert(b) ? "added" : "not added (already exists?)");
        } else if ('>' == *buffer) {
            char *b = buffer + strspn(buffer, "> ");
            printf("<%s> is%s in the hashtable!\n", b, contains(b) ? "" : " NOT");
        }
    }

    empty();
}

字符串
示例用法：

(< = input) (> = search) (# = dump) (. = exit): < foo
<foo> added!
(< = input) (> = search) (# = dump) (. = exit): < bar
<bar> added!
(< = input) (> = search) (# = dump) (. = exit): > foo
<foo> is in the hashtable!
(< = input) (> = search) (# = dump) (. = exit): > qux
<qux> is NOT in the hashtable!
(< = input) (> = search) (# = dump) (. = exit): #
9) foo
58) bar
(< = input) (> = search) (# = dump) (. = exit): .

型
为了完整性（问题的 Y 部分），您的示例中的一些问题是：
在load中，此分配的内存要求

root->sums[i] = malloc(26*(sizeof(node) - LENGTH + 1));

型
很困惑root->sums[i]的类型为sn *，因此每次分配应该是sizeof (sn)字节的某个因子。
正如你所发现的

root->sums[i]->children[j] = malloc(sizeof(node));
if (root->sums[i]->children[j] == NULL)
{
    return false;
}
root->sums[i]->children[j] = NULL;

型
是内存泄漏，因为指向新分配的内存的指针被覆盖。您通过删除对NULL的赋值来“解决”这个漏洞（还为结构成员赋值，大概是为了避免在使用未初始化的成员时，unload和check调用undefined behaviour的问题，例如，作为参数strcasecmp或控制变量）。
实际上，这些节点是多余的，充当“空”尾节点。不做任何分配，将root->sums[i]->children的每个元素都设置为NULL，也可以达到同样的效果。
在load中，word是while循环的 block 的 local。

while (fread(&c, sizeof(char), 1, dict))
{
    char word[LENGTH + 1];

型
您目前依赖于word来在每次迭代中占用相同的内存位置（并包含与前一次迭代相同的值），这并不保证是这种情况。阵列应移动到块外：

char word[LENGTH + 1];
while (fread(&c, sizeof(char), 1, dict))
{

型
在load中，对于这两行，

n->next = root->sums[sum]->children[word[0]-'a'];
root->sums[sum]->children[word[0]-'a'] = n;

型
如果生成的索引超出范围 [0，SIZE_OF_ALPHABET），则word[0]-'a'有问题。
在unload中，给定

node *ptr = root->sums[i]->children[j];

型
然后，

if(ptr == NULL)
{
    free(root->sums[i]->children[j]);
}

型
与free(NULL)完全相同（非操作）。
此外，中的循环条件

while (ptr->next != NULL)
{
    node *tmp = ptr;
    ptr = ptr->next;
    free(tmp);
}

型
确保ptr（tmp）仅在它不是链表中的最后一个节点时才被释放。
顺便说一句：你的hash函数当前在字谜上发生冲突。不是世界末日，而是值得注意的事情。

C语言在高级哈希表中释放内存时出现问题

1条答案

相关问题

热门标签

最新问答

C语言 在高级哈希表中释放内存时出现问题

1条答案

相关问题

热门标签

最新问答

C语言在高级哈希表中释放内存时出现问题