遍歷C++單鏈表

我想知道是否有可能遍歷鏈表這樣的：遍歷C++單鏈表


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

是否有可能做到這一點在C++中，當我試圖找到節點currentNode之前在一個單獨的鏈表中？

我試圖在學校任務的控制檯應用程序中實現類似的東西，所以假設我不能使用任何像boost庫/ list /任何讓生活變得更容易的東西等等。所以基本上，我只有我可以使用相當原始的數據類型和庫。

來源

2009-10-05 cskwrd

爲什麼「想知道」你是否可以試試看看它是如何工作的？我在這裏沒有看到任何問題，假設你總是至少有一個節點，並且'randomNode'保證是列表中的一個有效節點（所以你永遠不會運行「結束」）。 – 2009-10-05 22:58:28

你到底想做什麼？在鏈表中搜索節點？ – Ashwin 2009-10-05 22:59:52

while條件看起來有點奇怪...爲什麼要測試prevNode！= currentNode？另外，列表可以是空的嗎？是否可以發生currentNode不在列表中？ – 2009-10-05 23:03:17

如果currentNode未實際鏈接，您可能需要確保prevNode->鏈接不是空引用。

來源

2009-10-05 22:58:08

如果currentNode保證位於列表中（從描述中看，它似乎是），循環將始終在列表結束之前終止。 – sepp2k 2009-10-05 23:01:10

這應該工作得很好。你試過了嗎？

來源

2009-10-05 22:57:12

是和不是。它在我的代碼中，但還有其他部分丟失，我沒有爲它工作幾天，所以並不是所有東西都「連接起來了」 – cskwrd 2009-10-05 23:59:01

，你甚至可以有：

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

但是，你有什麼看起來不錯。

來源

2009-10-05 23:06:16 Ashwin

的代碼看起來不錯，但我建議一個小的改動你的while條件

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

兩個原因

您的代碼，按照目前的規定，可能會停止，如果節點我們尋找是由prevNode或prevNode->link（並因此我們不知道哪兩個點中的哪一個特定currentNode - 如果我們想知道，我們將不得不檢查與if c ondition）。隨着上面的變化，目標節點被保證存儲在prevNode（如果有的話 - 請參閱下一點）。
爲了安全起見，最好檢查prevNode不是NULL。但是，正如帕維爾提到的，如果currentNode保證在列表中，則此測試是不必要的。

編輯迴應評論

既然你不需要知道currentNode是否prevNode或prevNode->link，既然你要停止（如果可能）上currentNode == prevNode->link，那麼你的原始while是好的。然而...

有一個if語句中防止 prevNode從被空的代碼越往上已經

好像你缺少的，爲什麼你應該檢查點爲NULL。是的，這很好，你之前檢查它，但是爲什麼我們在循環中檢查NULL的原因是currentNode是而不是，因此您最終會到達最後一個節點。據推測（如果你像大多數其他鏈表一樣）link爲你的最後一個節點的值是NULL。如果是這樣，你當前的代碼最終會調用NULL->link，這當然會導致程序崩潰。這就是爲什麼你還是應該檢查NULL

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

如果你絕對相信這currentNode將出現在列表中，然後我猜，辦理入住手續也沒有必要的，但它確實是一個好習慣進入。

來源

2009-10-05 23:07:40 GRB

我有這種情況的原因，因爲在代碼中有更高的if語句可以防止prevNode已空，所以基本上我想確保prevNode等於當前節點或currentNode之前的節點。 – cskwrd 2009-10-05 23:56:24

該代碼將遍歷列表的一部分，但哪部分取決於列表鏈接的方式。如果它從head-> tail（讀取：頭節點鏈接到一個鏈接到尾部的節點），那麼您將遍歷從隨機位置開始到尾部的列表。如果鏈接是頭< -tail，那麼你會從隨機位置遍歷頭部。無論哪種情況，您都不會觸摸列表中的所有節點。

上述所有假設一些鏈接列表這樣：

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

的鏈接可能是兩種方式。

此外，您可以鏈接頭部和尾部節點並創建一個循環鏈接列表。在這種情況下，可以通過簡單遍歷訪問所有節點，直到返回到原始節點。

來源

2009-10-05 23:16:19 RyanY

一個小的東西，我會改變與張貼的代碼（除了在其他答案中討論的可能性，如果currentNode不在列表或其他錯誤處理的情況下跑掉列表的末尾）是當while循環完成後，您不知道prevNode或prevNode->link指向currentNode。這不是一個大問題（因爲你可以很容易地測試它），但在我看來，最好在搜索之前測試這種特殊情況，所以很明顯這是一種特殊情況。

來源

2009-10-05 23:28:35

確保您考慮所有可能的邊緣情況：

會發生什麼randomNode等於firstNode？你回來了什麼？ 您應該返回？
當randomNode是列表中的最後一個節點時會發生什麼？
randomNode是NULL會發生什麼情況？
randomNode不在列表中時會發生什麼？

現在，不是所有的這些案件可以適用，這取決於如果你知道什麼randomNode，而其中的一些可能是微不足道的。但他們都值得思考。

如果你仔細考慮所有這些，有一個簡單而優雅的解決方案來處理它們。

來源

2009-10-05 23:44:51

遍歷C++單鏈表

回答

相關問題