在 C++ 中编写一个函数来复制链表

2022-01-01 00:00:00 linked-list c++

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

I need to implement an auxilliary function, named copyList, having one parameter, a pointer to a ListNode. This function needs to return a pointer to the first node of a copy of original linked list. So, in other words, I need to code a function in C++ that takes a header node of a linked list and copies that entire linked list, returning a pointer to the new header node. I need help implementing this function and this is what I have right now.

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 结构:

Also, this is the Listnode structure I am working with:

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

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

Note: another factor I am running into with this function is the idea of returning a pointer to a local variable.

推荐答案

您需要问自己的第一个问题是复制语义是什么.特别是，您使用 Student* 作为节点内容.复制节点内容是什么意思?我们应该复制指针以便两个列表指向(共享)相同的学生实例，还是应该执行 深拷贝?

The first question you need to ask yourself is what the copy semantics are. In particular, you're using a Student* as node contents. What does copying node contents mean? Should we copy the pointer so that the two lists will point to (share) the same student instances, or should you perform a deep copy?

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

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

The next question you should ask yourself is how you will allocate the nodes for the second list. Currently, you only allocate 1 node in the copy.

我认为你的代码应该看起来更像:

I think you code should look more like:

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;
}

<小时>

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

If you prefer sharing student instances between the two lists, you can use

copy->student = current->student;

代替

copy->student = new Student(*current->student);

相关文章