Was bei der Durchführung von Versuchen die folgende Aussage macht

Question

Ich habe versucht, eine C++ Implementierung der Einführung von Trie-Datenstruktur zu implementieren, durch einen Blog arbeiten, in denen gibt es ein paar Dinge, die ich nicht in der Lage bin http://theoryofprogramming.com/2015/01/16/trie-tree-implementation/

zu verstehen

#define ALPHABETS 26 
#define CASE 'a' 
#define MAX_WORD_SIZE 25 
using namespace std; 

struct Node 
    { 
    struct Node * parent; 
    struct Node * children[ALPHABETS]; 
    vector<int> occurrences; 
    }; 

    // Inserts a word 'text' into the Trie Tree 
    // 'trieTree' and marks it's occurence as 'index'. 

    void InsertWord(struct Node * trieTree, char word[], int index) 
    { 
    struct Node * traverse = trieTree; 
    while (*word != '\0') { // Until there is something to process 
    if (traverse->children[*word - CASE] == NULL) { 

     // There is no node in 'trieTree' corresponding to this alphabet 

     // Allocate using calloc(), so that components are initialised 
     traverse->children[*word - CASE] = (struct Node *) calloc(1, sizeof(struct Node)); 
     traverse->children[*word - CASE]->parent = traverse; // Assigning parent 
    } 

    traverse = traverse->children[*word - CASE]; 
    ++word; // The next alphabet 
} 

    traverse->occurrences.push_back(index);  // Mark the occurence of the word 
} 

// Prints the 'trieTree' in a Pre-Order or a DFS manner 
// which automatically results in a Lexicographical Order 
void LexicographicalPrint(struct Node * trieTree, vector<char> word) 
    { 
    int i; 
    bool noChild = true; 
    if (trieTree->occurrences.size() != 0) { 
    // Condition trie_tree->occurrences.size() != 0, 
    // is a neccessary and sufficient condition to 
    // tell if a node is associated with a word or not 
    vector<char>::iterator charItr = word.begin(); 
    while (charItr != word.end()) { 
     printf("%c", *charItr); 
     ++charItr; 
    } 
    printf(" -> @ index -> "); 

    vector<int>::iterator counter = trieTree->occurrences.begin(); 
    // This is to print the occurences of the word 

    while (counter != trieTree->occurrences.end()) { 
     printf("%d, ", *counter); 
     ++counter; 
    } 

    printf("\n"); 
} 

for (i = 0; i < ALPHABETS; ++i) { 
    if (trieTree->children[i] != NULL) { 
     noChild = false; 
     word.push_back(CASE + i); // Select a child 

     // and explore everything associated with the cild 
     LexicographicalPrint(trieTree->children[i], word); 
     word.pop_back(); 
     // Remove the alphabet as we dealt 
     // everything associated with it 
    } 
} 

    word.pop_back(); 
} 

int main() 
    { 
    int n, i; 
    vector<char> printUtil;  // Utility variable to print tree 
    // Creating the Trie Tree using calloc 
    // so that the components are initialised 
    struct Node * trieTree = (struct Node *) calloc(1, sizeof(struct Node)); 
    char word[MAX_WORD_SIZE]; 
    printf("Enter the number of words-\n"); 
    scanf("%d", &n); 
    for (i = 1; i <= n; ++i) { 
    scanf("%s", word); 
    InsertWord(trieTree, word, i); 
    } 

    printf("\n"); // Just to make the output more readable 
    LexicographicalPrint(trieTree, printUtil); 

return 0; 
} 

vermag ich nicht zu verstehen, was diese Aussage in insertword tut:

 if (traverse->children[*word - CASE] == NULL) 

auch als wir alle Elemente 1 in der Hauptfunktion initialisiert haben dann Wie können wir es null sein?

Answer 1

Die Funktion InsertWord() fügt dynamisch ein neues Wort in den Trie ein und erzeugt dabei neue Knoten, wenn das Präfix dieses Wortes nicht mit dem Präfix eines bereits im Trie hinzugefügten Wortes übereinstimmt.

Dies ist genau das, was Ihre Linie testet. Von dem, was ich sehen kann, ist traverse ein Zeiger auf den aktuellen Knoten eines Präfix des Wortes. *word ist das nächste Zeichen im Wort nach dem Präfix. Wenn der Knoten, der dem aktuellen k-Präfix des Wortes entspricht, kein Kind hat (Zeiger ist NULL) und das Label dem nächsten Zeichen entspricht, bedeutet das, dass wir einen neuen Knoten für den nächsten k+1 -prefix des Wortes zuweisen müssen .