C++ の二重循環リンク リスト内の要素を検索する

二重循環リンク リストとキーワードが与えられた場合、リンク リストでキーワードを検索し、見つかったときに適切なメッセージを与える必要があります。特定の文字を含むリンク リストがあり、その中の要素を検索する必要があるとします。それでは、次のリンクリストから始めましょう -

5 8 9 2 4

指定された問題の解決策を見つけるためのキーとして 4 を使用します。二重リンクリストには固定ヘッドがないため、任意のノードから開始して、再びヘッドに遭遇するまでそのノードをヘッドとしてマークし、そこでリンクリストの線形検索を実行してキーワードを検索します。

いくつかの入出力シナリオを見てみましょう -

5 つのノード 3 4 5 6 7 を持つ双方向循環リンク リストがあるとします。求めたいのは の要素は 6 です。

リーリー

二重循環リンク リスト内に検索する要素がない別の状況を考えてみましょう。

リーリー ＃＃＃アルゴリズム＃＃＃

次にアプローチする手順を示します。

リンク リストを実装し、リンク リストの各ノードに前方ノードを割り当てることで値を渡します。
ノードの前の部分を最後のノードの次の部分に割り当てます。
ノードの前の各部分をノードの次の部分に割り当てます。
key 要素を、二重循環リンク リストに存在するかどうかを確認する key 要素に渡します。
キーが双方向循環リンク リストに存在する場合は true を返します。
それ以外の場合は、false を返します。
Example

の中国語訳は次のとおりです:

Example

以下は、二重リンクリストで検索操作を実行するための C 実装コードです。 リーリー ＃＃＃出力＃＃＃ リーリー

説明

の中国語訳は次のとおりです:

説明

キーワード 4 は二重リンクリストに存在します。

＃＃＃結論は＃＃＃

二重循環リンク リストでは、固定された先頭と末尾がないため、任意の位置から開始できます。上記の方法では、擬似的な頭である「頭」があり、ここから検索を開始します。上記のアルゴリズムは線形探索であるため、時間計算量は O(n) です。

以上がC++ の二重循環リンク リスト内の要素を検索するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。