Как рекурсивно напечатать все слова в дереве в C - PullRequest
Новая
       12

Как рекурсивно напечатать все слова в дереве в C

0 голосов
/ 29 октября 2018

Я пытаюсь написать функцию, которая печатает все слова в дереве на языке C. Я пробовал много разных методов, но я не получаю никакого вывода.

Вот моя структура: 

typedef struct TNode
{
  char letter;
  struct TNode * children[ALPHABET_SIZE];
  int count; 
}TNode;

Вот мой метод создания дерева. Он принимает URL-адрес, создает массив символов из слов на веб-странице и создает последовательность из массива. 

TNode * indexPage(const char* url)
{
  char buffer[BUFFER_SIZE]; //Holds the characters from the webpage.
  TNode * root;             //The root node of the trie.
  TNode * hold;             //Temporarily holds the node to be added to the trie.
  int charsRead;            //The number of characters read from the webpage.
  int i, j;                 

  charsRead = getText(url, buffer, BUFFER_SIZE);

  //Convert all uppercase letters to lowercase in buffer.
  for(i = 0; i < charsRead; ++i)
  {
    if((buffer[i] >= 'A') && (buffer[i] <= 'Z'))
    {
      //Lowercase characters are 32 greater than uppercase, and 
      //the 'space' ASCII character equals 32.
      buffer[i] += ' ';
    }
  }
  buffer[BUFFER_SIZE - 1] = '\0';

  //Initialize the root TNode.
  root = (TNode *)malloc(sizeof(TNode));
  root->letter = 0;
  root->count = 0;
  for(i = 0; i < ALPHABET_SIZE; ++i)
  {
    root->children[i] = NULL;
  }

  //Create the trie.
  hold = root;
  for(i = 0; i < charsRead; ++i)
  {
    if((buffer[i] >= 'a') && (buffer[i] <= 'z'))
    {
      for(j = 0; j < ALPHABET_SIZE; ++j)
      {
        if(hold->children[j] == NULL)
        {
          hold->children[j] = (TNode *)malloc(sizeof(TNode));
          hold->children[j]->letter = buffer[i];
          hold->children[j]->count = 0;
          int x;
          for(x = 0; x < ALPHABET_SIZE; ++x)
          {
            hold->children[j]->children[x] = NULL;
          }
          hold = hold->children[j];
          break;
        }
        else if(hold->children[j]->letter == buffer[i])
        {
          hold = hold->children[j];
          if((buffer[i + 1] < 'a') || (buffer[i + 1] > 'z'))
          {
            ++(hold->count);
            hold = root;
          }
        }
      }
    }
    return root;
  }

Я убедился, что функция getText правильно заполняет буфер и возвращает количество символов, прочитанных с веб-страницы.

Вот метод печати, который я пытаюсь безуспешно: 

void printTrieContents(TNode * root, char * buffer, int buffIndex)
{
  if(root == NULL)
  {
    return;
  }
  if(root->count != 0)
  {
    printf("\t%s\n", buffer);
  }
  int i;
  for(i = 0; i < ALPHABET_SIZE; ++i)
  {
    if(root->children[i] != NULL)
    {
      buffer[buffIndex] = root->children[i]->letter;
      printTrieContents(root->children[i], buffer, buffIndex + 1);
    }
  }
}

На многих страницах, которые я нашел на этой странице, дерево было создано в алфавитном порядке, но я должен распечатать слова в том порядке, в котором они появляются на странице. Если бы кто-нибудь мог дать мне предложение, я был бы признателен. Спасибо!

Ответы [ 2 ]

0 голосов
/ 30 октября 2018

Хорошо. Я изменил свой код так, чтобы он создавал дерево в алфавитном порядке. Я на самом деле получаю вывод, но это не слова на веб-странице. Это просто бред. Я чувствую, что я уже близко, но я все еще не уверен, что делаю не так.

Я изменил структуру на это: 

typedef struct TNode
{
  struct TNode * children[ALPHABET_SIZE]; //Children nodes
  int count;    //Word count
}TNode;

Вот функция для создания дерева: 

TNode * indexPage(const char* url)
{
  char buffer[BUFFER_SIZE]; 
  TNode * root;             
  TNode * hold;             
  int charsRead;            
  int i, j;                    

  charsRead = getText(url, buffer, BUFFER_SIZE);

  //printf("%s\n",buffer);

  //Convert all uppercase letters to lowercase in buffer.
  for(i = 0; i < charsRead; ++i)
  {
    if((buffer[i] >= 'A') && (buffer[i] <= 'Z'))
    {
      buffer[i] += ' ';
    }
  }

  //Initialize the root TNode.
  root = (TNode *)malloc(sizeof(TNode));
  root->count = 0;
  for(i = 0; i < ALPHABET_SIZE; ++i)
  {
    root->children[i] = NULL;
  }

  //Create the trie.
  hold = root;
  for(i = 0; i < charsRead; ++i)
  {
    if((buffer[i] >= 'a') && (buffer[i] <= 'z'))
    {
      if(hold->children[(buffer[i] - 'a')] == NULL)
      {
        hold->children[(buffer[i] - 'a')] = (TNode *)malloc(sizeof(TNode));
        hold->children[(buffer[i] - 'a')]->count = 0;
        for(j = 0; j < ALPHABET_SIZE; ++j)
        {
          hold->children[(buffer[i] - 'a')]->children[j] = NULL;
        }
      }
      if((buffer[i + 1] < 'a') || (buffer[i + 1] > 'z'))
      {
        ++(hold->count);
        hold = root;
      }
      else
      {
        hold = hold->children[(buffer[i] - 'a')];
      }
    }
  }

  //Return the pointer to the trie.
  return root;
}

Вот функция для печати всех слов в дереве: 

void printTrieContents(TNode * root, char * buffer, int buffIndex)
{
  int i;
  if(root == NULL)
  {
    return;
  }
  if(root->count != 0)
  {
    buffer[buffIndex + 1] = '\0';
    printf("\t%s\n",buffer);
    buffIndex = 0;
  }
  for(i = 0; i < ALPHABET_SIZE; ++i)
  {
    if(root->children[i] != NULL)
    {
      buffer[buffIndex] = i + 'a';
      printTrieContents(root->children[i], buffer, buffIndex + 1);
    }
  }
}

Если я использую, скажем, веб-страницу, содержащую pdf (https://www.constitution.org/us_doi.pdf),, я получаю путаницу, например: 

...        
bnr
emy
ozy
yz
zk
zk
ll
nl
...
0 голосов
/ 29 октября 2018

Три это не что иное, как эффективно организованный алфавитно отсортированный список. Как и любой отсортированный по алфавиту список, он ничего не помнит об исходном порядке его создания. Это отсортировано по алфавиту. Давайте рассмотрим отсортированный по алфавиту список. (Совершенно неважно, как это представляется, с помощью дерева или любым другим способом). 

brown
dog
fox
jumps
lazy
over
quick
the

Из какого текста он был построен? Кто знает. Может быть "быстрая коричневая лиса перепрыгивает через ленивую собаку". Может быть, «собака? Собака ленивая. Лиса? Лиса коричневая. Прыжки? Быстрые прыжки». Может быть из любого из бесконечного числа других текстов. Мы понятия не имеем.

Мы можем привить дополнительные данные в список (опять же, не имеет значения, если это три или что-то еще). Данные могут содержать некоторую информацию о порядке вставки. Давайте попробуем это: 

brown [3]
dog [9]
fox [4]
jumps [5]
lazy [8]
over [6]
quick [2]
the [1,7]

Это уже что-то, но много ли это? Что нужно для восстановления оригинального текста? Похоже, нам нужно извлечь числа, соединить их со словами, поместить пары в (например) массив и отсортировать их, используя числа в качестве ключей. Помогает ли нам алфавитная структура списка? Ни одного бита. Означает ли тот факт, что все вхождения одного слова хранятся вместе? Ни одного бита. Почему мы сохранили это в алфавитном порядке? Ради использования алфавитного списка? Хорошо, тогда мы использовали алфавитный список для комически неэффективного и бесполезного промежуточного хранилища. Если это цель этого упражнения, то мы достигли его.

И еще раз, не имеет значения, организован ли отсортированный по алфавиту список как три или как что-либо еще .

...