c - 将数据插入到 trie 中

Question

所以我尝试将数据插入到特里树中，并且我的代码工作正常。但后来我稍微改变了我的插入函数，它不再工作并且还导致内存泄漏。对我来说，两个版本的 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;
}

这是让我困惑的插入

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 类(class)的问题集执行此操作，其中我必须将包含 143091 个单词(按字母顺序)的字典加载到我的特里树中。我的程序加载大约需要 0.1 秒，卸载大约需要 0.06 秒，而员工只需要 0.02 秒和 0.01 秒即可完成相同的工作。我不允许查看工作人员的源代码，但我猜他们使用了 trie 来存储数据。如何改进我的代码以获得更快的运行时间？如果我将数据存储在数组中然后进行二分搜索，它会运行得更快吗？

Answer 1

当你写的时候

temp = temp->children[index];

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