实施TRIE数据结构 [英] implementing a TRIE data structure

问题描述

Hii，
i在C ...中执行一个特技，但是我在insert_trie函数中收到错误。

Hii , i Was implementing a trie in C ... but i am getting an error in the insert_trie function .

我不知道为什么根节点没有得到更新。请帮助我。

I could not figure out why the root node is not getting updated . Please help me with this.

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

由于线nodepointer = nodepointer->列表，我得到一个细分故障insert_trie函数...为什么????

I get a segmentation fault due to the line nodepointer = nodepointer->list in insert_trie function ... Why ????

PS：这不是功课。但是我试图实现它。我只是找不到错误。

P.S : This is not homework.But i am trying to implement it. I just could not find the mistake .

推荐答案

每个角色都有一个节点，你只能执行一个 malloc 每个字符串。您应该为每个节点调用 malloc 。 （另外， malloc.h 已过期。 stdlib.h 包含 malloc 自1989年的ANSI C标准。）

A trie holds one node per character and you're only performing one malloc per string. You should be calling malloc for every node. (Also, malloc.h is outdated. stdlib.h contains malloc since the ANSI C standard of 1989.)

这篇关于实施TRIE数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！