Сортировка связанного списка Java

Question

Таким образом, приложение считывает из внешнего файла набор строк, каждая в отдельной строке.

Например:

and
cake
here

Не организовано ни в каком конкретном порядке. Мне нужно прочитать эти письма, поместить их в связанный список и, наконец, отсортировать их.

Мне нужна помощь в этом:

Вот текущий код:

import java.util.*;
import java.io.*;
public class LinkedList
{
  static File dataInpt;
  static Scanner inFile;
  public static void main(String[] args) throws IOException
  {
    dataInpt=new File("C:\\lldata.txt");
    inFile=new Scanner(dataInpt);
    Node first = insertInOrder();
    printList(first);
  }
  public static Node getNode(Object element)
  {
    Node temp=new Node();
    temp.value=element;
    temp.next=null;
    return temp;
  }
  public static void printList(Node head)
  {
    Node ptr; //not pointing anywhere
    for(ptr=head;ptr!=null;ptr=ptr.next)
      System.out.println(ptr.value);
    System.out.println();
  }
  public static Node insertInOrder()
  {
    Node first=getNode(inFile.next());
    Node current=first,previous=null;
    Node last=first;
    int count=0;
    while (inFile.hasNext())
    {
      if (previous!=null
          && ((String)current.value).compareTo((String)previous.value) > 0)
      {
        last.next=previous;
        previous=last;
      }
      if (previous!=null
          && ((String)current.value).compareTo((String)previous.value) < 0)
      {
        current.next=last;
        last=current;
      }
      previous=current;
      current=getNode(inFile.next());
    }
    return last;
  }
}

Но это дает бесконечный цикл с "Cat".

Вот файл данных:

Lol
Cake
Gel
Hi
Gee
Age
Rage
Tim
Where
And
Kite
Jam
Nickel
Cat
Ran
Jug
Here

Answer 1

Хорошо, самостоятельная работа. Разделите чтение и вставку. Хотя старый и новый код имеют 14 строк кода, это делает его более понятным.

public static Node insertInOrder() {
    Node first = null;
    while (inFile.hasNext()) {
        String value = inFile.next().toString();
        first = insert(first, value);
    }
    return first;
}

/**
 * Insert in a sub-list, yielding a changed sub-list.
 * @param node the sub-list.
 * @param value
 * @return the new sub-list (the head node might have been changed).
 */
private static Node insert(Node node, String value) {
    if (node == null) { // End of list
        return getNode(value);
    }
    int comparison = node.value.compareTo(value);
    if (comparison >= 0) { // Or > 0 for stable sort.
        Node newNode = getNode(value); // Insert in front.
        newNode.next = node;
        return newNode;
    }
    node.next = insert(node.next, value); // Insert in the rest.
    return node;
}

Используется рекурсия (вложенный "перезапуск"), вызывая insert внутри insert. Это работает как цикл или делегирование работы клону, или как математическое индуктивное доказательство.

---

Итеративная альтернатива

также немного упростил.

private static void Node insert(Node list, String value) {
    Node node = list;
    Node previous = null;
    for (;;) {
        if (node == null || node.value.compareTo(value) >= 0) {
            Node newNode = getNode(value);
            newNode.next = node;
            if (previous == null)
                list = newNode;
            else
                previous.next = newNode;
            break;
        }
        // Insert in the rest:
        previous = node;
        node = node.next;
    }
    return list;
}

Answer 2

В относительно простом коде, подобном этому в вашем вопросе, хорошим упражнением для его понимания является проработка нескольких взаимодействий вашего цикла, проверка значений всей вашей локальной переменной, чтобы увидеть влияние вашего кода. Вы даже можете сделать это вручную, если код прост. Если это слишком сложно сделать вручную, ваш код, вероятно, слишком сложен. Если вы не можете следовать этому, как вы можете знать, если вы делаете то, что вы намерены. Например, я могу ошибаться, но это будет состояние вверху каждой итерации цикла. Он начинает разваливаться в третий раз, и к четвертому у вас появляется серьезная проблема, поскольку ваш список становится несвязным.

