鏈表的具體排序

我必須以特定的方式排序我的鏈表，例如我有這樣的鏈表：3-> 1-> 4-> 1-> 7-> 5-> 7它必須被排序如下：7-> 1-> 7-> 1-> 3-> 4-> 5。所以從我的理解，我必須找到例如列表中的最大元素，並在開始時添加它，並從當前列表中刪除這樣的元素，我很好奇是否有任何方式，例如將列表中的元素位置交換到開始列表。或者我必須刪除這樣的元素並分配給定數據的內存，並在開始時添加它？總的來說，這是編程類測試的任務，必須使用單向鏈表來完成。鏈表的具體排序

來源

2014-01-27 user3209183

我還不知道排序背後的邏輯是什麼。 – Raptor

你的問題不清楚，請給出具體的細節。 –

只能在雙向鏈表中交換元素，因爲即使交換了需要交換的節點的指針，也會運行前一個節點的「 - > next」。你*可以做的是交換節點的'data'。 – Quaker

這裏有一個方法：給定一個無序列表P：

創建列表Q。
附加max(P)到Q。
從P刪除max(P)。
追加min(P)至Q。
從P刪除min(P)。
重複第2步到第5步一次。
按照升序排列P。
追加P至Q。

Q現在是您的排序列表。

這種方法假定P的長度不超過4

來源

2014-01-27 20:40:28 Raptor

這將起作用我認爲我正在製作不少於8個任務中給出的預製數字列表，謝謝。 – user3209183

您可以交換節點單鏈表，如果你有一個指針到列表中的節點指針，即head指針少節點「next指針。你可以這樣做，因爲無論如何你必須走列表才能找到最大值。（小心選擇了最後一個最大的，否則這個函數subseqnet調用將alwas帶來同樣7前面。）

void max_to_front(struct node **head) 
{ 
    struct node **mp = head; // current max pointer address 
    struct node **pv = head; // iterator pointer address 
    struct node *nd = *head; // iterator pointer 
    int mx; 

    // nothing to do for empty or single-node lists 
    if (*head == NULL || (*head)->next == NULL) return; 

    // find maximum 
    mx = nd->value; 
    while (nd) { 
     if (nd->value >= mx) { 
      mp = pv; 
      mx = nd->value; 
     } 
     pv = &nd->next; 
     nd = nd->next; 
    } 

    // move max to the front, i.e. update the pointers 
    nd = *mp; 
    *mp = (*mp)->next; 
    nd->next = *head; 
    *head = nd; 
}

注意如何pv總是包含通過它，你已經來到了節點指針的地址當前節點nd，所以你可以更新它; mp只是具有最大值的節點的指針地址。

來源

2014-01-27 21:00:36

鏈表的具體排序

回答

相關問題