在单个链表 C 中实现复制构造函数

Question

我有一个 C++ 代码：

 #include <iostream>
using namespace std;
struct Node;

typedef Node *NodePtr;

struct Node
{
    int Item;
    NodePtr Next;
};

class LinkedList
{
public:
    LinkedList();                   // default constructor
    ~LinkedList();                  // destructor
    void AddTail(int);              // adds item to tail
private:
    NodePtr Head;
};

LinkedList::LinkedList()
{
    Head = NULL; //declare head as null
}
//Adding on tail
void LinkedList::AddTail(int Item)
{
    NodePtr Crnt;
    NodePtr node = new Node;
    node->Item = Item;
    node->Next = NULL;
//if head is in null declare the added node as head
    if (Head == NULL)
    {
        Head = node;
    }
    else
    { //set the current to head, move the current node to current next node
        Crnt = Head;
        while (Crnt->Next != NULL)
        {
            Crnt = Crnt->Next;
        }
        //Add item to the tail of the linked list
        Crnt->Next = node;
    }
}

int main()
{
    LinkedList la;
    la.AddTail(30);
    la.AddTail(60);
    la.AddTail(90);
    LinkedList lb;
    return 0;
}

所以我的问题是如何实现一个复制构造函数（假设在对象 lb 上），它对列表参数进行深层复制，并添加代码来测试空列表和非空列表上的复制构造函数？提前致谢。

原文由 Pattrick 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

编程的一大规则是不要重复自己（DRY）。如果您有一个添加功能并且您知道它可以工作，请继续将其用于与添加相关的工作。这意味着继续添加愚蠢和多才多艺的内容符合您的最大利益。

应用 DRY 理念，复制构造函数，假设 AddTail 方法正常工作，非常简单：为源列表中的每个节点调用 AddTail 。

 LinkedList::LinkedList(const LinkedList & src):Head(nullptr)
{
    NodePtr node = src.Head;
    while (node != nullptr)
    {
        AddTail(node->Item);
        node = node->Next;
    }
}

由于 Copy 和 Swap Idiom ，拥有一个有效的复制构造函数使得赋值运算符也简单得可笑：

 LinkedList & LinkedList::operator=(LinkedList src)
// pass by reference performs the copy
{
    std::swap(Head, src.Head); // now just swap the head of the copy
                               // for the head of the source
    return *this;
} // destructor fires for src and cleans up all the nodes that were on this list

为了完成 三连胜的规则， 我们需要一个析构函数。这就像复制构造函数是 DRY 的一个应用程序：一遍又一遍地调用你的节点删除函数，直到列表为空。删除函数几乎是任何链表的必然要求，所以在这里我假设有一个名为 Remove 的函数。

 LinkedList::~LinkedList()
{
    while (Head != nullptr)
    {
        NodePtr temp = Head;
        Remove(Head);
        delete temp;
    }
}

因此，现在基于链接列表无法运行的两个功能，无论如何我们已经实现了基本维护所需的所有其他功能。您需要的所有功能都经过测试且 Add 和 Remove 功能，其余功能几乎免费。

而且因为 AddTail 函数碰到了我的一个宠物……这是一个大大降低函数复杂性的技巧：

 void LinkedList::AddTail(int Item)
{
    NodePtr *Crnt = &Head; // instead of pointing where Head points, point at
                           // Head now we don't care if it is head or any
                           // other node's Next. They are all abstracted to
                           // the same thing: A pointer to where the next
                           // node can be found
    while (*Crnt != NULL) // keep looking until end of list
    {
        Crnt = &(*Crnt)->Next; // by pointing at the next Next pointer
    }
    //Add item to the tail of the linked list
    NodePtr node = new Node;
    node->Item = Item;
    node->Next = NULL;
    *Crnt = node; // Now just plop the new node over top of the terminating NULL
}

我没有实现的 Remove 函数使用相同的指针到指针技巧。

原文由 user4581301 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

试试这个（ https://ideone.com/9lywXc 使用您原来发布的代码）

 LinkedList::LinkedList(const LinkedList& other):Head(nullptr)
{
    cout << "copy constructor called:\n";
    if(other.Head == nullptr) return;
    NodePtr dummyHead = new Node;
    NodePtr curr = dummyHead;
    NodePtr othcurr = other.Head;
    for(; othcurr!=nullptr; othcurr = othcurr->Next)
    {
        curr->Next = new Node;
        curr = curr->Next;
        cout << (curr->Item = othcurr->Item) << ",";
        curr->Next = nullptr;
    }
    Head = dummyHead->Next;
    delete dummyHead;
}

int main()
{
    LinkedList la;
    la.AddTail(30);
    la.AddTail(60);
    la.AddTail(90);
    LinkedList lb(la);
    return 0;
}

输出：

复制构造函数调用：

30,60,90,

原文由 chrisg 发布，翻译遵循 CC BY-SA 3.0 许可协议