1)last = first = Lol, current = previous = null
  Lol->null
2)last = first = previous = Lol, current = Cake
  Lol->Lol
3)first = Lol, last = Cake, previous = Cake, current = Gel 
  Cake->Lol->Lol 
4)first = Lol, last = Cake, previous = Cake, current = Hi
  Cake->Gel, Lol->Lol

Answer 3

public static Node insertInOrder()
{
    Node first=getNode(inFile.next());
    Node current=first,previous=null;
    Node last=first;
    int count=0;
    while (inFile.hasNext())
    {
        if (previous!=null
            && ((String)current.value).compareTo((String)previous.value) > 0)
        {
            last.next=previous;
            previous=last;
        }
        if (previous!=null
            && ((String)current.value).compareTo((String)previous.value) < 0)
        {
            current.next=last;
            last=current;
        }
        previous=current;
        current=getNode(inFile.next());
    }
    return last;
}

Прежде всего, вы ничего не делаете с последней строкой, прочитанной из файла, поэтому она никогда не вставляется.Вы должны прочитать строку и создать новые Node перед повторным связыванием next указателей.

Затем, если last и previous ссылаются на те же Node и данные currentбольше, чем previous,

if (previous!=null
    && ((String)current.value).compareTo((String)previous.value) > 0)
{
    last.next=previous;
    previous=last;
}

Вы устанавливаете last.next = last, ломая список.Из кода (в частности, отсутствия функции sort(Node)) кажется, что вы хотите отсортировать список по мере его создания.Но вы только когда-либо сравниваете каждый новый Node друг с другом, так что это не поддерживает порядок.

Для каждого нового узла вы должны найти узел, после которого он должен быть вставлен, сканируя сперед списком и измените current.next и next.

предшественника.

Answer 4

Хорошо, я не помню точно школьную теорию о сортировке вставок, но вот как-то смесь того, что я думаю и ваш код импорт java.io.File; импорт java.io.IOException; import java.util.Scanner;

public class LinkedList {
    public static class Node {
        public String value;
        public Node next;
    }

    static File dataInpt;
    static Scanner inFile;

    public static void main(String[] args) throws IOException {
        inFile = new Scanner("Lol\r\n" + "Cake\r\n" + "Gel\r\n" + "Hi\r\n" + "Gee\r\n" + "Age\r\n" + "Rage\r\n" + "Tim\r\n" + "Where\r\n"
                + "And\r\n" + "Kite\r\n" + "Jam\r\n" + "Nickel\r\n" + "Cat\r\n" + "Ran\r\n" + "Jug\r\n" + "Here");
        Node first = insertInOrder();
        printList(first);
    }

    public static Node getNode(String element) {
        Node temp = new Node();
        temp.value = element;
        temp.next = null;
        return temp;
    }

    public static void printList(Node head) {
        Node ptr; // not pointing anywhere
        for (ptr = head; ptr != null; ptr = ptr.next) {
            System.out.println(ptr.value);
        }
        System.out.println();
    }

    public static Node insertInOrder() {
        Node current = getNode(inFile.next());
        Node first = current, last = current;
        while (inFile.hasNext()) {
            if (first != null && current.value.compareTo(first.value) < 0) {
                current.next = first;
                first = current;
            } else if (last != null && current.value.compareTo(last.value) > 0) {
                last.next = current;
                last = current;
            } else {
                Node temp = first;
                while (current.value.compareTo(temp.value) < 0) {
                    temp = temp.next;
                }
                current.next = temp.next;
                temp.next = current;
            }
            current = getNode(inFile.next());
        }
        return first;
    }
}

И это работает как шарм. Конечно, это далеко не оптимально, как с точки зрения производительности, так и повторного использования кода.

Answer 5

Честно говоря, если бы я проходил курс, я бы счел правильным ответ:

List<String> list = new LinkedList<String>();
// read in lines and: list.add(word);
Collections.sort(list);