add 函数中的 C trie 内存泄漏

Question

我一直在努力让我的代码正常工作。它可以编译，但是当我运行它时，我得到一个段错误，gdb 和 valgrind 特别指向这一行，我的问题是我真的不知道如何修复它:

    if (!pCrawl->cvec[index]) {

它在addword()中。 本质上，我应该在头文件中实现 trie 数据结构的函数:makedictionary、添加、搜索和删除。

这是学校提供的头文件:

#define VECSIZE ('z'-'a' + 1)

typedef char *word;
enum __bool__ { FALSE, TRUE };
typedef enum __bool__ bool;

typedef struct __tnode__  *Dict, TNode;

struct __tnode__ {
  Dict cvec[VECSIZE];          
  bool eow;                   
};

void newdict(Dict *dp);
void addword (const Dict r, const word w);
bool checkword (const Dict r, const word w);
void delword (const Dict r, const word w);

void barf(char *s);           

也不是因为我无法更改头文件，并且 bool 是一个 typedef，所以我无法使用 stdbool.h。 这是我正在编写的 C 代码:

#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

void newdict (Dict *dp) {
    *dp = NULL;
    dp = (Dict *)malloc(sizeof(Dict));
    if (dp) {
        int i;
        (*dp)->eow = FALSE;
        for (i = 0; i < VECSIZE; i++) {
            (*dp)->cvec[i] = NULL;
        }
    }
}

void addword (const Dict r, const word w) {
    int level;
    int length = strlen(w);
    int index;

    Dict pCrawl = r;
    printf("line 1\n");
    for (level = 0; level < length; level++) {
        index = CHAR_TO_INDEX(w[level]);
        if (!pCrawl->cvec[index]) {
            newdict(&(pCrawl->cvec[index]));
        }
        pCrawl = pCrawl->cvec[index];
    }
    pCrawl->eow = TRUE;
}

bool checkword (const Dict r, const word w) {
    int level;
    int length = strlen(w);
    int index;

    Dict pCrawl = r;

    for (level = 0; level < length; level++) {
        index = CHAR_TO_INDEX(w[level]);
        if (!pCrawl->cvec[index]) {
            return FALSE;
        }
        pCrawl = pCrawl->cvec[index];       
    }
    if (pCrawl != NULL && pCrawl->eow) {
        return TRUE;
    } else {
        return FALSE;
    }
}

我对 C 有点陌生，所以任何提示将不胜感激。提前致谢。

Answer 1

我猜困惑在于理解

typedef struct _tnode__ *Dict, TNode;

这意味着

Dict lookup;

与

相同

TNode* lookup;

所以当你创建字典时

void newdict(Dict* dp)

与相同

void newdict(TNode** dp)

因此，在分配时，分配 sizeof(Dict) 与 sizeof(TNode*) 相同，即 sizeof 指针。真正需要的是一个TNode。注意 - 在 C 中，不需要强制转换 malloc。仅 C++ 需要它。

*dp = malloc (sizeof(TNode));

尝试一下，看看是否可以解决您的问题。