如何鏈接列表指針排序

Question

[50] - > [20] - > [10] - > [30] 請告訴我如何按節點指向的節點按升序或降序排列未對齊列表。 我認爲這就是所謂的鏈接排序

p.s因爲我是初學者在C語言和英語，我需要考慮。 PTR ==尾（PTR不頭）

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

列表是一個圓形的列表，因此尾指針是不夠好，因爲在代碼如圖所示，tail->下將導致頭指針。該代碼沒有檢查只有單個節點的空列表或列表。

冒泡排序通常需要循環內的循環（外循環和內循環）。每個內部循環將應該是最後一個的節點移動到列表的末尾。第一個內部循環放置最後一個節點，第二個內部循環將下一個節點放置到最後一個節點，等等，最後一個內部循環將第二個節點放置到位。

爲了交換節點，代碼需要能夠更新先前節點的下一個指針。例如：

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 

由於返回的指針是尾指針，尾部指針既可以在第一內部循環後進行設置，因爲這是當最後節點被放置就位，或分選後，列表可以被掃描以找到最後一個節點。

我建議循環列表轉換爲正常列表中的排序函數內：由於節點

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

這簡化確定列表的末尾（檢查NULL與一個指針指向一個特定節點）在列表的開頭或結尾可能會在排序過程中交換。

可以通過跟蹤列表末尾的已排序節點來優化代碼，以避免掃描和比較已排序的節點。

優化氣泡排序的示例代碼。在設置pHead後，列表從圓形變爲正常（pTail-> next = NULL）。 pEnd用於跟蹤未排序列表的末尾並初始化爲NULL。 pnEnd基於亂序檢查跟蹤未排序列表的末尾，並用於爲下一個內部循環設置pEnd。排序是在pEnd是列表中的第二個節點時完成的，因爲第一個節點作爲單個節點也將被排序。 ppCurr是指向當前節點的指針的指針，並且是指向pHead或某個節點下一個指針的指針，它簡化了處理第一個和後面的節點的邏輯（在不支持指針的其他語言中，一個虛擬節點可以類似的方式使用，使用類似於* ppCurr的dummy.next）。內部循環首次完成的檢查將pTail設置爲最後一個節點，如果最後兩個節點已交換，則該節點可能已更改。排序完成後，將pTail-> next設置爲pHead將列表更改爲循環。

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