Файл: Массивы.doc

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

Память, выделяемая под переменные структурного типа, по умолчанию, выравнивается по границам Word (блоками, кратными машинному слову – 4 байта) для более быстрого доступа. Например, для типов Byte, Boolean или Char будет выделено 4 байта, хотя фактический размер хранимых данных составляет 1 байт. При объявлении структурного типа можно включить зарезервированное слово packed для того, чтобы уменьшить память, которую занимают данные. В этом случае данные структурного типа будут упакованы. Использование этого слова замедляет доступ к данным, но обеспечивает их компактное хранение.

Описание статических массивов в программе. Доступ к элементам.

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

Массив - структурированный тип данных, состоящий из фиксированного числа элементов одного типа. Например, при обработке результатов многократных замеров температуры воздуха в течение года удобно рассматривать значения температур как массив вещественных чисел. Число элементов массива фиксируется при описании типа и в процессе выполнения программы не изменяется. Для доступа к элементу массива необходимо указать имя массива и в квадратных скобках его номер. Для описания массивов используется служебное слово array. Описание переменной типа массив имеет вид:

var <имя переменной>: array [i..i1,j..j1] of <тип элементов>,

где i, i1 - границы первого индекса массива,

j, j1 - границы второго индекса массива.

Например:

var a: array [1..10] of integer; {массив из 10 целых чисел с номерами 1,2, …10}

Каждый элемент массива помечается целым числом или элементом другого порядкового типа, который называется индексом элемента. Массив задается указанием верхней и нижней границ индексов элементов массива (диапазоном индексов) и типом элементов массива. Диапазоном служат разделенные двумя точками (знак “..”) верхняя и нижняя границы массива. Память для статического массива выделяется в процессе компиляции программы, поэтому в качестве границ диапазонов могут выступать либо целые числа, либо константы, определенные в разделе констант, либо составленные из них выражения. Но необходимо помнить, что эти константы должны быть определены до использования. Статический массив не может быть переменной длины!

Допускается вместо диапазона указывать имя перечислимого типа или такого стандартного типа, как boolean или char. Строго говоря, индекс у массива может быть любого порядкового типа с областью изменения, не превышающей 2 Гбайт.

Примеры:

const N=100;

type

color = (white, black, red, blue, green, yellow, brown);

var

a,s,g:array [1 ..N] of integer;{целочисленные индексы}

b:array [color] of char;{ индексы перечисляемого типа}

c:array [char] of color;{ индексы символьного типа}

d:array[‘a’..’z’] of real;{ индексы символьного типа}

k:array[Boolean] of byte;{ индексы логического типа}

Доступ к каждому элементу массива осуществляется с помощью индекса, т.е. порядкового номера элемента массива. Когда мы хотим обратиться к элементу массива, надо указать имя массива и порядковый номер элемента: a[1], b[red], c['z'], d['s'] . Если указано только имя массива - речь идет обо всем массиве (a, s и d и т.д.). Для массивов определена единственная операция – операция присваивания для однотипных массивов. Например, s:=a (такая операция означает, что все элементы массива a копируются в соответствующие элементы массива s). Все остальные операции определены для элементов согласно их типу. При обработке массива нужно последовательно обрабатывать все его элементы; при вводе массива необходимо последовательно вводить 1-й, 2-й и 3-й и т.д. элементы массива; аналогично и при выводе. Если статический массив создан, но значения назначены не во все элементы, неиспользованные элементы занимают память и содержат произвольные данные.

Массив в памяти располагается непрерывным блоком. Для доступа к элементу массива программе необходимо определить его адрес An. Этот адрес определяется по адресу начала массива в памяти A_base, размеру одного элемента R и номеру элемента n. Если нумерация массива начинается с нуля, то программе для вычисления адреса элемента с номером n потребуется три целочисленные операции – An= A_base+n*R (к адресу начала массива необходимо прибавить смещение - номер элемента n умноженный на размер элемента R). Если нумерация начинается с ненулевого значения k, то требуется 4 целочисленные операции - An= A_base+(n-k)*R. Из вышесказанного можно сделать вывод о том что, при описании массивов выгоднее индексацию начинать с нуля (в некоторых языках программирования индексация массивов всегда начинается с нуля). Время обработки такого массива может оказаться на 10 –20% меньше времени обработки массива аналогичной длины, но с начальным индексом, отличным от нуля. Этот факт желательно учитывать при многократной обработке больших массивов данных. При работе с небольшим объемом данных разница во времени будет несущественна.

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

type

<имя типа> = array [ <тип индекса>] of <тип компонентов>;

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

