当链接列表合并排序时双链表被卡住 - java

Question

我将一个随机生成的数字存储在一个双向链表中。如果超过5个大于50的整数，我将合并排序链表。问题是，程序工作，但是当它到达合并排序部分，它永远不会终止，我不知道为什么。

这里是我的代码：合并排序实现在我的主要上面。

 import java.util.Random; 
     import java.util.Scanner; 

    public class DLinkedList<E> { 




    private static class DLinkedNode<E> { 
     private int item; 
     private DLinkedNode<E> prev; 
     private DLinkedNode<E> next; 

     private DLinkedNode(int rand) { 
      item = rand; 
      next = null; 
      prev = null; 
     } 

    private DLinkedNode(E value, DLinkedNode<E> prev, DLinkedNode<E> next) { 
     item = (int) value; 
     this.next = next; 
     this.prev = prev; 
    } 
    } 
protected DLinkedNode<E> head; 
protected int size; 
private static Scanner in; 

    private void verify(boolean mustBeTrue) { 
    if (! mustBeTrue) { 
     throw new java.lang.AssertionError("assertion error"); 
    } 
    } 

    private void checkInvariants() { 

    verify((size == 0) == (head == null)); 
    verify(size >= 0); 
    if (size == 0) { 
     return;  // no more checks 
    } 
    int measuredSize = 0; 
    DLinkedNode<E> node = head; 
    do { 
     node = node.next; 
     measuredSize++; 
    } while (node != head); 
    verify(measuredSize == size); 
    } 


    public DLinkedList() { 
    head = null; 
    size = 0; 
    // one of the constructor's jobs is to make sure that the invariants hold. 
    checkInvariants(); 
    } 


    public boolean add(int rand) { 
    checkInvariants(); 
    DLinkedNode<E> newNode = new DLinkedNode<E>(rand); 
    if (head == null) { 
     head = newNode; 
     newNode.next = head; 
     newNode.prev = head; 
    } else { 
     DLinkedNode<E> tail = head.prev; 
     tail.next = newNode; 
     head.prev = newNode; 
     newNode.next = head; 
     newNode.prev = tail; 
    } 
    size++; 
    checkInvariants(); 
    return true; 
    } 


    private DLinkedNode<E> nodeAtPosition(int index) { 
    verify (index >= 0); 
    DLinkedNode<E> result = head; 
    while (index > 0) { 
     result = result.next; 
     index--; 
    } 
    verify (result != null); 
    return result; 
    } 


    public int remove(int index) { 
    checkInvariants(); 
    if ((index < 0) || (index >= size)) { 
     String badIndex = 
     new String ("index " + index + " must be between 0 and " + (size - 1)); 
     throw new IndexOutOfBoundsException(badIndex); 
    } 
    verify (head != null); 
    int value = head.item; 
    if (size == 1) { 
     head = null; // very simple!! 
    } else { 
     DLinkedNode<E> node = nodeAtPosition(index); 
     value = node.item;    // return the value 
     if (index == 0) {    // removing the head node 
     head = node.next;   // new head node == old second node 
     } 
     node.prev.next = node.next; // get this node out of the list 
     node.next.prev = node.prev; 
    } 
    size--; 
    checkInvariants(); 
    return value; 
    } 
//////////////////////////////// MERGE SORT 
    public DLinkedNode<String> merge_sort(DLinkedNode<String> head) { 
     if(head == null || head.next == null) { return head; } 
     DLinkedNode<String> middle = getMiddle(head);  //get the middle of the list 
     DLinkedNode<String> sHalf = middle.next; 
     middle.next = null; //split the list into two halfs 

     return merge(merge_sort(head),merge_sort(sHalf)); //recurse on that 
    } 

    //Merge subroutine to merge two sorted lists 
    public DLinkedNode<String> merge(DLinkedNode<String> a, DLinkedNode<String> b) { 
     DLinkedNode<String> dummyHead, curr; 
     dummyHead = new DLinkedNode<String>(size); 
     curr = dummyHead; 
     while(a !=null && b!= null) { 
      if(a.item <= b.item) { curr.next = a; a = a.next; } 
      else { curr.next = b; b = b.next; } 
      curr = curr.next; 
     } 
     curr.next = (a == null) ? b : a; 
     return dummyHead.next; 
    } 

    //Finding the middle element of the list for splitting 
    public DLinkedNode<String> getMiddle(DLinkedNode<String> head) { 
     if(head == null) { return head; } 
     DLinkedNode<String> slow, fast; slow = fast = head; 
     while(fast.next != null && fast.next.next != null) { 
      slow = slow.next; fast = fast.next.next; 
     } 
     return slow; 
    } 
    //////////////////////////////////////////////// 

    public String toString() { 
    checkInvariants(); 
    DLinkedNode<E> node = head; 
    StringBuffer result = new StringBuffer(); 
    if (head != null) { 
     while (true) { 
     result.append (node.item); 
     node = node.next; 
     if (node == head) { 
      break; // entire list has been traversed 
     } 
     result.append (" ==> "); 
     } 
    } 
    checkInvariants(); // make sure we didn't break anything 
    return result.toString(); 
    } 






    public static void main (String [] arguments) { 

     Random rnd = new Random(); 
     in = new Scanner(System.in); 
     int listCount; 
     int countgrtr50=0; 

     DLinkedList<String> dll = new DLinkedList<String>(); 
     System.out.println (dll); 

     System.out.print("Enter number of integers: "); 
     listCount = in.nextInt(); 
     System.out.print("Enter range: "); 
     int range = in.nextInt(); 
     for (int i = 0; i < listCount; i++) 
     { 
      int rand = rnd.nextInt(range)+1; 
      dll.add(rand); 
      if(rand>50){ 
      countgrtr50++; 
      } 
     } 
     System.out.println (dll); 
     System.out.println ("more than 50: " + countgrtr50); 

     if (countgrtr50>5){ 
      System.out.println ("sorting... "); 

      dll.merge_sort(dll.head); 
      //dll.remove(1); 
      System.out.println ("after: "+dll); 
     } else { 
      // error if less than 5 
      dll.remove(4); 
      System.out.println ("else after: "+dll); 
     } 

     } 



} 

这是结果我得到：

Enter number of integers: 20 
Enter range: 100 
60 ==> 36 ==> 12 ==> 44 ==> 11 ==> 61 ==> 27 ==> 86 ==> 55 ==> 51 ==> 5 ==> 44 ==> 39 ==> 18 ==> 23 ==> 50 ==> 73 ==> 49 ==> 96 ==> 82 
more than 50: 8 
sorting... 

，然后它不会终止，但是当大于50整数都小于5，这导致它不排序工作正常或任何东西。

Answer 1

因为有时你会认为你的列表是循环的，有时候不是。在你的添加，checkInvariants和toString方法中，你假设head在tail之后（tail.next = head和head.prev = tail）。但是，在您的merge和getMiddle方法中，您认为null在tail（tail.next = null）之后。这就是为什么你的getMiddle方法以无限循环结束的原因，因为fast.next和fast.next.next都不为null。

我的建议是，让你的head.prev = null和tail.prev = null。另外，在构建双向链表时，应该有一个对尾部的引用。