Структура данных – это совокупность элементов данных, между которыми существуют некоторые отношения, причем элементами данных могут быть простые данные и структуры данных.
Обобщенная структура в определенном выше смысле без учета ее представления в памяти ЭВМ называется абстрактной или логической.
Любой из структурированных типов (массивы, записи, множества и файлы) характеризуется множественностью образующих этот тип элементов. Каждый элемент, в свою очередь, может принадлежать структурированному типу, что позволяет говорить о возможной вложенности типов. В Pascal допускается произвольная глубина вложенности типов, однако суммарная длина любого из них во внутреннем представлении не должна превышать 65520 байт.
Массив – это структура упорядоченных по номерам данных одного типа (простого или структурированного), фиксированная по размеру.
К отдельному элементу массива можно обращаться с помощью индексов, количество которых должно соответствовать размерности массива.
Описание типа массива задается следующим образом:
<имя типа>= array [ <сп. инд. типов> ]of <тип>;
Здесь <имя типа> – правильный идентификатор; array, of - зарезервированные слова (массив, из); <сп. инд. типов> - список из одного или нескольких индексных типов, разделенных запятыми; квадратные скобки, обрамляющие список, – требование синтаксиса; <тип> - любой тип Pascal.
В качестве индексных типов в Pascal можно использовать любые порядковые типы. Обычно в качестве индексного типа используется тип-диапазон, в котором задаются границы изменения индексов. Например,
digit= array [0..9] of Char;
vector =array [byte] of Single;
Определить переменную как массив можно и непосредственно при описании этой переменной, без предварительного описания типа массива, например:
vara,b: array [1..10] of Real;
Структура, примеры описаний и ввода значений элементов одномерного и двумерного массивов приведены в следующей таблице.
Одномерный массив.
Двумерный массив.
i-й элемент
Массив a (пустой):
…
i
…
n
a[1]
a[2]
a[3]
a[4]
a[i]
a[n]
3-й элемент
…
m
…
n
Описание:
1)
var
A: array [1..100] of real;
2)
Const
n=100;
var
A: array [1..n] of real;
3)
Const
n=100;
type
T_vector = array [1..n] of real;
var
A: T_vector;
Описание:
1)
var
A: array [1..100, 1..100] of real;
2)
Const
n=100; m=90;
var
A: array [1..n, 1..m] of real;
3)
Const
n=100; m=80;
type
T_Mat = array [1..n, 1..m] of real;
var
A: T_Mat;
Ввод одномерного массива.
for i:=1 to n do
begin
write (‘A[‘,i,’]=’);
readln (A[i]);
end;
Ввод двумерного массива.
for i:=1 to n do
for j:=1 to m do
begin
write (‘A[‘,i,’,’,j,’]=’);
readln (A[i,j]);
end;
В Pascal можно одним оператором присваивания передать все элементы одного массива другому массиву того же типа, например:
a,b: array [1..5] of Single;
а := b;
Над массивами не определены операции отношения. Нельзя, например, записать
if а = b then ...
Сравнить два массива можно только поэлементно, например:
a, b: array [1..5] of Single;
i : Byte;
...
for i:= 1to5do
if a[i]<> b[i]then ...
Пример. Заполнить одномерный массив по правилу: a[i]=2*i, 1<= i <=7.
program primer4;
var i,n:integer;
a: array[1..100] of integer; {описание переменной типа массив}
begin
writeln(‘Количество элементов массива=’); readln(n);
for i:=1 to n do a[i]:=2*i; {заполнение массива по правилу}
for i:=1 to n do writeln(i,‘ элемент массива = ’,a[i]); {вывод массива на экран}
end.
Пример. Вычислить суммы элементов строк матрицы n x m (n строк, m столбцов; n<=10, m<=10).
Program massiv2;
var a:array[1..10,1..10] of integer;
{описание исходной матрицы – двумерного массива}
s:array[1..10] of integer;
{описание одномерного массива для результата (сумм элементов строк матрицы)}
n,m,i,j:integer;
begin
writeln(‘Введите количество строк и столбцов’);
readln(n,m);
{Заполнение и вывод массива случайных целых чисел}
randomize;
for i:=1 to n do
begin
for j:=1 to m do //i – номер строки, j – номер столбца
begin
a[i,j]:=25-random(50);
write(a[i,j]:6);
end;
writeln;
end;
{Вычисление и вывод сумм элементов строк матрицы}
for i:=1 to n do
begin
s[i]:=0;
for j:=1 to m do s[i]:=s[i]+a[i,j];
writeln(‘Сумма ’,i,’-ой строки = ’,s[i]);
end;
readln;
end.
Запись - это структура данных, состоящая из фиксированного количества компонентов, называемых полями записи. В отличие от массива компоненты (поля) записи могут быть различного типа. Чтобы можно было ссылаться на тот или иной компонент записи, поля именуются.
Структура объявления типа записи такова:
<имя типа>= record <сп. полей>end;
Здесь <имя типа> – правильный идентификатор; record, end – зарезервированные слова (запись, конец); <сп. полей> – список полей; представляет собой последовательность разделов записи, между которыми ставится точка с запятой.
Каждый раздел записи состоит из одного или нескольких идентификаторов полей, отделяемых друг от друга запятыми. За идентификатором (идентификаторами) ставится двоеточие и описание типа поля (полей), например:
BirthDay =record
Day, Month: Byte;
Year : Word
vara, b : BirthDay;
…
В этом примере тип BirthDay (день рождения) есть запись с полями Day, Month и Year (день, месяц и год); переменные a и b содержат записи типа BirthDay.
Как и в массиве, значения переменных типа записи можно присваивать другим переменным того же типа, например
а := b;
К каждому из компонентов (полей) записи можно получить доступ, если использовать составное имя, т. е. указать имя переменной, затем точку и имя поля:
a.day := 27;
b.year := 1939;
Для вложенных полей приходится продолжать уточнения:
BirthDay =record
Day, Month: Byte;
Year: Word
с:record
Name: String;
Bd : BirthDay
if c.Bd.Year = 1989then ...
Чтобы упростить доступ к полям записи, используется оператор присоединения with:
with <переменная> do <оператор>;
Здесь with, do – зарезервированные слова (с, делать); <переменная> – имя переменной типа запись, за которой, возможно, следует список вложенных полей; <оператор> – любой оператор Pascal.
Например:
with с.Bd do Month := 9;
или
withсdo
with Bddo Month := 9;
Это эквивалентно
с.Bd.Month := 9;
Пример. Для каждого из учеников класса известны фамилия и оценки в баллах по 5 предметам. Требуется найти учеников со средним баллом большим 4 и вывести на экран.
program primer_record_file;
type pupil=record {описание типа-записи Ученик}
fam:string[15];
b1,b2,b3,b4,b5:2..5;
sb:real;
end;
const n=2; {n – количество учеников}
var class:array[1..n] of pupil; {описание массива Учеников}
i:integer;
begin
{ввод исходных данных}
for i:=1 to n do
with class[i] do begin
writeln('Введите фамилию и 5 оценок: ');
readln(fam,b1,b2,b3,b4,b5);
end;
{вычисление среднего балла ученика}
for i:=1 to n do
with class[i] do sb:=(b1+b2+b3+b4+b5)/5;
{вывод исходных данных на экран}
writeln('Список учеников');
writeln('Фамилия':20, ' Средний балл');
for i:=1 to n do
with class[i] do writeln(fam:20,sb:10:1);
{поиск учеников со средним баллом >4 и вывод на экран}
writeln('Ученики со средним баллом большим 4:');
for i:=1 to n do
with class[i] do
if sb>4 then writeln(fam:20,sb:10:1);
readln;
end.
Множества – это наборы однотипных логически связанных друг с другом объектов. Характер связей между объектами лишь подразумевается программистом и никак не контролируется Pascal. В Pascal множества могут включать элементы только порядковых типов. Элементы множества должны принадлежать одному типу, который называется базовым. Количество элементов, входящих в множество, может меняться в пределах от 0 до 256 (множество, не содержащее элементов, называется пустым). Именно непостоянством количества своих элементов множества отличаются от массивов.
Два множества считаются эквивалентными тогда и только тогда, когда все их элементы одинаковы, причем порядок следования элементов в множестве безразличен. Если все элементы одного множества входят также и в другое множество, говорят о включении первого множества во второе. Пустое множество включается в любое другое.
Описание типа множества имеет вид:
type <имя типа> =set of <базовый тип>;
Здесь <имя типа> – правильный идентификатор; set, of – зарезервированные слова (множество, из); <базовый тип> – базовый тип элементов множества, в качестве которого может использоваться любой порядковый тип, кроме Word, Integer, Longint.
Для задания множества используется так называемый конструктор множества: список элементов множества, отделенных друг от друга запятыми; список обрамляется квадратными скобками. Элементами могут быть константы или выражения базового типа, а также тип-диапазон того же базового типа.