手动对Java中的链表进行排序(按词法) [英] Manually sorting a linked list in Java (lexically)

问题描述

我正在用Java实现自己的链表.节点类仅具有一个称为名称"的字符串字段和一个称为链接"的节点.现在，我有一个测试驱动程序类，该类仅顺序插入几个名称.现在，我正在尝试编写一种排序方法来按字母顺序对节点进行排序，但是这样做有点麻烦.我从其他人的帖子中找到了冒泡冒充的伪代码，并尝试实现它，但它并未完全对条目进行排序.我不太确定为什么.任何建议表示赞赏！

I am implementing my own linked list in Java. The node class merely has a string field called "name" and a node called "link". Right now I have a test driver class that only inserts several names sequentially. Now, I am trying to write a sorting method to order the nodes alphabetically, but am having a bit of trouble with it. I found this pseudocode of a bubblesort from someone else's post and tried to implement it, but it doesn't fully sort the entries. I'm not really quite sure why. Any suggestions are appreciated!

    private void sort()
    {
        //Enter loop only if there are elements in list
        boolean swapped = (head != null);

        // Only continue loop if a swap is made
        while (swapped)
        {
            swapped = false;

            // Maintain pointers
            Node curr = head;
            Node next = curr.link;
            Node prev = null;

            // Cannot swap last element with its next
            while (next != null)
            {
                // swap if items in wrong order
                if (curr.name.compareTo(next.name) < 0)
                {
                    // notify loop to do one more pass
                    swapped = true;

                    // swap elements (swapping head in special case
                    if (curr == head)
                    {
                        head = next;
                        Node temp = next.link;
                        next.link = curr;
                        curr.link = temp;
                        curr = head;
                    }
                    else
                    {
                        prev.link = curr.link;
                        curr.link = next.link;
                        next.link = curr;
                        curr = next;
                    }
                }

                // move to next element
                prev = curr;
                curr = curr.link;
                next = curr.link;
            }
        }
    }

推荐答案

我花了几分钟查看您的代码中是否有错误，但没有发现.

I spent some minutes eyeballing your code for errors but found none.

我想说，除非有人变得更聪明或更努力，否则您应该尝试自己调试.如果您拥有像Eclipse这样的IDE，则可以在观察变量值的同时单步执行代码；如果没有，您可以在几个地方插入打印语句，然后手动检查您看到的内容与期望的内容.

I'd say until someone smarter or more hard working comes along you should try debugging this on your own. If you have an IDE like Eclipse you can single-step through the code while watching the variables' values; if not, you can insert print statements in a few places and hand-check what you see with what you expected.

更新我

我复制了您的代码并对其进行了测试.除了它以降序排序(这可能不是您想要的)外，它还可以完美地用于0、1和10个随机节点的样本.那么问题出在哪里呢?

I copied your code and tested it. Apart from the fact that it sorts in descending order (which may not be what you intended) it worked perfectly for a sample of 0, 1 and 10 random nodes. So where's the problem?

UPDATE II

仍在猜测它没有完全对条目进行排序"的含义.您可能期望按字典顺序进行排序(即"a"先于"B")，并且对于混合大小写的单词而言，这并不是按计划进行的.在这种情况下，解决方案是使用String方法compareToIgnoreCase(String str).

Still guessing what could be meant by "it doesn't fully sort the entries." It's possible that you're expecting lexicographic sorting (i.e. 'a' before 'B'), and that's not coming out as planned for words with mixed upper/lower case. The solution in this case is to use the String method compareToIgnoreCase(String str).

这篇关于手动对Java中的链表进行排序(按词法)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！