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

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

Недостаток связан с операциями вставки и удаления элементов. Допустим, одномерный массив 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  Удаление элемента в векторе: а  до удаления, б  после удаления

6. Связные списки и алгоритмы их обработки

   1. Списки и их разновидности

В повседневной жизни под термином «список» (list) подразумевают некий перечень объектов реального мира, например, «список студентов группы» или «список комплектующих деталей на сладе». При этом указанный перечень мо­жет содержать не только наименование объектов, но и их дополнительные атрибуты. В нашем примере к таким атри­бутам можно отнести пол студента, размер сти­пендии и т. д.

С точки зрения организации данных под списком пони­мают структуру данных, представляющую собой логически связанную последовательность элементов. Элементом спи­ска обычно является запись. Список называется линейным (linear list), если входящие в него элементы e₁ , e₂ ,…,e_n  линейно упорядочены. Упорядоченность элементов линей­ного списка может задаваться неявно путем последова­тельного расположения его элементов как в логической структуре, так и в памяти ЭВМ. Такой список называют последовательным (sequential list). Примером последовательного списка является вектор, в котором элементы используются для хранения информации списка. С другой стороны, упорядоченность может задаваться с помощью специаль­ных указателей (ссылок), располагаемых в элементах и дающих возможность для каждого элемента определить его непо­средственных предшественника и последователя. Такой список называется связным (linked) или цепным (chained) списком.

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

Элемент связного списка называется обычно узлом (node) Каждый узел связного списка состоит из двух различных по назначению видов полей: содержательные (информационные) поля и поля структурных (или логических) указателей. В содержательных полях хранятся данные, ради которых и создавался список. Некоторые содержательные поля могут хранить указатели на данные, по каким либо причинам не вместившиеся в содержательные поля; такие указатели называются дополнительными или вторичными (secondary pointer). Поля логических или структурных указателей (logical pointer) хранят адреса других элементов списка. Пользуясь логическим указателем (адресом), можно получить доступ от элемента, содержащего этот указатель, к тому элементу списка, на который этот указатель направлен.

Определение связного списка отличается от определения массива, в котором следующий элемент находится в памяти рядом с предыдущим. В связном списке элементы могут быть разбросаны по разным местам памяти, а их порядок определяется ссылками.

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