为链表创建复制构造函数

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)

设置为v.head(head = v.head)

2. Set the Elem's values to v's (pri = v.pri , info = v.info , next = v.next)

将Elem的值设置为v(pri = v.pri,info = v.info,next = v.next)

3. Iterate through, repeating step 2.

迭代,重复步骤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.

我很确定这很有效。我画了一些逻辑图片来帮助,我没有遇到任何问题。

5 个解决方案

#1

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应分配一个新节点并将其用作头部。在步骤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 next and prior pointers in the nodes of the new list should refer to new nodes you create specifically for 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.

复制诸如链接列表之类的容器时,您可能需要深层复制,因此需要创建新节点并仅复制数据。新列表的节点中的下一个和先前的指针应该引用您专门为该列表创建的新节点,而不是原始列表中的节点。这些新节点将具有来自原始列表的相应数据的副本,以便可以将新列表视为值或深度副本。

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

这是描绘浅层和深层复制之间差异的图片:

Notice how in the Deep Copy portion 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.

请注意,在图的深层复制部分中,没有一个节点指向旧列表中的节点。有关浅拷贝和深拷贝之间差异的更多信息,请参阅*有关对象复制的文章。

#2

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.head into your new head. Otherwise you'd have two pointers pointing to the same thing.

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

2. You then would have to create a temporary Elem pointer that starts with v.head and iterate through the list, copying its values to new Elem pointers into the new copy.

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

3. See above.

#3

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

您的复制构造函数应该复制什么?它应该复制pri - 容易。它也应该复制信息。如果next不为null,它也应该复制它。你怎么能下次复制?想想递归:嗯,接下来是Elem *,Elem有一个复制构造函数:只需用它来复制引用的Elem并引用它。

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

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

#4

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).

您更愿意为源列表中的每个元素制作一个真正的深层副本(或者只是按需复制,如果您想要花哨的话)。

#5

You forgot the line return; after

你忘记了线路返回;后

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

You need to get out, right?

你需要离开,对吧?