0

そこで、単語を辞書ファイルに保存する試みを実装しています。挿入操作を実装しました。今、私は辞書的に印刷しようとしています。私はそれを手に入れようとしていますが、修正方法がわからないという小さな問題があります。また、プログラムの速度にも注意を払っています。そのため、配列または連結リストよりもトライを選択しました。単一のノードは次のようになります。

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

"end" は、単語の完成を示します (たとえば、単語帳の文字 '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

これはおそらく、単語の接頭辞が失われないように格納する「ホールド」配列と関係があることを知っています。接頭辞とそれに関連するすべての単語 (boo、book、booking が良い例) の完了を示すために、どこかでインデックスをゼロに戻す必要がありますが、成功していません。どんな助けでも大歓迎です。私の思考プロセスをさらに明確にすることができれば幸いです.

4

1 に答える 1

2

あなたはとても近くにいます。

2 つの問題があり、どちらもforトライ ブランチを通過するループにあります。

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

最初の問題は、(ほぼ) すべてを 2 回印刷していることです。上記のスニペットでは、ツリーをトレースしながらプレフィックスを出力します。その後、単語の終わりに到達したら、単語全体を出力します。

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

したがって、プレフィックスを印刷する必要はまったくなく、二重印刷は混乱を招きます。

次に、s引数はツリーの深さを表します。これは、現在のプレフィックスの長さです。したがって、トライノードの探索中は一定である必要があります。ただし、新しいブランチを見つけるたびに、それをインクリメントします (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 に答える