2番目の位置にリストを挿入するC++

Question

2番目の要素としてリスト内に要素を挿入して、元のものを変更せずに新しいリストを作成したいと考えています。

例： リスト1 2 3 4 5、CIN >> 55、新しいリストが1 55 2 3 4 5

なる問題は、両方のリストが変更されることです。なぜこうなった？

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); 

} 

私は正常に動作insertAtTop機能を書いた：

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); 

} 

あなたは、この2つの関数の違いは何ですか説明できますか？ insertAtTop（）が元のリストを変更しないのはなぜですか？

Answer 1

どちらのリストも同じセルを共有します。だからこそあなたは困っている。

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

tmpは= UUU、あなたが第2の位置にそれを挿入する場合、

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

しかし、あなたが見ることができるよう、headから始まるオリジナルのリストも変更されます。

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

は、あなたが

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

を挿入することができます可能な解決策が考えられます：あなたはそれを変更したくない場合は

あなたが挿入する前に、元のリストを複製する必要が

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

insertAtTop(ptr_list head)であなたはまだ共有の問題がありますが、それはすぐには見えません。いくつかの時間後に、あなたはまた、あなたの結果を変更しますheadから2番目の位置に別のセルを挿入する場合それはそう

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

を作成します。 insertAtTopのいずれかの株式なし

実装は

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

また

細胞を解放することを忘れないことです。 reference-countingのような追加のメカニズムを使用しないと、株式で自由にすることはほとんど不可能です。