0
我將一個隨機生成的數字存儲在一個雙向鏈表中。如果超過5個大於50的整數，我將合併排序鏈表。問題是，程序工作，但是當它到達合併排序部分，它永遠不會終止，我不知道爲什麼。當鏈接列表合併排序時雙鏈表被卡住 - java
這裏是我的代碼：合併排序實現在我的主要上面。
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，這導致它不排序工作正常或任何東西。
您嘗試過哪些調試技巧？ https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ –
我試着在Netbeans上調試你的代碼。事實證明，當使用範圍爲101的100個整數運行時，第一次進入getMiddle方法時，while中有一個無限循環。我發現你將鏈表的末尾與基於'add'方法的開始鏈接起來。在'add'方法中，當你回到列表的最初頭部時，你會驗證它，但不在'getMiddle'中。我建議你不要直接鏈接它們，而是在你的類中使用兩個'head'和'tail'變量引用。 –