向量的双链表列指针双向链接列表

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的各种实例可以直接存储指向彼此的指针，并且在矢量中移动指针不会对其有效性产生任何影响。

当然，这个解决方案还有其他一些需要解决的问题，比如堆管理，这些问题都需要解决。但那将是一个不同的问题。