Пример:

const n=100;

type

vector:array[0..n] of integer;

var a,b,c:vector;

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

Пример описания типа матрицы.

const n=3;m=5;

type

vector:array[1..n] of integer;

matrix: array[1..m] of vector;

var v : vector;

C,D:matrix;

При таком описании вектором (vector) является строка матрицы из 3-х целых чисел, а сама матрица (matrix) это набор из 5 строк (векторов). Матрицы в памяти располагаются построчно – элементы первой строки, второй и т.д. Для обращения к элементу матрицы необходимо указывать два индекса через запятую, первый индекс определяет – номер строки, второй – положение элемента в строке (номер столбца). Приведем примеры возможных операций для матриц С и D. Если после имени такой переменной не указывается никаких индексов, то это матрицы целиком, если один индекс – это строка матрицы с указанным номером, если два индекса – это элемент в заданной строке в заданном столбце.

D:=C; {все элементы матрицы С скопировать в соответствующие элементы матрицы D}

V:=C[1]; {все элементы первой строки матрицы C скопировать в одномерный массив v}

C[2,3]:=5;или C[2][3]:=5; {в третий элемент второй строки матрицы C записать число 5}

V:=D[1]; D[1]:=D[m]; D[m]:=V; {поменять местами первую и последнюю строки матрицы D, используя третью переменную V}

Такую же структуру можно получить, используя другую форму записи (обратите внимание, что первыми указываются индексы строк, матрица m строк и n столбцов).

const n=3;m=5;

type matrix = array [1..m,1..n] of integer;

vector:array[1..n] of integer;

var C,D:matrix; v : vector;

или

var C,D:array [1..m,1..n] of integer; v : vector;

При таком описании доступ к отдельным строкам, как к единому целому, невозможен. Можно оперировать или матрицами целиком, или их элементами. Т.е. операция V:=D~~[1];~~ недопустима.

Аналогично можно ввести 3-мерный массив или массив большего числа измерений

type MatrixArray=array [1..10,1..5,1..3] of integer;

var b: MatrixArray;

или

const n=3;m=5; k=10

type

vector:array[1..n] of integer;

matrix: array[1..m] of vector;

MatrixArray:array[1..k] of matrix;{массив, состоящий из матриц}

var b: MatrixArray;

Переменную b можно использовать для хранения оценок по нескольким предметам для нескольких групп. Тогда vector – это оценки одного ученика по трем предметам, matrix – оценки одной группы из пяти человек. Для доступа к значениям такой структуры указываются три индекса, например, b[2,3,1]:=5 будет означать запись оценки 5 по первому предмету для третьего ученика из второй группы. Первый индекс обозначает номер группы, второй – номер ученика, а третий – номер предмета. Если переменная b используется с одним индексом (b[2]) – это целиком оценки одной группы с номером два, если два (b[2,4]) – это оценки четвертого ученика из второй группы.

Массивы констант.

Если константа принадлежит составному типу или типу, введенному в разделе type, этот тип должен быть указан (такая константа называется типизированной):

const <имя константы> : <тип> = <значение константы> ;

Константа отличается от переменной тем, что значение ей присваивается при трансляции программы, а не в процессе выполнения, как для переменной. Обычно в раздел констант включают те данные, которые не меняются в процессе работы программы. Описание массива констант выглядит так

const

<имя константы массива> : array[<диапазон индексов>] of <тип элементов массива> = (<значение1>,<значение1>, ……,<значениеN>) ;

Число значений должно совпадать с числом элементов массива, а тип значений с типом элементов массива.

Пример:

{массив Days хранит количество дней в месяце, номер месяца соответствует номеру элемента в массиве}

const Days:array[1..12] of integer =(31,28,31,30,31,30,31,31,30,31,30,31);

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

Операции с элементами массива.

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

Стандартные функции Low() и High() действуют для идентификаторов типа массива. Они возвращают нижние и верхние границы массива. Стандартная функция Length() возвращает количество элементов первого измерения массива (для матрицы возвращается число строк)

Ввод-вывод элементов одномерного массива.

Паскаль не имеет средств ввода-вывода всего массива, поэтому ввод-вывод следует организовывать поэлементно (см. рис.1, 2). Блок-схема, изображённая на рис.1 и 2 может быть реализована циклами while, for.

Рис. 1 Ввод элементов массива.

Рис.2 Ввод элементов массива

Пример - ввод элементов массива X с помощью цикла while.

const n=10;

var x: array [1..n] of real;

i: integer;

begin

i:=1;

while (i<=N) do

begin

