Wie wird der Zeiger der verknüpften Liste sortiert?

Question

[50] -> [20] -> [10] -> [30] Bitte sagen Sie mir, wie Sie fehlausgerichtete Listen in aufsteigender oder absteigender Reihenfolge nach dem vom Knoten angegebenen Knoten ordnen. Ich denke, das heißt Link sort

ps. Da ich ein Anfänger in C-Sprache und Englisch bin, brauche ich Überlegung. ptr == tail (PTR nicht head)

void sort_data(Node* ptr){ 
    Node* head = ptr->Next; 
    Node* tail = ptr; 
    for (int i = 0; i < 10; i++) { 
     if (head->Next == tail) { 
     } 
     if (head->data < head->Next->data) { 
      Node* swap1 = head; 
      Node* swap2 = head->Next; 
      swap1->Next = swap2->Next; 
      swap2->Next = swap1; 
      tail->Next = swap2; 
      tail = tail->Next; 
     } 
     else { 
      head = head->Next; 
      tail = tail->Next; 
     } 
    } 
} 

Answer 1

Die Liste ist eine zirkulare Liste, so dass ein Endzeiger gut genug ist, da, wie in dem Code gezeigt, Schwanz-> nächstes wird in dem Kopfzeiger führen. Der Code sucht nicht nach einer leeren Liste oder einer Liste mit nur einem einzigen Knoten.

Eine Blasensortierung benötigt normalerweise eine Schleife innerhalb einer Schleife (eine äußere Schleife und eine innere Schleife). Jede innere Schleife verschiebt den letzten Knoten zum Ende der Liste. Die erste innere Schleife setzt den letzten Knoten an Ort und Stelle, die zweite innere Schleife setzt den vorletzten Knoten an die Stelle, und so weiter, wo die letzte innere Schleife den zweiten Knoten in Position bringt.

Um Knoten zu tauschen, muss der Code in der Lage sein, den vorherigen Knoten als nächsten Zeiger zu aktualisieren. Zum Beispiel:

A->B->C->D  // to swap B and C, A's next pointer needs to be updated 
A->C->B->D  // along with B and C's next pointers 

Da der Zeiger zurückgegeben ist der Endzeiger kann der Endzeiger entweder nach der ersten inneren Schleife gesetzt werden, da das ist, wenn der letzte Knoten in Position gebracht wird, oder nach dem Sortieren der Liste könnte gescannt werden, um den letzten Knoten zu finden.

ich vorschlagen würde die zirkulare Liste zu einer normalen Liste innerhalb der Sortierfunktion Umwandlung:

Node *head = ptr->next; // same as above 
    Node *tail = ptr;   // same as above 
    tail->next = NULL;  // convert to normal list 

Dies vereinfacht das Ende einer Liste Bestimmen (Prüfung auf NULL gegenüber einem festen Zeiger auf einen bestimmten Knoten), da die Knoten am Anfang oder am Ende einer Liste kann während der Sortierung ausgetauscht werden.

Der Code könnte optimiert werden, indem die sortierten Knoten am Ende der Liste nachverfolgt werden, um zu vermeiden, dass bereits sortierte Knoten gescannt und verglichen werden.

Beispielcode optimierter Blasensortierung. Nach dem Einstellen von pHead wird die Liste von zirkulär auf normal geändert (pTail-> next = NULL). pEnd wird verwendet, um das Ende der unsortierten Liste zu verfolgen, und wird auf NULL initialisiert. pnEnd verfolgt das Ende der unsortierten Liste basierend auf der Out-of-Order-Prüfung und wird verwendet, um pEnd für die nächste innere Schleife zu setzen. Die Sortierung erfolgt, wenn pEnd der zweite Knoten in der Liste ist, da der erste Knoten als einzelner Knoten ebenfalls sortiert würde. ppCurr ist ein Zeiger auf den Zeiger auf den aktuellen Knoten und ist ein Zeiger auf entweder pHead oder den nächsten Zeiger eines Knotens, was die Logik für die Behandlung des ersten und späterer Knoten vereinfacht (in anderen Sprachen, die keine Zeiger unterstützen, ein Dummy-Knoten) kann auf ähnliche Weise mit dummy.next ähnlich wie * ppCurr) verwendet werden. Eine Überprüfung zum ersten Mal, wenn die innere Schleife abgeschlossen ist, wird durchgeführt, um pTail auf den letzten Knoten zu setzen, der sich möglicherweise geändert hat, wenn die letzten zwei Knoten vertauscht wurden. Wenn die Sortierung abgeschlossen ist, wird pTail-> next auf pHead gesetzt, um die Liste wieder auf zirkulär umzustellen.

/* bubble sort circular linked list */ 
NODE * SortList(NODE *pTail) 
{ 
NODE *pHead;     /* ptr to first node */ 
NODE *pEnd;      /* ptr to end of unsorted part of list */ 
NODE *pnEnd;     /* pEnd for next pass */ 
NODE *pNext;     /* ptr to next node */ 
NODE **ppCurr;     /* ptr to ptr to curr node */ 
    if(pTail == NULL || pTail->next == pTail) /* if empty list or single node */ 
     return pTail;   /* return pTail */ 
    pHead = pTail->next; 
    pEnd = pTail->next = NULL; /* change to normal list */ 
    do{ 
     ppCurr = &pHead;  /* set ppCurr to start of list */ 
     pnEnd = pHead->next; /* set pnEnd to 2nd node */ 
     while((pNext = (*ppCurr)->next) != pEnd){ 
      if((*ppCurr)->data > pNext->data){ /* if out of order swap */ 
       (*ppCurr)->next = pNext->next; 
       pnEnd = pNext->next = *ppCurr; 
       *ppCurr = pNext; 
      } 
      ppCurr = &(*ppCurr)->next; /* advance to next node */ 
     } 
     if(pEnd == NULL)  /* if first time, set pTail */ 
      pTail = *ppCurr; /* in case last two nodes swapped */ 
     pEnd = pnEnd;   /* update pEnd since rest of list is sorted */ 
    }while(pEnd != pHead->next); /* loop until pEnd => 2nd node */ 
    pTail->next = pHead;  /* change to circular list */ 
    return pTail; 
}