5 "Резиновый" массив

1 "Резиновый массив"

"Резиновый массив", или - в простонаречии - вектор - структура данных, в которой n однотипных элементов хранятся непосредственно друг за другом (без пропусков) в памяти, и котоая автоматически расширяется при добавлении новых элементов.

Поддерживает 3 основные операции:

  • прочитать элемент в заданной позиции;
  • поменять (существующий!) элемент в заданной позиции;
  • добавить новый элемент в заданную позицию (со сдвигом остальных элементов вправо);
  • удалить элемент в заданной позиции (со сдвигом остальных элементов влево).

Типичная реализация (на примере операции вставки):

public class Vector{

    private double[] arr = new double[10];

    private int size = 0;            // изначально - пусто

    public void insert(double val, int pos){

        if(все место занято){

            создать новый массив в 2 раза больше

            скопировать в него элементы

            присвоить ссылку на него "старому" массиву arr

        }//if

        // собственно вставка:

          сдвинуть элементы с номерами pos+1...size-1 на 1 позицию вправо

        в позицию pos записать val

        увеличить size на 1

    }//insert

    public void print(){

        // распечатать элементы в строку, разделяя пробелами

    }

}//class       

2 Assert

Правило хорошего тона - обнаруживать ошибку как можно раньше после ее возникновения. Поэтому, если ваш метод предъявляет определенные требования к своим входным данным и/или состоянию объекта - пропишите в первых его строках проверку диагностических утверждений.

Применительно к классу Vector - метод insert должен проверять корректность переданной позиции для вставки.

См. также http://prog-school.ru/2010/03/zashhitnoe-programmirovanie-kak-pravilno и http://habrahabr.ru/post/191548/.

Задание

Реализовать упрощенную версию Vector'а как в примере выше. Протестировать: Vector_Tests_Lite.java

Comments