write(' x[ ', i , '] = '); readln(x[i]);

i:=i+1 // или inc(i);

end;

……………….

end.

Пример - ввод элементов массива X с помощью цикла for.

const n=10;

var x: array [1..n] of real;

i: integer;

begin

for i:=1 to N do

begin

write(' x[ ', i , '] = '); readln(x[i]);

end;

………..

end.

Пример – вывод элементов массива Х в одну строку.

for i: = 1 to n do write (x[i]:6:2,’ ‘);

или

for i: = 1 to n do write (‘X[‘,i,’] = ’,x[i]:6:2,’ ‘);

Алгоритм нахождения суммы и произведения элементов массива.

Рис.3 Нахождение суммы элементов массива Х.

Рис.4 Нахождение произведения элементов массива Х.

Пример – фрагмент программы нахождения суммы и произведения элементов массива Х из n целочисленных элементов.

const n=10;

var x: array [1..n] of integer;

i, s ,p : integer;

begin

{ввод элементов массива}

s:=0;

for i:=1 to N do // нахождение суммы элементов

s:=s+x[i];

writeln(‘сумма = ‘,s);

p:=1;

for i:=1 to N do // нахождение произведения элементов

p:=p*x[i];

writeln(‘произведение = ‘,p);

……..

end.

Нахождения максимального элемента массива и его номера.

Алгоритм решения задачи следующий. Пусть в переменной с именем Max хранится максимальный элемент массива, а в переменной с именем Nmax - его номер. Предположим, что первый элемент массива является максимальным, и запишем его в переменную Max, а в Nmax запишем его номер (т.е. 1). Затем все элементы, начиная со второго, сравниваем с максимальным. Если текущий элемент массива (i-й) оказывается больше максимального, то записываем его в переменную Max, а в переменную Nmax текущее значение индекса i.

Рис.5 Нахождения максимального элемента массива и его номера

Соответствующий участок программы будет иметь вид:

const n=10;

var x: array [1..n] of integer;

i, Max, NMax : integer;

begin

{ввод элементов массива}

Max:=X[1];

Nmax:=1;

for i:=2 to N do

if X[i]>Max then

begin

Max:=X[i];

Nmax:=i;

end;

writeln(‘Max = ‘,Max,’ Max position = ‘, Nmax);

В данном примере можно обойтись одной переменной Nmax, т.к. зная позицию максимального элемента, мы знаем и его значение. Тогда код можно переписать так

Nmax:=1;

for i:=2 to N do

if X[i]>X[NMax] then

Nmax:=i;

writeln(‘Max = ‘,X[NMax],’ Max position = ‘, Nmax);

Упорядочивание массива по возрастанию

Решим следующую задачу: задан массив из n целых чисел, упорядочить массив по возрастанию. Блок-схема представлена на рис.6. Алгоритм упорядочивания состоит в следующем. Сравниваем текущий и последующий элементы массива, если текущий больше последующего, то меняем их местами. В результате этих действий самый большой элемент станет на последнее место, т.е. на N-е. Теперь повторяем этот алгоритм для N-1 элемента массива и устанавливаем максимальный элемент на (N-1)-е место. Так повторяем до тех пор, пока не упорядочим весь массив. Для упорядочивания по убыванию необходимо при сравнении элементов массива заменить знак “больше” на знак “меньше”. Такой метод получил название пузырьковой сортировки.

Рис.6. Алгоритм упорядочивания массива

Пример программы упорядочивания массива (пузырьковая сортировка).

const n=10;

var i,j,b: integer;

y: array [1..n] of integer;

begin

for i:=1 to n do //ввод элементов массива

begin

write('y[',i']='); readln (y[i]);

end;

writeln ('массив y ');

for i:=1 to n do //вывод элементов массива

write (y [i],' ');

writeln;

for j:=1 to n-1 do

for i:=1 to n-j do

if y[i] > y[i+1] then

begin // Меняем элементы местами

b:=y[i];

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

y[i+1]:=b;

end;

writeln('упорядоченный массив');

for i:=1 to n do

write (y[i],' ');

writeln;

end.

Пузырьковая сортировка является самой медленной. Так как для размещения элемента на свое место необходимо много раз переставить его с соседними элементами. Сортировка выбором (selection sort) работает несколько быстрее пузырьковой, т.к. в ней существенно меньше перестановок элементов. Задача сортировки выбором - искать наименьший элемент, который затем меняется местами с элементом из начала массива. Затем находится наименьший из оставшихся элементов и меняется местами со вторым элементом. Процесс продолжается до тех пор, пока все элементы не займут свое конечное положение.