In Liste an zweiter Position einfügen C++

Question

Ich möchte ein Element als zweites Element in eine Liste einfügen, um eine neue Liste zu erstellen, ohne die ursprüngliche zu ändern.

Beispiel: Liste 1 2 3 4 5, cin >> 55, dann werden neue Liste 55 1 2 3 4 5

Problem ist, dass beide Listen modifiziert sind. Warum passiert dies?

ptr_list insertAfterFirstElem(ptr_list head){ 
    ptr_list tmp; 
    tmp=new list; 
    cout<<"Insert value"<<endl; 
    cin>>tmp->val; 
    tmp->next=head->next; 
    head->next=tmp; 
    return (head); 

} 

Ich schrieb eine insertAtTop Funktion, die gut funktioniert:

ptr_list insertAtTop(ptr_list head){ 
    ptr_list tmp; 
    tmp=head; 
    head=new list; 
    cout<<"Insert value"<<endl; 
    cin>>head->val; 
    head->next=tmp; 
    return (head); 

} 

Können Sie erklären, was ist der Unterschied zwischen diesen beiden Funktionen? Warum ändert insertAtTop() die ursprüngliche Liste nicht?

Answer 1

Beide Listen teilen sich die gleichen Zellen; deshalb hast du Probleme.

head: xxx -> yyy -> zzz -> ttt 
    ^
res: --| 

Wenn tmp = uuu, können Sie es an der zweiten Position einfügen,

head: xxx -> uuu-> yyy -> zzz -> ttt 
    ^ ^
res: --|  |-- tmp 

Aber, wie Sie sehen können, die ursprüngliche Liste von head Start wird ebenfalls modifiziert.

Wenn Sie es nicht ändern wollen müssen Sie die ursprüngliche Liste vor dem Einsetzen duplizieren:

head: xxx -> yyy -> zzz -> ttt 
copy: xxx -> yyy -> zzz -> ttt 
    ^
res: --| 

dann können Sie

head: xxx -> yyy -> zzz -> ttt 
copy: xxx -> uuu-> yyy -> zzz -> ttt 
    ^ ^
res: --|  |-- tmp 

Eine mögliche Lösung könnte ein:

ptr_list copyList(ptr_list head) { 
    ptr_list copy = nullptr; 
    ptr_list* copy_last = © 
    for (ptr_list iter = head; iter != nullptr; iter = iter->next) { 
     *copy_last = new list(*iter); 
     copy_last->val = iter->val; 
     copy_last->next = nullptr; 
     copy_last = &copy_last->next; 
    }; 
    return copy; 
} 

ptr_list insertAfterFirstElem(ptr_list head){ 
    ptr_list copy = copyList(head); 
    ptr_list tmp; 
    tmp=new list; 
    cout<<"Insert value"<<endl; 
    cin>>tmp->val; 
    tmp->next=copy->next; 
    copy->next=tmp; 
    return (copy); 
} 

Jetzt mit insertAtTop(ptr_list head) haben Sie immer noch Probleme zu teilen, aber Sie don Ich sehe es nicht sofort. Es schafft

head: xxx -> yyy -> zzz -> ttt 
     ^
res: uuu --| 

Also, wenn nach einiger Zeit Sie eine andere Zelle in der zweiten Position von head einfügen wollen, müssen Sie auch Ihr Ergebnis ändern.

Eine Implementierung ohne Aktien von insertAtTop ist

ptr_list insertAtTop(ptr_list head){ 
    head = copyList(head); 
    ptr_list tmp; 
    ... 
} 

Vergessen Sie auch nicht die Zellen zu befreien. Freigeben mit Freigaben ist fast unmöglich, wenn Sie keinen zusätzlichen Mechanismus wie reference-counting verwenden.