2. Массивы

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

Массив – это набор элементов одного типа.

Описание типа массива задается следующим образом:

<имя типа> = ARRAY [<сп. инд. типов>] OF <тип>

где <имя типа> - идентификатор , <сп.инд. типов> - список из одного или нескольких индексных типов, разделенных запятыми, <тип> - любой тип ТР.

Массив определяется именем и количеством размерностей, необходимых для указания местонахождения требуемого элемента массива. Имя массива является единым для всех его элементов.

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

В качестве индексных типов можно использовать любые порядковые типы, кроме LongInt и типов – диапазонов с базовым типом LongInt.

var

a, b : array [1..10] of real;

type

matrica = array [0..5] of array [-2..2] of array [char] of byte;

matrica = array [0..5,-2..2, char] of byte;

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

var

a : array [1..2, 1..2] of byte;

begin

a[1,1] :=1; a[2,1] :=2;

a[1,2] :=3; a[2,2] :=4;

end.

В памяти последовательно друг за другом будут расположены байты со значениями 1, 3, 2, 4.

В ТР можно одним оператором присваивания передать все элементы одного массива другому массиву того же типа, например,

var

a, b : array [1..5] of integer;

begin

…

a:=b;

…

end.

После такого присваивания все пять элементов массива А получат те же значения, что и в массиве В.

Однако над массивами не определены операции отношения. Нельзя, например, записать

IF a=b then …

Сравнивать два массива можно поэлементно, например:

const

min = 1;

max = 5;

type

Matr = array [min..max] of byte;

var

a, b : Matr;

i : Byte;

eq : Boolean;

begin

…

eq := true;

for i := min to max do

if a[i] <> b[i] then

eq := false;

if eq then

write (‘Массивы тождественны’)

else write(‘Массивы различны’);

…

end.

2.1. Сортировка массивов

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

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

1. количество присваиваний;

2. количество сравнений.

Все методы сортировки можно разделить на две большие группы:

1. прямые методы сортировки;

2. улучшенные методы сортировки.

Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:

1. сортировка вставкой (включением);

2. сортировка выбором (выделением);

3. сортировка обменом («пузырьковая» сортировка).

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