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

Question

我的代码有问题，我制作了一个单链表类，您可以在其中添加、删除、修改、合并等。。。然而，我正在尝试一个简单的冒泡排序，并且遇到了列表排序不正确的问题。以下是一些需要注意的事项：

• 它是链表的自定义实现
• 单链接列表的节点包含两个内容：一个包含客户所有数据的CustomerFile对象和一个指向列表中下一项的“next”节点指针
• 列表按存储在每个节点的客户文件中的姓氏按升序（A-Z）排序
• “添加记录”功能将节点插入列表中的正确位置，这样列表在开始时不需要排序-但是，如果姓氏发生变化，作为程序的一部分，列表需要再次排序
• 我不希望创建一个新的列表，而是重复使用该列表上的插入记录来创建一个新的列表，因为这需要大量内存，我的任务是尽可能提高效率
• 链表的结构本身无法更改-它已决定，我太远无法更改为数组之类的内容
• 列表有一个头部节点，它有下一个项目，但没有尾部节点。它有一个指定的NULL next指针来指示列表的结束

public static void sortList()
{
    if (isEmpty() == true)
    {
        System.out.println("Cannot sort - the html" target="_blank">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 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

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

Answer 2

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

current = getHead().getNext()

有了这段代码，您将把head完全排除在排序过程之外，可能这里的数据需要转到列表的另一端，但在这种情况下，它将始终是head元素中的数据，或者是head节点后面的数据（后者是由于末尾的if语句）。

试着从列表的开头开始，看看会带来什么。

Answer 3

您的代码是一个奇怪的混合体，主要是交换数据，但要特别对待头部，试图通过切换链接来交换数据。

正如在另一个答案中所指出的，最后一次交换没有正确实现，但是如果您通过交换数据来做事情，实际上没有理由特别对待头部。

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

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

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())

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