C++ Dodaj do listy powiązanej w uporządkowanej kolejności

Question

Witam Mam listę połączonych przy użyciu struktur. Właśnie teraz dodałem każdy element na końcu. Chciałbym jednak dodać każdy element w porządku posortowanym na podstawie identyfikatora. Struktura ma dwa elementy: nazwę ciągu i długi identyfikator.

node* temp = new node; 
temp->name = nameRead; 
temp->id = idRead; 

//check if first item, if so add as head 
if(head == NULL) 
{ 
    head = temp; 
} 
else 
{ 
    node* temp2 = head; 
    while(temp2->next != NULL) 
    { 
     temp2 = temp2->next; 
    } 
    temp2->next = temp; 
} 

Answer 1

node* temp = new node; 
temp->name = nameRead; 
temp->id = idRead; 

node* temp2 = head; 
node** temp3 = &head; 
while(temp2 != null && temp2->id < temp->id) 
{ 
    temp3 = &temp2->next; 
    temp2 = temp2->next; 
} 
*temp3 = temp; 
temp->next = temp2; 

EDIT: punktach 'temp3' wskaźnik do miejsca, gdzie 'temp' musiałby przejść: Wyjaśnienie. Zainicjuj temp2 na head i trzymaj pętlę, dopóki nie dojdziemy do końca listy lub do momentu, gdy temp2 ma identyfikator> = niż identyfikator temp. W każdej iteracji pętli przesuń zarówno temp3, jak i temp2.

Na końcu pętli, "temp3" będzie zawierał adres wskaźnika, w którym powinna znajdować się temperatura. Dlatego przypisz * temp3, aby wskazywało temp, i przypisz temp-> obok punktu do temp2 (które w tym miejscu będzie miało wartość zerową lub wskaże element, który ma większy identyfikator niż temp-> id).

Answer 2

Większość modyfikacji kodu jest dość banalna - wystarczy dodać porównanie na podstawie identyfikatora, aby przejść tylko przez listę, aż do węzła o identyfikatorze większym od nowego, który należy wstawić (lub dotrzeć do końca listy).

W tym momencie sytuacja staje się nieco skomplikowana: zanim "uświadomisz sobie", że osiągnąłeś właściwe miejsce na liście, już za jednym węzłem minąłeś (i na pojedynczo połączonej liście, nie ma sposobu, aby odejść plecy). Sposób na naprawienie tego jest całkiem prosty: przydziel nowy (pusty) węzeł i wstaw go po znalezionym zbyt dużym węźle. Skopiuj tę zbyt dużą zawartość węzła do nowo wstawionego, a następnie skopiuj dane nowego węzła do miejsca, które właśnie zostało opuszczone.

Należy jednak dodać, że wszystko to jest w większości kwestią dyskusyjną. Jeśli chcesz posegregować kolekcję przedmiotów, lista połączona jest zwykle bardzo kiepskim wyborem. Jeśli nie robisz czegoś takiego, jak praca domowa, w której nie masz wyboru, jak zrobić cokolwiek, co zostało ci przypisane do mózgu, poszukaj std::set [Edytuj: lub std::multiset, jeśli duplikaty są dozwolone - lub ewentualnie std::map lub std::multimap, jeśli chcesz mieć możliwość znalezienia węzła na podstawie identyfikatora] i zapomnieć o samodzielnym wdrożeniu.

Answer 3

Zrobione z mojego studenckiego notebooka:

void addSorted(node * head, int id){ 
     node* newNode = new node; 
     newNode->number = n; 
     newNode->next = NULL; 

     if(head == NULL || head->number >= id ){ 
      newNode->next = head; 
      head = newNode; 
      return; 
     }else if(head->next != NULL && head->next->id >= id){ 
      node * nextNode = head->next; 
      newNode->next = nextNode; 
      head->next = newNode; 
      return; 
     }else{ 
      node * left; 
      node * right = head; 
      while(right != NULL && right->next->id <= id){ 
       left = right; 
       right = right->next; 
      } 
      left->next=newNode; 
      newNode->next = right; 
     } 
    }