c++ - C++で単一リンクリストをトラバースする

Question

次のようなリンクリストをトラバースできるかどうか疑問に思いました。


currentNode = randomNode;//where randomNode may or may not = firstNode
prevNode = firstNode;
while(prevNode != currentNode && prevNode->link != currentNode)
{
    prevNode = prevNode->link;
}

単一リンクリストでcurrentNodeの前のノードを見つけようとしているときにC++でこれを行うことは可能ですか？

私は学校の課題のコンソールアプリにこのようなものを実装しようとしているので、ブーストライブラリ/リスト/生活を楽にするものなどのような派手なものは使用できないと仮定します。したがって、基本的に、私はかなり原始的なデータ型と私が自由に使えるライブラリ。

score 3 · Accepted Answer

currentNodeが実際にリンクされていない場合に備えて、prevNode->linkもnull参照ではないことを確認することをお勧めします。

score 1 · Accepted Answer

考えられるすべてのエッジケースを必ず考慮してください。

何が起こるrandomNodeのかfirstNode？何を返しますか？何を返せばいいですか？
randomNodeリストの最後のノードはいつですか？
いつ何が起こりrandomNodeますNULLか？
リストにない場合はどうrandomNodeなりますか？

さて、あなたが何かを知っているかどうかによっては、これらのケースのすべてが当てはまるわけではなく、これらのrandomNodeいくつかは些細なことかもしれません。しかし、それらはすべて考える価値があります。

これらすべてを非常に注意深く検討すると、それらすべてを処理するシンプルでエレガントなソリューションがあります。

score 1 · Accepted Answer

1

それはうまくいくはずです。もう試しましたか？

于 2009-10-05T22:57:12.053 に答える

score 1 · Accepted Answer

コードは問題ないように見えますが、while条件を少し変更することをお勧めします

while(prevNode != currentNode && prevNode != NULL)

2つの理由で

現在述べているように、探しているノードがまたはのいずれかでポイントされている場合、コードが停止する可能性があります（したがって、2つのポイントのどちらを指しているprevNodeのprevNode->linkかわかりませんcurrentNode-知りたい場合は、条件で確認してくださいif）。上記の変更により、ターゲットノードはに保存されることが保証されますprevNode（あるとしても、次のポイントを参照してください）。
prevNode安全のために、そうでないことを確認することをお勧めしNULLます。ただし、Pavelが言及しcurrentNodeているように、リストに含まれることが保証されている場合、このテストは不要です。

コメントに応じて編集する

currentNodeがであるprevNodeか、であるかを知る必要がなくprevNode->link、（可能であれば）で停止したいのでcurrentNode == prevNode->link、オリジナルwhileは問題ありません。でも...

prevNodeコードの上位にifステートメントがあり、すでにnullになるのを防ぎます

なぜチェックする必要があるのかという点を見逃しているようですNULL。NULLはい、それは前にチェックするのは良いことですが、ループでチェックを行う理由は、リストにないcurrentNode場合であるため、最終的に最後のノードに到達します。おそらく（他のほとんどのリンクリストのようにこれを行う場合）、最後のノードのの値はです。もしそうなら、あなたの現在のコードは最終的にあなたのプログラムをクラッシュさせるであろう呼び出しをすることになります。だからあなたはまだチェックする必要がありますlinkNULLNULL->linkNULL

while(prevNode != NULL && prevNode != currentNode && prevNode->link!=currentNode)

それがリストに含まれることを絶対に確信しているなら、チェックも不要だと思いますが、それは本当に良い習慣です。currentNode

score 1 · Accepted Answer

そのコードはリストの一部をトラバースしますが、どの部分がリストのリンク方法によって異なります。それが頭->尾から行く場合（読む：頭のノードは尾に向かってリンクするノードにリンクします）、ランダムな場所から尾に向かってリストをトラバースします。リンクがhead<-tailの場合、ランダムな場所から頭までトラバースします。どちらの場合も、リスト内のすべてのノードに触れることはありません。

上記のすべては、そのようないくつかのリンクリストを前提としています。

[head]<->[0...N Nodes]<->[Tail]

リンクはどちらの方法でもかまいません。

また、ヘッドノードとテールノードをリンクして、循環リンクリストを作成することもできます。そのシナリオでは、元のノードに戻るまでトラバースするだけで、すべてのノードにアクセスできます。

score 0 · Accepted Answer

あなたも持つことができます：

while (prevNode && prevNode != currentNode)
    prevNode = prevNode->link;

しかし、あなたが持っているものはうまく見えます。

score 0 · Accepted Answer

投稿されたコードで変更する小さなこと（currentNodeがリストにない場合にリストの最後から実行される他の回答で説明されている可能性や他のエラー処理を除く）は、whileループが実行されるときですかどうか、prevNodeまたはprevNode->linkを指しているかどうかはわかりませんcurrentNode。これは大きな問題ではありませんが（簡単にテストできるため）、検索の前にこの特殊なケースの状況をテストするのが最善のように思われるので、それが特殊なケースであることは明らかです。

c++ - C++で単一リンクリストをトラバースする

7 に答える 7

Related

Reference