Действия над массивами

15.6.1 Можно присваивать содержимое одного массива другому, но не всегда.

Type

t = array [1..10] of byte;

Var

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

c: array [1..10] of byte

e, f: t;

Правильно

begin

a := b;

e := f;

Неправильно

a := c;

e := a;

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

Тип С неэквивалентен типам А и В. Если бы нужно было сделать тип С эквивалентным типам А и В, то нужно:

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

Замечание: хотя можно присваивать содержимое одного массива другому, вы нельзя их сравнивать.

if a = b then ... - нельзя.

Поэтому, если нужно сравнить 2 массива, то их сравнивать придется посимвольно (кроме символьных массивов, которые в Паскале эквивалентны строкам).

15.6.2 Инициализация массивов.

Замечание: в отличие от языка Си, где есть старт языка т согласно этому стандарту все глобальные переменные, в том числе массивы, в начале выполнения программы инициализируются нулями, для Паскаля (Турбо-Паскаля) нет стандарта (этот язык - внутренняя разработка фирмы Борланд) и массивы (в зависимости от реализации) могут не инициализироваться (инициализироваться всяким мусором - не обязаны инициализироваться обязательно 0). Поэтому для определенности необходимо перед использованием массивов задать им начальное значение. Для этого есть три пути:

1. Использование типизированных констант (уже рассмотрели выше)

2.

Const a: array[1..2, 1..3] of byte = ((1,2,3), (4,5,6));

Использование цикла (по элементам)

3. Использование специализированной функции Fillchar().

Использование цикла (по элементам)

с ее помощью удобно обнулять массив

Var

a: array [1..5] of byte;

i: byte;

begin

randomize;

for i := 1 to 5 do

a[i] := i; // элементы массива инициализируются значениями параметра цикла

или

a[i] := random(100); // элементы массива инициализируются псевдослучайными числами

или

// элементы массива инициализируются в диалоге с пользователем

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

Использование процедуры Fillchar(): типа char

