0

私は何年もの間これを理解しようとしてきましたが、役に立ちませんでした。私のコードには、見えない問題がいくつかあるに違いないと思います。以前は少し複雑な方法で実装したことがあり、苦労している下の年の友人を助けるために簡単な形式で書いていましたが、混乱してしまいました!

コードは次のとおりです。

 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 の精査的な視線が私を助けてくれることを望んでいました. どうもありがとう ！

4

3 に答える 3

4 
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]。次にメソッドが呼び出されるときは、tempArrayfor capacity+1==11スロットを割り当てますが、2 番目のメソッドでtoから0to への for ループをトラバースします。ループの最後のパスは次のようになります。deque.length010

tempArray[11] = ...

これは、スロット ( to ) のみを持っている端tempArrayを過ぎています。11[0][10]

単純な修正は、 for ループを fromではなく from 0toにすることですが、これが実際に必要な動作を実装しているかどうかはわかりません。別のアプローチは を割り当てることですが、実際には容量を意味するものではなく、その状況で「正しい」動作であると考えるものを概念的に反映していない可能性があります。capacity0deque.lengthtempArray = new Object[deque.length+1]capacity

于 2011-02-08T17:47:34.050 に答える
0

私は Java の経験があまりないので、ここではベースから外れている可能性がありますが... InsertFirst を呼び出すと、まだ容量に値が設定されていません。したがって、デフォルトは 0 またはジャンクです。いずれにせよ、 tempArray = (EltType[]) new Object[capacity+1]; を呼び出すと、容量は 1 か、「乱数」のいずれかになります。したがって、outOfBounds になっているのはなぜですか。CAPACITYを使用するつもりだったと思いますか？

于 2011-02-08T17:46:06.580 に答える
0

これがその特定のバグに対する答えです。インスタンス変数を更新していないため、一時配列配列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++;
}

それでも、全体的なクラスは正しくありません。

于 2011-02-08T17:52:03.727 に答える