向量的雙鏈表列指針雙向鏈接列表

Question

我有一個向量包含雙向鏈表（即std :: vector < DoublyLinkedList>），然後每個雙鏈表將包含一個指向另一個雙鏈表的指針向量。

這裏是什麼我談論的例子：

所以我們可以說，我們有雙向鏈表以下向量，{{1,2,0}，{0,2,1,5 }，{2,1,0,4,5}，{4,5,1,0}，{5,4}}。

讓我們看看向量{1,2,0}中的第一個雙鏈表。我想要的是1指向列表{1,2,0}和2指向列表{2,1,0,4,5}，指向0指向{0,2,1,5}和矢量中的其他列表類似。

除了有這種結構，我還需要指針指向正確的列表，如果我們排列向量的元素。

所以，就是說，如果在上面的例子中我交換第一兩個列表在載體中，其給出：

{{0,2,1,5}，{1,2,0}，{ 2,1,0,4,5}，{4,5,1,0}，{5,4}}

我仍然想在列表{1,2,0}中指出1 { 1,2,0}，2分爲{2,1,0,4,5}，0分爲{0,2,1,5}。

所以我能夠實現每個部分，直到最後一部分。

到目前爲止，我對這部分做的事情是，在排列之前，我可以將每個列表中的所有0指向& vector [1]，然後在置換之後，我將不得不遍歷每個元素每個列表找到0並將它們指向0的新位置，因此他們會指向& vector [k]。

這個問題是我必須搜索每個列表爲0，但我不想做搜索。那麼有沒有什麼方法可以實現這一點，而不必搜索？ （代碼是用C++編寫的）

Answer 1

除了你描述的問題之外，將結構直接存儲在向量中的另一個問題是對向量的某些操作會使某些或全部存在的向量指針無效。即從元素中移除或插入元素。

一般情況下，在這些情況下，向量存儲指向對象的指針，而不是對象本身更好。在你的例子中，std::vector< DoublyLinkedList *>會更好地工作。 DoubleLinkedList的各種實例可以直接存儲指向彼此的指針，並且在矢量中移動指針不會對其有效性產生任何影響。

當然，這個解決方案還有其他一些需要解決的問題，比如堆管理，這些問題都需要解決。但那將是一個不同的問題。