深度复制链表 [英] Deep copying linked list

问题描述

我正在尝试使用链接列表在堆上实现堆栈. 但是，对于使用列表"功能，我需要创建链接列表的深层副本，但我不确定该如何完成.

I'm trying to implement a stack on the heap using a linked list. However, for using the 'list' function I need to create a deep copy of the linked list, which i'm not completely sure how it's done.

这是我的代码的一部分:

Here's a part of my code:

class Stack {
    private:
        struct Node  {
           int data;
           Node *next;
       };

        Node *stackTop;

    public:
        Stack() {stackTop = nullptr;}
        Stack(const Stack& original);
        ~Stack();
        bool isEmpty() const;
        int top() const;
        int pop();
        void push(int newItem);
};

Stack::~Stack()   {
        delete stackTop;
}

Stack :: Stack (const Stack& original)   {

// DEEP COPY

}

void list (obj)   {
    cout << "[";
    while(temp -> link != nullptr)
    {
        cout << temp -> data << ",";
        temp = temp -> next;
    }
    cout<< temp -> data << "]" << endl;
    }

推荐答案

我正在尝试使用链接列表在堆上实现堆栈.

I'm trying to implement a stack on the heap using a linked list.

要进行深层复制，只需对列表进行迭代，即可为源列表中的data值分配新的节点.

To make a deep copy, simply iterate the list allocating new nodes for the data values in the source list.

要使用列表"功能，我需要创建链表的深层副本*

for using the 'list' function I need to create a deep copy of the linked list*

不，你不知道.显示堆栈列表内容的功能根本不需要复制任何内容.

No, you don't. A function to display the contents of the stack list should not need to make any copy at all.

尝试这样的事情:

class Stack {
private:
    struct Node {
        int data;
        Node *next = nullptr;
        Node(int value) : data(value) {}
    };

    Node *stackTop = nullptr;

public:
    Stack() = default;
    Stack(const Stack& original);
    Stack(Stack &&original);
    ~Stack();

    Stack& operator=(Stack rhs);

    ...

    void list(std::ostream &out) const;
};

Stack::~Stack()
{
    Node *current = stackTop;
    while (current) {
        Node *next = current->next;
        delete current;
        current = next;
    }
}

Stack::Stack(const Stack& original)
    : Stack()
{
    Node **newNode = &stackTop;
    Node *current = original.stackTop;
    while (current) {
        *newNode = new Node(current->data);
        newNode = &((*newNode)->next);
    }
}

Stack::Stack(Stack &&original)
    : Stack()
{
    std::swap(stackTop, original.stackTop);
}

Stack& Stack::operator=(Stack rhs)
{
    std::swap(stackTop, rhs.stackTop);
    return *this;
}

...

void Stack::list(std::ostream &out)
{
    out << "[";
    Node *current = stackTop;
    if (current) {
        out << current->data;
        while (current->next) {
            out << "," << current->data;
            current = current->next;
        }
    }
    out << "]" << endl;
}

void list(const Stack &obj)
{
    obj.list(std::cout);
}

这篇关于深度复制链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！