Не удается найти проблемы с деком на основе массива, но возникает исключение outOfBounds - PullRequest
Новая
       5

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

0 голосов
/ 08 февраля 2011

Я пытался понять это целую вечность, но безрезультатно. Я думаю, что у меня должно быть несколько проблем с моим кодом, которые я просто не вижу. Я реализовал это, используя немного более сложный способ раньше, и писал это в более простой форме, чтобы помочь другу в следующем году, который борется, но я только что закончил тем, что оказался в замешательстве!

Код выглядит следующим образом: 

 public class ArrayBasedDeque<EltType> implements Deque<EltType> {

  private final int CAPACITY = 10;
  private int capacity;
  private int end;
  private EltType deque[];  

  public ArrayBasedDeque() {
    this.capacity = CAPACITY;
    deque = (EltType[]) (new Object[capacity]);  
  }
  public EltType first() {
    return  deque[0];
  }
  public EltType last() {
    return deque[end];
  }

  public boolean isEmpty() {
    return end == 0;
  }

  public int size() {
   return deque.length;
  }

  public boolean isFull() {
   int curSize = size();
   return curSize >= capacity;
  }

  public void insertFirst(EltType first) {
    if(!isEmpty()) {
    EltType[] tempArray;
    tempArray = (EltType[]) new Object[capacity+1];
    for (int i=0;i<deque.length;i++) {
      tempArray[i+1] = deque[i]; 
    }
    deque = tempArray; 
    }
   deque[0] = first;
   end++;
  }

  public void insertLast(EltType last) {
    if (isFull()){
          EltType[] tempArray;
      tempArray = (EltType[]) new Object[CAPACITY+1];
      for (int i=0;i<deque.length;i++) {
        tempArray[i] = deque[i]; 
      }
    }
    deque[end] = last;   
    end++;
  }

  public EltType removeFirst() {
    EltType[] tempArray;
    EltType returned = deque[0];
    tempArray = (EltType[]) new Object[capacity];
      for (int i=1;i<capacity;i++) {
        tempArray[i-1] = deque[i]; 
      }
      deque = tempArray;
      end--;
    return returned;
  }

  public EltType removeLast() {
    EltType[] tempArray;
        System.out.println(end);
    EltType returned = deque[end];

    tempArray = (EltType[]) new Object[capacity];
      for (int i=0;i<deque.length;i++) {
        tempArray[i] = deque[i]; 
      }
      deque = tempArray;
    return returned;
  }
}

Проблема в том, что когда я звоню 

abd.insertFirst( 3 );
abd.insertFirst( 3 );
abd.insertFirst( 3 );

это возвращает ошибку. 

java.lang.ArrayIndexOutOfBoundsException: 11
    at ArrayBasedDeque.insertFirst(ArrayBasedDeque.java:37)
    at TestABD.main(TestABD.java:7)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
    at java.lang.reflect.Method.invoke(Unknown Source)
    at edu.rice.cs.drjava.model.compiler.JavacCompiler.runCommand(JavacCompiler.java:271)

то же самое верно для метода insertLast. Я не могу понять это, и надеялся, что пристальный взгляд на stackOverflow поможет мне. Большое спасибо!

Ответы [ 3 ]

4 голосов
/ 08 февраля 2011 
tempArray = (EltType[]) new Object[capacity+1];
for (int i=0;i<deque.length;i++) {
  tempArray[i+1] = deque[i]; 
}
deque = tempArray;

После первого вызова метода deque - это массив длиной 11 (deque == tempArray == new Object[capacity+1] == new Object[11]. При следующем вызове метода вывыделить tempArray для capacity+1 == 11 слотов, но пройти цикл for от 0 до deque.length, что составляет от 0 до 10 при втором вызове метода. Последний проход циклазаканчивается: 

tempArray[11] = ...

после конца tempArray, который имеет только 11 слотов ([0] до [10]).

НаивныйЧтобы исправить это, нужно, чтобы цикл for шел от 0 до capacity вместо 0 до deque.length, но я не уверен, реализует ли это требуемое поведение., но тогда capacity на самом деле не означает способность, и все же может не отражать концептуально то, что вы считаете «правильным» поведением в этой ситуации.

0 голосов
/ 08 февраля 2011

Вот ответ на эту конкретную ошибку. Вы не обновляете переменную экземпляра capacity, поэтому каждый раз, когда вы вызываете insertFirst, массив временных массивов фактически не увеличивается. Так что код должен выглядеть так: 

public void insertFirst(EltType first) {
    if (!isEmpty()) {
        EltType[] tempArray;
                       capacity += 1;
        tempArray = (EltType[]) new Object[capacity];
        for (int i = 0; i < deque.length; i++) {
            tempArray[i + 1] = deque[i];
        }
        deque = tempArray;
    }
    deque[0] = first;
    end++;
}

Тем не менее, общий класс далек от правильного.

0 голосов
/ 08 февраля 2011

У меня нет большого опыта работы с Java, поэтому я мог бы быть здесь неосновным, но ... когда вы вызываете InsertFirst, никакие значения еще не были установлены в емкость. По умолчанию это либо 0, либо мусор. В любом случае, когда вы звоните tempArray = (EltType []) новый объект [емкость + 1]; емкость будет либо 1, либо ... какое-то «случайное» число. Отсюда и почему выходят из границ. Я предполагаю, что вы хотели использовать CAPACITY?

...