13

我需要实现一个名为 copyList 的辅助函数，它有一个参数，一个指向 ListNode 的指针。该函数需要返回一个指向原始链表副本的第一个节点的指针。因此，换句话说，我需要在 C++ 中编写一个函数，该函数采用链表的头节点并复制整个链表，返回指向新头节点的指针。我需要帮助来实现这个功能，这就是我现在所拥有的。

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;  //holds the current node

    Listnode *copy = new Listnode;
    copy->next = NULL;

    //traverses the list
    while (current != NULL) {
       *(copy->student) = *(current->student);
       *(copy->next) = *(current->next);

        copy = copy->next;
        current = current->next;
    }
    return copy;
}

此外，这是我正在使用的 Listnode 结构：

struct Listnode {    
  Student *student;
  Listnode *next;
};

注意：我在使用此函数时遇到的另一个因素是返回指向局部变量的指针的想法。

4

7 回答 7

5

您需要问自己的第一个问题是复制语义是什么。特别是，您使用的是Student*as 节点内容。复制节点内容是什么意思？我们应该复制指针以便两个列表指向（共享）相同的学生实例，还是应该执行深度复制？

struct Listnode {    
  Student *student; // a pointer?  shouldn't this be a `Student` object?
  Listnode *next;
};

您应该问自己的下一个问题是如何为第二个列表分配节点。目前，您仅在副本中分配 1 个节点。

我认为你的代码应该更像：

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;

    // Assume the list contains at least 1 student.
    Listnode *copy = new Listnode;
    copy->student = new Student(*current->student);
    copy->next = NULL;

    // Keep track of first element of the copy.
    Listnode *const head = copy;

    // 1st element already copied.
    current = current->next;

    while (current != NULL) {
       // Allocate the next node and advance `copy` to the element being copied.
       copy = copy->next = new Listnode;

       // Copy the node contents; don't share references to students.
       copy->student = new Student(*current->student);

       // No next element (yet).
       copy->next = NULL;

       // Advance 'current' to the next element
       current = current->next;
    }

    // Return pointer to first (not last) element.
    return head;
}

如果您更喜欢在两个列表之间共享学生实例，您可以使用

copy->student = current->student;

代替

copy->student = new Student(*current->student);
于 2012-04-10T03:11:08.143 回答
2

这是一个很好的问题，因为你自己完成了大部分工作，比大多数“请为我做作业”的问题要好得多。

几点。

首先，如果你传入一个空列表会发生什么？您可能想提前抓住它，然后将一个空列表返回给调用者。

其次，您只分配副本列表中的第一个节点，您需要为原始列表中的每个节点分配一个。

类似于（用于作业的伪代码（但类似于 C++），抱歉）：

# Detect empty list early.

if current == NULL:
    return NULL;

# Do first node as special case, maintain pointer to last element
# for appending, and start with second original node.

copy = new node()
last = copy

copy->payload = current->payload
current = current->next

# While more nodes to copy.

while current != NULL:
    # Create a new node, tracking last.

    last->next = new node()
    last = last->next

    # Transfer payload and advance pointer in original list.

    last->payload = current->payload
    current = current->next

# Need to terminate new list and return address of its first node

last->next = NULL
return copy

而且，虽然您不应该返回指向本地堆栈变量的指针是正确的，但这不是您正在做的事情。您返回的变量指向堆分配的内存，它将在函数退出后继续存在。

于 2012-04-10T03:08:15.673 回答
1

我一直在尝试做同样的事情。我的要求是：

1. 每个节点都是一个非常基本和简单的类（我离开了结构模型）。
2.我想创建一个深拷贝，而不仅仅是一个指向旧链表的指针。

我选择这样做的方式是使用以下 C++ 代码：

template <class T>
Node <T> * copy(Node <T> * rhs)
{
    Node <T> * current = new Node<T>();
    Node <T> * pHead = current;
    for (Node <T> * p = rhs; p; p = p->pNext)
    {
        Node <T> * prev = current;
        prev->data = p->data;
        if (p->pNext != NULL)
        {
            Node <T> * next = new Node<T>();
            prev->pNext = next;
            current = next;
        }
        else
        {
            prev->pNext = NULL;
        }
    }
    return pHead;
}

这很好用，没有错误。因为“头”是一个特例，所以我需要实现一个“当前”指针。

于 2015-02-11T19:02:05.000 回答
0

说法 copy->next = current->next 是错误的。你应该做

Create the first node copy here
copy->student = current->student;
copy->next = NULL;
while(current->next!=NULL)
{
    Create new node TEMP here
    copy->next = TEMP;
    TEMP->student = current->student;
    TEMP->next = NULL;
    copy = TEMP;
}
于 2012-04-10T03:07:48.413 回答
0

由于您需要链表的副本，因此您需要在遍历原始列表时在循环中创建一个新节点。 

Listnode *startCopyNode = copy;

while (current != NULL) {
   *(copy->student) = *(current->student);
    copy->next = new Listnode;
    copy = copy->next;
    current = current->next;
}

copy->next = NULL;
return startCopyNode;

记住delete链表的节点。

于 2012-04-10T03:07:53.653 回答
0

@pat，我猜你会得到一个 seg_fault，因为你只创建一次内存。您需要为每个节点创建内存（基本上称为“新”）。找出需要在哪里使用“new”关键字来为所有节点创建内存。

完成此操作后，您需要将其链接到前一个节点，因为它是一个单链表，您需要维护指向前一个节点的指针。如果您想学习并且应该能够记住所有生活，请不要看到上面提到的任何代码。尝试考虑上述因素并尝试提出自己的代码。

于 2012-04-10T03:10:07.363 回答
0

正如其他人指出的那样，您需要调用原始列表中new的每个节点来为副本分配空间，然后将旧节点复制到新节点并更新复制节点中的指针。

我在使用此函数时遇到的另一个因素是返回指向局部变量的指针的想法。

您没有返回指向局部变量的指针；当您调用时new，您在堆上分配了内存并返回了一个指向该内存的指针（这当然意味着您需要记住delete在完成新列表后从函数外部调用以释放它）。

于 2012-04-10T03:15:11.327 回答