1. Сложные типы данных (массивы)
Необходимость в массивах возникает всякий раз, когда приходится иметь дело с большим, но конечным набором однотипных данных - последовательностью (вектором), таблицей (матрицей), пакетом таблиц ("параллелепипедом'') и т. д. Эти структуры данных называются, соответственно, одномерным, двумерным, трехмерным и т. д. массивами. Каждый массив, используемый в программе, нужно объявить. Компилятор, получая информацию об имени массива и типе элементов, его размерности и размере, резервирует соответствующий объем памяти и определяет вид допустимых операций над элементами. Элементы массива размещаются в смежных областях памяти. Всей области назначается имя массива, которое выбирается по обычным правилам. Чтобы обратиться к элементу, надо использовать индексированную переменную, т. е. написать имя массива, а в квадратных скобках указать индекс, если массив одномерный, либо два индекса, если массив двумерный и т. д. Если элементам массива не были назначены значения, то он так же, как и любая переменная, будет иметь своим значением некий «мусор».
Массивы могут быть статическими и динамическими. Память под статический массив выделяется при компиляции программы. Во время ее выполнения длина такого массива остается неизменной. В Паскале динамическим массивом является ссылочный массив. Память под такие массивы отводится в процессе работы программы и при необходимости может быть изменена или освобождена.
Построение более крупных структур данных для хранения и обработки в программах сложных видов информации обеспечивается структурными типами. Они образуются путем объединения простых элементов данных, называемых компонентами. Компоненты могут быть при этом однородными или разнородными. В первом случае тип данных определяется как тип-массив, а во втором - как тип-запись.
Тип элементов массива называется базовым. Используя любой ранее описанный тип, такой, как, например, базовый, можно получить массив массивов, массив записей, массив строк, массив множеств и т. д.
1.1. Одномерные массивы
Простейшая форма - это одномерный массив (линейная таблица). Он аналогичен одномерному числовому вектору и имеет индивидуальное имя, а для обозначения отдельной компоненты к имени массива добавляется индекс, который и выделяет нужную компоненту.
Компоненты массива называются переменными с индексами. В обычной математической символике записывают: X1, Х2, ..., Хn; или a1,..., а50 и т. д. Наименьший индекс называется нижней границей, наибольший - верхней границей, а число элементов - размером массива. Размер массива фиксируется при описании и в процессе выполнения программы не меняется. Индексы можно вычислять. Наиболее часто в качестве типа индекса используется ограниченный целый тип или перечисляемый тип.
Описание массивов включает в себя следующие указания:
- из переменных какого типа должен состоять массив;
- сколько в нем должно быть элементов;
- какие индексы должны быть использованы для доступа к его элементам.
В общем виде объявление массива выглядит так:
Var <Имя массива> : Array [Нижний индекс .. Верхний индекс] Of <Тип элементов>;
Для имени массива применяются идентификаторы, отвечающие тем же правилам, что и имена переменных и других элементов программы. Параметры массива - нижний и верхний индексы - должны являться константами и определяют пределы изменения индекса и, соответственно, количество элементов, которые содержатся в массиве. Например, если в качестве нижнего индекса использовано значение 5, а в качестве верхнего индекса - 7, то массив будет включать в себя три элемента, доступ к которым может быть осуществлен по индексам 5, 6 и 7. Array - слово языка Pascal, показывающее, что объявляемый элемент данных является массивом;
В качестве типа элемента может быть использован любой необходимый для решения поставленной задачи тип данных, например Integer или String.
Рассмотрим примеры описания массивов с пояснениями:
Program massiv1;
Const
Start =100;
Finish = 105;
Var
S : Integer;
Al: Array [1..10] Of Integer;
{массив десяти переменных типа Integer, для доступа будут использоваться
индексы 1, 2, 3, 4, 5, 6, 7, 8, 9 и 10. Имя массива-А1}
А2: Array [5.. 10] Of Real;
{массив шести переменных типа Real, для доступа будут использоваться
индексы 5, 6, 7, 8, 9 и 10. Имя массива - А2}
Names: Array [5.. 10] Of String;
{массив шести переменных типа String, для доступа будут использоваться
индексы 5, 6, 7, 8, 9 и 10. Имя массива – Names}
В: Array [Start..Finish] Of Byte;
{массив шести переменных типа Byte, диапазон индексов задается константами
Start и Finish - от 100 до 105. Имя массива – В}
Bl: Array [Start..ll0] Of Byte;
{массив одиннадцати переменных типа Byte, диапазон индексов задается
константами Start и 110 - от 100 до 110. Имя массива - В1}
IC1: Array [Start..90] Of Byte;
{некорректное описание массива: нижний индекс (задан константой Start = 100)
превышает верхний индекс (задан константой 90)}
Begin
{Тело программы}
End.
Использование массивов заключается в основном в операциях с его элементами. При этом элементы рассматриваются как отдельные переменные. Для обращения к конкретному элементу в составе массива используются имя массива и индекс необходимого элемента в квадратных скобках:
< Имя массива >[< Индекс элемента >]
Индекс может быть константой или выражением целого типа, например:
Fam[1]: = 'Иванов';
D: = koef [1] * koef [1] -4 * koef [2] * koef [1];
ReadLn (name[n + 1]);
WriteLn (temper [I]);
Под вводом массива понимают ввод значений элементов массива, а именно:
- как и вывод массива, ввод удобно реализовать при помощи инструкции For;
- чтобы пользователь программы знал, ввода какого элемента массива ожидает программа, следует организовать вывод подсказок перед вводом очередного элемента массива. В подсказке обычно указывается индекс элемента массива;
- в качестве индексов массивов могут использоваться не только константы, но и переменные, в том и числе и счетчики оператора цикла For;
- в прикладных программах ввод, как правило, осуществляется либо с клавиатуры, либо из файла;
- можно заполнить массив с помощью датчика случайных чисел.
Остановимся подробнее на вводе с клавиатуры элементов массива и n-количества элементов в массиве.
Количество элементов массива, их упорядоченность и тип задают явно до начала выполнения программы. Поэтому если границы массива точно неизвестны, то их выбирают «с запасом», так чтобы его размер был не меньше значения n, которое будет введено. Например, после описания
a: Array [1.. 100] of Real;
введенное n должно принадлежать диапазону 1..100, а после описания
а: Array [Byte] of Real;
введенное n должно принадлежать типу Byte.
Рассмотрим пример заполнения элементов массива с помощью оператора присваивания и вывод без использования оператора цикла For.
Program massiv2;
Var
A: Array [1..3] Of Integer;
Begin
A[1]: = 8;
A[2]: = 12;
A[3]:=A[1]+A[2];
WriteLn('Первый: ', A[l]);
WriteLn('Второй: ', A[2]);
WriteLn('Третий: ', A[3]);
End.
Массив А содержит 3 элемента типа Integer. Размерность массива задана явно в описании массива. Изменение значений элементов массива происходит с помощью оператора присваивания.
Рассмотрим пример программы, заполняющей элементы массива размерностью n квадратами их индексов и вывод результата работы программы с помощью оператора цикла For.
Program massiv3;
Const
n = 9;
Var
A : Array [l..n] Of Integer;
i: Integer;
BEGIN
For i: = 1 To n Do
A[i]: = i*i;
WriteLn;
For i: = 1 To n Do
Begin
WriteLn (i, '-й элемент');
WriteLn (A[i]);
end;
End.
Массивы предусмотрены в подавляющем большинстве языков программирования и используются в широком круге задач. При этом все-таки имеются некоторые стандартные операции с массивами, которые часто применяются вне зависимости от функциональной направленности решаемой задачи. Это операции поиска в массиве или его части минимального и (или) максимального значения, а также упорядочение массива или его части - выстраивание элементов некоторым образом, обычно просто по возрастанию или убыванию.
Имеется большое разнообразие задач на одномерные массивы. Как и все задачи вообще, условно их можно разделить на три вида:
- задачи, решаемые в «одно соображение»;
- стандартные задачи;
- задачи, решения которых требуют знания вспомогательных алгоритмов, специальных методов и приемов (например, улучшенные методы сортировки массивов, поиск моды и медианы массива; алгоритмы генерирования комбинаторных объектов, алгоритмы на графах и т. д.). Очевидно, что без умения решать задачи первых двух видов невозможно решать нестандартные задачи.
Перечислим стандартные (типовые) задачи на одномерные массивы:
1) нахождение наибольшего (наименьшего) элемента;
2) суммирование элементов (безусловное и условное);
3) подсчет (замена) элементов, удовлетворяющих заданному условию;
4) поиск заданного элемента:
- в неупорядоченном массиве;
- в упорядоченном массиве;
5) определение заданного расположения элементов;
6) удаление элемента, включение элемента в заданную позицию;
7) переразмещение (инвертирование, циклический сдвиг) элементов;
8) случайная выборка элементов (с повторениями и без повторений);
9) слияние двух упорядоченных массивов в упорядоченный массив;
10) сортировка массива (простые методы).
Рассмотрим алгоритм задачи поиска минимального (максимального) элемента в неупорядоченном массиве. Делается предположение, что первый элемент массива является минимальным (максимальным), затем остальные элементы массива последовательно сравниваются с этим элементом. Если во время очередной проверки обнаруживается, что проверяемый элемент меньше (больше) принятого за минимальный (максимальный), то этот элемент принимается за минимальный (максимальный) и продолжается проверка оставшихся элементов. Если в массиве несколько наибольших (наименьших) элементов, то программа находит тот, индекс которого минимальный. Чтобы найти эти величины с максимальным индексом, достаточно добавить знаки равенств в условиях операторов ветвления.
Например, в некоторых видах спортивных состязаний выступление каждого спортсмена оценивается независимо несколькими судьями. Затем из всей совокупности оценок удаляются наиболее высокая и низкая, а для оставшихся оценок вычисляется среднее арифметическое, которое и идет в зачет спортсмену. Если наиболее высокую оценку выставило несколько судей, то удаляется только одна такая оценка. Аналогично поступают с наиболее низкими оценками. Дано натуральное число n, положительные действительные числа a1, ..., an (n > 3). Считая, что числа a1, ..., an - это оценки, выставленные судьями одному из участников соревнований, определить оценку, которая пойдет в зачет этому спортсмену.
Program massiv4;
Const n= 10;
Var
А : Array [l..n] of Real = (5.4, 5.6, 5.3, 5.8, 5.4, 5.5, 5.5, 5.6, 5.0, 5.7);
i: integer;
min, max, sum: Real;
BEGIN
min : = a[l];
max : = a[l];
sum: = a[l];
for i: = 2 to n do
begin
sum : = sum + a[i];
if a[i] > max Then max : = a[i];
if a[i] < min Then min : = a[i];
end;
WriteLn('Оценка в зачет:', (sum - max - min)/(n - 2) : 2 : 2);
ReadLn;
END.