挿入中にリンクリストを並べ替える

Question

リンクリストに降順でノードを挿入しようとしていますが、重複した番号を取得しているときに問題を解決できないときは苦労します。私は不足している数字/プログラムのクラッシュやプログラムリストを1回だけ無限に遭遇します。ここで

は、私は「他」の文までの作品は、それは私が把握カントとイムだけで、他の場合

明らか

void Link::insert(int number) { 
    Node *news = new Node; 

    news->number = number; 

    if(first == NULL) { 
     first = news; 
    } 
    if(news->number > first->number) { 
     Node *temp = first; 
     first = news; 
     news->next = temp; 
    } else { 
     Node *temp = first; 
     while (temp->next || news->number < temp->number) { 
      temp=temp->next; 
     } 
     temp->next = news; 
     news->next = temp->next; 
    } 

} 

を仕事をdoesntの私の最後のバージョンを、残し部分だと思う私のコードです関数が必要ですか、私のmain.cppに教えてください。

Answer 1

最初に挿入するときは、最初のifの状態になり、その後first=newsに設定されますが、それ以降はfalseとなるnews->number > first->numberを再度チェックして、不必要にelse条件に入ります。そのため、最初にifブロックにreturn;を追加するか、他のブロックをelseブロックに入れます。前の要素の キープトラック

else{ 
    Node *temp=first,*prev=null; 
    while (temp && (temp->next || news->number < temp->number)){ 
     prev=temp; 
     temp=temp->next; 
    } 
    if(prev==null){ 
     news->next=first;first=news; 
    } 
    else{ 
     prev->next=news;news->next=temp; 
    } 
} 

Answer 2

たぶん

void Link::insert(int number){ 
Node *news = new Node; 

news->number = number; 

if(first == NULL){ 
    first = news; 
    return; 
} 

for(Node *i=first, *pred=NULL;!i;i=i->next){ 
if(i->number<number){ 
    if(i==first) { 
    news->next=first; 
    first=news; 
    } else { 
    pred->next=news; 
    news->next=i; 
    } 
    break; 
} 
pred=i; 
} 
} 

Answer 3

あなたはサイクルを作成し、あなたはnews->next = newsを持っている他、あなたの2つの最後の行を交換する必要があります。

とにかく、私はNode*がどこに挿入されるか（最初の位置はnullptr）、挿入の方法がわかりました（2つの（プライベート）部分で機能を分割することをお勧めします。 ）。

Node* Link::upper_bound(int value) const 
{ 
    if (first == nullptr || first->number <= value) { 
     return nullptr; 
    } 
    Node* node = first; 
    Node* next = first->next; 

    while (next && value < next->number) { 
     node = next; 
     next = node->next; 
    } 
    return node; // we have: node->number < value && (next == nullptr || value <= next->number) 
} 

void Link::insert_after(Node* node, int value) 
{ 
    Node* new_node = new Node(value); 

    if (node == nullptr) { 
     new_node->next = first; 
     first = new_node; 
    } else { 
     new_node->next = node->next; 
     node->next = new_node; 
    } 
} 

、最終的には：どうやら、問題の半分を解決し

void Link::insert(int number) { 
    insert_after(upper_bound(number), number); 
}