C++鏈表遍歷和修改

鏈表：C++鏈表遍歷和修改

pointer2 -> [a] 
pointer ->[a] -> [b] -> [c] -> [d] -> null  
pointer = b; //makes it point one down so it will be pointer -> [b] ->[c] -> [d] -> null  
pointer = pointer 2; //makes pointer point back to where it was pointing to before, both pointers point to [a] 
pointer2 = pointer->next; //makes pointer 2 point to [b] 
pointer2->next = pointer->next; //makes [c] point to [b]

是我的理解是否正確？節點可以指向自己嗎？像pointer-> next = pointer-> next？

基本上是：

指針=指針2 - 使指針指向任何指針2指向？
指針 - >下一=指針2 - 使該指針指向指向指針2鏈路節點鏈路節點
指針 - >下一= pointer2->下 - 使該指針指向後指向一個鏈路節點指針指向的鏈接節點
指針=指針2 - >下一個 - 使指針指向指向一個指針2後的鏈接節點的指針。

是嗎？

來源

2017-10-16 Duxa

在普通PC上，指針變量只是一個整數，其值是一個地址在記憶中。您可以像任何其他變量一樣以任何方式分配此值。只要變量的類型當然是兼容的。 –

是的，我明白指針是什麼。我試圖確認我是否理解如何瀏覽鏈接列表是正確的。如果底部的這些任務按照我認爲他們所做的做。 – Duxa

節點能指向自己嗎？

正如其他人所說，這當然是可能的。但是，也許你的意思是「這是否有效？」。答案就是，它取決於操縱鏈表的代碼。如果您正在編寫該代碼，那麼這取決於您是否有效。

例如，您可能會決定當節點指向自身時，則表示鏈接列表的末尾。那麼這裏就是你怎麼可能代碼搜索一個整數鏈表數3功能：

struct ListNode { 
    int value; 
    ListNode* next; 
}; 

bool containsThree(ListNode* list) { 
    for (; list->next != list; list = list->next) { 
     if (list->value == 3) { 
      return true; 
     } 
    } 
    // Also check final node 
    if (list->value == 3) { 
     return true; 
    } 
    return false; 
}

另外，您可以決定next == nullptr意味着列表的末尾。在這種情況下containsThree看起來更像是這樣的：

bool containsThree(ListNode* list) { 
    for (ListNode* node = list; node; node = node->next) { 
     if (node->value == 3) { 
      return true; 
     } 
    } 
    return false; 
}

有了這項新功能，如果在本身的任何節點分則函數會永遠循環下去。你可以解決這個問題，甚至在列表中選中了較大的循環，就像這樣：

bool containsThree(ListNode* list) { 
    std::set<ListNode*> seenNodes; 
    for (ListNode* node = list; node; node = node->next) { 
     if (seenNodes.count(node)) { 
      break; 
     } 
     seenNodes.insert(node); 
     if (node->value == 3) { 
      return true; 
     } 
    } 
    return false; 
}

有此功能的最後一個問題：它比前一個顯著的性能損失。因此，是否允許列表中的循環取決於您，並且您將在命令中檢查它們，否則將不允許循環。任何一個都是正確的，你只需要做出決定並堅持下去。

（編輯：第一個例子功能是有點亂，因爲剛剛我們期待在最後一個節點3之前結束循環的條件這樣做，它也不可能在一個空的列表來傳遞這兩個。 nullptr例子中的問題已經修復，但實際上甚至可以使用「node == node->next意味着列表結束」規則來修復它們，關鍵是在鏈表的末尾添加一個虛擬節點，並要求這個額外的節點具有這個屬性，你不需要檢查這個節點是否具有三重性，而這個節點本身就表示一個空的列表）。

來源

2017-10-16 09:51:15

你是最後一個指針賦值權exect：

... 
pointer2 = pointer->next; //makes pointer 2 point to [b]: Ok 
pointer2->next = pointer->next; //makes [c] point to [b]: Wrong

pointer2點，[B]，並pointer->next點到B。最後指針賦值使乙組分本身導致：

pointer2 -> b -> b !

和：

pointer -> a -> b -> b

你誤解可能來自一個事實，即你的僞代碼不明確什麼是a，b，C和d，代表下一步以及您使用地址的位置。寫下所有這些都是C++，它會更清晰。

來源

2017-10-16 09:27:17

Linked data structure有一個指針用於當前數據，一個用於下一個（它是指向下一個當前數據的指針），如果是雙向鏈表，那麼一個指向前一個（這是指向當前數據的指針的前一個）。

節點能指向自己嗎？像pointer-> next = pointer-> next？

是的。這與將任何指針分配給自身相同。不是很有用。

指針 - >下一= pointer2->下 - 使該指針指向指針2點

指針= pointer2->下鏈路節點之後指向一個鏈路節點 - 使指針指向一個pointer2指向的鏈接節點之一。

在此之後然而，當前數據指針和下一個數據指針是相同的，點同樣的事情。這意味着如果有人想沿着這個鏈表進行遍歷，如果他們沒有指針檢查，它們可能會以無限循環結束。

來源

2017-10-16 09:32:29 Griffin

C++鏈表遍歷和修改

回答

相關問題