2

我现在正在研究哈佛 cs50 的 pset6，问题是要实现一个 trie 字典。我终于设法让它解决了一个小问题。

  1. 当我运行 valgrind 检查内存泄漏时，它告诉我释放的内存比分配的多，但我的卸载函数看不到任何问题。
  2. 它还警告我有一些未初始化的值，但我无法弄清楚，尽管它不会影响结果。

这是我的整个代码：

/****************************************************************************
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 6
 *
 * valgrind warn that there are uninitialized values, could be the node struct, but don't
 * know how to initialize it, anyway, it works at last!
 * 
 * Implements a dictionary's functionality.
 ***************************************************************************/

#include <stdbool.h>
#include <ctype.h>   
#include "dictionary.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define HASHTABLE_SIZE 5000

int count = 0;     // gloabal counter

typedef struct node {         // data structure 
    bool end_word;
    struct node *children[27];
    } node;

int
charNumber(char c);   // function prototype

void 
freeNode(node *currentNode);

node root = {false,{NULL}};
/*
 * Returns true if word is in dictionary else false.
 */

bool
check(const char *word)
{
    node *ptr = &root;
    for (int i=0;i<strlen(word);i++)
    {
        if (ptr->children[charNumber(word[i])] == NULL)
            return false;
        ptr = ptr->children[charNumber(word[i])];
    }
    if (ptr->end_word)
        return true;
    else
        return false;
}


/*
 * Loads dictionary into memory.  Returns true if successful else false.
 */

bool
load(const char *dictionary)
{
//    char word[LENGTH+1];  // must initialize to zero! Or there will be some weird problem.
    FILE *fp = fopen(dictionary,"r");
    if (fp == NULL)
        return false;
    while (!feof(fp))
    {
        char word[LENGTH+1] = {};
        fscanf(fp,"%s\n",word); // have to use "%s\n" instead of "%s", or the count will be wrong, don't know why.
        count++;    
        node *ptr = &root;
        for (int i=0;i<strlen(word);i++)
        {
            if (ptr->children[charNumber(word[i])] == NULL)
            {
                node *new = malloc(sizeof(node));   
                *new = (node) {false,{NULL}};       // initiallization
                ptr->children[charNumber(word[i])] = new;
                ptr = new;
            }
            else
            {
                ptr = ptr->children[charNumber(word[i])];
            }
         }
         ptr->end_word = true;
    }
fclose(fp);           
return true;
}


/*
 * caculate a number for the character
 */

int
charNumber(char c)
{
    int num;
    if (c == '\'')
        return 26;
    else if(c >= 'A' && c <= 'Z')
        c += 32;
    num = c - 'a';
    return num;
}



/*
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */

unsigned int
size(void)
{
    if (count)
        return count;
    else
        return 0;
}


/*
 * Unloads dictionary from memory.  Returns true if successful else false.
 */

bool
unload(void)
{
    freeNode(&root);
    return true;         // can't figure out when to return false...
}

void freeNode(node *currentNode)
{
    for (int i=0;i<27;i++)
    {
        if (currentNode->children[i] != NULL)
            freeNode(currentNode->children[i]);
    }
    free(currentNode);
 }

这是一些 valgrind 输出：

==22110== Invalid free() / delete / delete[]
==22110==    at 0x4024ECD: free (vg_replace_malloc.c:366)
==22110==    by 0x8048F90: freeNode (dictionary_tries.c:152)
==22110==    by 0x8048F45: unload (dictionary_tries.c:141)
==22110==    by 0x8048AB5: main (speller.c:158)
==22110==  Address 0x804a5a0 is 0 bytes inside data symbol "root"
==22110==
--22110-- REDIR: 0x40b2930 (strchrnul) redirected to 0x4028570 (strchrnul)


==22110==
==22110== HEAP SUMMARY:
==22110==     in use at exit: 0 bytes in 0 blocks
==22110==   total heap usage: 367,083 allocs, 367,084 frees, 41,113,776 bytes allocated
==22110==
==22110== All heap blocks were freed -- no leaks are possible
==22110==
==22110== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 14 from 9)
==22110==
==22110== 1 errors in context 1 of 1:
==22110== Invalid free() / delete / delete[]
==22110==    at 0x4024ECD: free (vg_replace_malloc.c:366)
==22110==    by 0x8048F90: freeNode (dictionary_tries.c:152)
==22110==    by 0x8048F45: unload (dictionary_tries.c:141)
==22110==    by 0x8048AB5: main (speller.c:158)
==22110==  Address 0x804a5a0 is 0 bytes inside data symbol "root"
==22110==
--22110--
--22110-- used_suppression:     14 U1004-ARM-_dl_relocate_object
==22110==
==22110== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 14 from 9)
4

2 回答 2

2

假设您的load函数打开一个空白文件。feof(fp)最初将返回0，因为尚未使用读取操作；EOF只有在读取操作返回指示错误的值后才会设置该标志。这就是错误所在。在您的情况下，您需要循环的返回值fscanf(fp,"%s\n",word);而不是返回值feof. 例如：

while (fscanf(fp, "%s", word) == 1) {
    /* ... */
}

if (feof(fp)) {
    /* The loop ended due to EOF */
}
else if (ferror(fp)) {
    /* The loop ended due to some file input error */
}
else {
    /* The loop ended because the input was invalid
     * (this applies to input where a conversion is
     *  required eg. the conversion in %d, %u, %f, etc... */
}

详细说明，feof仅用于确定上次读取失败的原因！

在空白文件的情况下会导致此类警告的原因是它word包含不确定的信息。

此外，freeNode(&root);是错误的，因为free仅在由calloc,realloc和. 返回的指针上调用malloc。

于 2013-05-21T03:35:51.703 回答
0 
node root = {false,{NULL}};

没有在堆上分配，但是你尝试像它一样释放它

unload(void)
{
    freeNode(&root);
于 2013-05-21T03:37:55.817 回答