向 trie 中插入数据

Question

所以我正在尝试 insert 数据到一个 trie 中，我的代码工作正常。但是后来我稍微改变了我的插入功能，它不再工作了，也导致了内存泄漏。对我来说，insert 的两个版本都做同样的事情，但显然，它们不是。有人可以向我解释为什么吗？提前致谢。

这是有效的代码

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

#define SIZE 26

#define hash(c) (tolower(c) - (int)'a')

typedef struct node{
    bool endWord;
    struct node* children[SIZE];
} node;

void freeTrie(node* root){

    if(root == NULL) return;

    for (size_t i = 0; i < SIZE; i++) {
        freeTrie(root->children[i]);
    }

    free(root);
}

node* newNode(){
    node* new = NULL;

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

    if(new != NULL){

        new->endWord = false;

        for(int i = 0; i < SIZE; i++)
            new->children[i] = NULL;
    }

    return new;
}

void insert(node* root, const char* data){

    node* temp = root;

    for (size_t i = 0, len = strlen(data); i < len; i++) {

        int index = hash(data[i]);

        if(temp->children[index] == NULL){

            temp->children[index] = newNode();

            if (temp->children[index] /*still*/ == NULL){
                printf("Something went wrong\n");
                return;
            }
        }

        temp = temp->children[index];
    }
    temp->endWord = true;
}

bool search(node* root, const char* data){

    node* temp = root;

    for (size_t i = 0, len = strlen(data); i < len; i++) {

        int index = hash(data[i]);

        temp = temp->children[index];

        if (temp == NULL){
            printf("search end here\n");
            return false;
        }
    }

    return (temp != NULL && temp->endWord);
}

int main() {

    char data[][8] = {"fox", "foo", "dog", "do"};

    node* root = newNode();

    if(root == NULL){
        printf("Something went wrong\n");
        return 1;
    }

    for (size_t i = 0, dataSize = sizeof(data)/sizeof(data[0]); i < dataSize; i++) {
        insert(root, data[i]);
    }

    printf("Check: \n");

    char output[][32] = {"not found", "found"};

    // char s[5];
    // fscanf(stdin, "%s", s);

    printf("%s\n", output[search(root, "fox")]);

    freeTrie(root);

    printf("Done\n");

    return 0;
}

下面是让我困惑的insert

void insert(node* root, const char* data){

    node* temp = root;

    for (size_t i = 0, len = strlen(data); i < len; i++) {

        int index = hash(data[i]);

        temp = temp->children[index];

        if(temp == NULL){

            temp = newNode();

            if (temp /*still*/ == NULL){
                printf("Something went wrong\n");
                return;
            }
        }
    }

    temp->endWord = true;
}

PS：我这样做是为了解决 CS50x 课程的问题集，其中我必须将 143091 个单词（按字母顺序）的字典加载到我的 trie 中。我的程序加载大约需要 0.1 秒，卸载大约需要 0.06 秒，而员工只需 0.02 秒和 0.01 秒即可完成相同的工作。我不允许看到工作人员的源代码，但我猜他们使用 trie 来存储数据。我如何改进我的代码以获得更快的运行时间？如果我将数据存储在一个数组中然后使用二进制搜索，它会运行更快吗？

Answer 1

写的时候

temp = temp->children[index];

您将 temp->children[index] 中包含的值（我称之为 A）复制到名为 temp 的完全独立的变量中。当您稍后修改 temp 时，您只修改 temp，而不修改 A。也就是说，不会将所有新节点都插入到 trie 中。

向 trie 中插入数据

Insert data into a trie

c

trie

data-structures

cs50