在C中雙向鏈表中交換節點＃

Question

我在嘗試使用冒泡排序對雙向鏈表進行排序。我自己寫了雙鏈表類。節點包含四個值（firstName，lastName，Id和department）。

以下是我試圖用來對列表進行排序的方法（我使用Windows窗體並從窗體調用sortList方法）。

K和I是doubleLinkedList類的節點。

public DoubleLinkedList sortList(ref DoubleLinkedList toSort) 
{ 
    for (toSort.K = toSort.First; toSort.K != endOfTheList(toSort.First); toSort.K = toSort.K.NextLink) 
    { 
    for(toSort.I = toSort.K.NextLink; toSort.I != endOfTheList(toSort.First); toSort.I = toSort.I.NextLink) 
    { 
     if (string.Compare(toSort.K.Department, toSort.I.Department) > 0) 
     { 
     MessageBox.Show(toSort.ToString()); 
     swap(toSort, toSort.K, toSort.I); 
     } 
    } 
    } 

    MessageBox.Show("List is sorted"); 
    MessageBox.Show(this.ToString()); 
    return toSort; 
} 

public void swap(DoubleLinkedList swapList, Node _k, Node _i) 
{ 
    MessageBox.Show("Swapping " + swapList.K.ToString() + "for" + swapList.I.ToString()); 

    Node temp = _k; 
    swapList.K = _i; 
    swapList.I = temp; 
    MessageBox.Show(swapList.K.ToString() + swapList.I.ToString()); 
    MessageBox.Show(swapList.ToString()); 
} 

倒數第二個消息框顯示，名字，姓氏，Id和部門節點K和節點我已經交換的方法，但他們並沒有真正在doublelinkedlist交換。

如果有人可以給我建議，我如何改變這些方法來實際交換列表中的值，將不勝感激。我在網上找到了一些例子，但他們使用的是LinkedList<>類，我真的想要使用我自己的類。

作爲一個例子，節點K =米歇爾賣方，NO12，銷售 節點I =尼克霍奇，NO22，帳戶

所述交換方法之後，K =尼克霍奇，NO22，帳戶和I =米歇爾賣家，No12，Sales，但在實際列表中節點未交換。

Answer 1

交換節點彼此相鄰

由於您使用冒泡，我要假設你希望交換的兩個節點是相鄰。這是一個假設：如果這不成立，問題更復雜。

假設你有一個雙向鏈表像下面這樣：

First      Last 
|       | 
v       v 
+---+ -> +---+ -> +---+ -> +---+ 
| 1 | | 4 | | 2 | | 5 | 
+---+ <- +---+ <- +---+ <- +---+ 

隨着->和<-鏈接到NextLink和PrevLink。現在，我們要爲實例，以交換與4和2節點，則列表會像：

First      Last 
|       | 
v       v 
+---+ -> +---+ -> +---+ -> +---+ 
| 1 | | 2 | | 4 | | 5 | 
+---+ <- +---+ <- +---+ <- +---+ 

所以現在我們應該問自己：「有什麼改變」​​：我們看到了很多變化：

• 節點1的NextNode現在是節點2;
• 節點2的NextNode現在是節點4;
• 節點4的NextNode現在是節點5;
• 節點5的PrevNode現在是節點4;
• 節點4的PrevNode現在是節點2;和
• 節點2的PrevNode現在是節點1

此外，如果節點交換的一個是first節點或last節點，那麼我們就必須得更新這些指針。在那種情況下，節點4通常沒有先前的節點（在節點4是start節點的情況下），或節點2沒有下一個節點（在節點2是最後一個節點的情況下）。所以有很多情況。這當然取決於鏈表是否具有對first和/或last節點的引用。

因此，我們可以這樣寫一個算法：

public void swap(DoubleLinkedList swapList, Node i, Node j) { 
    Node h = i.PrevNode; 
    Node k = j.NextNode; 
    if(swapList.First == i) { 
     swapList.First = j; 
    } 
    if(h != null) { 
     h.NextNode = j; 
    } 
    j.PrevNode = h; 
    j.NextNode = i; 
    i.PrevNode = j; 
    i.NextNode = k; 
    if(k != null) { 
     k.PrevNode = i; 
    } 
    if(swapList.Last == j) { 
     swapList.Last = i; 
    } 
} 

交換兩個隨機節點

如果節點是隨機的，這個問題更加嚴重。在這裏，我們考慮，我們希望交換節點b與節點f場景：

 -> +---+ -> +---+ -> +---+ ->  -> +---+ -> +---+ -> +---+ -> 
...  | a | | b | | c |  ...  | e | | f | | g |  ... 
    <- +---+ <- +---+ <- +---+ <-  <- +---+ <- +---+ <- +---+ <- 

在我們想交換b與f情況下，我們將有：

• 讓a的NextNode是f;
• let f's NextNode be c;
• let e's NextNode be b;
• let b's NextNode be g;
• let c's PrevNode be f;
• let f's PrevNode be a;
• let g's PrevNode be b;和
• 讓b的PrevNode是e。

因此，我們可以實現這個樣：

public void swap(DoubleLinkedList swapList, Node b, Node f) { 
    Node a = b.PrevNode; 
    Node c = b.NextNode; 
    Node e = f.PrevNode; 
    Node g = f.NextNode; 


    if(swapList.First == b) { 
     swapList.First = f; 
    } else if(swapList.First == f) { 
     swapList.First = b; 
    } 

    if(a != null) { 
     a.NextNode = f; 
    } 
    f.PrevNode = a; 
    f.NextNode = c; 
    if(c != null) { 
     c.PrevNode = f; 
    } 

    if(e != null) { 
     e.NextNode = b; 
    } 
    b.PrevNode = e; 
    b.NextNode = g; 
    if(g != null) { 
     g.PrevNode = b; 
    } 

    if(swapList.Last == b) { 
     swapList.Last = f; 
    } else if(swapList.Last == f) { 
     swapList.Last = b; 
    } 
}