对如何制作双链表的深层副本感到困惑？

2024-06-02 • 问答

我一直在尝试实现双向链接列表的深层副本，但是我一直在遇到麻烦。我必须做几次不同的操作，但是最终出现地址错误。我只需要解释一下如何正确执行操作即可。

List.H

class List 
{
public:
    List();
    ~List();
    List(const List& c);
    List& operator= (const List& t);
private:
    List *Next;
    List *Prev;
    Node *Head;

List.cpp

List::~List()
{
    Node* move = Head;
    while (move!=NULL)
    {
        Node *temp = move->Next;
        delete move;
        move = temp;
    }
}

List::List(const List& c)
{
    name = c.name;
    if (c.Head == NULL) {
        Head = NULL;
    }
    else {
        Head = new Node(*c.Head);
        Node* Current = Head;
        Node* ObjHead = c.Head;
        Node* CurrentObj = ObjHead;

        while (Current->Next!=NULL) {
            Current->Next = new Node (CurrentObj->Next->condiments);
        }
    }
}

复制链表涉及三件事：

遍历要复制的列表。
从原始副本中复制新节点。
对于（2）中的每个新节点，将其尾链到链接列表。

第一个是微不足道的，第二个是相当基本的，但是第三个是经常把人扔掉的循环。对于您的复制对象，一种实现方法是使用指针到指针。这样，我们就可以通过链接列表中的每个指针自己的地址来对其进行寻址。

List::List(const List& c)
    : Head(nullptr),name(c.name)
{
    Node *prev = nullptr;
    Node **pp = &Head;

    for (const Node *p = c.Head; p; p = p->Next)
    {
        // make a new node,storing its address at the
        // pointer obtained by dereference of `pp`. the
        // first iteration that will be the Head member.
        *pp = new Node(*p);
        (*pp)->Prev = prev;
        prev = *pp;

        // now just advance `pp` to point to the `Next`
        // member of the node we just hung on the list.
        pp = &(*pp)->Next; 
    }
    *pp = nullptr; // terminate the list.
}

这假设您是Node类，它支持复制构造（最好）。但这就是全部。由此，您可以使用copy/swap idiom来制造您的副本分配运算符，并拥有一个基本的三规则合规性列表类。

您可以使用虚拟头开始。深度复制完成后，您可以将if (c.Head == NULL)设置到虚拟磁头的下一个并删除虚拟磁头。您也不必通过这种方式检查Node *ptr1,*ptr2; head = ptr1 = new Node(); ptr2 = c.head; while (ptr2) { ptr1->next = new Node(*ptr2); ptr1 = ptr1->next; ptr2 = ptr2->next; } Node *temp = head; head = head->next; delete temp;。

IF OBJECT_ID('Tempdb..#TestTable') IS NOT NULL
    DROP TABLE #TestTable;

CREATE TABLE #TestTable (Names VARCHAR(75),Random_No INT); 

INSERT INTO #TestTable (Names,Random_No) VALUES
 ('Animal',363),('Bat',847),('Cat',655),('Duet',356),('Eagle',136),('Frog',784),('Ginger',690); 

SELECT * FROM #TestTable;

对如何制作双链表的深层副本感到困惑？

jjjjcccchhhh 回答：对如何制作双链表的深层副本感到困惑？

大家都在问