c++ - 在复制构造函数中执行深复制

Question

我有一个定义如下的类栈:

#ifndef STACK_H
#define STACK_H
#include "MyException.h"
#include <iostream>

using namespace std;

template<class T>
class Stack;

template<class T>
ostream& operator<<(ostream&,Stack<T>&);

template<class T>
class Stack
{
public:

    friend ostream& operator<< <T>(ostream&,Stack<T>&);

    /*The constructor for the Stack class*/
    Stack();

    /*The copy constructor*/
    Stack(const Stack<T>& other);

    Stack<T>& operator=(const Stack<T>& other);

    /*The destructor for the stack class*/
    ~Stack();

    void push(const T& el);

    T pop();

    bool isEmpty();

private:
    /*The node class.*/
    class Node
    {
        public:
            Node(const T& data, Node* n = 0)
            {
                element = data;
                next = n;
            }

            T element;
            Node* next;
    };

    /*The top of the stack*/
    Node* top;
};
#include "Stack.C"
#endif

而且我必须在我的复制构造函数中执行深复制。但是我所做的是创建一个临时数组并将参数接收到的对象中的所有元素复制到数组中，然后将节点复制到数组中，然后将所有元素推送到 Stack 类中定义的节点中。我是这样做的:

template<class T>
    Stack<T>::Stack(const Stack<T>& other)
    {

        top = NULL;

        if(other.top == NULL)
        {
            this->top=NULL;
        }

        else
        {

            Node* count;
            count= other.top;

            int num=1;

            while(count->next != NULL)
            {
                num++;
                count = count->next;
            }
            cout<<"test"<<endl;



            T arr[num];
            arr[0] = other.top->element;



            Node* count2;
            count2= other.top;

            for(int i = 1 ; i<num; i++)
            {
                arr[i] = count2->next->element;

                count2 = count2->next;
            }

            T temp;
            for(int i =0, j=num-1; i<num/2 ; i++, j--)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }


            for(int i =0; i<num; i++)
            {
                push(arr[i]);
                cout<<arr[i]<<endl;
            }
        }
    }

您可以假设我的 push(const T& el) 和 pop() 工作正常。谁能帮我做一个深拷贝？

Answer 1

没有理由用数组来深度复制堆栈。由于您拥有指向当前堆栈链中节点的所有指针，因此只需遍历该链表即可。该算法的不寻常部分涉及在新节点输入时前向链接，从而保留原始堆栈顺序。有多种方法可以做到这一点，但我更喜欢使用一个指针到指针，它始终保存将在下一个拷贝中填充的指针的地址。

Stack(const Stack<T>& other)
    : top(nullptr)
{
    const Node* p = other.top;
    Node **pp = &top;
    while (p)
    {
        *pp = new Node(*p);
        p = p->next;
        pp = &(*pp)->next;
    }
    *pp = nullptr;
}

完成后，堆栈将被深拷贝复制并保留源对象顺序。我强烈建议实现 Node(const Node&) 复制构造器，仅 复制数据元素并将下一个指针硬设置为 null。

工作原理

归根结底，这只不过是前向链表的单次扫描拷贝。指针 pp 始终保存将分配给新节点的下一个指针的地址。重要的是要记住它寻址的指针是列表的一部分，而不是某个临时指针。最初 pp 被分配了顶部指针的地址，并非巧合的是它已经被初始化为 NULL。从那里开始，重复以下操作，直到我们用完所有节点:

1. 将当前源节点的拷贝分配给*pp。这意味着由 pp 寻址的指针将接收新的节点地址。
2. 推进 pp 以保存刚刚分配的节点的 next 成员的地址。这成为下一次插入的下一个目标
3. 将源指针推进到下一个源节点。

重复此操作，直到我们用完所有节点。那时 pp 保存着 last 节点的 next 指针的地址，应该为我们的列表分配 null 以正确终止。这就是关闭 *pp = nullptr; 的目的。这样，列表现在就终止了，对象现在有了源对象链表的拷贝。

一些值得思考的东西。如果源列表最初是空的，会发生什么？这是否适用于循环列表(答案:否，甚至不要尝试)。