Fillchar(имя массива, число байт (не элементов), значение) - заполняет побайтно всю область памяти под массив заданным значением {fillchar (a, 5 ,#0);}, причём проверка на выход за границы массива не выполняется.

Пользоваться этой процедурой необходимо аккуратно: если тип элемента массива будет не byte, а integer, то fillchar (a,5,#1) забьет массив значением 257, а не 1. Кроме того, если бы тип элементов был integer, надо было бы писать 5*sizeof(integer) вместо 5.

15.6.3 Элементы массива можно использовать везде, где можно использовать обычные скалярные переменные (в операторах присваивания и процедурах ввода-вывода и т.п.)

15.6.4 Обмен значениями между подмассивами и между массивом и подмассивами

15.6.4.1 Обмен между подмассивами

Подмассив – часть массива, к которой можно обратиться, используя число индексов, меньшее чем число размерностей массива. Более общее название подмассива – сечение. В языке PL/I: А(1,*) – 1-я строка, А(*,1) – 1-я колонка массива. В Паскале сечения возможны только для строк: A[1] – первая строка n-мерного массива.

Правило (выше было дано): тип элемента массива определяется тем, сколько индексов указано после имени массива.

Рассмотрим пример:

Const N=3;

Var

A: array[1..2, 1..N] of byte;

B: array[1..2, 1..N] of byte;

Begin можно использовать sizeof(тип элемента)*число_ячеек

Fillchar(a, sizeof(a) div 2, 1); ------------- заполнение 1-ой строки единицами (правильно)

Fillchar(a[2,1], sizeof(a) div 2, 2); ------------- заполнение 2-ой строки двойками (неправильно)

можно и так: round(sizeof(a)/2) -- в отличие от DIV деление с помощью ‘/’ всегда дает вещественный результат

Замечание. Так указывать параметр fillchar нельзя (и указатель использовать тоже нельзя)

Надо (можно) один из двух вариантов:

1) Fillchar(a, sizeof(a), 2); //весь массив а заполняем двойками

Fillchar(а, sizeof(a) div 2, 0); //первую строку очищаем от двоек

2) Fillchar(a[2], sizeof(a) div 2, 2); //вторую строкузаполняем двойками

a[1] := a[2]; -------- можно ------- обмен между 1 и 2 строками одного массива

b[1] := a[2]; -------- нельзя (типы не эквивалентны)

Правило: Обмениваться могут подмассивы только эквивалентных типов.

Однако это правило можно обойти следующим образом. Пусть надо b[1] := a[2].

Move( a[2], -- 1 аргумент (откуда брать)

b[1], -- 2 аргумент (куда помещать)

sizeof(a) div 2); -- 3 аргумент (сколько переслать байтов)

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

15.6.4.2 Обмен между подмассивом и массивом

Рассмотрим сразу Пример:

Type

t=array[1..3] of byte;

Var

A: array[1..2, 1..3] of byte;

B: t;

C: array[1..2] of t;

Begin тип A[2] = array[1..3] of byte (≠ t)

A[2] := b; ------------------------- нельзя (типы не эквивалентны)

тип b = t

C[2] := b; ------------------------- можно (тип c[2] = t = тип b)

Move(b, a[2], sizeof(b)); ------- можно

B := a[2]; -------------------------- нельзя

B := t(a[2]); -------------------------- можно

Move(a[2], b, sizeof(b)); ------- можно

B := c[2]; --------------------- можно

15.6.5 Сдвиг значений внутри массива

15.6.5.1 Сдвиг элементов одномерного массива вправо

Задача: необходимо выполнить сдвиг заданной части массива M (начиная с позиции i₁ (пусть i₁=3) и заканчивая позицией i₂ (пусть i₂=7) на заданное число позиций вправо (пусть = 2).

Изображение постановки задачи имеет вид:

Var M: array[1..11] of byte; Используем разработку цикла восходящим

a=1; b=-2;

j=i-2

Обобщенная запись для сдвига вправо: M[i]:=M[i-2];

i

jшшiii

кстати для сдвига влево: M[i]:=M[i+2];

i₁ i₂ i уменьшается методом и получим следующий линейный

алгоритм:

Массив одномерный и для прохода по нему достаточно одного индекса – i (а у нас в обобщенной записи – два индекса). Чтобы избавиться от второго индекса (j), надо в общем случае выразить зависимость j от i. В общем виде эта зависимость линейная (можно по точкам построить зависимость j от i для проверки) и имеет вид: j := a*i + b

Для нахождения a и b надо составить систему уравнений (из линейного алгоритма):

7 = a*9 + b

6 = a*8 + b

j i

Теперь можно записать цикл. НО:

Нельзя

(глядя на рисунок выше написать)

M[5]:=M[3]; M[6]:=M[4]; M[7]:=M[5]; M[8]:=M[6]; M[9]:=M[7];

i₁ + i₃ i₂ + i₃-1

For i:= 5 to 9 do

M[i] := M[i-2];

Здесь новые значения преждевременно

будут затирать старые

Надо число байт

Самостоятельно: разобрать сдвиг массива влево.

15.6.6 Поиск элемента (одномерного ) массива

Поиск – это нахождение индекса(ов) элемента(ов), значение которого удовлетворяет некоторому установленному правилу (критерию). Обычно в качестве критерия принимают равенство эталону.

Поиск

Среди неупорядоченных элементов Простейший из методов - Линейный поиск: Последовательный перебор в цикле всех элементов массива и cравнение их с "эталоном" до тех пор, пока не будет совпадения. Нельзя проверить до завершения поиска, есть или нет в массиве искомый эталон.   Среднее число шагов = N/2

Среди упорядоченных элементов ascend - по возрастанию descend – по убыванию Можно (и нужно) проверить до начала поиска, есть или нет в массиве искомый эталон. Простейший из методов - двоичный поиск. Пусть требуется найти в массиве A (элементы в нём отсортированы по возрастанию) из N элементов элемент, совпадающий с "эталоном". Вначале мы массив из N элементов делим на 2 половины и определяем, в какой из половин находится эталон. Эта половина принимается за новый интервал и снова делится и т.д. 1 N/2 N низ середина верх левая половина правая половина новый интервал поиска, если A[N/2]>эталона (надо корректировать верхнюю границу интервала) новый интервал поиска, если A[N/2]<эталона (надо корректировать нижнюю границу интервала) Среднее число шагов = log2N

Var A: array[1..10] of byte; эталон: integer; {то, что ищем} i: byte; {индекс массива} совпадение: Boolean; {признак того, что нашли} rez: byte; {индекс искомого элемента} Begin совпадение := ложь; Rez := 0; эталон := ....; перебор и анализ for i:=1 to 10 do (разработка цикла IF A[i] = эталон нисходящим then методом) begin Совпадение := инстина; если надо найти первый Rez := i; break; (а не последний) end; IF совпадение = TRUE then writeln(‘Нашли в ‘, Rez, ‘-ом элементе.’) else writeln(«Совпадений не найдено.») end.

label уходим; Const L=1; H=10; Var A: array[L..H] of integer; эталон: integer; Результат: Longint; Нашли: Boolean; Середина, Низ, Верх: Longint; //текущие границы интервала Begin Низ := L; {левая граница интервала} Верх := H; {правая граница интервала } Нашли := FALSE; {признак того, что нашли} Середина:= 0; {индекс середины интервала между Верх и Низ} Результат := 0; {индекс искомого элемента} эталон := ....; {то, что ищем} {Проверка - есть ли искомый эталон в массиве?} IF (A[Низ] > эталон) OR (A[Верх] < эталон) then begin writeln('Совпадение искать бесполезно'); goto уходим; end; Repeat Середина := round((Верх+Низ)/2); IF A[Середина] > эталон then Верх := Середина //эталон в левой половине else if A[Середина] < эталон then Низ := Середина //эталон в правой половине else Нашли := TRUE; // значит A[Середина] = эталон until (Нашли=TRUE) OR (Низ >= Верх)) IF Нашли = TRUE then Результат := Середина {в Результат - индекс искомого элемента} else writeln(«Совпадений не найдено.») уходим:; end.

В самом начале двоичного поиска имеем 2 ситуации:

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

середину и анализируем 3 ситуации:

выход из цикла := ((Нашли = True) OR

(Низ >= Верх))

Мы рассмотрели ситуацию, когда поиск выполняется только по одному критерию (признаку). Поиск по нескольким критериям может быть выполнен:

см. Однопроходные алгоритмы (индуктивные функции) в Кушниренко, Лебедев «Программирование для математиков»

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

Например: выбрать из всех студентов только мужского пола ростом выше 1.8м и не старше 20 лет.

Здесь можно записать обобщенный критерий поиска в виде логического выражения

П1 и П2 и П3

Пол = мужской рост >= 180 см возраст <=20

Задача поиска сводится к однократному проходу по массиву и отбору в ходе прохода тех студентов, характеристики которых обращают приведенное логическое выражение в истину (TRUE):

Repeat

if (П1 and П2 and П3)

then отобрать

else искать дальше

перейти к следующему

until закончить

б) За несколько проходов по массиву– если удовлетворение запроса связано с накоплением и анализом статистики.

Например: надо выбрать из всех студентов только 3 студентов моложе 20 лет и ростом не ниже 180см которые чаще всего звонят (пишут) мне после 22:00.

Слово чащев условии говорит о том, что необходимо накопить статистику перед выбором.

Здесь уже надо рассматривать не один критерий, а два (второй позволит выбрать из тех, кого отобрали по первому критерию):

- критерий, по которому отбирается (накапливается) статистика;

- критерий отбора из того, что накопили.

Критерий для накопления статистики (сколько раз звонил) должен включать признаки:

- информация о поле студента;

- информация о возрасте студента;

- информация о росте студента;

- информация о времени звонка студента

и будет иметь вид, подобный рассмотренному выше

П1 и П2 и П3 и П4

Пол = мужской рост >= 180 см возраст <=20 время >= 22

Решить поставленную задачу можно по крайней мере так:

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

15.6.7 Сортировка элементов (одномерного) массива (для ускорения поиска в массиве)

Сортировка - расположение (переупорядочивание) элементов по определенному критерию. Обычно - по убыванию (descend) или возрастанию (ascend). Существует много методов сортировки. Простейший, но не самый худший (лучший) - сортировка выбором. Рассмотрим, как выполнить сортировку по убыванию. Для этого надо:

- сначала последовательно рассматривать кандидатов на место самого первого элемента (самого большого), после чего наибольший из кандидатов становится первым (обменивается с первым);

- затем среди оставшихся (N-1) элементов массива последовательно рассматриваются кандидаты на место 2-го элемента и наибольший из кандидатов при просмотре становится вторым (обменивается со вторым элементом);

- и т.д.

Очевидно, что число просматриваемых элементов с каждым шагом уменьшается.

Введем обозначения:

i – индекс элемента, на место которого ищем кандидата

j – индекс элемента, который мы просматриваем в качестве кандидата

i=1 i=2 i=3 i=4 i=5

1 3 4 2 5--- Исходное состояние массива

3 1 4 2 5----После итерации для j=2----------i = 1 j = 2

4 1 3 2 5----После итерации для j=3----------i = 1 j = 3 i = 1

4 1 3 2 5----После итерации для j=4----------i = 1 j = 4

5 1 3 2 4----После итерации для j=5----------i = 1 j = 5

-----------------------------------------------------------------

5 3 1 2 4----После итерации для j=3----------i = 2 j = 3

5 3 1 2 4----После итерации для j=4----------i = 2 j = 4 i = 2

5 4 1 2 3----После итерации для j=5----------i = 2 j = 5

-----------------------------------------------------------------

5 4 2 1 3----После итерации для j=4----------i = 3 j = 4 i = 3

5 4 3 1 2----После итерации для j=5----------i = 3 j = 5

------------------------------------------------------------------

5 4 3 2 1---- После итерации для j=5---------i = 4 j = 5 i = 4

Можно заметить:

- при поиске каждого нового кандидата число просматриваемых элементов уменьшается на единицу;

- при поиске кандидата на I-ое место I фиксируется, а J пробегает значения от I+1 до N.

Очевидно, что требуется два цикла:

- внешний по элементам, для которых ищем кандидата (цикл по параметру I, где I изменяется от 1 до N-1);

- внутренний по элементам-кандидатам (цикл по параметру J, где J изменяется от I+1 до N).

В итоге получим следующий фрагмент программы:

for i:= 1 to N-1 do

for j:=i+1 to N do

ему ищем замену

if ( a[j] > a[i] ) // если кандидат больше по значению, чем текущий

1)

