Einfügen von Daten in einen Trie

Question

So versuche ich insert Daten in einen Trie, und mein Code funktioniert gut. Aber dann ändere ich meine Insert-Funktion ein wenig und es funktioniert nicht mehr und verursacht auch das Speicherleck. Für mich tun beide Versionen von insert das gleiche, aber offensichtlich sind sie nicht. Kann mir bitte jemand erklären warum? Danke im Voraus.

Hier ist der Code, der

#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; 
} 

Hier ist die insert, die mich verwirrt macht

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 funktioniert: Ich mache das für ein Problem des Kurses CS50x gesetzt, in dem ich um ein Wörterbuch von 143091 Wörtern (in alphabetischer Reihenfolge) in meinen Trie zu laden. Mein Programm benötigt etwa 0,1 Sekunden zum Laden und 0,06 Sekunden zum Entladen, wenn die Mitarbeiter den gleichen Job mit nur 0,02 Sekunden und 0,01 Sekunden machen. Ich bin nicht berechtigt, den Quellcode der Mitarbeiter zu sehen, aber ich nehme an, dass sie einen Trie verwendet haben, um Daten zu speichern. Wie kann ich meinen Code für eine schnellere Laufzeit verbessern? Würde es schneller laufen, wenn ich Daten in einem Array und dann binäre Suche speichern würde?

Answer 1

Wenn Sie

temp = temp->children[index]; 

schreiben kopieren Sie Wert in temp->children[index] enthalten (Ich werde es nennen A) in eine völlig unabhängige Variable mit dem Namen temp. Wenn Sie später temp ändern, ändern Sie nur temp, nicht A. Das heißt, alle neuen Knoten werden nicht in den Trie eingefügt.