我正在用 Java 实现自己的链表。节点类只有一个名为“name”的字符串字段和一个名为“link”的节点。现在我有一个测试驱动程序类,它只按顺序插入几个名字。现在,我正在尝试编写一种排序方法来按字母顺序对节点进行排序,但遇到了一些麻烦。我从别人的帖子中找到了这个冒泡排序的伪代码并尝试实现它,但它没有完全对条目进行排序。我不太确定为什么。任何建议表示赞赏!
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;
}
}
}
最佳答案
我花了几分钟观察您的代码是否有错误,但一无所获。
我会说,在出现更聪明或更努力工作的人之前,您应该尝试自己调试它。如果你有像 Eclipse 这样的 IDE,你可以在观察变量值的同时单步执行代码;如果没有,您可以在几个地方插入打印语句,然后手动检查您看到的内容是否符合您的预期。
更新一
我复制了你的代码并测试了它。除了它按降序排序(这可能不是你想要的)之外,它对 0、1 和 10 个随机节点的样本非常有效。那么问题出在哪里呢?
更新二
仍在猜测“它没有完全对条目进行排序”是什么意思。您可能希望按字典顺序排序(即“B”之前的“a”),但对于大小写混合的单词,这并没有按计划出现。这种情况下的解决方案是使用 String
方法 compareToIgnoreCase(String str)
。
关于java - 在 Java 中手动排序链表(词法),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1854870/