Java 按名称的字母顺序排列链表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19776700/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Order a linked list alphabetically by name
提问by Shawn
I am having an issue organizing a linked list alphabetically. I am reading the names in from a text file and storing them into a linked list. The problem I am having is how to sort them alphabetically. If anybody could point me in the right direction that would be amazing. The idea is to get the value of the first 3 letters in each name and compare them to the first 3 in the next name. But where would I compare the letters together?
我在按字母顺序组织链表时遇到问题。我正在从文本文件中读取名称并将它们存储到链表中。我遇到的问题是如何按字母顺序对它们进行排序。如果有人能指出我正确的方向，那就太棒了。这个想法是获取每个名称中前 3 个字母的值，并将它们与下一个名称中的前 3 个字母进行比较。但是我在哪里比较这些字母呢？
Here is the LinkedListNode class:
这是 LinkedListNode 类：
public class LinkedListNode
{
private String data;
private LinkedListNode next;
public LinkedListNode(String data)
{
this.data = data;
this.next = null;
}
public String getData()
{
return data;
}
public LinkedListNode getNext()
{
return next;
}
public void setNext(LinkedListNode n)
{
next = n;
}
}
Here is the LinkedList file with the main method:
这是带有 main 方法的 LinkedList 文件：
import java.io.*;
import java.util.Scanner;
public class LinkedList {
public LinkedListNode head;
String fname;
public static void main(String[] args) throws FileNotFoundException{
Scanner scan = new Scanner(new File("Names.txt"));
LinkedList l = new LinkedList();
int i = 1;
while(scan.hasNext()) {
String s = scan.nextLine();
l.insertBack(s);
i++;
}
System.out.print(l.showList());
}
public LinkedList() {
this.head = null;
}
public void insertBack(String data){
if(head == null){
head = new LinkedListNode(data);
}else{
LinkedListNode newNode = new LinkedListNode(data);
LinkedListNode current = head;
while(current.getNext() != null){
current = current.getNext();
}
current.setNext(newNode);
}
}
public String showList(){
int i = 0, j;
String retStr = "List nodes:\n";
LinkedListNode current = head;
while(current != null){
i++;
retStr += "Node " + i + ": " + current.getData() + "\n";
current = current.getNext();
}
return retStr;
}
}
回答by InfernalRapture
To do easy comparisons, your nodes should implement Comparable. The base Java libraries tend to rely upon this for easy sorting.
为了进行简单的比较，您的节点应该实现Comparable。基本的 Java 库倾向于依靠它来轻松排序。
The Comaprable interface will require you to implement compareTo (see below).
Comaprable 接口将要求您实现 compareTo（见下文）。
public int <LinkedListNode> compareTo(LinkedListNode n){
//Case insensitively compare the first 3 characters of the two nodes
String myHead = data.substring(0,3).toLowerCase();
String comparableHead = n.data.substring(0,3).toLowerCase();
return (myHead.compareTo(comparableHead));
}
If you use a standard List structure like, ArrayList, the Collections.sort(list) will be able to use this method to order your list.
如果您使用标准列表结构，如 ArrayList，则 Collections.sort(list) 将能够使用此方法对您的列表进行排序。
And here's an insertion sort based "insert" function for your runTime, using this comparable.
这是您的运行时基于插入排序的“插入”函数，使用此比较。
public void insert(String data){
LinkedListNode newNode = new LinkedListNode(data);
if(head == null){
head = newNode;
}else{
LinkedListNode current = head;
LinkedListNode prev;
//This is missing some key edge cases, but it inserts properly in the general case. You'll have to add to it to handle things like running off the list, or this needing to be inserted before the head.
while(current.getNext() != null){
if(current.compareTo(newNode)<0){
newNode.setNext(current);
prev.setNext(newNode);
break;
}
prev = current;
current = current.getNext();
}
}
}
回答by Cruncher
Some pseudo code for you:
一些伪代码给你：
OUTER:
for word in file
node = head
while node.next
if word > node.word
node.next
else
Node temp = new Node(word)
temp.next = word.next
node.next = temp
continue OUTER
node.next = new Node(word)
This is an as-you-go insertion sort. After every insert the file will be sorted. Or you could use other sorting algorithms after you read all of the data
这是一种随时可用的插入排序。每次插入后都会对文件进行排序。或者您可以在读取所有数据后使用其他排序算法
if it's if word > node.wordthis part you're having trouble with, the String#compareTomethod will be useful
如果if word > node.word这是您遇到问题的部分，则String#compareTo方法将很有用
回答by user2927391
Try using Collections.sort(list)
尝试使用Collections.sort(list)
Also, for comparing, you can use compareTofunction under Comparable Interface
此外，为了进行比较，您可以使用Comparable Interface 下的compareTo函数
