В программировании часто встречаются задачи, связанные с хранением и обработкой большого количества однотипных данных. Например, требуется ввести оценки по информатике для 25 студентов группы ИС-09 и определить средний балл. Для решения этой задачи опишем 25 переменных: is09_1, is09_2,is09_3, …, is09_25:
Var is09_1, is09_2, is09_3, …, is09_25: 2..5;
Каждая из них будет соответствовать одному студенту. После этого используем 25 операторов для ввода оценок:
А что произойдет, если нужно будет решить эту задачу для всего университета? Вводить несколько тысяч переменных?
Для решения таких задач используют массивы. Для структур, используемых в алгоритмизации, организация массивов представляется наиболее удобной для программирования. Это связано с возможностью непосредственного логического доступа к любому их элементу, без обращения к предыдущим элементам, что обеспечивает простоту интерфейса между логической организацией данных и их физическим представлением, поскольку массив легко проецируется на оперативную память. Это обстоятельство оказалось столь удобным для программирования, что для большинства структур данных разработаны механизмы их эмуляции на базе массивов.
Массив состоит из конечного числа элементов (компонент), содержимое которых относится к некоторому общему, базовому типу. При этом сам базовый тип должен быть таким, что принадлежность к нему гарантирует одинаковые размеры памяти для размещения каждой из компонент. Элементы различаются местом их размещения внутри структуры, иначе говоря, номером или индексом. Обычным является непрерывное представление массива, как логическое, так и физическое, то есть логический (описанный в программе) массив проецируется на непрерывный участок оперативной памяти. Значит, необходимо, чтобы такой участок существовал. Отсюда вытекают ограничения на размер массива, диктуемые организацией оперативной памяти: массив должен поместиться в сегмент данных программы, размеры которого фиксированы. И, конечно, данные в массивах сохраняются только до конца работы программы.
Таким образом, массив представляет собой структуру данных, определяемую на основе следующих своих свойств:
1. массив состоит из однотипных элементов, при этом используемый тип называется базовым,
2. число элементов массива строго фиксировано,
3. элементы массива упорядочены в том смысле, что каждому из них соответствует один или несколько индексов, позволяющих однозначно указать его расположение в составе структуры,
4. количество индексов, которое связано с отдельным элементом массива, определяет его размерность,
5. число элементов массива совпадает с общим количеством возможных значений его индексов,
6. массив – именованная совокупность данных, причем использование его имени совместно с индексами позволяет определять значения его элементов,
7. доступ к элементам массива является прямым, то есть любой элемент массива полностью определяется своими индексами и возможности доступа к нему не зависят от других элементов.
Массивы можно определить и через понятия математики.
В современной математике для описания и решения многих задач используются матрицы и вектора.
МатрицейAnm называется таблица чисел, состоящая из n строк и m столбцов.
Каждый элемент матрицы aij полностью определяется своими индексами – номерами строки i и столбца j , в которых он расположен.
Количество индексов определяет размерность матрицы: одномерная (вектор), двумерная, трехмерная и т.д.
Максимальное значение каждого индекса определяет размер матрицы.
В качестве аналога матриц в программировании выступают массивы.
Массив – это упорядоченный набор фиксированного количества однотипных компонентов, имеющих общее имя – имя массива, и различающихся значениями своих индексов. В зависимости от количества индексов компонентов (элементов) массива различают одномерные (вектора), двумерные (матрицы) и т.д. массивы. В Паскале допускаются восьмимерные массивы.
Элементы векторов хранятся в оперативной памяти компьютера в расположенных друг за другом ячейках в том порядке, в котором они размещены в векторе. Таким образом, структура вектора полностью соответствует структуре оперативной памяти компьютера, поэтому остальные структуры данных размещаются в памяти так, как они размещались бы в одномерных массивах.
Двумерный массив состоит из элементов, образующих прямоугольную таблицу, причем первый индекс элемента обозначает номер строки, а второй – номер столбца этой таблицы, на пересечении которых расположен данный элемент:
a11 a12 a13 …
a21 a22 a23 …
a31 a32 a33 …
……………………..
Таким образом, двумерный массив полностью соответствует понятию матрицы. В оперативной памяти элементы двумерного массива расположены последовательно, строка за строкой: сначала элементы первой строки, затем второй и так далее: a11, a12, a13,…, a21, a22, a23,…, a31, a32, a33,… Значит, быстрее изменяется второй индекс (номер столбца), чем первый (номер строки).
Многомерные массивы располагаются в памяти компьютера так, что сначала изменяется последний индекс элемента, затем – предпоследний и так далее.
Массив как структура данных характеризуется тем, что с помощью индексов обеспечивается прямой (непосредственный) доступ к каждому его элементу: чтение или запись любого элемента массива не зависит от того, прочитаны или записаны предшествующие ему элементы.
Тип элементов массива называется его базовым типом. В Паскале это может быть любой стандартный (целый, вещественный, строковый, символьный, логический) или пользовательский (массив записей, файлов, множеств) тип данных.
Индексы элементов массива могут быть не только целыми положительными числами, но и данными любого упорядоченного типа (интервального, перечисляемого, символьного, строкового).
Перед использованием массива в программе его необходимо описать – назвать его имя, указать начальное и конечное значения каждого индекса элементов массива и их базовый тип.
Пусть имеется целочисленный массив A23, состоящий из следующих элементов:
-5 8 0
Описание массива можно произвести несколькими способами:
а) в разделе описания переменных:
Var A : Array [1..2,1..3] Of Integer;
Описан массив целых чисел А , имеющий две строки с индексами 1 и 2 и три столбца с индексами 1,2,3.
Внимание! Индексы указываются в квадратных скобках, между начальными и конечными значениями индексов ставится по две точки, а между измерениями – запятая.
Внимание! При компиляции программ, использующих массивы, настоятельно рекомендуется использовать директиву компиляции {$R+}. В этом режиме проверяются все индексы массивов на выход за свои границы. При выходе за границы выполнение программы прерывается и выдается сообщение об ошибке:
Error 201: Range check error
б) в разделе определения констант, типов и описания переменных:
Const row = 2;
Col = 3;
Type TMatrix = Array [1..row,1..col] Of Integer;
Var A : TMatrix;
Сначала определены поименованные константы row и col (описаны их имена и заданы конкретные значения), затем определен новый тип данных TMatrix с использованием ранее определенных констант, а в конце описан массив A с использованием ранее определенного типа данных,
в) определением массива как типизированной константы:
Const A : Array [1..2,1..3] Of Integer =((-5,8,0),(9,-1,4));
При этом задаются не только имя, размеры и базовый тип массива, но и конкретное значение его элементов. Эти значения могут изменяться в программе.
Номера строк и столбцов массивов могут быть заданы не только целыми положительными числами, но и символами, отрицательными целыми числами и строками.
Примеры:
1. Описать массив Doska, позволяющий рассматривать его как модель шахматной доски.
На шахматной доске строки обозначаются латинскими буквами от a доh, а столбцы – цифрами от 1 до 8, а шахматные фигуры – тоже латинскими буквами. Поэтому описание этого массива может выглядеть так:
Var Doska : Array [‘a’..’h’,1..8] Of Char;
а обращение к элементу этого массива – так:
Doska[‘c’,2]:=’f’;
Использование нечисловых индексов элементов массива повышает наглядность программы, делает ее более понятной.
2. Описать массив Roma, в котором можно было бы хранить данные о количестве жителей Рима с года его основания (754 г. до н.э.) и до 33 г. н.э.
Традиционное описание:
Var Roma : Array [1..787] Of Word;
В этом случае первый элемент массива соответствует году основания Рима:
Roma[1]:=2;в год основания Рима в нем жили два основателя
Roma[787]:=450000;в 33 г. н.э. в Риме проживали 450000 жителей
Тогда какой элемент массива соответствует, например, 639 году до н.э.? Сразу сказать трудно, необходимо вычислить индекс этого элемента.
Таким образом, при традиционном описании этого массива возникают трудности сопоставления индекса элемента с годом.
Опишем массив по-другому, используя отрицательные индексы элементов:
Var Roma : Array [-754..33] Of Word;
В этом случае можно сразу сказать, что 639 году до н.э. соответствует элемент Roma[-639].
3. Описать массив Ozenka, в котором можно было бы хранить оценки студентов Иванова И. и Петрова П. по математике, физике и информатике:
