指定された文字列リストから構築されたトライの可能なノードをすべて出力します。
- 王林転載
- 2023-09-06 18:01:03876ブラウズ
C では、trie はツリーのコレクションを格納するために使用される高レベルのデータ構造です。トライという言葉は検索という言葉に由来しており、番号ツリーまたは接頭辞ツリーと呼ばれます。
文字列のリストが与えられた場合に考えられるすべての結合の例を見てみましょう。
入力文字列を {"tutor", "true", "tuo"}
異なる文字列が 1 つの文字列に連結されていることがわかります。したがって、ここの t と u は、すべての可能な文字列を接続する文字リストです。
この記事では、trie データ構造を使用して、文字列のリスト内のすべての可能な接続を解決します。
＃＃＃文法＃＃＃ リーリーパラメータ
- struct
-このキーワードは、構造データ型を表すために使用されます。
- name_of_ Structure
- 構造に任意の名前を指定します。
構造とは、関連するさまざまな変数を 1 か所に集めたものです。 -
リーリー alpha は、treetrie という名前の
を指す変数の名前です。 alphabet は、文字の合計値を整数として設定するマクロです。 ＃＃＃アルゴリズム＃＃＃
最初に、
‘bits/stdc .h’- という名前のヘッダー ファイルを使用します。これには、C の標準テンプレート ライブラリがすべて含まれています。
-
2 つのマクロ
'alphabet' と - 'max'
を定義しています。これらは、アルファベットの合計文字数と文字の最大値を定義します。
'tree node' という構造体を作成し、レターのアドレスを格納するための - 'tree_node'
へのポインタを定義しています。 bool データ型を使用して変数 'end_word' を定義します。これは文字列の終了文字として使用されます。 ポインタを使用して、トライによって構築されたツリーを表す新しいノードに接続し、
'buildNode' という関数を定義します。 -
文字列を挿入するには、
'ins_recursive_of_string' という再帰関数を作成します。この関数は、itm、str (挿入される文字列)、i (挿入される現在の文字を表す 3 つのパラメータ) を受け入れます。加工済み）。 -
関数
ins() は、 - ins_recursive_of_str()
のラッパー関数としてコード内で定義されています。 tree_trie* itm (tree_trie オブジェクト) と string str (挿入される文字列) の 2 つのパラメーターを受け入れます。現在のノード、挿入される文字列、開始インデックス 0 を使用して再帰関数を呼び出します。 次に、
LeafNode() という関数を作成します。この関数は、tree_trie オブジェクトをパラメータとして受け取り、それがリーフ ノードであるかどうか、つまり子ノードがないかどうかを確認します。 -
Function
display_joint() はコードで定義されており、4 つのパラメータを受け入れます: - tree_trie* root、tree_trie* itm
(現在処理中のノード)、 char str[] (ルート ノードから現在のノードまで形成されたパス文字列を格納するために使用される文字配列 str)、および int レベル (現在のノードの深さを表す整数レベル)。 このコードは、
display_joint() のラッパー関数である - displayJ()
関数を定義します。これは、tree_trie オブジェクトをパラメータとして受け取り、ルート ノード、空の文字配列、および開始レベル 0 をパラメータとして使用して display_joint() 関数を呼び出します。 このコードは、新しい
tree_trie オブジェクトを Trie ルート ノードとして生成する main() 関数を定義します。トライに挿入される文字列のリストを含むベクトル s を生成します。次に、 - ins()
関数を呼び出して、各文字列をトライに挿入します。 最後に、出力の開始を示すメッセージを出力し、
displayJ() 関数を呼び出してすべての Trie 接続ポイントを表示します。 -
＃＃＃例＃＃＃ このプログラムでは、指定された文字列リストから構築されたトライの可能な結合点をすべて出力します。
リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃ 私たちはトライ データ構造の概念を検討し、指定された文字列リストから可能なすべてのトライ結合ポイントを構築しました。出力では、文字 u と t が、tutor、true、tuo などの文字列を使用してトライのすべての可能な結合ポイントを接続していることがわかります。したがって、ツリーは可能な接続点を与えることによってノードを減らすことができます。
以上が指定された文字列リストから構築されたトライの可能なノードをすべて出力します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。