C++中的双向链表

Question

我有一个作业需要我们实现一个双向链表类。出于某种原因，他们定义了节点struct如下：

struct node {
  node   *next;
  node   *prev;
  T      *o;
};

在我看来，如果结构体成员“data”不是指针，编写该类会更加容易。无需多言，我不能改变它，所以我必须绕过它。我尝试按以下方式实现将元素添加到列表开头的方法：

template <typename T>
void Dlist<T>::insertFront(T *o) {
    node *np = new node;
    T val = *o;

    np->o = &val;
    np->prev = NULL;
    np->next = first;

    if (!isEmpty()) {
        first->prev = np;
    } else {
        last = np;
    }
    first = np;
}

在使用ddd进行调试时，我意识到第一次插入数字时一切都正常，但第二次插入时一切都混乱了，因为一旦将“val”设置为新元素，它就会“覆盖”第一个元素，因为使用了val的内存地址。我尝试做其他事情，例如不仅仅有'val'变量，而是执行以下操作：

T *valp = new T;
T val;
valp = &val;
val = *o;

np->o = valp

这似乎也没有起作用。我认为这是因为它基本上只是我上面所做的更复杂的形式，只是多了一个内存泄漏 :)

有任何想法/指向正确方向的建议都将不胜感激。

- Ian Burris

---

感谢您的值得尊敬的家庭作业免责声明。+1 - Drew Dormann

看一下这个链接，第一个答案可能会帮助你理解问题：https://dev59.com/AnVD5IYBdhLWcg3wWaVh - Dan

有机会的话，也请看一下这个：https://dev59.com/pXRB5IYBdhLWcg3wgXhV -- 栈和堆分配的区别。 - Dan

Answer 1

你创建的T val是一个自动变量。你的错误在于存储了该堆栈变量的地址。

正如你所怀疑的那样，你应该使用new在堆上分配空间，但是你的数据指针需要直接指向new返回的地址。

你最近尝试中的错误在这里:

valp = &val;

你正在将 valp 改为指向其他地方（即 val 的地址），而你可能想要复制 val 的数据，而不是它的地址。

传递给你的函数的数据应该被复制到 valp 指向的新内存中。

- Drew Dormann

---

啊，这就解释了为什么我在尝试读取值时得到了-1074723840的返回值。虽然这很有帮助，但我还是不太确定该如何解决这个问题？你能给我一些关键词来帮助我搜索吗？谢谢。 - Ian Burris

只是挑刺一下：val 不是临时变量。它是一个“自动”变量，也就是栈变量。除此之外，回答得很好。 - Dan

编辑后，希望能回答您的评论。 - Drew Dormann

完全正确，丹。并不是吹毛求疵。我那里用错了术语。 - Drew Dormann

Answer 2

我认为你不应该这样做：

T val = *o;

由于节点结构中的o成员是一个指针，而insertFront的参数也是一个指针，您的教练可能希望您将给定的指针存储在列表中，而不是复制对象并将指针存储到该对象上。只需将传递到insertFront的o指针存储为节点的o成员，您就应该没问题了。

- Wyzard

---

我完全同意。应该写成 np->data = o;。 - Samrat Patil

不一定。应该有一些注释来解释传入的T*是否是动态分配的，DList是否应该拥有它或者是否应该复制它。如果你不知道这些问题的答案，除了靠运气，你不可能正确地实现它。 - Dan

@Sammy，你怎么知道它不应该是 np->data = new(*o);？ - Dan

抱歉，各位，我在将结构体复制到SO后修改了它，但忘记在其他地方进行更改。 - Ian Burris

Answer 3

你认为指针负载不方便。但也许这个列表是用来在现有对象的基础上创建链接的，例如：

struct A { int i; };
A as[10] = { 1,2,3,4,5,6,7,8,9,10 };

LinkedList primes_in_my_data;
insertFront( primes_in_my_data, &as[1] );
insertFront( primes_in_my_data, &as[2] );
insertFront( primes_in_my_data, &as[3] );
insertFront( primes_in_my_data, &as[5] );
insertFront( primes_in_my_data, &as[7] );

// now I have a linked list of primes, and caused no extra memory allocation
// (except for the list overhead)

- xtofl

Answer 4

 T val = *o;

    np->o = &val;

这部分有些可疑。提示是，函数中分配在栈上的内存一旦超出范围，将不再可用。

- aJ.

Answer 5

你的代码与node的定义不符 -- 在node中，你定义了一个data成员，但在你的代码中却使用了o。

无论如何，你需要进行两个动态分配来添加每个节点 -- 一个是节点本身，另一个是它将要指向的数据对象。当你分配那个数据对象时，最好直接将new的返回值赋给节点中的指针。然后，你需要将传递到数据对象中的指针所指向的数据对象复制到你刚刚分配的数据对象中，这样节点中的指针才能指向它。

- Jerry Coffin

---

不错的发现。我在将结构体复制到 SO 后进行了修改，但忘记在其他地方进行更改了。 - Ian Burris