0

所以我正在实现一个尝试将单词存储在字典文件中。我已经实现了插入操作;现在我正在尝试按字典顺序打印。我快得到它了,但我有一个小问题,我不知道如何解决。我还试图记住我的程序的速度,这就是为什么我选择了数组或链表的 trie。这是单个节点的样子:

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

“end”表示单词的完成(例如,单词 book 中字母 'k' 处的 end == 1;这可以防止在检查单词是否已实际插入树中时产生混淆)。

这是方法:

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、john、tex、text。它们应该按该顺序打印并分开行。我的输出看起来像:

boo
book
booking
bookingjohn
bjohntex
bjtext
bjtext

我知道这可能与我的“保持”数组有关,该数组存储单词的前缀,因此它们不会丢失。我需要在某处将索引设置回零以指示前缀及其所有相关单词(嘘,书,预订是一个很好的例子)的完成,但没有成功。任何帮助将不胜感激,我很乐意进一步澄清我的思考过程。

4

1 回答 1

2

你很亲密。

有两个问题,都在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);
  }
}
于 2015-10-10T22:30:13.027 回答