заднее значение не работает должным образом в очереди кругового массива - PullRequest
Новая
       29

заднее значение не работает должным образом в очереди кругового массива

0 голосов
/ 12 октября 2011

У меня есть этот код для добавления: 

public void add(AnyType item){
    if(isEmpty()){
        q[f]=item;
    }
    else{
        if(size==q.length){
            AnyType[] copyQ = (AnyType[]) new Object[q.length*2];
            System.arraycopy(q, f, copyQ, 0, q.length-f);
            System.arraycopy(q, 0, copyQ, q.length-f, r);
            f = 0;
            q = copyQ;
        }
    }
    q[r]=item;
    r = (r+1)%(q.length);
    size++;
}

Но тогда, когда я хочу получить значение r, это дает мне еще одно значение, чем оно есть на самом деле.Кроме того, когда я копирую значения из одного массива в другой, появляется значение, которое пропускает одно значение.Я знаю, что все связано со значением r = (r+1)%(q.length);, и я работал над этим часами и не могу понять.После присвоения значения q [r], даже если это только первое значение, и я пытаюсь получить значение того, где должно быть r, оно дает мне 1, потому что оно увеличивается по формуле, но я не могу понять,как написать это по-другому, не путая формулу круговой очереди.Любая помощь будет принята с благодарностью.Спасибо!

Ответы [ 2 ]

1 голос
/ 12 октября 2011

Юнит-тесты - твой друг! : -)

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

public void add(AnyType item){
    if(isEmpty()){
        q[f]=item;
    } 
    else {
        if (size == q.length) {
            AnyType[] copyQ = (AnyType[]) new Object[q.length*2];
            System.arraycopy(q, f, copyQ, 0, q.length-f);
            System.arraycopy(q, 0, copyQ, q.length-f, (r + 1));
            f = 0;
            r = q.length -1;
            q = copyQ;
        }
    }

    r = (r+1)%(q.length); 
    q[r]=item;
    size++;
}

Обратите внимание на различия:

  • r - это смещение - вы не можете использовать его как длину во втором arraycopy()
  • r необходимо обновить при изменении размера внутреннего массива
  • Изменен порядок оценки, с шагом r перед сохранением item
0 голосов
/ 12 октября 2011

Это потому, что последние три строки должны быть внутри блока else?Попробуйте код наподобие: 

public void add(AnyType item){
    if(isEmpty()){
        q[f]=item;
    }
    else{
        if(size==q.length){
            AnyType[] copyQ = (AnyType[]) new Object[q.length*2];
            System.arraycopy(q, f, copyQ, 0, q.length-f);
            System.arraycopy(q, 0, copyQ, q.length-f, r);
            f = 0;
            q = copyQ;
        }
    q[r]=item;
    r = (r+1)%(q.length);
    size++;
    }
}

Когда три строки находятся за пределами блока else, вы добавляли новый элемент дважды в случае, когда структура данных пуста.

...