對一個鏈表進行排序而不分配新的節點實例

-2

我使用的是C＃，並且我想在不使用額外內存的情況下對鏈表進行排序。對一個鏈表進行排序而不分配新的節點實例

Input: listptr→ 11 → 8 → 2→ 4 → 5 
Output: listptr→ 2 → 4 → 5 → 8 → 11

這是我的課：

public class SNode 
{ 
    public int data; 
    public SNode next; 
}

我應該創建一個新temp變量來存儲臨時列表？

贊SNode temp = new SNode(2,NULL);？

這是一項家庭作業。

來源

2012-10-21 user1690002

爲什麼不使用內置['LinkedList ']（http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx）class？ –

問題是什麼？如何排序？如何分配內存？爲什麼你想分配內存，並在你說你想分類而不使用額外內存的問題？ –

temp只是持有你SNode的地址。 –

我應該認爲練習的重點是在不創建整個事物的副本的情況下對列表進行排序（因此，您大概可以使用少量的變量形式的內存來幫助排序）。

最簡單的編碼方式可能是使用bubble sort（雖然這對於大型列表來說效率非常低）。訣竅是使用變量跟蹤當前對之前的節點，因爲如果需要交換對中節點的順序，您將不得不調整其next。

正如其他人所指出的那樣，你可以使用.NET框架做繁重的你一個真實的項目，但我想這是一種理論上的做法在指針操縱所以你應該代碼時一切爲了你自己。

來源

2012-10-21 10:41:59

好吧，一個簡單的方法是打破鏈條，將其排序在列表<>中，然後重新鏈接對象。

這是我對此的看法。我知道我完全失敗了「沒有額外的記憶」。部分。抱歉。

public class SNode : IComparable 
{ 
    public int data; 
    public SNode next; 

    // Implement IComparable, so List.Sort can do its magic. 
    public int CompareTo(object obj) 
    { 
     SNode node = obj as SNode; 
     if (node == null) 
      throw (new Exception()); // Wrong type? 

     if (this.data < node.data) 
      return -1; 
     else if (this.data > node.data) 
      return 1; 
     else 
      return 0; 
    } 
} 

// Sort the linked nodes. 
public SNode Sort(SNode root) 
{ 
    List<SNode> list = Unlink(root); 
    list.Sort(); 
    return Link(list); 
} 

// Unlink a chained link and return a list of them. 
public List<SNode> Unlink(SNode root) 
{ 
    List<SNode> nodes = new List<SNode>(); 

    nodes.Add(root); 
    nodes.AddRange(Unlink(root.next)); 
    root.next = null; 

    return nodes; 
} 

// Take a list and build a linked list. 
public SNode Link(List<SNode> list) 
{ 
    if (list.Count == 0) 
     return null; 

    for(int i = 0; i < list.Count - 1; i++) 
     list[i].next = list[i + 1]; 

    return list[0]; 
}

來源

2012-10-21 07:27:23 LightStriker

一個簡單的（不是最有效的）方法是創建一個與列表大小相同的數組，並讓數組中的每個元素引用一個節點。然後使用內置排序方法對數組進行排序。作爲循環訪問數組的最後一步，將每個節點的鏈接設置爲正確的後繼。

由於這個問題是作業，我懷疑你不允許使用內置的排序方法。如果是這樣，你必須爲你的鏈表實現任何現有的排序算法。 Merge sort似乎是一個很好的候選人。 Here是單鏈表上算法的一個很好的描述。

來源

2012-10-21 09:29:37 PHeiberg

對一個鏈表進行排序而不分配新的節點實例

回答

相關問題