按名称的字母顺序对链表进行排序

Question

我遇到按字母顺序组织链表的问题。 我正在从文本文件中读取名称并将它们存储到链表中。 我遇到的问题是如何按字母顺序对它们进行排序。 如果有人能指出我正确的方向，那就太神奇了。 这个想法是获取每个名称中前 3 个字母的值，并将它们与下一个名称中的前 3 个字母进行比较。 但是我在哪里比较这些字母呢？

下面是 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;
    }
}

这是带有 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;
    }
}

Answer 1

一些伪代码给你：

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)

这是一种即用即用的插入排序。每次插入后，文件将被排序。或者，您可以在读取所有数据后使用其他排序算法

如果您遇到问题的这部分if word > node.word，则 String#compareTo 方法将很有用

Answer 2

尝试使用 Collections.sort（list）

此外，为了进行比较，您可以使用 比较 在可比较接口下

Answer 3

为了进行简单的比较，您的节点应该实现 Comparable。 基本的 Java 库倾向于依赖这一点来轻松排序。

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));
}

如果您使用像 ArrayList 这样的标准列表结构，则 Collections.sort（list） 将能够使用此方法对列表进行排序。

这是一个基于插入排序的"插入"函数，用于您的运行时，使用此可比函数。

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