4

こんにちは、私は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;
  }

insert_trie関数のnodepointer=nodepointer->listという行が原因でセグメンテーション違反が発生します...なぜ????

PS：これは宿題ではありませんが、私はそれを実装しようとしています。間違いを見つけることができませんでした。

4

3 に答える 3

2

mallocトライは文字ごとに 1 つのノードを保持し、文字列ごとに 1 つしか実行していません。mallocすべてのノードを呼び出す必要があります。(また、malloc.h時代遅れです。1989 年の ANSI C 標準以降がstdlib.h含まれています。)malloc

于 2010-10-25T18:17:37.887 に答える
1 
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 テストが完了すると、if ブロック内で発生した進行から nodepointer が NULL であるかどうかを確認せずに、nodepointer を nodepointer->next に進めます。

于 2010-11-12T16:23:56.523 に答える