почему он выбрасывает индекс за пределы исключения?

Question

Я хочу использовать сортировку слиянием для сортировки моего двусвязного списка. Я создал 3 класса (Node, DoublyLinkedList, MergeSort), но он выдаст это исключение для следующих строк:

1.in the getNodes method of DoublyLinkedList--->   throw new IndexOutOfBoundsException();
2.in the add method of DoublyLinkedList----->   Node cursor = getNodes(index);
3.in the sort method of MergeSort class------>    listTwo.add(x,localDoublyLinkedList.getValue(x));
4.in the main method of DoublyLinkedList----->merge.sort();

это мой класс слияния: (я поместил весь код для этого класса для лучшего понимания)

public class MergeSort {

private DoublyLinkedList localDoublyLinkedList;

public MergeSort(DoublyLinkedList list) {
    localDoublyLinkedList = list;

}

public void sort() {

    if (localDoublyLinkedList.size() <= 1) {
        return;
    }
    DoublyLinkedList listOne = new DoublyLinkedList();
    DoublyLinkedList listTwo = new DoublyLinkedList();
    for (int x = 0; x < (localDoublyLinkedList.size() / 2); x++) {
        listOne.add(x, localDoublyLinkedList.getValue(x));
    }
    for (int x = (localDoublyLinkedList.size() / 2) + 1; x < localDoublyLinkedList.size(); x++) {
        listTwo.add(x, localDoublyLinkedList.getValue(x));
    }
//Split the DoublyLinkedList again
        MergeSort sort1 = new MergeSort(listOne);
        MergeSort sort2 = new MergeSort(listTwo);
        sort1.sort();
        sort2.sort();

    merge(listOne, listTwo);
}

public void merge(DoublyLinkedList a, DoublyLinkedList b) {
    int x = 0;
    int y = 0;
    int z = 0;
    while (x < a.size() && y < b.size()) {
        if (a.getValue(x) < b.getValue(y)) {
            localDoublyLinkedList.add(z, a.getValue(x));
            x++;
        } else {
            localDoublyLinkedList.add(z, b.getValue(y));
            y++;
        }
        z++;
    }
    //copy remaining elements to the tail of a[];
    for (int i = x; i < a.size(); i++) {
        localDoublyLinkedList.add(z, a.getValue(i));
        z++;
    }

    for (int i = y; i < b.size(); i++) {
        localDoublyLinkedList.add(z, b.getValue(i));
        z++;
    }

}
}

и только часть моего DoublyLinkedList:

    private Node getNodes(int index) throws IndexOutOfBoundsException {
    if (index < 0 || index > length) {
        throw new IndexOutOfBoundsException();
    } else {
        Node cursor = head;
        for (int i = 0; i < index; i++) {
            cursor = cursor.getNext();
        }
        return cursor;
    }
}
  public void add(int index, int value) throws IndexOutOfBoundsException {
    Node cursor = getNodes(index);
    Node temp = new Node(value);
    temp.setPrev(cursor);
    temp.setNext(cursor.getNext());
    cursor.getNext().setPrev(temp);
    cursor.setNext(temp);
    length++;
}

    public static void main(String[] args) {
    int i = 0;
    i = getRandomNumber(10, 10000);
    DoublyLinkedList list = new DoublyLinkedList();
    for (int j = 0; j < i; j++) {
        list.add(j, getRandomNumber(10, 10000));
        MergeSort merge = new MergeSort(list);
        merge.sort();

        System.out.println(list.getValue(j));
    }
}

также есть трассировка стека:

run:
0
0
Exception in thread "main" java.lang.IndexOutOfBoundsException
    at datastructureproject.DoublyLinkedList.getNodes(DoublyLinkedList.java:57)
    at datastructureproject.DoublyLinkedList.add(DoublyLinkedList.java:34)
    at datastructureproject.MergeSort.sort(MergeSort.java:31)
    at datastructureproject.DoublyLinkedList.main(DoublyLinkedList.java:82)
Java Result: 1
BUILD SUCCESSFUL (total time: 0 seconds)

также, когда я отлаживаю:

debug:
0
0
Exception in thread "main" java.lang.IndexOutOfBoundsException
    at datastructureproject.DoublyLinkedList.getNodes(DoublyLinkedList.java:57)
    at datastructureproject.DoublyLinkedList.add(DoublyLinkedList.java:34)
    at datastructureproject.MergeSort.sort(MergeSort.java:31)
    at datastructureproject.DoublyLinkedList.main(DoublyLinkedList.java:82)
Java Result: 1
BUILD SUCCESSFUL (total time: 2 seconds)

ПОЖАЛУЙСТА, помогите мне большое спасибо.

Answer 1

Это нетрадиционный «ответ» - я буду здесь в течение следующих нескольких часов, поэтому я постараюсь помочь вам в процессе поиска и исправления этой ошибки.

Шаг 1. Захват ошибокинформация в исключениях

Исключение выдается в getNodes этой проверкой:

if (index < 0 || index > length) {
   throw new IndexOutOfBoundsException();

Чтобы упростить отладку, вы всегда должны предоставлять информацию для своих исключений (см .: Эффективная JavaИздание 2-е: Пункт 63: Включить информацию о сбое в подробные сообщения ).Первый шаг, который поможет нам выявить и исправить эту ошибку, заключается в следующем:

if (index < 0 || index > length) {
   throw new IndexOutOfBoundsException("Index=" + index + "; length=" + length);

Теперь, когда выдается исключение, мы также получаем подробное сообщение о значениях index и length был.

---

Перерыв: Подозреваемый # 1

DoublyLinkedList listTwo = new DoublyLinkedList();
for (int x = (localDoublyLinkedList.size() / 2) + 1;
        x < localDoublyLinkedList.size(); x++) {
    listTwo.add(x, localDoublyLinkedList.getValue(x));
}

По всей вероятности, это виновник.listTwo пусто при попытке добавить элемент с индексом x.Возможно, вы хотите что-то вроде этого:

DoublyLinkedList listTwo = new DoublyLinkedList();
for (int x = (localDoublyLinkedList.size() / 2) + 1, offset = x;
        x < localDoublyLinkedList.size(); x++) {
    listTwo.add(x - offset, localDoublyLinkedList.getValue(x));
}

При этом используется вычисление offset, так что listTwo.add начинается с индекса 0.

---

Intermission # 2: Используйте большеfinal локальные переменные

Я предлагаю что-то вроде этого:

final int L = localDoublyLinkedList.size();
final int M = L / 2;

Затем используйте L и M в ваших алгоритмах для улучшения читаемости.