Создание конструктора копирования для связанного списка

Question

Это домашнее задание

Я работаю над реализацией класса связанного списка для своего класса C ++, и конструктор копирования меня очень смущает.

Связанный список состоит из структур, называемых Elems:

struct Elem 
    {
        int pri;
        data info;
        Elem * next;
    };
    Elem * head;

info - это отдельный пользовательский класс, который хранится в Elem.

подпись для конструктора копирования:

linkedList::linkedList( const linkedList &v )

Проблема, с которой я сталкиваюсь, заключается в том, чтобы взять мою логику и фактически написать ее как код.

Моя общая идея заключается в следующем:

1. Установить головку на v.head(head = v.head)
2. Установите значения элемента в v (pri = v.pri, info = v.info, next = v.next)
3. Выполните итерацию, повторяя шаг 2.

Это общая идея?

Любая помощь будет отличной. Помните, что это домашнее задание, поэтому, пожалуйста, никаких прямых ответов!

Спасибо за ваше время

====================================================================================================================================================================

Спасибо всем за ваше время!

Мне кажется, я понял это:

//Copy Constructor
LinkedList::LinkedList( const LinkedList &v )
{
Elem * p1 = 0;//current
Elem * p2 = 0;//next

if( v.head == 0 )
    head = 0;

else
{
    head = new Elem;
    head -> pri = v.head -> pri;
    head -> info = v.head -> info;

    p1 = head;
    p2 = v.head -> next;
}

while( p2 )
{
    p1 -> next = new Elem;
    p1 = p1 -> next;
    p1 -> pri = p2 -> pri;
    p1 -> info = p2 -> info;

    p2 = p2 -> next;
}
p1 -> next = 0;
}

Я почти уверен, что это работает.Я нарисовал несколько логических картинок, чтобы помочь, и я не столкнулся с какими-либо проблемами.

Answer 1

Вы должны быть осторожны с Шагом 1 и частью Шага 2. Шаг 1 должен выделить новый узел и использовать его как head.На шаге 2 часть о next = v.next, если вы не собираетесь делать поверхностную копию, является неправильной.

Когда вы копируете контейнер, такой как связанный список, вам, вероятно, понадобится глубокая копия, поэтому новаянеобходимо создать узлы и скопировать только данные.Указатели next и prior в узлах нового списка должны ссылаться на новые узлы, которые вы создаете , в частности для этого списка, а не на узлы из исходного списка.Эти новые узлы будут иметь копии соответствующих данных из исходного списка, так что новый список можно рассматривать как значение или глубокую копию.

Вот изображение, показывающее различия между мелким и глубоким копированием:

Обратите внимание, что в части диаграммы Deep Copy ни один из узлов не указывает на узлы в старом списке.Для получения дополнительной информации о разнице между мелкими и глубокими копиями см. Статью в Википедии о копировании объектов .

Answer 2

1. Вы не должны устанавливать this->head = v.head. Потому что голова просто указатель. Что вам нужно сделать, это создать новую головку и скопировать значения по отдельности из v.head в вашу новую голову. В противном случае у вас будет два указателя, указывающих на одно и то же.

2. Затем вам потребуется создать временный указатель Elem, который начинается с v.head, и выполнить итерацию по списку, копируя его значения в новые указатели Elem в новую копию.

3. См. Выше.

Answer 3

Что должен копировать ваш конструктор копирования? Стоит скопировать pri - легко. Это должно скопировать info - также легко. И если next не равно нулю, его тоже следует скопировать. Как вы можете скопировать next? Подумайте рекурсивно: next - это Elem *, а Elem имеет конструктор копирования: просто используйте его для копирования ссылочной Elem и обращения к ней.

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

Answer 4

Вы забыли линию return; после

if( v.head == 0 )
    head = 0;

Тебе нужно выйти, верно?

Answer 5

Итак, вот мой ответ (не знаю, подходит ли это к вашей домашней работе или нет - у преподавателей иногда бывают свои идеи;):

Обычно конструктор копирования должен «копировать» ваш объект.То есть, у вас есть LinkList l1, и вы создаете LinkList l2 = l1 (который вызывает connectedList :: connectedList (l1)), тогда l1 и l2 - совершенно отдельные объекты в том смысле, что модификация l1 не влияет на l2 и наоборот.

Когда вы просто назначаете указатели, вы не получите реальную копию, поскольку разыменование и модификация любого из них затронут оба объекта.

Вы, скорее, хотите сделать настоящую глубокую копию каждого элемента в вашем списке источников (или делать копию только по требованию, если хотите быть модным).