Структурированные типы
Структура — расположение, порядок, совокупность устойчивых связей объекта, обеспечивающих его целостность и тождественность самому себе, т.е. сохранение основных свойств при различных внешних и внутренних изменениях.
Общие понятия.
Рассмотрим следующую задачу: ввести с клавиатуры 20 действительных чисел и вычислить их сумму, при этом каждое из чисел сохранить в памяти для последующей обработки. Мы будем вынуждены ввести 20 имен переменных, что, естественно очень неудобно.
Паскаль позволяет работать с более сложными по своей конструкции типами. Они называются типами данных пользователя и относятся к структурированным типам (от слова структура). Отличаются они тем, что переменные структурного типа состоят не из одного элемента (как все стандартные типы — целые, вещественные, символьные и логические), а из нескольких элементов.
К структурированным типам относятся массивы, записи, множества и файлы.
Массивы.
МАССИВ — а) область машинной памяти, в которой могут размещаться совокупности значений одного и того же типа
б) набор переменных, объединенных общим назначением и имеющих одно имя.
Элемент массива— отдельная переменная, входящая в массив.
Размерность массива— количество элементов, которое содержит массив.
Индекс — числовой или буквенный указатель, которым снабжаются математические выражения для того, чтобы отличать их друг от друга.
Индекс элемента массива — номер элемента в массиве.
Особенность массивов заключается в том, что все элементы массива являются данными одного типа (возможно и структурированного).
При назначении массиву имени соблюдаются те же требования, какие предъявляются к именам переменных простых типов.
Доступ к элементам массива.
Массив можно условно изобразить в виде прямоугольника с n делениями, каждое деление — это элемент массива, он имеет свой номер (индекс). Индекс записывается рядом с именем массива в квадратных скобках.
Пример А[1] — первый элемент массива; А[5] - пятый элемент массива; А[1] — 1-тый элемент массива, в последнем примере мы указали в качестве индекса переменную 1. Каждая переменная в Паскале должна быть объявлена, следовательно, и переменная, указывающая индекс (индексная переменная) тоже.
Прежде чем приступить к описанию типа, назначим имена — имя типа массив и имя переменной, которая относится к типу массив. В описании типа мы должны указать, что объявляется тип массив для этого используется служебное слово аrrау, указать границы изменения индексов. У нас 20 элементов, следовательно, индекс изменяется от 1 до 20. Синтаксически это записывается следующим образом 1..20, называется такая запись —диапазон.
Все вышесказанное записывается в программе на языке Паскаль следующим образом:
A :array [1..20] of integer
Необходимо помнить, что значением переменной а является весь массив.
Потребность использовать массив возникает всякий раз, когда при решении задачи приходится иметь дело с большим, но конечным количеством однотипных данных, которые необходимо хранить в памяти.
Предположим, что мы наблюдали температуру воздуха в течение некоторого периода времени (например, месяца). Закончив наблюдения, приступаем к обработке полученных данных: поиску самого холодного или самого теплого дня, вычислению среднемесячной температуры и т.д.
Для этого мы должны составить алгоритм и программу осуществляющие обработку данных.
Основные алгоритмы для работы с одномерными массивами
Одномерным массивом будем называть массив, в котором для указания местоположения элемента достаточно одного индекса.
В разделе описания переменных мы объявили тип массив, а затем отнесли переменную к данному типу. В памяти ЭВМ будет отведено место для размещения элементов массива. Следует особо отметить, что размерность (количество элементов) массива определяется при объявлении типа и изменить количество элементов в процессе работы программы нельзя. Можно пользоваться меньшим количеством элементов.
Наша задача заполнить массив, т.е. каждому элементу дать свое значение, а затем уже обрабатывать по заданному алгоритму. Есть несколько основных алгоритмов, которые необходимо знать. Любую задачу по обработке одномерных массивов можно решить, используя эти основные алгоритмы (такие алгоритмы мы уже называли базовыми).
Перечислим базовые алгоритмы:
1. заполнение одномерного массива значениями;
2. вывод на экран значений элементов одномерного массива;
3. нахождение суммы элементов одномерного массива;
4. подсчет количества элементов, удовлетворяющих заданному условию;
5. поиск максимального (минимального) элемента одномерного массива и его номера.
При этом надо помнить, что массивы нужны тогда, когда для решения задачи необходимо хранение последовательности значений.
Заполнение.
Заполнить элементы одномерного массива значениями мы можем:
• вводя значения с клавиатуры;
• случайным образом;
• по формуле.
Надо помнить, что во всех трех случаях нам не обойтись без организации цикла.
Поиск максимального (минимального) элемента массива.
Пусть мы имеем одномерный массив:
20,-2, 4, 10,7, 21,-12, 0, 4, 17.
Подумаем, какие операции нужно выполнить, если требуется найти максимальный элемент. Естественно, операцию сравнения Мы не задумываемся над тем, что сравниваем всегда пару, "пробегая" глазами все элементы массива. Алгоритм поиска максимального (минимального) элемента мы построим таким образом чтобы сравнивать пару чисел, повторяя действие сравнения нужное количество раз.
Итак, нам необходимо ответить на два вопроса:
1) какие числа входят в пару, составляющую операцию отношения;
2) сколько раз необходимо повторить операцию сравнения. Введем дополнительную переменную с именем mах. Она и будет одним из чисел, второе число — это очередной элемент массива. Для того, чтобы провести первую операцию сравнения необходимо переменной mах присвоить некоторое начальное значение. Здесь могут быть два варианта:
1) присвоить переменной mах первый элемент массива;
2) присвоить число заведомо меньшее всех элементов массива.
Массив содержит сведения о количестве студентов каждой группы I курса. Определить группу с максимальным количеством студентов, считая, что номер группы соответствует порядковому номеру числа в массиве (считаем, что такая группа единственная).
Другими словами, мы должны найти максимальный элемент и его номер.
program max_num;
type mas=array[ 1.. 10] of byte;
var a: mas;
num, i: byte;
max: byte;
begin
{блок заполнения}
for i:=l to 7 do
readln(a[i]);
{поиск максимального и его номера}
max:==0;
{вводим самое маленькое число для данного массива}
for i:=l to n do
if a[i]>max then begin
num:=i;
max:=a[i]
end;
writeln('максимальное число студентов=',mах);
writeln('номер группы=',num);
end.
3) Найти минимальный элемент среди четных элементов массива.
Пояснение: мы не можем переменной min присвоить первый элемент массива, т.к. он может быть нечетным. Следовательно мы должны выбрать какое-то очень большое число для данного типа данных.
Если мы объявим элементы массива integer, то таким числом будет +32767.
program min_even;
var
a:array [1..10] of integer;
i: integer;
min:integer;
begin
for i:=l to 10 do beein
writeln('введите очередной элемент массива ');
readln(a[i]) ;
end;
min:=32767;
for i:=l to 10 do
if (a[i]<min) and (a[i] mod 2=0) then min:=a[i];
if min=32767 then writeln ('в массиве нет четных элементов') else writein ('минимальный элемент среди четных элементов массива=',min)
end.
Обратите внимание: необходимо проверить, изменилось ли значение переменной min, т.к. четных элементов могло и не быть.
Двумерные массивы
В предыдущих параграфах мы рассматривали массивы, каждый элемент которых содержал только один индекс. Такие массивы мы называли одномерными. В математике часто используют многомерные массивы, т.е. массивы массивов. Особенно широкое распространение получили двумерные массивы. Такие массивы условно можно изобразить в виде таблицы. С информацией, представленной в виде таблицы, мы очень часто встречаемся в различных областях знаний — экономике, статистике, математике физике, химии и т.д.
Каждый элемент таблицы имеет два индекса, значения которых позволяют указать местоположение элемента (его координаты).
В математике квадратные и прямоугольные таблицы часто называют матрицами.
Первый индекс — это номер строки, который изменяется только с переходом на следующую строку; второй индекс _ номер столбца. При решении экономических, статистических задач очень часто информация заносится в таблицы, в информатике каждая таблица это тоже двумерный массив.
Про матрицу, имеющую m строк и n столбцов, говорят, что она имеет размер m*n.
Перемещаться по таблице мы можем, двигаясь по строке в этом случае индекс строки изменяется медленнее, чем индекс столбца, и, соответственно, по столбцу (индекс столбца будет изменяться медленнее, чем индекс строки).
При решении задач с использованием двумерных массивов во всех случаях (кроме некоторых частных) организуются вложенные циклы.
Перемещение по строке:
For i:=l to m do —> внешний цикл, изменяется номер строки
For j:=l to n do —> внутренний цикл, изменяется номер столбца
Перемещение по столбцу:
For j:=l to n do —> внешний цикл, изменяется номер столбца
For i:=l to m do —> внутренний цикл, изменяется номер строки
Перечислим базовые алгоритмы и рассмотрим каждый из них. Заполнение двумерного массива:
а) по строке,
б) по столбцу.
2. Печать в виде таблицы.
3. Вычисление суммы элементов каждой строки и каждого столбца.
4. Поиск максимального (минимального) элементов каждой строки (столбца) и их индексов.
5. Сумма элементов массива.
6. Максимальный (минимальный) элемент массива.
Заполнение двумерного массива по строке.
Массив содержит 3 строки и 4 столбца, т.е. 3х4=12 элементов.
Заполним значениями элементы первой строки:
For j:=l to 4 do
a[i]:=random(100);
Для того, чтобы перейти к заполнению элементов второй строки, мы должны изменить индекс строки на 1 и получить два, и т.д. Индекс строк меняется медленнее, чем индекс столбца. Фрагмент программы для общего случая:
for i:=l to 3 do
for j:=l to 4 do
a[i,j]:=random(100);
Заполнение двумерного массива по столбцу.
Заполним двумерный массив, перемещаясь по столбцу.
for j:=l to 4 do {внешний цикл: j — индекс столбца; он меняется медленнее}
for i:=l to 3 do
a[i,j]:==random(100);
Обратите внимание на порядок расположения индексов a [i,j] !
Печать содержимого двумерного массива в виде таблицы.
for i:=l to 3 do begin
for j:=l to 4 do
write(a[i,j],' '); {печатаем элементы строки, не перемещая курсор}
writeln() {перемещаем курсор}
end;
МАССИВЫ (еще раз)
При составлении программ ранее использовались переменные. Для каждой переменной компьютер отводит ячейку памяти обращение к которой выполняется по имени переменной. Недостатком такого способа написания программ – при работе с большим количеством данных пришлось бы выделять большое количество переменных. Зачастую работа с одним типом данных проводится по одному принципу меняется лишь числовое значение. Гораздо легче данные одного типа обозначать одной переменной меняя лишь номер ячейки в которой хранится значения. Такая организация данным называется массив.
Массивом называется упорядоченная последовательность величин, обозначенная одним именем. В языках программирования массивы могут быть одномерные и двухмерные. Если в одномерном массиве указывается имя и номер ячейки, то в двух мерном указывается имя, номер строки и номер столбца, на котором он расположен. Чтобы получить доступ к ячейкам необходимо указать имя массива и его индекс. Один – для одномерного массива и два для двухмерного.
Под массивы, также как и под переменные, машина должна выделять память. Если для переменной машина выделяет одну ячейку памяти, то для массива машина резервирует память сразу под весь массив. Для этого компьютеру необходимо указать, сколько памяти, сколько ячеек необходимо зарезервировать, т.е. какие массивы будут использованы в программе и их размер.
Массив - это упорядоченная структура однотипных данных, хранящая их последовательно. Доступ к элементу массива осуществляется через его индекс. Массивы описываются следующим образом:
Имя типа = ARRAY [ диапазоны индексов ] OF тип элемента массива;
В качестве типа для элементов массива можно использовать любые типы Турбо Паскаля кроме файловых. Диапазоны индексов представляют собой один или несколько диапазонов, перечисленные через запятую. В качестве диапазонов индексов нельзя использовать диапазоны с базовым типом Longint.
ПРИМЕР: Три способа описания одного и того же типа массива:
type {1} M1 = array [0..5] of integer;
M2 = array [char] of M1;
M3 = array [-2..2] of M2;
{2} M3 = array [-2..2] of array [char] of array [0..5] of integer;
{3} M3 = array [-2..2,char,0..5] of integer;
var A:M3;
{Обращаться к элементам массива можно следующим образом:}
begin
read(A[-1,'a',3]);
read(A[1]['x'][0]);
A[1]['c',1]:=100;
end.
Глубина вложенности, т.е. количество индексов, при определении массивов не ограничена. Играет роль только суммарный объем данных в программе. В стандартном режиме работы Турбо Паскаля этот объем ограничен размерами сегмента, т.е. 64 килобайта. Целиком над массивами допускается применение только операции присваивания массивов (подмассивов) одинаковых типов. Остальные операции должны выполняться поэлементно.
ПРИМЕР: Вычисление значения многочлена степени N, коэффициенты которого находятся в массиве A в точке X по схеме Горнера.
Pn(x) = A[0]*X^n + A[1]*X^(n-1) + ... + A[n-1]*X + A[n] =
= (...((A[0]*X + A[1])*X + A[2])*X + ... + A[n-1])*X + A[n].
program Scheme_Gorner;
type Mas = array[0..100] of integer;
var A:Mas; i,j,n:integer; x,p:real;
begin
write('степень многочлена = '); read(n);
writeln('введите целые коэффициенты : ');
for i:=0 to n do read(A[i]);
write('значение X = '); read(x);
p:=0;
for i:=0 to n do p:=p*x+A[i];
writeln('Pn(X) = ',p);
end.
Массив (еще раз)
В программировании даже при написании самых простых программ возникает необходимость в большом количестве переменных. Обычно они разные по типам и по использованию, но бывают ситуации, когда эти переменные одинаковы и их необходимо очень большое количество.
Для того, чтобы Вы лучше поняли, я приведу простой пример. Давайте представим работу такой программы, как нахождение среднего арифметического среди 100 чисел. Что нам понадобиться для написания такой программы? Конечно, сами числа. Для хранения 100 чисел мы должны использовать 100 переменных. Описать их можно, скажем, следующим образом:
var
n1,n2,n3,n4,n5,
n6,n7, ..., n100: Integer;
Это будет выглядеть крайне громоздко, не так ли? Вот здесь и возникает понятие массивов. Массив - это на самом деле одна переменная, но она содержит в себе большое количество отдельных элементов, того типа, который определит программист, и столько, сколько он захочет. (При этом размер массива несколько ограничен). Что это означает? Что заведя переменную-массив мы как бы создаем цепочку переменных. После чего мы можем обратиться к любому элементу этой цепочки: прочитать его, изменить, сделать с ним все, что можно сделать с обычной переменной.
Помните строку? Я имею в виду тип String, который позволяет обратиться к любому символу своему символу:
S: String; S[2] := 'a';
Так вот, String - это и есть своего рода массив. Массив из переменных типа Char. Посмотрите, мы заводим всего одну переменную, после чего можем обратиться к любому ее символу, изменить его, прочитать и т.д. (Однако предупрежу, String - это всеже не массив. Просто этот тип очень подходит для примера).
Также мы можем создать цепочку и из чисел, и из символов, да и вообще из чего угодно. Сегодня мы разберем создание массивов из чисел, а далее по ходу рассылки разберемся и с другими типами массивов.
Создание (описание) массивов
Итак, мы решили создать и использовать в своей программе массив из чисел. Для примера возьмем ту программу, которую я придумал в описании понятия массива: найти среднее арифметическое среди 100 чисел.
Массив - это переменная и как все переменные описывается в разделе var программы. Описание переменной - массива состоит из:
Имени переменной;
Служебного слова Array, означающего "массив";
Описания размера массива (в нашем случае 100 чисел). Диапазон записывается в квадратных скобках - [ и ]. Внутри пишется сам диапазон, в виде двух чисел, разделенных двоeточием: начало..конец;
Задании типа для элементов массива (в нашем случае - целые числа, или Integer). Задание типа начинается со служебного слова of;
Вот пример описания массива на 100 чисел:
var
Mas: Array [1..100] of Integer;
Выпишите этот пример на бумагу. Он вам понадобиться в дальнейшем, так как с первого раза не все его запоминают.
Теперь в программе можно обратиться к любому элементу этого массива - от 1 до 100. Делается это посредством указания имени переменной с номером элемента в квадратных скобках. Вот примеры:
begin
Mas[1] := 100;
Readln(Mas[2]);
Write(Mas[4);
if Mas[100] < 18 then Halt;
Mas[50] := Mas[49] + Mas[1];
end.
Думаю, из примера видно, что с отдельным элементом массива можно делать все, что с любой переменной.
Ну а теперь давайте всеже напишем нашу программу.
Program N1;
var
M: Array [1..100] of Integer;
A: Real;
I: Byte;
begin
Randomize;
For I := 1 to 100 do
M[I] := Random(500);
For I := 1 to 100 do
A := A + M[I];
A := A / 100;
Write('Среднее арифметическое всех чисел массива: ', A);
end.
Вот такая программа. Здесь я использую новую функцию Random , думаю, она вам не знакома. Очень интересная функция.
Функция Random(A: Integer);.
Данная функция возвращает от своей работы случайное число. Что значит "случайное число"? Это значит, что функция возвращает от своей работы какое-то число, каждый раз новое. В качестве параметра задается максимальное значение случайного числа, иначе говоря функция не возвратит число большего диапазона. Для того, чтобы использовать эту функцию, необходимо включить (так говорят, однако мне нравиться больше "инициализировать" - на включение это мало похоже) датчик случайных чисел. Тогда функция начнет нормально работать и возвращать действительно случайные значения.
Инициализация датчика случайных чисел (ДСЧ) происходит вызовом процедуры Randomize. Вы видите ее перед циклом.
Теперь посмотрите, как я использую эту функцию в программе. Дело в том, что вводить с клавиатуры 100 чисел не так уж и приятно, верно? Вот я и заполняю массив случайными числами. Диапазон до 500 вполне здесь подходит, числа будут не очень большие, но и не очень маленькие. При этом я циклом изменяю значение массива и с помощью переменной I пробегаюсь по всем его элементам, заполняя их случайными числами.
Этот пример хорошо демонстрирует создание массива и доступ к его элементам.
Ну а теперь давайте напишем еще одну программу, демонстрирующую работу с массивом. На сей раз мы уже коснемся одного из множества алгоритмов по обработке массивов, а именно алгоритма поиска максимального числа.
Итак, давайте заведем массив. Вводить его будем с клавиатуры, поэтому давайте не будем делать его слишком большим, а ограничимся, скажем, десятью элементами. После этого мы составим алгоритм, находящий максимальное число среди введенных чисел и выведем его на экран.
Текст программы:
Program N2;
var
M: Array [1..10] of Integer;
Max: Integer;
I: Byte;
begin
Writeln('Введите 10 чисел: ');
For I := 1 to 10 do
begin
Write('N',i,': ');
Readln(M[i]);
end;
Max := M[1];
For I := 1 to 10 do
if Max < M[i] then Max := M[i];
Write('Максимальное число: ', Max);
Readln;
end.
Алгоритм работы этой программы очень и очень прост. Среди введенных чисел мы находим максимальное следующим образом:
Сначала за максимальное принимается первое число;
После оно сравнивается со всеми оставшимися числами, при этом:
Если следующий элемент больше принятого за максимум (переменная Max), то оно принимается за максимум.
После сравнения всех элементов в конце концов остается одно число, которое больше всех в массиве.
Надеюсь, это не сложно. Если вы не поняли работы этого алгоритма, то задумайтесь получше, перепишите программу и поэкспериментируйте. В дальнейшем таких алгоритмов будет множество. В большинстве своем они простые, но есть и довольно (и даже очень!) сложные. Без понимания таких простеньких на первых порах алгоритмов невозможно усвоить серьезные.
3. Паскаль. Двухмерные массивы.
Сегодня я продолжаю тему массивов. Останавливаться пока, я считаю рано - во-первых, массивы как таковые очень часто используются в программировании, во-вторых, мы еще не прошли все возможности, связанные с массивами.
Одна из такие возможностей - пожалуй, самая главная, это создание многомерных массивов. Многомерность означает, что массив содержит не только элементы, упорядоченные один за другим в строку:
1
2
3
4
5
, но и дополнительные элементы - например, помимо строк массив имеет и столбцы:
1 2 3 4 5
2
4
6
8
10
3
6
9
12
15
4
8
12
16
18
5
10
15
20
25
Чаще всего среди многомерных массивов используются двухмерные массивы, пример которого вы и можете видеть выше. Двухмерный - значит измеряющийся двумя индексами. Здесь первым индеском служит строка, сторым - столбец.
Как описываются такие массивы и где применяются я покажу немножко ниже, а пока давайте разберем, как поисходит эта самая индексация по номерам строк и символов в них (столбцов).
К примеру, имеем вышеописанный массив - таблица Пифагора то 1го до 5ти. Как мы можем обратиться к элементу, который находится в строке 5, столбце 3 (число 15)? Вот и всплывает упомянутое выше измерение двумя индеками. Мы так и поступим: в качестве первого индекса укажем номер строки, в качестве второго - столбец. Смотрите, что получиться:
Mas[5,3];
Думаю, вы поняли как происходит обращение к элементам такого массива. Более конкретные примеры использования см. ниже. А теперь давайте разберемся, как же такие массивы создаются в программе.
Создание 2х мерных массивов
Создать такой массив не сложнее, чем одномерный. Вот пример:
var
Mas: Array[1..5, 1..5] of Integer;
Здесь создается двухмерный массив, размером в 5 строк и 5 столбцов. Сначала указывается количество строк, после - через запятую - количество столбцов. Вот еще один пример создания массива:
var
Mas: Array[1..50, 1..25] of Integer;
А теперь давайте посмотрим, как же эти массивы можно использовать. Для начала напишем маленькую программу, которая будет создавать массив и записывать в него таблицу умножения, после чего распечатывать ее на экран. Вот сама программа:
Program N1;uses Crt;var Mas: Array[1..10, 1..10] of Integer; I, J: Byte;Begin ClrScr; For I := 1 to 10 do For J := 1 to 10 do Mas[I, J] := I * J; For I := 1 to 10 do Begin For J := 1 to 10 do If Mas[I, J] < 10 then Write(Mas[I, J], ' ') else Write(Mas[I, J], ' '); Writeln; end; Readln;end.
Запустите эту программу. Видите, массив распечатыват таблицу умножения, причем наглядно видна сама структура массива. Сразу бросается в глаза, что это 2х мерный массив, не так ли?
При выполнении этой программы я использую очень простой алгоритм для заполнения массива таблицей умножения. Вы должны помнить его по прошлым выпускам, когда мы просто ее печатали.
Также заметьте, я использую изученый модуль CRT - и его процедуру ClrScr. Учитесь использовать модули, это очень важно.
Двигаемся дальше. Я считаю, что это тема не должна вызывать затруднений, так как с массивами вы уже знакомы, а 2х мерные - это всего лишь интерпритация.
Итак, давайте теперь напишем программу, которая будет интенсивно использовать массивы. На этот раз это будет пример реализации "бегущих огней", которая пока использует одномерный массив, но тем не менее показывает новый алгоритм по его обработке. а именно сдвиг элементов по массиву.
Бегущие огни:
uses crt; const n=80; Var A:array[1..n] of byte; i,r:byte; c:char;Begin clrscr; write(' Esc -> Exit'); for i:=1 to n do a[i]:=random(2); repeat for i:=1 to n do begin gotoxy(i,4); if a[i]=0 then write('*') else write('-'); gotoxy(81-i,8); if a[i]=0 then write('*') else write('-'); end; r:=a[1]; for i:=1 to n-1 do a[i]:=a[i+1]; a[n]:=r; c:=readkey; until c=#27;end.
Запустите эту программу. Теперь нажмите любую клавишу. Видите, происходит сдвиг огней? Разноцветные огни реализованы двумя символами " * " и " - ".
Как же Огонек бежит по кругу? Если цепочку лампочек представить массивом чисел (1010010) то 1 шаг огней, есть сдвиг элементов массива на 1 (0100101) то есть:
a[1]:=a[2];
a[2]:=a[3]; и т.д.
a[n]:= {то что было в a[1], надо запомнить! }
Итак сдвиг всех элементов массива на 1 шаг влево это:
R:=a[1];
for i:=1 to N -1 do a[i]:=a[i+1];
a[n]:=R;