java - 在java中使用单链表和冒泡排序进行编码

Question

我的代码有问题，我制作了一个单向链表类，您可以在其中添加、删除、修改、合并等...但是，我正在尝试简单的冒泡排序并遇到了以下问题该列表未正确排序。这里有一些注意事项:

• 它是链表的自定义实现
• 单向链表的节点包含两件事:一个包含客户所有数据的 CustomerFile 对象和一个指向列表中下一项的“下一个”节点指针
• 列表按照存储在每个节点的客户文件中的姓氏按升序(A-Z)排序
• 添加记录功能将节点插入列表中的正确位置，因此列表最初不需要排序 - 但是如果姓氏更改，作为程序的一部分，列表需要再次排序
• 我宁愿不创建新列表并在该列表上重复使用此插入记录来创建新列表，因为这是内存密集型的，我的任务是尽可能高效
• 链表的结构本身是不能改变的——它已经决定了，我太过分了，不能改变成数组之类的东西
• 列表有一个头节点，它有下一个项目但没有尾节点。它有一个指定的 NULL next 指针来指示列表的结尾

代码

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

非常感谢您的反馈

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 不需要在其使用位置之外声明。