реализация структуры данных TRIE

Question

Hii, Я реализовал Trie в C ... но я получаю сообщение об ошибке в функции 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;
  } 

Я получаю ошибку сегментации из-за строки listpointer = nodepointer-> list в функции insert_trie ... Почему ????

П.С .: Это не домашняя работа. Но я пытаюсь ее реализовать. Я просто не смог найти ошибку.

Answer 1

"Реализация дерева с вставками, поиском и запусками с методами. Замечания: Вы можете предположить, что все входные данные состоят из строчных букв a-z. "

Я написал это очень простое решение для вышеуказанного вопроса из LeetCode. Он прошел все 16 тестовых случаев из LeetCode. Я надеюсь, это поможет.

//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);

Answer 2

Три содержат один узел на символ, а вы выполняете только один malloc на строку. Вы должны звонить malloc для каждого узла. (Кроме того, malloc.h устарел. stdlib.h содержит malloc, начиная со стандарта ANSI C 1989 года.)

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 без проверки, равен ли nodepointer NULL по сравнению с расширением, которое произошло в блоке if.