C++ プログラム: リンクされたリストで 2 番目に小さい要素を見つける

データ要素の順序付けられたコレクション。各データ要素には、次の要素 (場合によっては前の要素) へのリンクがあります。リンクされたリストがあると仮定すると、2 番目の要素を見つける必要があります。最小の要素。以下は次のシナリオです。

いくつかの単純な入出力シナリオを想定してみましょう

このシナリオでは、リンク リストがあり、それに含まれる要素は "8->4->6->2->9" であると仮定します。 リンクされたリスト全体を反復した後、2 番目に小さい要素は 8 になります。

リーリー

リンクリストのプログラミング実装

リーリー

リンクされたリスト内のすべての要素が同じ値を持つ別の状況を考えてみましょう。すべての要素を反復処理した後、リンクされたリスト内で 2 番目に小さい要素は見つかりません。リンクされたリストの各要素には同じ値が含まれているためです。

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

タスクを実行するときに従う手順は次のとおりです

2 つの変数 (S1、S2) を割り当てます
S1 はリンクされたリストの最小要素を保存します
S2 は、リンクされたリストで 2 番目に小さい要素を保持します。
各反復では、最小の要素が S1 に移動され、それに遭遇すると S2

• に移動されます。

最小値(S1)が新しい小さい値より小さい場合、新しい小さい値が最小値(S1)になります。
新しい小さいものは小さくなり (S1)、小さいもの (S1) は 2 番目の小さいもの (S2) に移動します。
可能な各走査の後、最終出力の 2 番目に小さい要素が出力になります。

• ＃＃＃例＃＃＃
C 実装では、2 つの変数を保持できます。 1 が最小、もう 1 つが 2 番目に小さく、リンク リストが走査されます。より小さい要素が見つかるたびに、最小の変数が次に小さい変数に更新され、新しい小さい変数が最小になります。したがって、要素が最小の要素より小さい場合は常に、2 番目に小さい要素が最小の要素になり、最小の要素が新しい要素になります。そうでない場合は、2 番目に小さい要素を比較し、現在の要素が 2 番目に小さい要素より小さいかどうかを判断し、それに応じて更新します。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

リンク リストを 1 回トラバースすると、時間計算量は O(n) になります。上記の情報が役立つと思われた場合は、公式 Web サイトにアクセスして、プログラミングに関する関連トピックをさらにご覧ください。

以上がC++ プログラム: リンクされたリストで 2 番目に小さい要素を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。