Запутались, как сделать глубокую копию двусвязного списка? - PullRequest
Новая
       44

Запутались, как сделать глубокую копию двусвязного списка?

0 голосов
/ 18 января 2020

Я пытался создать глубокую копию двусвязного списка, но у меня возникли проблемы с этим. Я должен был сделать это несколько раз, но в итоге я получил ошибку адреса. Мне просто нужно объяснение, как это сделать правильно.

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 ]

2 голосов
/ 18 января 2020

Копирование связанных списков - это три вещи:

  1. Обход копируемого списка.
  2. Создание копий новых узлов из оригиналов.
  3. Для каждого нового узел из (2), привязать его к связанному списку.

Первый из них тривиальный, второй довольно базовый c, но третий часто бросает людей для всех oop. Для вашего copy-ctor один из способов сделать это - использовать указатель на указатель. Это позволяет нам обращаться к каждому указателю в нашем связанном списке по их собственным адресам. 

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 для изготовления вашего оператора назначения копирования и иметь базовый класс списка соответствия правилу 1022 *.

0 голосов
/ 18 января 2020

Вы можете использовать пустышку для начала. Когда глубокое копирование завершено, вы можете установить head на следующую заглушку и удалить заглушку. Вам также не придется проверять 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;
...