2017-02-19 48 views
-2

Мне нужно прочитать целые числа из файла в связанный список, отсортировать список с помощью сортировки вставки, а затем сообщить, сколько времени потребовалось моей машине для завершения сортировки вставки используя java. В настоящее время мой код делает все правильно, за исключением чтения из файла, он только читает в первом и последнем номере. Например, если я прочитал из файла с номерами от 1 до 5000 в обратном порядке, он будет читать и сортировать только 5000 и один.Вставка сортировки целых чисел, считанных из файла в связанный список java

Как я могу прочитать все целые числа из файла в ListNodes? Код размещен ниже:

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.*; 

class ListNode { 
    int val; 
    ListNode next; 

    ListNode(int x) { 
     val = x; 
     next = null; 
    } 
} 

public class InsertionLinkedList { 

    public static ListNode insertionSortList(ListNode head) { 

     long start = System.nanoTime(); 
     if (head == null || head.next == null) 
      return head; 

     ListNode newHead = new ListNode(head.val); 
     ListNode pointer = head.next; 

     // loop through each element in the list 
     while (pointer != null) { 
      // insert this element to the new list 

      ListNode innerPointer = newHead; 
      ListNode next = pointer.next; 

      if (pointer.val <= newHead.val) { 
       ListNode oldHead = newHead; 
       newHead = pointer; 
       newHead.next = oldHead; 
      } else { 
       while (innerPointer.next != null) { 

        if (pointer.val > innerPointer.val && pointer.val <= innerPointer.next.val) { 
         ListNode oldNext = innerPointer.next; 
         innerPointer.next = pointer; 
         pointer.next = oldNext; 
        } 

        innerPointer = innerPointer.next; 
       } 

       if (innerPointer.next == null && pointer.val > innerPointer.val) { 
        innerPointer.next = pointer; 
        pointer.next = null; 
       } 
      } 

      // finally 
      pointer = next; 
     } 
     long time = System.nanoTime() - start; 
     System.out.printf("The time taken was %.1f ns%n", (double) time); 
     return newHead; 
    } 

    public static void main(String[] args) throws FileNotFoundException { 

     Scanner scanner = new Scanner(new File("random5k.txt")); 
     ListNode insertion = new ListNode(scanner.nextInt()); 
     while(scanner.hasNextInt()){ 
      ListNode nextNode = new ListNode(scanner.nextInt()); 
      insertion.next = nextNode; 
     } 

     insertion = insertionSortList(insertion); 
    } 
} 
+0

Добро пожаловать в переполнение стека! Похоже, вы можете просить о помощи в домашней работе. Хотя у нас нет проблем с самим собой, обратите внимание на эти [dos and don'ts] (http://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions/338845 # 338845), и соответственно отредактируйте свой вопрос. (Даже если это не домашнее задание, пожалуйста, рассмотрите совет в любом случае.) –

+0

Я исправил свой вопрос, чтобы соответствовать этим dos и dont's. –

+0

Это лучше, однако, похоже, вам нужно научиться использовать отладчик. Пожалуйста, помогите нам с некоторыми [дополнительными методами отладки] (https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). Если у вас все еще есть проблемы, пожалуйста, не стесняйтесь возвращаться с более конкретным вопросом. –

ответ

-1

В настоящее время мой код делает все правильно для чтения из файла за исключением, он читает только в первом и последнем номере. Например, если I считывает из файла с номерами от 1 до 5000 в обратном порядке, то будет читать и сортировать только 5000 и один.

Вы на самом деле правильно читаете все цифры из файла. Это просто, когда вы пытаетесь заполнить объект ListNodeinsertion, вы не указываете next каждого узла на фактический следующий узел. См. Мои изменения в вашей программе.

public static void main(String[] args) throws FileNotFoundException { 

Scanner scanner = new Scanner(new File("random5k.txt")); 
ListNode insertion = new ListNode(scanner.nextInt()); 
ListNode intNodes = insertion; 
while(scanner.hasNextInt()){ 
    ListNode nextNode = new ListNode(scanner.nextInt()); 
    insertion.next = nextNode; 
    insertion = nextNode; 
} 
intNodes = insertionSortList(intNodes); 
} 
+0

Вопрос требует сортировки, и ваш ответ не выполняет его. Он также терпит неудачу в пустых списках. – EJP

+0

@EJP, извинения. Я попытался дать ответ, прежде чем даже прочитать полный вопрос. Я отредактировал свой ответ. – VHS

+0

Добро пожаловать. Не могли бы вы позаботиться об отрицательном голосовании по этому вопросу? – VHS