0

我在按字母顺序组织链接列表时遇到问题。我正在从文本文件中读取名称并将它们存储到链接列表中。我遇到的问题是如何按字母顺序对它们进行排序。如果有人能指出我正确的方向，那就太棒了。这个想法是获取每个名称中前 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;
    }
}
4

3 回答 3

2

给你一些伪代码：

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方法将很有用

于 2013-11-04T20:45:43.943 回答
0

为了进行简单的比较，您的节点应该实现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();

        }

    }
}
于 2013-11-04T20:43:25.843 回答
0

尝试使用Collections.sort(list)

此外，为了进行比较，您可以使用Comparable Interface 下的compareTo函数

于 2013-11-04T20:51:56.693 回答