кандидат

then

begin

2)

1) R := a[i]; //чтобы не потерять значение переменной a[i]

2) a[i] = a[j];

3)

3) a[j] = R;

end;

Замечания: по поводу реализации массивов в Паскале:

1. Число размерностей массива ничем не ограничено, однако размер массива как любой статической переменной в памяти ограничен 64 Кб (нельзя объявить тип размером >64 Кб).

2. Индексы могут быть как положительными, так и отрицательными.

3. Тип индексов может быть любым порядковым, кроме типа longint.

4. В Турбо-Паскале имеется два режима компиляции, имеющие отношение к массивам:

{$R+} и {$R-} - выполняется или нет проверка, не выходит ли индекс за объявленные границы диапазона:

- если проверка выполняется, то при нарушении границ диапазона программа аварийно завершается с кодом 201 (Range Check Error);

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

Примечание:

Если отключить контроль диапазонов, можно создать массив с переменными границами (свободный массив):

{$R-}

Var a: array [1..1] of integer:

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

Если по адресу а динамически выделить память, то получим массив такого размера, какого пожелаем (мы вернемся к этому, когда будем рассматривать тему «Указатели»).

5. При передаче массивов как параметров в подпрограммы не рекомендуется определять тип массива непосредственно в заголовке подпрограммы (из-за невозможности при этом обеспечить эквивалентность типов фактического и формального параметров - массивов).

Замечание. Записать-то так при объявлении подпрограммы можно (сама запись не есть ошибка), но делать так не надо из-за проблем с совместимостью дальше по тексту программы..

6. В качестве формального параметра подпрограммы можно использовать массив без границ (открытый массив).

Var

a: array of char;

Для работы с ними используются функции High (возвращает верхнюю границу индекса - обычно = число элементов массива минус 1; не путать с Hi(x) для целый аргументов) и Low (возвращает нижнюю границу индекса, обычно = 0; не путать с Lo(x) для целых аргументов).

Множества.