Bestellung einer verketteten Liste nach einem Wert -

Question

Bitte ertragen Sie mich, ich bin neu zu stackoverflow, also lassen Sie mich versuchen, mein Problem zu erklären, wenn es irgendwelche Punkte gibt, die ich in meiner Frage verbessern könnte bitte sicher sein Kommentar und ich werde die Frage

Gut bearbeiten, so ich habe mir eine verlinkte Liste, ich habe es in der Liste mit einem Wert bestellen möchten, die der Preis sein passiert:

tmpPtr->item->price; 

Das Problem, das ich habe, ist das Umschalten der Positionen, hier ist der Code:

struct inventory *sort_list() { 
     struct inventory *tmpPtr = pFirstNode; 
     struct inventory *temp = NULL; 
     struct inventory *tmpNxt = pFirstNode->next; 
     int tmp; 
     while(tmpNxt != NULL){ 
       while(tmpNxt != tmpPtr){ 
         if(tmpNxt->item->price < tmpPtr->item->price){ 
           // if next item price is smaller than current 
           // temp for the next item 
           // heres the problem.... 
           temp = tmpNxt->next; 
           tmpNxt->next = tmpPtr; 
           tmpPtr->next = temp; 
         } 
         else{ 
          // if not any smaller continue  
          tmpPtr = tmpPtr->next; 

         } 
       } 
       tmpPtr = pFirstNode; 
       tmpNxt = tmpNxt->next; 
     } 
     return tmpPtr; 
    } 

Die Werte werden die Bestellung nicht wie ich aus meiner Logik erwartet, würden alle Hinweise große EDIT sein:

struct inventory *sort_list() { 
     struct inventory *tmpPtr = pFirstNode; 
     struct inventory *temp = NULL; 
     struct inventory *tmpNxt = pFirstNode->next; 
     while(tmpNxt != NULL){ 
       while(tmpNxt != tmpPtr){ 
         if(tmpNxt->item->price < tmpPtr->item->price){ 
           // if next item price is smaller than current 
           // temp for the next item 
           if(tmpPtr == pFirstNode){ 
            tmpPtr = pFirstNode->next; // tmpPtr is now second node 
            pFirstNode->next = tmpPtr->next; 
            tmpPtr->next = pFirstNode; 
            pFirstNode = tmpPtr; 
           } 

           tmpNxt = tmpPtr->next; 
           tmpPtr->next = tmpNxt->next; 
           tmpNxt->next = tmpPtr; 
           temp->next = tmpNxt; 
         } 

       } 
        temp = tmpPtr; 
     } 
     return tmpPtr; // Place holder 
    } 

Answer 1

Wenn Sie in der Innen sind, wenn die Bedingung, haben Sie den folgenden Zustand:

Node1 -> tmpPtr -> tmpNxt -> Node2

Was Sie wollen, zu erreichen ist:

Node1 -> tmpNxt -> tmpPtr -> Node2

Dann haben Sie den folgenden Code ein:

1. temp = tmpNxt->next; // macht temp = Node2
2. tmpNxt->next = tmpPtr; // Änderungen Liste Node1 -> tmpPtr <-> tmpNxt,
3. tmpPtr->next = temp; // ändert Liste Node1 ->tmpPtr und tmpNxt -> tmpPtr -> Node2

Wie Sie sehen können, fehlt Ihnen der Link von Node1 -> tmpNext. Sie können das tun und Ihre Ergebnisse überprüfen.

Answer 2

Um zwei benachbarte einfach verknüpfte Listenmitglieder zu tauschen, benötigen Sie drei benachbarte Mitglieder (das eine hinter den beiden, die Sie tauschen möchten), es sei denn, einer von ihnen ist der Kopf der Liste.

1. Kopf der Liste Fall & rightarrow; Swap list_head und list_head->next

   assert(list_head->next); 
   next = list_head->next; 
   list_head->next = next->next; 
   next->next = list_head; 
   list_head = next; 
   

2. Andere Fälle & rightarrow; Swap cur und cur->next

   assert(prev->next == cur && cur->next); 
   next = cur->next; 
   cur->next = next->next; 
   next->next = cur; 
   prev->next = next; 
   

Diese beiden Fälle können jedoch in einem einzigen Gehäuse zusammengeklappt werden, wenn der vorhergehende Knoten zu sein die Adresse des nächsten Mitglied des vorherigen Knotens neu definiert wird.

void swap_cur_with_next (node **pnext, node *cur) { 
    assert(*pnext == cur && cur->next); 
    node *next = cur->next; 
    cur->next = next->next; 
    next->next = cur; 
    *pnext = next; 
} 

/* swap list_head with list_head->next */ 
swap_cur_with_next(&list_head, list_head); 

/* swap cur with cur->next */ 
swap_cur_with_next(&prev->next, cur); 

Mit einer korrekten Auslagerungsroutine ist es einfacher, Ihren Blasensortieralgorithmus in einer Liste zu implementieren.Die Codestruktur könnte wie folgt aussehen:

void bubble_up(node **pnext, node *cur) { 
    while (cur->next) { 
     if (need_to_swap(cur)) { 
      swap_cur_with_next(pnext, cur); 
     } 
     pnext = &(*pnext)->next; 
     cur = *pnext; 
    } 
} 

node **pnext = &list_head; 
while (*pnext) { 
    bubble_up(pnext, *pnext); 
    pnext = &(*pnext)->next; 
} 

jedoch, wie in einer anderen Antwort erwähnt, Mergesort ist ein natürlicher und effizienter Algorithmus zu verwenden, um eine Liste zu sortieren.

Zumindest können Sie die Knotenzeiger in ein Array packen und qsort() verwenden, um die Knotenzeiger zu sortieren und anschließend in sortierter Reihenfolge zu verknüpfen.