Печать лексикографического дерева в c

Итак, я пытаюсь сохранить слова в файле словаря. Я реализовал операцию вставки; теперь я пытаюсь печатать лексикографически. Я близок к этому, но у меня есть небольшая проблема, которую я не знаю, как исправить. Я также стараюсь не забывать о скорости моей программы, поэтому я выбрал trie, а не массив или связанный список. Вот как выглядит отдельный узел:

struct node {
  int end;
  int occurrences;
  int superwords;
  struct node* child[26];
};

«end» указывает на завершение слова (например, end == 1 на букве «k» в книге слов; это предотвращает путаницу при проверке того, действительно ли слово было вставлено в дерево).

Вот метод:

void preorder(struct node *follow, char hold[200], int s){
  int i = 0;
  if(follow == NULL){
    return;
  }

  for(i = 0; i < 26; i++){
    if(follow->child[i] == NULL){
      continue;
    }
    else{
      printf("%c",'a'+i);
      hold[s] = 'a'+i;
      s++;
      if(follow->child[i]->end == 1){
        printf("\n");
        hold[s] = '\0';
        printf("%s", hold);
      }
      preorder(follow->child[i], hold, s);
    }
  }
  return;
}

Я вставил следующие слова: бу, книга, бронирование, джон, текс, текст. Они должны быть напечатаны в этом порядке и разделены строкой. Мой вывод выглядит так:

boo
book
booking
bookingjohn
bjohntex
bjtext
bjtext

Я знаю, что это, вероятно, как-то связано с моим массивом «hold», в котором хранятся префиксы слов, чтобы они не терялись. Мне нужно где-то снова установить индекс на ноль, чтобы указать завершение префикса и всех связанных с ним слов (хорошим примером является бу, книга, бронирование), но это не удалось. Любая помощь будет высоко оценена, и я был бы рад еще больше прояснить свой мыслительный процесс.


c sorting trie lexicographic preorder
person Sara    schedule 10.10.2015    source источник
comment
насколько вы знакомы с концепцией статических переменных? поскольку эта функция является рекурсивной, было бы неплохо использовать одну или две статические переменные для отслеживания информации, которую следует запоминать между вызовами функции.   -  person Joel Trauger    schedule 11.10.2015
comment
Не очень знакомо. Я новичок в c. Пожалуйста, дополните.   -  person Sara    schedule 11.10.2015
comment
Я думаю, что вместо использования s++ вам может понадобиться передать s+1 рекурсивному вызову preorder. Обычно это то, как вы справляетесь со спуском, позволяя вам делать резервные копии по мере возвращения. Вы также должны были бы завершиться нулем в s+1 перед печатью.   -  person Daniel Stevens    schedule 11.10.2015
comment
@Sara Статическая переменная сохраняет свое значение между вызовами функций. В следующий раз, когда вы вызовете функцию, переменная сохранит то значение, которое было в последний раз, когда ей было присвоено значение.   -  person Joel Trauger    schedule 11.10.2015
comment
@JoelTrauger спасибо, я буду иметь это в виду.   -  person Sara    schedule 11.10.2015

Ответы (1)


arrow_upward
2
arrow_downward

Вы очень близко.

Есть две проблемы, обе в цикле for, который проходит через ветки trie:

else{
  printf("%c",'a'+i);
  hold[s] = 'a'+i;
  s++;

Первая проблема заключается в том, что вы печатаете (почти) все дважды. В приведенном выше фрагменте вы печатаете префикс при трассировке дерева. Затем, когда вы дойдете до конца слова, вы напечатаете все слово целиком:

  if(follow->child[i]->end == 1){
    printf("\n");
    hold[s] = '\0';
    printf("%s", hold);
  }

Так что префикс вообще не нужно было печатать, а двойная печать сбивает с толку.

Во-вторых, аргумент s представляет глубину дерева, то есть длину текущего префикса. Поэтому он должен быть постоянным во время исследования узла trie. Но каждый раз, когда вы находите новую ветку, вы увеличиваете ее (s++ в первом фрагменте выше). Вместо этого вам нужно, чтобы рекурсивный вызов использовал s + 1 в качестве аргумента, чтобы он вызывался с правильной длиной префикса.

Вы также можете немного упростить свои управляющие структуры.

Вот пример:

void preorder(struct node *follow, char hold[200], int s){
  int i = 0;
  if(follow == NULL){
    return;
  }
  /* Print the word at the beginning instead of the end */
  if (follow->end) {
    hold[s] = 0;
    printf("%s\n", hold);
  }

  for(i = 0; i < 26; i++){
    /* preorder returns immediately if its argument is NULL, so
     * there's no need to check twice. Perhaps even better would be
     * to do the check here, and not do it at the beginning.
     */
    hold[s] = 'a'+i;
    preorder(follow->child[i], hold, s + 1);
  }
}
person rici    schedule 10.10.2015
comment
Я придумал почти точно такое же решение. У меня было hold[s] = 0, а не s+1. Вы уверены в индексе? - person Daniel Stevens; 11.10.2015
comment
@DanielStevens: Нет, ты прав. Перемещение его на один уровень вверх в дереве вызовов означает, что он должен быть s. Спасибо. - person rici; 11.10.2015
comment
Большое спасибо. Я чувствовал, что мой код становится слишком сложным, и день работы над ним сделал меня слепым к упрощениям. Ваше объяснение имеет смысл. - person Sara; 11.10.2015