实现 TRIE 数据结构

Question

你好，我正在用C语言实现Trie树，但在insert_trie函数中出现了错误。

我无法确定为什么根节点没有得到更新，请帮助我解决这个问题。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef struct
 {
  char value;
  int level;
  struct node *next;
  struct node *list;
 }node;

 node *trie = NULL;

 node *init_trie()
  {
   node *new = (node *)malloc(sizeof(node));
   if(trie == NULL)
    {
     new->value = '$';
     new->next = NULL;
     new->list = NULL;
     new->level = 0;
     trie = new;
     printf("\n Finished initializing the trie with the value %c",trie->value);
     return trie;
    }
    printf("\n Trie is already initialized");
    return trie;
  }  

 node *insert_trie(char *s)
  {
   node *nodepointer = trie;
   node *new = (node *)malloc(sizeof(node));
   node *save = NULL;
   int i=0;
   while(s[i]!=NULL)
    {
       nodepointer = nodepointer->list;
     while(nodepointer!=NULL)
      {
        if(s[i] == nodepointer->value)
         {
          printf("\n Found %c",nodepointer->value);
          nodepointer = nodepointer->list;
          i++;
         }
         save = nodepointer;
         nodepointer = nodepointer->next;
      }
      new->value = s[i];
      new->next = NULL;
      new->list = NULL;
      printf("\n Inserting %c",new->value);
      save->next = new;     
      i++;
    }

   return trie;
  } 


 int main()
  {

   int num;
   char *s = (char *)malloc(sizeof(char)*10);
   trie = init_trie();
   printf("\n Enter the number of words to enter into the trie "); 
   scanf("%d",&num);
   while(num>0)
   {
   scanf("%s",s);
   //printf("%s",s);
   trie = insert_trie(s);
   printf("\n Finished inserting the word %s into the trie \n",s);
   num --;
   } 
   return 0;
  } 

在 insert_trie 函数的 nodepointer = nodepointer->list 这一行出现分割错误，为什么？

附注：这不是作业。我只是想尝试实现它。但我找不到错误。

- Flash

---

你遇到了什么错误？它出现在哪一行？ - David Wolever

请看一下...我编辑了这个问题。 - Flash

Answer 1

实现一个trie，包括插入、搜索和startsWith方法。 注意： 你可以假设所有的输入都是小写字母a-z。

我已经为上述LeetCode问题编写了这个非常简单的解决方案。它已经通过了LeetCode的16个测试用例。希望这会有所帮助。

//node structure
struct TrieNode {
     char value;
     int count;
    struct TrieNode * children[27];
};


static int count =0;
/** Initialize your data structure here. */
//return root pointer
struct TrieNode* trieCreate() {
    struct TrieNode *pNode = NULL;

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

    if (pNode)
    {
        pNode->value = '\0';
        pNode->count =0;

        memset(pNode->children, 0, sizeof(pNode->children));

    }
    return pNode;


}

/** Inserts a word into the trie. */
void insert(struct TrieNode* root, char* word) {

    struct TrieNode *pCrawl = root;
    count ++;
    //check if the word is not empty 
    if(word){
    int index=0, i =0;

    //check if the root is not empty
    if (root){

    while( word[i] != '\0'){
        index =  ( (int) (word[i]) - (int)'a');

        if(!pCrawl->children[index])
        {
            pCrawl->children[index] = trieCreate();
            pCrawl->children[index]->value = word[i];
        }

        pCrawl = pCrawl->children[index];
        i++;

    }

         //Count !=0 tell us that this is the last node;;
    pCrawl->count = count;

    }
}}



/** Returns if the word is in the trie. */
bool search(struct TrieNode * root, char* word) {

    struct TrieNode *pCrawl = root;
    bool flag = false;

    //check if word is NULL
    if(!word)
    return false;

    //if the trie is empty
    if(!root)
    {
        return false;
    }
    //if word is empty
    if (*word == '\0') {
        return true;
    }

    int i=0, index =0 ; 


    while (word[i] != '\0')
    {
     index = ((int) (word[i]) - (int)'a');

         //// if the node/character is not in Trie
        if(!pCrawl->children[index])
        {
            flag = false;
             break;
        }

        pCrawl = pCrawl->children[index];
        i++;
    }

          //count != 0 marks node as last / leaf node
          if(pCrawl->count != 0 && word[i] == '\0')
          {
              flag = true;
          }
        return flag;

}

/** Returns if there is any word in the trie 
    that starts with the given prefix. */
bool startsWith(struct TrieNode* root, char* prefix) {

    struct TrieNode * pCrawl = root;

    int i =0, index=0;
    bool flag = false;
    if(root){
    while(prefix[i] != '\0')
    {
         index = ((int) (prefix[i]) - (int)'a');

     if(pCrawl->children[index] == NULL){
     flag = false;
         return flag;
     }
     else 
     flag = true;

     pCrawl = pCrawl->children[index];
     i++;
    }

    }

    return flag;


}

/** Deallocates memory previously allocated for the TrieNode. */
void trieFree(struct TrieNode* root) {

    if(root){

        for(int i = 0; i <=26; i ++)
        {
            trieFree(root->children[i]);
        }
        free(root);

    }

}

// Your Trie object will be instantiated and called as such:
// struct TrieNode* node = trieCreate();
// insert(node, "somestring");
// search(node, "key");
// trieFree(node);

- Utsav Popli

Answer 2

字典树每个节点只包含一个字符，每个字符串仅需要进行一次malloc。但实际上每个节点都应该调用一次malloc。（另外，malloc.h已经过时了，在1989年ANSI C标准中，stdlib.h中包含了malloc函数。）

- Fred Foo

Answer 3

node *insert_trie(char *s) 
  { 
   node *nodepointer = trie; 
   node *new = (node *)malloc(sizeof(node)); 
   node *save = NULL; 
   int i=0; 
   while(s[i]!=NULL) 
    { 
       nodepointer = nodepointer->list; 
     while(nodepointer!=NULL) 
      { 
        if(s[i] == nodepointer->value) 
         { 
          printf("\n Found %c",nodepointer->value); 
          nodepointer = nodepointer->list; // Advance pointer once OK
          i++; 
         } 
         save = nodepointer; 
         nodepointer = nodepointer->next; // Advance pointer without checking
      } 
      new->value = s[i]; 
      new->next = NULL; 
      new->list = NULL; 
      printf("\n Inserting %c",new->value); 
      save->next = new;      
      i++; 
    } 

   return trie; 
  } 

在 if 测试中，您将 nodepointer 推进到 nodepointer->list。一旦 if 测试完成，您将 nodepointer 推进到 nodepointer->next，而不检查发生在 if 块内的推进是否导致 nodepointer 为 NULL。

- Bayou Bob