c - 在 C 中打印 trie 中的所有单词

Question

我试图在 C 中打印 trie 的内容。但是我不是很成功。而且让我一开始就说，这是我们现在在学校做的事情，这是一个练习。

这是我的 trie 的样子:

struct node{
char letter;//holds the letter associated with that node
int count;//its count
struct node* child[26];//each node can have 26 children
};

struct trie{
struct node* root;
}

此打印方法必须遍历此 trie 并按字母顺序打印单词，不应打印计数为 0 的单词。

我在考虑递归，这就是我的代码:

void print(node* root){
char buffer[15];//array to store the letters
if(root==NULL){ return;}//if the root is null return
int i;
int index=0; //index for the buffer
int hasAChild=hasChild(root);
if(hasAChild!=0){//the root has children keep on goinf

    for(i=0;i<27;i++){//go thru all the children and if they have children call print                         recursively
       if(hasChild(root->child[i]){
         print(root->child[i]);
         }
       else{
          //if they have no more children add the letter to the buffer
          buffer[index++]=root->child[i]->letter;
        }
          //print the contents in the bufffer
       printf("%s: %d",root->child[i]->count);
  }
}

//函数判断一个节点是否有 child ，如果有则返回他们的编号如果没有，返回0

 int hasChild(root)
    {
  if(root==NULL){
        return 0;
       }

 int i;
 int count=0;
 for(i=0;i<27;i++){
       if(root->child[i]!=NULL){
                   count++;
       }
    }
   return count;
}

原来是这样的

     root
ab'c'defghijklmn'o'pqr's''t'uvwxyz
  'o'           'p'   'o''o'-subtrie-> "contribute", "open", "source"
  'n'           'e'   'u'
  't'           'n'   'r'
  'r'                 'c'-subtrie->"contribute", "to", "open", 
  'i'                     
  'b'
  'u'
  't'
  'e'-subtrie-> "to", "open", "source" 

所以我只假设打印形成的单词，而不是不形成单词的字母。任何帮助或指导将不胜感激。谢谢!

Answer 1

这个呢？

struct list
{
  char *word;
  list *next;
};

void getWord(node *node, list *words, char *previous)
{
  int i;
  char *newWord;
  char *tmp;

  if (node == NULL)
  {
     if (previous == NULL)
       return;
     addBloc(words, previous);
  }
  if (node.count == 0)
     return;
  if (previous == NULL)
  {
    previous = malloc(2);
    previous[0] = node.letter;
    previous[1] = '\0';
  }
  else
  {
    tmp = malloc(strlen(previous) + 2);
    strcpy(tmp, previous);
    tmp[strlen(previous)] = node.letter;
    tmp[strlen(previous) + 1] = '\0';
    free(previous);
    previous = tmp;
  }
  for (i = 0; i < 27; i++)
  {
     if (node.child[i] != NULL)
     {
       getWord(node.child[i], words, strdup(previous));
     }
  }
}

待办事项:

• 使用 (node, NULL, NULL) 调用 getWord;
• 代码函数addBloc，向链表words中添加一个bloc

解释:

目的是遍历所有 child 并构建单词。然后将单词存入链表。

示例:

T和C是A的 child

O是T的 child

I 和 U 是 O 的 child

算法将使

   - previous = 'A'

然后调用T的方法

   - previous = 'AT'

然后调用O的方法

   - previous = 'ATO'

然后调用我的方法

  - previous = 'ATOI'
  - STORE 'ATOI'

然后调用U的方法

  - previous = 'ATOU'
  - STORE 'ATOU'

然后调用C的方法

 - previous = 'AC'
 - STORE 'AC'