 |
Составление программ с структурированными данными.
|
|
|
|
Л Е К Ц И Я № 7
по дисциплине «Программирование»
Тема: «Структурированные данные. Массивы»
План лекции:
Введение.
1. Массивы.
2. Составление программ с структурированными данными.
3. Задача сортировки. Методы сортировки.
Литература:
1. Беляева Т.А. и др. Алгоритмические языки программирования. Паскаль. – Севастополь: СНИЯЭиП, 2002 г.
2. Фаронов В.В. - "DELPHI. Программирование на языке высокого уровня: Учебник для вузов" – СПб.: Питер, 2006. – 640 с.
3. Марченко А.И. Программирование в среде Borland Pascal 7.0.-К.:Юниор,1997.-480 с.
Введение
В различных областях знаний часто приходится сталкиваться с ситуацией, когда необходимо обработать большое количество значений переменных одного и того же типа. В принципе мы можем обойтись понятием обычной переменной, но остается ощущение неудобства, особенно, если задача сопряжена с огромным их количеством. Для таких случаев Паскаль предоставляет введение большого числа переменных одного и того же типа, используя понятие «массив». Массив, как и любой из структурированных типов (а в Delphi их четыре: массивы, записи, множества и файлы) характеризуется множественностью образующих этот тип элементов. Каждый элемент, в свою очередь, может принадлежать структурированному типу, что позволяет говорить о возможной вложенности типов, однако суммарная длина любого из них во внутреннем представлении не должна превышать 2 Гбайт.
Описание типа Массив
Итак, массив – это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип и объединенных одним именем.
Так совокупность действительных чисел 1.6, 14.9, -5.0, 8.5, 0.46, 2.37, 0.53 можно считать массивом и обозначить именем, например А. Число элементов фиксируется. В нашем примере количество элементов 7. Доступ к каждому элементу массива осуществляется путем индексирования элементов массива. Индекс – это величина, характеризующая положение объекта в массиве. Каждый элемент массива обозначается именем и индексом.
|
|
|
Индекс заключается в квадратные скобки. В нашем примере элементами массива являются: А[1] = 1.6, A[2] = 14.9, A[3] =-5.0, A[4]=8.5, A[5]=0.46.
Если в программе используется массив, то он должен быть описан либо в разделе типов, либо в разделе переменных.
В разделе типов
TYPE <имя типа>= array [<сп. инд. типов>] of <тип>;
Здесь <имя типа> – правильный идентификатор; array,of – зарезервированные слова (массив, из); <сп. инд. типов> – список из одного или нескольких индексных типов, разделенных запятыми; квадратные скобки, обрамляющие список, – требование синтаксиса; <тип> любой тип Delphi.
TYPE M = array[1..5] of real;
VAR A: M;
В разделе переменных
VAR A: array [[<сп. инд. типов>] of <тип>;
VAR A: array [1..5] of real;
Здесь А – имя массива, элементы которого имеют базовый тип REAL. Тип индекса ограниченный от 1 до 5.
Примеры:
1. TYPE Color = (red, blue, black);
mas1 = array [-5..15] of real;
mas2 = array [1..10,1..10] of integer;
mas3 = array [‘A’..’C’] of array [1..5] of boolean;
mas4 = array [boolean] of char;
VAR A:mas3; B:mas2; C:mas4; D:mas1; E: array [color] of real;
В качестве элементов массива можно использовать данные любого, (в том числе и структурированного) типа. Вполне правомерно существование массивов записей, массивов строк, массивов множеств, массивов и т.д.
Если несколько массивов имеют одинаковый тип индексов и одинаковый базовый тип, то допускается объединить массивы в список, например:
VAR A,B,C: array [1..50] of real;
Нельзя путать понятие «индекс» и «тип индекса». Тип индекса используется только в разделе описаний массива, а индекс указывается в разделе операторов для обозначения конкретных элементов массива. Индекс должен быть того же типа, что и описание типа индекса.
|
|
|
Пример: B[5]:=B[3]+1; C[1]=3.4;
Индекс может быть выражением, частным случаем которого является константа или переменная. Элемент массива иначе называется переменной с индексом. N[I+J]; MAS[2*I].
Если в качестве базового массива взят другой массив, образуется структура, которую принято называть многомерным массивом.
Например:
TYPE Vector = array [1..4] of integer;
Massiv = array [1..4] of vector;
VAR Matr: Massiv;
Ту же структуру можно получить, используя другую форму записи.
VAR Matr: array [1..4,1..4] of integer;
Если в такой форме записи массива задан один индекс, массив называется одномерным, если два индекса – двумерным, если N индексов, N – мерным.
Одномерные массивы обычно используются для представления векторов, а двумерные – для представления матриц. Элементы массива располагаются в памяти последовательно. Элементы с меньшими адресами – в более низких адресах памяти. Многомерные располагаются таким образом, что самый правый индекс возрастает самым первым.
Например, если имеется массив A: array [1..5,1..5] of integer;, то в памяти элементы будут размещены по возрастанию адресов. A[1,1]; A[1,2]; … A[1..5]; … A[2,1]; A[2,2]; … A[5,5]; т.о. матрицы размещаются по строкам.
Задав конкретные значения индексов можно выбрать определенную компоненту массива. Например, запись N:=A[1,2] означает, что в N будет отправлено значение, стоящее в 1-й строке,
2-м столбце.
1.1 Действия над элементами массивов
Для работы с массивом как единым целым используется идентификатор массива без указания индекса в квадратных скобках, (так называемая полная переменная). Массив может участвовать только в присваивания, при этом массивы должны быть идентичны по структуре, т.е. иметь одинаковые типы индексов и одинаковые типы компонентов.
Полная переменная (массив как единое целое) ни в коем случае не может быть операндом арифметического выражения, даже если он состоит из единственной компоненты.
Например.
VAR X: real;
Y: array [1..1] of real;
………………………………..
X:=Y; Y:=X; X:=Y+0.5; Y=3.14 – недопустимо.
После объявления массива, каждый его элемент можно обработать, указав имя массива и индекс элемента в квадратных скобках. Например, запись MAS[2], VEG[10] позволяет обратиться ко второму элементу массива MAS и к десятому элементу массива VEG.
|
|
|
При работе с двумерными массивами указывается два индекса, с N-мерными, N индексов. Например, запись MATR[2,3] делает доступным для обработки значение элемента находящегося во 2-й строке 3 столбца массива MATR.
Элементы массива могут стоять, как в левой части оператора присваивания, так и в выражениях. Над элементами массива можно производить операции, которые допустимы для данных его базового типа. Примеры:
B[10]: = B[3] + 1;
Sum: = Sum – C[K];
P1: = A[2*I + 1];
Инициализация массива заключается в присваивании каждому элементу массива значения, соответствующего базовому типу. Это можно сделать, записав группу операторов присваивания. Например,
A[1]:=0; A[2]:=0; A[3]:=0; A[4]:=0;
Однако, при большом количестве элементов такой способ нерационален. Гораздо удобнее получить тот же результат, используя оператор FOR.
FOR I:=1 TO 4 DO A[I]:=0;
Для инициализации двумерного массива, обычно используют вложенный оператор FOR:
FOR I:= 1 TO 10 DO
FOR I:=1 TO 15 DO B[I,J]:=0;
Паскаль не имеет средств ввода-вывода элементов массива сразу, поэтому ввод-вывод производится поэлементно.
Значения элементам массива можно присвоить с помощью оператора присваивания, однако чаще всего они вводятся с помощью оператора READ (READLN).
FOR I:=1 TO 4 DO READLN(A[I]);
для двумерного
FOR I:=1 TO 10 DO
FOR J:=1 TO 15 DO READLN(B[I,J]);
Можно ввести и значения отдельных элементов, а не всего массива.
Например, Read(A[3]); Read(B[6,9]);
Вывод значений элементов массива выполняется аналогичным образом с помощью оператора WRITE или WRITELN
FOR I:=1 TO 4 DO WRITELN(A[I]);
Или для двумерного:
FOR I:=1 TO 10 DO
FOR J:=1 TO 15 DO WRITELN(B[I,J]);
Некоторое неудобство состоит в том, что приходится сразу же жестко фиксировать число элементов массива. В версии Delphi 4 появилась возможность избавится от этого неудобства. Именно в этой версии введены так называемые динамические массивы.
1.2 Динамические массивы
При объявлении динамических массивов в программе не следует указывать границы индексов:
Var
A: array of integer;
B: array of array of char;
C: array of array of array of real;
В этом примере динамический массив A имеет одно измерение, массив B – два и массив C – три измерения. Распределение памяти и указание границ индексов по каждому измерению динамических массивов осуществляется в ходе выполнения программы путем инициализации массива с помощью функции SetLength.
|
|
|
Например, SetLength(A,3) – в ходе выполнения этого оператора одномерный массив A будет инициализирован, то есть получит память, достаточную для размещения трех целочисленных значений.
Нижняя граница индексов по любому измерению динамического массива всегда равна 0, поэтому верхней границей индексов для A станет значение 2.
В многомерных массивах сначала устанавливается длина его первого измерения, затем второго, третьего и т.д.
Например, вот как создается динамический массив 3´3:
Var
A: array of array integer;
Begin
// устанавливаем длину первого измерения (количество столбцов):
SetLength(A,3);
// задаем длину каждого столбца:
SetLength(A[0],3);
SetLength(A[1],3);
SetLength(A[2],3);
…………..
end;
Составление программ с структурированными данными.
2.1 Составление программ с массивами
пример1{организация ввода и вывода матрицы }
program Project2;
{$APPTYPE CONSOLE}
Uses
SysUtils;
var a: array [1..4,1..3] of byte;
i,j:byte;
Begin
writeln('Enter elementi masiva');
for i:=1 to 4 do
for j:=1 to 3 do
readln(a[i,j]);
writeln; writeln;
readln;
for i:=1 to 4 do
begin
for j:=1 to 3 do
write(a[i,j]:2,' ');
writeln;
end;
readln
end.
|
|
|
