C++ 为链表创建复制构造函数

Creating a copy constructor for a linked list

提问by Joshua

This is homework

这是作业

I'm working on implementing a linked list class for my C++ class, and the copy constructor has be very confusing for me.

我正在为我的 C++ 类实现一个链表类，而复制构造函数对我来说非常混乱。

The linked list is comprised of structs called Elems:

链表由称为 Elems 的结构组成：

struct Elem 
    {
        int pri;
        data info;
        Elem * next;
    };
    Elem * head;

info is a separate, custom class that is stored in the Elem.

info 是一个单独的自定义类，存储在 Elem 中。

the signature for the copy constructor is:

复制构造函数的签名是：

linkedList::linkedList( const linkedList &v )

The issue I am having is mostly taking my logic and actually writing it as code.

我遇到的问题主要是采用我的逻辑并将其实际编写为代码。

My general idea is to:

我的总体思路是：

1. Set head to v.head (head = v.head)
2. Set the Elem's values to v's (pri = v.pri , info = v.info , next = v.next)
3. Iterate through, repeating step 2.

1. 将 head 设置为 v.head (head = v.head)
2. 将 Elem 的值设置为 v (pri = v.pri , info = v.info , next = v.next)
3. 迭代，重复步骤 2。

Is this the general idea?

这是一般的想法吗？

Any help would be great. Remember, this is homework, so no direct answers please!

任何帮助都会很棒。请记住，这是作业，所以请不要直接回答！

Thank you for your time

感谢您的时间

====================================================================================================================================================================

================================================== ================================================== ================================================== ==============

Thanks for your time everybody!

谢谢大家的时间！

I think I have it figured out:

我想我已经弄清楚了：

//Copy Constructor
LinkedList::LinkedList( const LinkedList &v )
{
Elem * p1 = 0;//current
Elem * p2 = 0;//next

if( v.head == 0 )
    head = 0;

else
{
    head = new Elem;
    head -> pri = v.head -> pri;
    head -> info = v.head -> info;

    p1 = head;
    p2 = v.head -> next;
}

while( p2 )
{
    p1 -> next = new Elem;
    p1 = p1 -> next;
    p1 -> pri = p2 -> pri;
    p1 -> info = p2 -> info;

    p2 = p2 -> next;
}
p1 -> next = 0;
}

I'm pretty sure that works. I drew some logical pictures to help, and I didn't run into any issues.

我很确定这有效。我画了一些合乎逻辑的图片来提供帮助，我没有遇到任何问题。

回答by Michael Goldshteyn

You have to be careful with Step 1 and part of Step 2. Step 1 should allocate a new node and use that as the head. In Step 2, the part about next = v.next, unless your intention is to make a shallow copy, is incorrect.

您必须小心步骤 1 和步骤 2 的一部分。步骤 1 应分配一个新节点并将其用作head. 在第 2 步中，关于 的部分next = v.next，除非您打算进行浅拷贝，否则是不正确的。

When you copy a container such as a linked list, you probably want a deep copy, so new nodes need to be created and only the data copied over. The nextand priorpointers in the nodes of the new list should refer to new nodes you create specificallyfor that list and not the nodes from the original list. These new nodes would have copies of the corresponding data from the original list, so that the new list can be considered a by value, or deep copy.

当您复制一个容器（如链表）时，您可能需要一个深层复制，因此需要创建新节点并且只复制数据。在next与prior指针在新的列表中的节点应该是指你创建新的节点专为列表，而不是节点从原来的名单。这些新节点将拥有原始列表中相应数据的副本，因此可以将新列表视为按值或深度复制。

Here is a picture depicting the differences between shallow and deep copying:

这是一张描绘浅复制和深复制之间差异的图片：

Notice how in the Deep Copyportion of the diagram, none of the nodes point to nodes in the old list. For more information about the difference between shallow and deep copies, see the Wikipedia article on object copying.

注意图中的Deep Copy部分，没有一个节点指向旧列表中的节点。有关浅拷贝和深拷贝之间区别的更多信息，请参阅维基百科关于对象复制的文章。

回答by Zeenobit

1. You shouldn't set this->head = v.head. Because the head is simply a pointer. What you need to do is to create a new head and copy the values individually from v.headinto your new head. Otherwise you'd have two pointers pointing to the same thing.

2. You then would have to create a temporary Elempointer that starts with v.headand iterate through the list, copying its values to new Elempointers into the new copy.

3. See above.

1. 你不应该设置this->head = v.head. 因为头部只是一个指针。您需要做的是创建一个新头并将值单独复制v.head到新头中。否则，您将有两个指针指向同一事物。

2. 然后，您必须创建一个临时Elem指针，该指针以v.head该列表开头并遍历该列表，将其值复制到新Elem指针中的新副本中。

3. 看上面。

回答by Landei

What should your copy constructor copy? It should copy pri- easy. It should copy info- easy as well. And if nextis not null, it should copy it, too. How can you copy next? Think recursive: Well, nextis an Elem *, and Elemhas a copy constructor: Just use it to copy the referenced Elemand refer to it.

你的复制构造函数应该复制什么？它应该复制pri- 容易。它应该复制info- 也很容易。如果next不为空，它也应该复制它。你怎么能复制next？考虑递归：嗯，next是一个Elem *，并且Elem有一个复制构造函数：只需使用它来复制引用Elem并引用它。

You can solve this iteratively, too, but the recursive solution is much more intuitive.

您也可以迭代解决这个问题，但递归解决方案更直观。

回答by cli_hlt

So here is my answer (don't know if that fits to your homework or not - instructors tend to have their own ideas sometimes ;):

所以这是我的答案（不知道这是否适合您的家庭作业 - 教师有时往往有自己的想法；）：

Generally a copy constructor should "copy" your object. I.e. say you have linkedList l1, and do a linkedList l2 = l1 (which calls linkedList::linkedList(l1)), then l1 and l2 are totally separate objects in the sense that modification of l1 doesn't affect l2 and vice versa.

通常，复制构造函数应该“复制”您的对象。即说你有linkedList l1，并做一个linkedList l2 = l1（它调用linkedList::linkedList(l1)），那么l1和l2是完全独立的对象，因为l1的修改不会影响l2，反之亦然。

When you just assign pointers you won't get a real copy, as dereferencing and modifying either of them would affect both objects.

当您只分配指针时，您将不会获得真正的副本，因为取消引用和修改它们中的任何一个都会影响两个对象。

You rather want to make a real deep copy of every element in your source list (or do a copy-on-demand only, if you want to be fancy).

您更愿意为源列表中的每个元素制作真正的深层副本（或者仅按需复制，如果您想变得更漂亮）。

回答by andy

You forgot the line return;after

你忘记了return;之后的线路

if( v.head == 0 )
    head = 0;

You need to get out, right?

你需要出去，对吗？