Sortieren der verknüpften Liste während des Einfügens

Question

So versuche ich, Knoten in verkettete Liste in absteigender Reihenfolge einzufügen, aber ich habe Mühe, wenn ich doppelte Zahlen bekomme und kann keine gute Lösung für das Problem finden. Ich stoße entweder auf fehlende Nummern/Programmabsturz oder Programmlisten nur 1 Nummer unendlich oft. Wenn die anderen

Hier ist mein Code, die ich Werke bis zur „else“ Anweisung denke, es ist der Teil, den ich herausfinden und im kippe gerade meine letzte Version zu verlassen, die offensichtlich

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

} 

funktionieren nicht Funktionen benötigt werden oder meine main.cpp bitte lassen Sie es mich wissen.

Answer 1

Beim ersten Einfügen bist, geht es in dem ersten if Zustand und setzt dann first=news, aber nach, dass seine wieder news->number > first->number Überprüfung, die falsch sein, so unnötig den sonst Zustand geht in. Also entweder return; in den ersten if Block hinzufügen oder andere in else Block setzen. verfolgen vorherigen Element

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

Sie sollten vielleicht Ihre 2 letzten Zeilen tauschen, sonst Sie news->next = news haben, einen Zyklus zu schaffen.

Wie auch immer, ich schlage vor, die Funktion in 2 (private) teilen: Eine, die Node* wo nach (oder nullptr für die erste Position) einfügen, und die Methode für die Einfügung (und es ist so einfacher zu debuggen).

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

und schließlich:

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