Чтение онлайн

на главную - закладки

Жанры

Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

Шрифт:

Стандартные массивы

Можно даже не сомневаться, что все вы знаете стандартный способ объявления массивов в Delphi. Так, объявление

var

MyIntArray : array [0..9] of integer;

создает массив из 10 элементов типа integer. В языке Object Pascal диапазон изменения индексов элементов можно выбирать любым (в приведенном случае - от 0 до 9). В следующем примере объявляется еще один массив из 10 элементов типа integer, но здесь индексация элементов следует от 1 до 10:

var

MyIntArray : array [1..10] of integer;

Некоторые

считают, что работать с массивом, объявленном во втором примере, удобнее (в конце концов, первый элемент имеет индекс 1).

Тем не менее, нужно сказать несколько слов о работе с массивами, индексация которых начинается с нуля. Во-первых, очень часто в API-интерфейсах операционных систем Windows и Linux, а также Delphi-библиотеках VCL и CLX предполагается, что первый элемент в массиве имеет индекс 0. Кроме того, в языках программирования С, С++ и Java индексация всех массивов обязательно начинается с 0. Поскольку и Windows, и Linux реализованы на С (или С++), при вызове API-функций считается, что индекс первого элемента массива равен 0.

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

В-третьих, если вы передаете массивы в качестве параметров функциям (скоро мы перейдем к рассмотрению открытых массивов), то функция Low (которая возвращает индекс первого элемента массива) внутри некоторой функции будет возвращать 0 независимо от того, как массив объявлен вне этой функции. (Обратите внимание, что сказанное было справедливо для всех версий Delphi на момент написания книги; в будущих версиях, возможно, будет введена возможность индексирования элементов массивов в функциях по реальным индексам.)

Еще один момент, о котором необходимо помнить, - для основных типов массивов, элементы которых располагаются в памяти непрерывно, вычисление адреса элемента N (т.е. элемента MyArray[N]) в случае индексации с 0 производится по следующему выражению:

AddressOfElementN :=

AddressOfArray + (N * sizeof(ElementType));

Если же индексация массива начинается с X, то адрес элемента N будет вычисляться в соответствии с выражением:

AddressOfElementN :=

AddressOfArray + ((N - X) * sizeof(ElementType));

Как видите, в последнем случае выражение несколько сложнее. Несмотря на то что вычисление адреса каждого отдельного элемента лишь немного медленнее (о снижении быстродействия можно даже не говорить), при использовании нескольких массивов снижение скорости работы приложения вследствие того, что индексация элементов всех массивов начинается не с 0, может оказаться весьма существенной.

И в качестве последнего аргумента в пользу применения массивов, индексация элементов которых начинается с нуля, может служить удобство вычислений и программирования. Например, если доступ ко всем элементам осуществляется в цикле For, компилятор получает возможность оптимизировать цикл таким образом, чтобы последним значением переменной цикла был 0, поскольку сравнение с 0 в конце цикла будет быстрее, нежели сравнение с произвольным числом. В книге можно будет встретить несколько таких примеров. Таким образом, учитывая все вышесказанное, имеет смысл использовать массивы, первый элемент которых имеет индекс 0.

Так что же такого замечательного в использовании массивов в качестве структуры данных? Во-первых, вычисление адресов элементов выполняется очень быстро. Как уже говорилось, для этого нужно всего лишь умножение и сложение. При получении доступа к элементу N (MyArray [N]) компилятор для вычисления адреса добавляет простой машинный код. Независимо от значения числа N, формула для вычисления адреса будет одной и той же. Другими словами, получение доступа к элементу с индексом N принадлежит к классу операций O(1) и не зависит от величины N.

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

До сих пор мы рассматривали только преимущества массивов, но хотелось бы знать и об их недостатках. Первый недостаток связан с операциями вставки и удаления элементов. Что происходит, если, например, в массив необходимо вставить новый элемент с индексом n? В общем случае, все элементы с индексами, начиная с n и до конца массива, потребуется переместить на одну позицию, чтобы освободить место под новый элемент. А фактически выполняется следующий блок кода:

