-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);？

这是一个家庭作业。

4

3 回答 3

2

好吧，一种简单的方法是断开链，将其排序到 List<> 中，然后重新链接对象。

这是我对此的看法。我知道我完全失败了“没有额外的记忆”。部分。对不起。

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-21T07:27:23.827 回答
0

一种简单（不是最有效）的方法是创建一个与列表大小相同的数组，并让数组中的每个元素引用一个节点。然后使用内置的排序方法对数组进行排序。作为最后一步，您循环遍历数组并将每个节点的链接设置为正确的后继节点。

由于这个问题是家庭作业，我怀疑您不允许使用内置的排序方法。如果是这样，您必须为您的链表实现任何现有的排序算法。合并排序似乎是一个不错的选择。这是对单链表算法的一个很好的描述。

于 2012-10-21T09:29:37.243 回答
0

我应该认为练习的重点是在不创建整个内容的副本的情况下对列表进行排序（因此您可能可以使用变量形式的少量内存来帮助排序）。

最简单的编码方法可能是使用冒泡排序（尽管这对于大型列表来说效率极低）。诀窍是使用变量来跟踪当前对之前的节点，因为next如果需要交换对中节点的顺序，则必须调整它。

正如其他人指出的那样，在实际项目中，您将使用 .NET 框架为您完成繁重的工作，但我想这是指针操作的理论练习，因此您应该自己编写所有代码。

于 2012-10-21T10:41:59.347 回答