Вставка и удаление в массиве

Основным достоинством массива является прямой доступ к его элементам: для использования элемента нужно указать только имя массива и индекс (или индексы), которые преобразуются в физический адрес элемента. Скорость доступа не зависит от положения элемента в структуре.

Недостаток связан с операциями вставки и удаления элементов. Допустим, одномерный массив arrTable используется для хранения в своих элементах полезной информации, причем содержат информацию только начальные элементы, число которых равно Count. Эти «занятые» элементы называются активными, активные элементы имеют индексы в диапазоне [0, LastIndex]. Очевидно, LastIndex = Count - 1. Если, например, в массив нужно вставить новую информацию в элемент с индексом ind, то все элементы с индексами, начиная с ind и до конца активной части, потребуется переместить на одну позицию, чтобы освободить место под вставляемый элемент NewElement. Эта операция может быть описана следующим фрагментом:

For i:= LastIndex DownTo ind Do

arrTable [i+1]:= arrTable [i];

arrTable [ind]:= NewElement;

Inc(Count); Inc(LastIndex);

Сдвиг части элементов означает их физическое перемещение в памяти. Логическая схема операции вставки показана на рисунке 5.4

Рисунок 5.4 - Вставка в вектор нового элемента: а - до вставки, б - после вставки

Объем памяти, который будет затронут при вставке нового элемента, зависит от значения n и количества сдвигаемых элементов. Время, требуемое на выполнение вставки, зависит от числа активных элементов в массиве: чем больше это количество, тем больше (в среднем) потребуется времени на сдвиг.

Тот же ход рассуждений справедлив и для операции удаления активного элемента из вектора. В случае удаления элемента с индексом ind, все элементы, начиная с элемента arrTable[ind+1], должны быть перенесены на одну позицию к началу вектора, чтобы «закрыть» образовавшуюся от удаления элемента «дыру». Логическая схема операции удаления приводится на рисунке 5.5. Программный фрагмент удаления может иметь вид:

For i:= ind + 1 To LastIndex Do

arrTable [i-1]:= arrTable [i];

Dec(Count); Dec(LastIndex);

Таким образом, можно сделать вывод: операции вставки и удаления в массиве выполняются медленнее при увеличении количества элементов.

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

Рисунок 5.5 - Удаление элемента в векторе: а - до удаления, б - после удаления

Дата добавления: 2014-01-07