{сначала освободить место под новый элемент}

for i := LastElement downto N do

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

{вставить новый элемент в позицию с индексом N}

MyArray[N] := NewElement;

{увеличить значение длины массива на единицу}

inc(LastElementIndex);

(Конечно, на практике цикл заменяется вызовом процедуры Move.)

Рисунок 2.1. Вставка в массив нового элемента

Рисунок 2.2. Удаление элемента из массива

Объем памяти, который будет затронут при вставке нового элемента, зависит от значения n и количества элементов в самом массиве. Чем больше количество элементов, которые необходимо переместить, тем больше времени потребуется на выполнение операции. То есть, время, требуемое на выполнение цикла For, будет пропорционально количеству элементов в массиве. Другими словами, вставка нового элемента в массив принадлежит к классу операций O(n).

Тот же ход рассуждений справедлив и для операции удаления элемента из массива. Но в этом случае удаление элемента с индексом n означает, что элементы, начиная с индекса n + 1 и до конца массива, будут перенесены на одну позицию к началу массива, чтобы "закрыть" образовавшуюся от удаления элемента "дыру". Как и в случае со вставкой, удаление принадлежит к классу операций O(n).

{удалить элемент, переместив следующие за ним элементы на одну позицию вперед}

for i := N+ 1 to LastElementIndex do

Поделиться:
Популярные книги

Береги честь смолоду

Вяч Павел
1. Порог Хирург
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Береги честь смолоду

Убивать чтобы жить 2

Бор Жорж
2. УЧЖ
Фантастика:
героическая фантастика
боевая фантастика
рпг
5.00
рейтинг книги
Убивать чтобы жить 2

Тринадцатый

NikL
1. Видящий смерть
Фантастика:
фэнтези
попаданцы
аниме
6.80
рейтинг книги
Тринадцатый

Белые погоны

Лисина Александра
3. Гибрид
Фантастика:
фэнтези
попаданцы
технофэнтези
аниме
5.00
рейтинг книги
Белые погоны

Разведчик. Заброшенный в 43-й

Корчевский Юрий Григорьевич
Героическая фантастика
Фантастика:
боевая фантастика
попаданцы
альтернативная история
5.93
рейтинг книги
Разведчик. Заброшенный в 43-й

Последняя Арена 10

Греков Сергей
10. Последняя Арена
Фантастика:
боевая фантастика
рпг
5.00
рейтинг книги
Последняя Арена 10

Идеальный мир для Социопата 5

Сапфир Олег
5. Социопат
Фантастика:
боевая фантастика
рпг
5.50
рейтинг книги
Идеальный мир для Социопата 5

Энфис 2

Кронос Александр
2. Эрра
Фантастика:
героическая фантастика
рпг
аниме
5.00
рейтинг книги
Энфис 2

Ты не мой Boy 2

Рам Янка
6. Самбисты
Любовные романы:
современные любовные романы
короткие любовные романы
5.00
рейтинг книги
Ты не мой Boy 2

Под маской моего мужа

Рам Янка
Любовные романы:
современные любовные романы
5.67
рейтинг книги
Под маской моего мужа

Лорд Системы 7

Токсик Саша
7. Лорд Системы
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Лорд Системы 7

Жандарм 4

Семин Никита
4. Жандарм
Фантастика:
попаданцы
альтернативная история
аниме
5.00
рейтинг книги
Жандарм 4

Релокант. Вестник

Ascold Flow
2. Релокант в другой мир
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Релокант. Вестник

Неудержимый. Книга VIII

Боярский Андрей
8. Неудержимый
Фантастика:
фэнтези
попаданцы
аниме
6.00
рейтинг книги
Неудержимый. Книга VIII