用单独的链接列表进行编码，并在Java中进行泡泡排序

Question

我的代码有问题，我完成了一个单独的链接列表类，您可以在其中添加，删除，修改，合并等...但是，我正在尝试一个简单的气泡排序并遇到了列表未正确排序的问题。以下是要注意的事情：

• 这是链接列表的自定义实现
• 单独链接列表的节点包含2件事：一个带有所有数据的CustomerFile对象，一个"下一个"节点指针指向列表中的下一个项目
• 该列表由存储在每个节点的客户文件中的姓氏按升序（A-Z）排序
• 添加记录函数插入列表中正确位置的节点，以便最初不需要对列表进行排序 - 但是，如果更改了姓氏，作为程序的一部分，则需要再次对列表进行排序<</li>
• 我宁愿不创建一个新列表，并在该列表上重复使用此插入记录以创建一个新列表，因为这是内存密集的，我的任务是尽可能高效
• 无法更改链接列表的结构 - 它是决定的，我太远了，无法更改为诸如数组之类的东西
• 列表具有头节点，它具有下一个项目，但没有尾部节点。它具有指定的NULL下一个指针，以指示末端pf列表

代码

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

Answer 2

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

开始

current = getHead().getNext()

使用此代码，您将完全摆脱排序过程，可能是此处的数据需要转到列表的另一端，但是在这种情况下，它始终是数据在头部元素中，或直接在头节点后成为数据（后者是由于您的if语句末尾引起的）。

尝试从列表的头部开始，然后看看会带来什么。

Answer 3

您不在分类中包括头部。

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

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