Блог

Я реализовал структуру данных trie (ссылка). Когда я вставляю в структуру данных, я получаю ошибку сегментации. Это может быть семантическая ошибка. Пожалуйста, помогите это исправить.

 #include <stdio.h>
#include <stdlib.h>
#define maxlength 10

typedef struct node {
  int isend;
  struct node *branch[27];
} trinode;

int count, len;

trinode *createnode() {
  trinode *new = (trinode *)malloc(sizeof(trinode));
  int ch;
  for (ch = 0; ch < 26; ch  ) {
    new->branch[ch] = NULL;
  }
  new->isend = 0;
}

trinode *insert_trie(trinode *root, char *newenty) {
  int ind;
  trinode *proot;
  if (root == NULL)
    root = createnode();
  proot = root;
  for (int i = 0; i < maxlength; i  ) {
    ind = newenty[i] - 'a';
    if (newenty[i] == '')
      break;
    else {
      if (root->branch[ind] == NULL)
        root->branch[ind] = createnode();
      root = root->branch[ind];
    }
    if (root->isend != 0)
      printf("trying to insert duplicate");
    else
      root->isend = 1;
    return proot;
  }
}

void print_trie(trinode *cur) {
  char word[40];

  for (int i = 0; i < 26; i  ) {
    if (cur->branch[i] != NULL) {
      word[count  ] = (i   'a');
      if ((cur->branch[i]->isend) == 1) {
        printf("n");
        for (int j = 0; j < count; j  ) {
          printf("%c", word[j]);
        }
      }
      print_trie(cur->branch[i]);
    }
  }
  count--;
}

int search_trie(trinode *root, char *target) {
  int ind;
  for (int i = 0; i < maxlength amp;amp; root; i  ) {
    ind = target[i] - 'a';
    if (target[i] == '')
      break;
    else
      root = root->branch[ind];
  }
  if (root amp;amp; root->isend == 1)
    return root;
  else
    return 0;
}
int main() {
  int ch;
  trinode *root = NULL;
  char *newenty;
  char *target;
  int check;

  while (1) {
    printf("n enter option 1.insert_trie 2.display 3.search 4.exit");
    scanf("%d", amp;ch);
    switch (ch)

    {
    case 1:
      printf("enter word");
      scanf("%s", newenty);
      root = insert_trie(root, newenty);
      break;

    case 2:
      count = 0;
      print_trie(root);
      break;

    case 3:
      printf("enter elem you want to search");
      scanf("%s", target);
      check = search_trie(root, target);
      if (check == 0)
        printf("word not found");
      else
        printf("found");
      break;

    case 4:
      exit(0);
      break;
    }
  }
}
  

Для начала функция createnode ничего не возвращает

 trinode *createnode()
{
  trinode *new=(trinode *)malloc(sizeof(trinode));
  int ch;
  for(ch=0;ch<26;ch  )
  {
    new->branch[ch]=NULL;
  }
  new->isend=0;
}
  

Также неясно, почему условие в цикле for ch<26 вместо ch < 27 while элемент данных branch содержит 27 элементов

 struct node *branch[27];
  

Это для функции insert_trie

 for(int i=0;i<maxlength;i  )
  

не имеет смысла, потому что внутри цикла есть оператор return

 return proot;
  

Таким образом, цикл имеет не более одной итерации.

Функция print_trie зависит от глобальной переменной count , что является очень плохим дизайном, и неясно, что делает функция.

Функция search_trie объявляется как

 int search_trie(trinode *root,char *target)
  

То есть он имеет возвращаемый тип int . Однако функция возвращает указатель типа trinode* :

 if(root amp;amp; root->isend==1)
   return root;
  

В основном указатели

 char *newenty;
char *target;
  

не инициализированы и имеют неопределенные значения. Таким образом, эти утверждения

 scanf("%s",newenty)
  

и

 scanf("%s",target);
  

вызов неопределенного поведения.

И вам нужно отформатировать текст программы. Плохое форматирование обычно является причиной ошибок.

  char *newenty;
  ….
 scanf("%s",newenty);
 root=insert_trie(root,newenty);
  

newenty не указывает на действительную память, выделите для нее память, как показано ниже.

   char *newenty = malloc(maxLength);