Tworzenie konstruktor kopiujący dla połączonej listy

Question

To praca domowa

pracuję nad wdrożeniem połączonej listy klas dla mojego klasy C++, a konstruktor kopia ma być bardzo mylące dla mnie.

prowadzi link lista składa się z kodowanym zwanych Elems:

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

informacji jest oddzielnym, niestandardowe klasy, która jest przechowywana w Elem.

podpis dla konstruktora kopii jest:

linkedList::linkedList(const linkedList &v) 

Problem mam jest głównie z moją logikę i rzeczywiście pisanie go jako kod.

Moja ogólna idea jest do:

1. Zestaw głowa do v.head (głowa = v.head)
2. wartości ustawień Elem do (pri = v.pri V, w info = v.info obok = v.next)
3. iterację, powtarzając krok 2.

jest to ogólna idea?

Każda pomoc będzie świetna. Pamiętaj, to jest praca domowa, więc nie proszę o bezpośrednie odpowiedzi!

Dziękuję za poświęcony czas

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

Dzięki za poświęcony czas wszystkim!

Myślę, że mam to zorientowali się:

//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; 
} 

Jestem pewien, że prace. Narysowałem kilka logicznych zdjęć, które mi pomogły i nie napotkaliśmy żadnych problemów.

Answer 1

Musisz zachować ostrożność w kroku 1 i części kroku 2. Krok 1 powinien przydzielić nowy węzeł i użyć go jako head. W kroku 2 część o numerze next = v.next, o ile nie masz zamiaru wykonać płytkiej kopii, jest niepoprawna.

Podczas kopiowania kontenera, takiego jak połączona lista, prawdopodobnie potrzebujesz głębokiej kopii, więc musisz utworzyć nowe węzły i skopiować tylko dane. Wskaźniki next i prior w węzłach nowej listy powinny odnosić się do nowych węzłów utworzonych dla tej listy w postaci , konkretnie, a nie do węzłów z pierwotnej listy. Te nowe węzły będą miały kopie odpowiednich danych z pierwotnej listy, tak aby nową listę można było uznać za wartość lub głęboką kopię.

Oto obraz przedstawiający różnice między płytkich i głębokich Kopiowanie:

zauważyć, jak w głęboką kopię części diagramu, żaden z węzłów wskazują na węzłach w starej listy . Aby uzyskać więcej informacji na temat różnicy między płytkimi i głębokimi kopiami, zobacz artykuł z Wikipedii na object copying.

Answer 2

1. Nie powinieneś ustawiać this->head = v.head. Ponieważ głowa jest po prostu wskaźnikiem. Musisz utworzyć nową głowę i skopiować wartości indywidualnie z v.head do swojej nowej głowy. W przeciwnym razie masz dwa wskaźniki wskazujące na to samo.

2. wtedy musiałby utworzyć tymczasowy Elem wskaźnik, który zaczyna się v.head i iterację listy, kopiując jej wartości dla nowych Elem wskaźników do nowej kopii.

3. Patrz wyżej.

Answer 3

Co powinien skopiować twój konstruktor kopii? Powinno to skopiować pri - łatwe. Powinno również skopiować: info - łatwe. A jeśli next nie ma wartości null, powinien również skopiować. Jak skopiować next? Pomyśl rekursywnie: Cóż, next to Elem *, a Elem ma konstruktora kopiującego: po prostu użyj go do skopiowania odnośnika Elem i odnieś się do niego.

Można to również rozwiązać iteracyjnie, ale rozwiązanie rekurencyjne jest znacznie bardziej intuicyjne.

Answer 4

Więc tutaj jest moja odpowiedź (nie wiem, czy pasuje do twojej pracy domowej, czy też nie - instruktorzy wydają się mieć własne pomysły czasami;):

ogólnie konstruktor kopia powinna „kopia” swój obiekt. To znaczy. powiedzmy, że masz linkList l1, i wykonaj linkList l2 = l1 (który wywołuje linkList :: linkedList (l1)), a następnie l1 i l2 są całkowicie oddzielnymi obiektami w tym sensie, że modyfikacja l1 nie wpływa na l2 i na odwrót.

Po prostu przypisanie wskaźników nie dostanie prawdziwej kopii, ponieważ wyłuskiwanie i modyfikowanie któregokolwiek z nich wpłynęłoby na oba obiekty.

Raczej chcesz zrobić prawdziwą, głęboką kopię każdego elementu na liście źródłowej (lub wykonać kopię tylko na żądanie, jeśli chcesz mieć ochotę).

Answer 5

Zapomniałaś linię return; po

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

Musisz się wydostać, prawda?