§ 40. Динамические массивы

Определения и обозначения

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

Тип динамического массива — объявление вида array of ТипЭлементов, без фиксированных границ индексов. Например, array of Integer задаёт массив целых чисел, но не сообщает, сколько их будет. Такое объявление описывает, какие значения можно хранить, а размер задают отдельно.

Процедура SetLength задаёт или изменяет количество элементов динамического массива. Ей передают имя массива и нужную длину, например SetLength(a, 10). Вызов выделяет память для элементов, поэтому без него обращаться к элементам ещё нельзя.

Функция Length возвращает текущее количество элементов массива. Например, если Length(a) равно 10, то в массиве десять элементов, обычно с индексами от 0 до 9. Значение функции удобно использовать в циклах и проверках границ.

Как это устроено

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

Чтобы создать массив из n элементов, вызывают SetLength(a, n). В распространённых языках Pascal индексация динамического массива начинается с нуля: первый элемент имеет индекс 0, а десятый — 9. Поэтому количество элементов равно n, а допустимые индексы — от 0 до n − 1; у пустого массива обращаться не к чему.

После выделения памяти к элементу обращаются по имени массива и индексу: например, a[i]. Значение индекса должно оставаться в допустимых границах, иначе программа может выдать ошибку или получить неверный результат. Количество элементов возвращает Length(a), поэтому цикл перебора обычно заканчивают индексом Length(a) − 1.

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

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

Сравнение статических и динамических массивов

Сравнивай прежде всего момент задания размера и возможность его менять: эти признаки помогают выбрать подходящий вид массива. Если количество элементов известно и не изменится, достаточно статического массива. Если объём данных определяется во время работы программы, удобнее динамический.

Разбор задач

Массив квадратов индексов

Условие. Объявить динамический массив целых чисел, выделить место для 10 элементов, записать в каждый квадрат его индекса и вывести массив. Поскольку индексы начинаются с нуля, значения будут квадратами чисел от 0 до 9. Для перебора подойдёт цикл по всем допустимым индексам.

1. Объявляем переменную как array of Integer, затем вызываем SetLength(a, 10).
2. В цикле от 0 до Length(a) − 1 записываем a[i] := i * i.
3. Вторым циклом выводим значения массива в том же порядке.

Ответ. На экране появятся числа 0, 1, 4, 9, 16, 25, 36, 49, 64, 81. Длина массива равна 10, а последний индекс — 9. Использование Length в границе цикла позволяет не задавать количество элементов повторно.

Последовательность неизвестной длины

Условие. Считать целые числа, заранее не зная их количества, и вывести среднее арифметическое. В примере конец последовательности обозначается концом входного потока, например условием EOF. Число прочитанных значений нужно хранить отдельно либо определять через длину массива.

1. Начинаем с массива нулевой длины. Для каждого прочитанного числа увеличиваем длину на единицу через SetLength.
2. Записываем новое число в элемент с индексом Length(a) − 1. Так сохраняется порядок поступления значений.
3. После чтения проверяем, что длина больше нуля, суммируем элементы и делим сумму на Length(a).

Ответ. Среднее равно сумме всех считанных чисел, делённой на их количество. Проверка ненулевой длины не позволяет делить на ноль, если вход оказался пустым. Для длинных последовательностей частое изменение длины может быть неэффективным, но здесь оно показывает принцип накопления.

Удаление заданного значения

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

1. Устанавливаем индекс записи в 0 и просматриваем массив слева направо.
2. Если текущий элемент не равен заданному, копируем его в позицию записи и увеличиваем индекс записи. Совпавшее значение пропускаем.
3. После прохода индекс записи показывает число оставшихся элементов. Вызываем SetLength(a, индексЗаписи) и выводим массив.

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

Типичные ошибки

Обращаться к элементам сразу после объявления массива нельзя: память ещё не выделена, поэтому доступных позиций нет. Ошибку допускают, принимая объявление типа за создание массива нужной длины. Сначала вызови SetLength, а затем проверь, что длина больше нуля.

Индекс, равный Length(a), не принадлежит массиву: при длине 5 допустимы индексы 0–4. Такое обращение возникает, когда количество элементов путают с номером последнего. Для проверки подставь небольшую длину, например 1: единственный индекс будет 0, а не 1.

Уменьшение размера до завершения обработки может удалить нужные значения. Так бывает, если SetLength воспринимают как команду «убрать один элемент», не подготовив данные к сдвигу. Перед вызовом проверь, что нужные элементы уже перенесены в начало массива и известен новый размер.

Length возвращает количество элементов, а не максимальный индекс. Путаница появляется потому, что оба числа описывают границу массива, но отличаются на единицу при индексации с нуля. Проверяй себя формулой «последний индекс = Length(a) − 1» и не используй индекс длины в цикле.

Связь с другими темами

Для работы с динамическими массивами нужны знания об обычных массивах, индексах и циклах: именно ими перебирают и изменяют элементы. При обработке последовательностей пригодится умение читать данные и накапливать результат. Объявление массива связано с переменными, а изменение его размера — с выделением и освобождением памяти. Такой способ хранения используют при чтении файлов, списков данных и любых последовательностей неизвестной заранее длины.

Что запомнить

• Размер динамического массива задают во время выполнения программы.
• Для выделения или изменения памяти используют SetLength.
• Количество элементов динамического массива возвращает Length.
• Индекс последнего элемента равен Length(массив) − 1.
• При увеличении размера существующие элементы обычно сохраняются.
• При уменьшении размера элементы за новой границей удаляются.
• Динамический массив удобен, когда число входных данных заранее неизвестно.