用Java编写单链表和冒泡排序的代码

Question

我有一个代码问题，我已经制作了一个单向链表类，可以添加、删除、修改、合并等操作。但是，我尝试进行简单的冒泡排序时遇到了问题，列表没有正确排序。以下是需要注意的几点：

• 这是一个自定义的链表实现。
• 单向链表的节点包含两个部分：一个CustomerFile对象，其中包含客户的所有数据，以及指向列表中下一项的“next”节点指针。
• 列表按照每个节点中存储的姓氏按升序（A-Z）排序。
• 添加记录函数将节点插入到正确的位置，因此最初不需要对列表进行排序 - 但是如果作为程序的一部分更改了姓氏，则需要重新对列表进行排序。
• 我宁愿不创建新列表，并重复使用此插入记录在该列表上以创建新列表，因为这会消耗内存，而我的任务是尽可能高效。
• 链表的结构不能更改 - 这已经确定了，我无法更改为诸如数组之类的内容。
• 列表有一个头节点，有下一个项目，但没有尾节点。它具有指定的NULL下一个指针，以指示列表的末尾。

代码：

public static void sortList()
{
    if (isEmpty() == true)
    {
        System.out.println("Cannot sort - the list is empty");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("List sorted");
    }
    else
    {
        Node current = getHead().getNext();
        CustomerFile tempDat;
        boolean swapDone = true;
        while (swapDone)
        {
            current = getHead().getNext();
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null &&
                    current.getData().getSurname().compareTo(
                        current.getNext().getData().getSurname()) >0)
                {
                    tempDat = current.getData();
                    current.setData(current.getNext().getData());
                    current.getNext().setData(tempDat);
                    swapDone = true;
                }
                current = current.getNext();
            }
        }
        if (getHead().getData().getSurname().compareTo(
            getHead().getNext().getData().getSurname()) >0)
        {
            current = getHead().getNext();
            getHead().setNext(current.getNext());
            setHead(current);
        }
    }
}

我希望得到您的反馈意见。

- Lukeg101

---

这个方法真的是静态的，没有参数吗？你是怎么获取你要排序的列表的？ - Don Roby

它位于单向链表类本身中，与列表使用的其他方法一起 - getHead() 方法允许您检索列表的头部，然后从那里开始工作。 - Lukeg101

你的列表以什么方式未排序？
14358 -> 14358？
14358 -> 13485？
14358 -> 81345？ - Mike Rylander

旧列表 "Jay Gatsby, Bob Marley, John Smith, Ziggy Stardust" 将 Jay Gatsby 的姓氏更改为 "Turner" 新列表 "Bob Marley, Jay Turner, John Smith, Ziggy Stardust" 它只循环一次并重新分配一个节点。 - Lukeg101

它不区分大小写，因为姓氏以大写字母存储。 - Lukeg101

Answer 1

你的代码是一个奇怪的混合体，大部分是交换数据，但特别对待头节点，试图通过切换链接与下一个节点交换。

正如其他答案中提到的那样，这个最后的交换没有正确实现，但如果你通过交换数据来完成操作，就没有理由特别对待头节点。

你所要做的就是在外部循环中从头开始遍历列表。

这将产生一个可行的解决方案：

public void sortList()
{
    if (isEmpty())
    {
        System.out.println("An empty list is already sorted");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("A one-element list is already sorted");
    }
    else
    {
        Node current = getHead();
        boolean swapDone = true;
        while (swapDone)
        {
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null && current.getData().getSurname().compareTo(current.getNext().getData().getSurname()) >0)
                {
                    CustomerFile tempDat = current.getData();
                    current.setData(current.getNext().getData());
                    current.getNext().setData(tempDat);
                    swapDone = true;
                }
                current = current.getNext();
            }
            current = getHead();
        }
    }
}

我将其改为了非静态，因为如评论中所述，如果以静态方式运行可能会不清楚。在您的上下文中，您可能能够使其静态。

我还更改了一些其他小细节。从未有必要通过像这样的代码来检查条件：

if (isEmpty() == true)

在Java中，这与以下完全等价：

if (isEmpty())

而且tempDat不需要在使用它的地方之外声明。

- Don Roby

Answer 2

您在排序时没有包含头部。

public static void sortList()
{
    if (isEmpty() == true)
    {
        System.out.println("Cannot sort - the list is empty");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("List sorted");
    }
    else
    {
        Node current = getHead();
        // Node current = getHead().getNext();
        CustomerFile tempDat;
        boolean swapDone = true;
        while (swapDone)
        {
            current = getHead().getNext();
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null && current.getData().getSurname().compareTo(current.getNext().getData().getSurname()) >0)
                {
                    tempDat = current.getData(); // td -> objectA, cd -> objectA
                    current.setData(current.getNext().getData()); // cd -> objectB
                    current.getNext().setData(tempDat); // nd -> td -> objectA
                    swapDone = true;
                }
                current = current.getNext();
            }
        }
        //if (getHead().getData().getSurname().compareTo(getHead().getNext().getData().getSurname()) >0)
        //{
        //  current = getHead().getNext(); // current -> head+1
        //  getHead().setNext(current.getNext()); //head+1 -> head+2
        //  setHead(current); // head -> head+1
        //}
    }
}

另外，在上面被注释掉的代码中存在一个错误。应用该代码会删除一个节点。

// list: a -> b -> c -> d
current = getHead().getNext(); // current = b
getHead().setNext(current.getNext()); // a -> c 
setHead(current); // head = b
// list: b -> c -> d
// and nothing points to 'a' anymore

你应该尝试交换节点而不是交换数据。如果你采用这种方法，你应该能找到更好的解决方案。

- Mike Rylander

Answer 3

我认为这里的主要问题是你从

current = getHead().getNext()

使用此代码，您将完全排除头部的排序过程，可能需要将此处的数据移动到列表的另一端，但在这种情况下，它将始终是头元素中的数据，或者是紧接在头节点之后的数据（后者是由于您在结尾处的if语句所致）。

尝试从列表的头部开始，看看会出现什么情况。

- dbriggs