Массив – это упорядоченная последовательность элементов одного типа данных. Существуют одномерные и двумерные массивы.
В информатике массив называется одномерным, если для получения доступа к его элементам достаточно одной индексной переменной, например, a=(a[1], a[2], ... , a[n]) – одномерный массив a, состоящий из n элементов, a[i] – элемент, стоящий на i-м месте, i=1,...,n. Массив называется двумерным, если для доступа к любому его элементу достаточно двух индексов – номера строки и номера столбца, на пересечении которых он находится.
Описание типа массива задается следующим образом:
<имя типа> = ARRAY [ <сп.инд.типов> ] OF <тип>;
где <имя типа> – правильный идентификатор; ARRAY, OF – зарезервированные слова (массив, из); <сп.инд.типов> – список из одного или нескольких индексных типов, разделенных запятыми; квадратные скобки, обрамляющие список, - требование синтаксиса; <тип> – любой тип Турбо Паскаля.
В качестве индексных типов в Турбо Паскале можно использовать любые порядковые типы, кроме LONGINT и типов-диапазонов с базовым типом LONGINT. Определить переменную как массив можно и непосредственно при описании этой переменной, без предварительного описания типа массива, например:
var
а,b : array [1..10] of Real; {описание одномерных массивов}
Обычно в качестве индексного типа используется тип-диапазон, в котором задаются границы изменения индексов. Так как тип <тип>, идущий за словом OF, - любой тип Турбо Паскаля, то он может быть, в частности, и другим массивом, например:
type
mat = array [0..5] of array [-2..2] of array [Char] of Byte;
Такую запись можно заменить более компактной:
type
mat = array [0..5,-2..2,Char] of Byte;
Глубина вложенности структурированных типов и массивов - произвольная, поэтому количество элементов в списке индексных типов (размерность массива) не ограничено, однако суммарная длина внутреннего представления любого массива не может быть больше 65520 байт. В памяти ПК элементы массива следуют друг за другом так, что при переходе от младших адресов к старшим наиболее быстро меняется самый правый индекс массива. Если, например,
var
а : array[1. .2,1. .2] of Byte;
begin
a [1,1]:=1;
a [2,1]:=2;
a [l, 2]:=3;
a [2,2]:=4;
end.
то в памяти последовательно друг за другом будут расположены байты со значениями 1,3,2,4 . В Турбо Паскале можно одним оператором присваивания передать все элементы одного массива другому массиву того же типа, например:
var
а,b:array [1..5] of Single;
begin
a := b;
end.
После этого присваивания все пять элементов массива А получат те же значения, что и в массиве В. Однако над массивами не определены операции отношения. Нельзя, например, записать
if a = b then ...
4.2.2. Записи
Запись – это структура данных, состоящая из фиксированного числа компонентов, называемых полями записи. В отличие от массива, компоненты (поля) записи могут быть различного типа. Чтобы можно было ссылаться на тот или иной компонент записи, поля именуются.
Структура объявления типа записи такова:
<имя типа> = RECORD <сп.полей> END;
здесь <имя типа> - правильный идентификатор; RECORD, END - зарезервированные слова (запись,конец); <сп.полей> - список полей; представляет собой последовательность разделов записи, между которыми ставится точка с запятой.
Каждый раздел записи состоит из одного или нескольких идентификаторов полей, отделяемых друг от друга запятыми. За идентификатором (идентификаторами) ставится двоеточие и описание типа поля (полей), например:
type
BirthDay = record
day,month : Byte;
year : Word
end;
var
a,b : Birthday;
В этом примере тип BIRTHDAY (день рождения) есть запись с полями DAY, MONTH и YEAR (день, месяц и год); переменные А и В содержат записи типа BIRTHDAY.
Как и в массиве, значения переменных типа записи можно присваивать другим переменным того же типа, например
а := b;
К каждому из компонентов записи можно получить доступ, если использовать составное имя, т.е. указать имя переменной, затем точку и имя поля:
а.day := 27;
b.year := 1939;
Для вложенных полей приходится продолжать уточнения:
type
BirthDay = record
day,month: Byte;
year : Word
end;
var
с: record
name : String;
bd : BirthDay
end;
begin
if c.bd.year = 1939 then ...
end.
Чтобы упростить доступ к полям записи, используется оператор присоединения WITH:
WITH <переменная> DO <оператор>
здесь WITH, DO – ключевые слова (с, делать); <переменная> – имя переменной типа запись, за которым, возможно, следует список вложенных полей; <оператор> – любой оператор Турбо Паскаля.
Например:
with c.bd do month := 9;
Это эквивалентно
with с do with bd do month := 9;
или
with c,bd do month := 9;
или
c.bd.month := 9;
Турбо Паскаль разрешает использовать записи с так называемыми вариантными полями, например:
type
Forma = record
Name: String;
case Byte of
0: (Birthplace: String [40]);
1: (Country : String [20];
EntryPort : String [20];
EntryDate : 1. . 31;
ExitDate : 1..31)
end;
В этом примере тип FORMA определяет запись с одним фиксированным полем NAME и вариантной частью, которая задается предложением CASE... OF. Вариантная часть состоит из нескольких вариантов (в примере – из двух вариантов: 0 и 1). Каждый вариант определяется константой выбора, за которой следует двоеточие и список полей, заключенный в круглые скобки. В любой записи может быть только одна вариантная часть, и, если она есть, она должна располагаться за всеми фиксированными полями.
Особенностью вариантной части является то обстоятельство, что все заданные в ней варианты «накладываются» друг на друга, т.е. каждому из них выделяется одна и та же область памяти. Это открывает дополнительные возможности преобразования типов, например:
var
mem4: record case Byte of
0: (by : array'[0..3] of Byte);
1: (wo : array [0..1] of Word);
2: (lo : longint);
end;
В этом примере запись МЕМ4 имеет три варианта, каждый из которых занимает в памяти один и тот же участок из 4 байт. В зависимости от того, к какому полю записи мы обращаемся в программе, этот участок может рассматриваться как массив из 4 байт (поле ВТ), массив из двух целых типа WORD (поле WO) или, наконец, как одно целое число типа LONGINT (поле LO). Например, этой записи можно сначала присвоить значение как длинному целому, а затем проанализировать результат по байтам или словам:
var
х : Word;
xb: Byte;
x1: Longint;
begin
.....
with m do
begin
lo := trunc(2*pi*x);
if wo[1] = 0
then if by[l] = 0 then
xb := x[0]
else
x := wo[0]
else
x1 := lo
end;
.....
end.
Предложение CASE... OF, открывающее вариантную часть, внешне похоже на соответствующий оператор выбора, но на самом деле лишь играет роль своеобразного служебного слова, обозначающего начало вариантной части. Именно поэтому в конце вариантной части не следует ставить END как пару к CASE... OF. (Поскольку вариантная часть – всегда последняя в записи, за ней все же стоит END, но лишь как пара к RECORD). Ключ выбора в предложении CASE... OF фактически игнорируется компилятором: единственное требование, предъявляемое к нему Турбо Паскалем, состоит в том, чтобы ключ определял некоторый стандартный или предварительно объявленный порядковый тип. Причем сам этот тип никак не влияет ни на количество следующих ниже вариантных полей, ни даже на характер констант выбора. В стандартном Паскале в качестве ключа выбора необходимо указывать некоторую переменную порядкового типа, причем в исполняемой части программы можно присваивать значение этой переменной и таким образом влиять на выбор полей. В Турбо Паскале также можно в поле ключа выбора указывать переменную порядкового типа и даже присваивать ей в программе значение, что однако не влияет на выбор поля: значения констант выбора в Турбо Паскале могут быть произвольными, в том числе повторяющимися, например:
type
reel = record
a : Byte;
b : Word;
end;
rec2 = record
с: longint;
case x : Byte of
1: (d : Word);
2: (e : record
case Boolean of
3:( freel);
3:( g Single);
'3':( с Word);
end)
end;
var
r : rec2;
begin
r.x := 255;
if r.e.g = 0 then
WriteLn('O.K. ')
else
WriteLn(r.e.g)
end.
В этом примере предложение
case Boolean of
в записи, определяемой в поле Е, объявляет ключом выбора логический тип, который, как известно, имеет лишь два значения –TRUE и FALSE. Константы же выбора следующих далее вариантов не только содержат совершенно не свойственные этому типу значения, но и две из них повторяются, а общее количество вариантов – три, а не два, как следовало бы ожидать.
Имена полей должны быть уникальными в пределах той записи, где они объявлены, однако, если записи содержат поля-записи, т.е. вложены одна в другую, имена могут повторяться на разных уровнях вложенности.
4.2.3. Множества
Множества – это наборы однотипных логически связанных друг с другом объектов. Характер связей между объектами лишь подразумевается программистом и никак не контролируется Турбо Паскалем. Количество элементов, входящих в множество, может меняться в пределах от 0 до 256 (множество, не содержащее элементов, называется пустым). Именно непостоянством количества своих элементов множества отличаются от массивов и записей.
Два множества считаются эквивалентными тогда и только тогда, когда все их элементы одинаковы, причем порядок следования элементов в множестве безразличен. Если все элементы одного множества входят также и в другое, говорят о включении первого множества во второе. Пустое множество включается в любое другое.
Пример определения и задания множеств:
type
digitChar= set of '0'..'9';
digit = set of 0. .9;
var
sl,s2,s3 :digitChar;
s4,s5,s6 :digit;
begin
.....
s1:=['1','2','3'];
s2:=['3','2','1'];
s3:=['2','3'];
s4:=[0..3,6];
s5:=[4,5];
s6:=[3..9];
.....
end.
В этом примере множества S1 и S2 эквивалентны, а множество S3 включено в S2 , но не эквивалентно ему.
Описание типа множества имеет вид:
<имя типа> = SET OF <баз.тип> ;
здесь <имя типа> - правильный идентификатор; SET, OF - зарезервированные слова (множество, из); <баз.тип> – базовый тип элементов множества, в качестве которого может использоваться любой порядковый тип, кроме WORD, INTEGER, LONGINT.
Для задания множества используется так называемый конструктор множества: список спецификаций элементов множества, отделяемых друг от друга запятыми; список обрамляется квадратными скобками. Спецификациями элементов могут быть константы или выражения базового типа, а также тип-диапазон того же базового типа.
Над множествами определены следующие операции:
* пересечение множеств; результат содержит элементы, общие для обоих множеств; например, S4*S6 содержит [3], S4*S5 – пустое множество;
+ объединение множеств; результат содержит элементы первого множества, дополненные недостающими элементами из второго множества:
S4+S5 содержит [0,1,2,3,4,5,6];
S5+S6 содержит [3,4,5,6,7,8,9];
– разность множеств; результат содержит элементы из первого множества, которые не принадлежат второму:
S6 – S5 содержит [3,6,7,8,9];
S4 – S5 содержит [0,1,2,3,6];
= проверка эквивалентности; возвращает TRUE, если оба множества эквивалентны;
<> проверка неэквивалентности; возвращает TRUE, если оба множества неэквивалентны;
<= проверка вхождения; возвращает TRUE, если первое множество включено во второе;
>= проверка вхождения; возвращает TRUE, если второе множество включено в первое;
IN проверка принадлежности; в этой бинарной операции первый элемент – выражение, а второй – множество одного и того же типа; возвращает TRUE , если выражение имеет значение, принадлежащее множеству:
3 in s6 возвращает TRUE;
2*2 in s1 возвращает FALSE.
Дополнительно к этим операциям можно использовать две процедуры. INCLUDE – включает новый элемент во множество. Обращение к процедуре:
INCLUDE (S,I);
здесь S – множество, состоящее из элементов базового типа TSetBase; I – элемент типа TSetBase, который необходимо включить во множество.
EXCLUDE – исключает элемент из множества. Обращение:
EXCLUDE(S,I);
Параметры обращения – такие же, как у процедуры INCLUDE.
В отличие от операций + и – реализующих аналогичные действия над двумя множествами, процедуры оптимизированы для работы с одиночными элементами множеcтва и поэтому отличаются высокой скоростью выполнения.
В приведенном ниже примере, иллюстрирующем приемы работы с множествами, реализуется алгоритм выделения из первой сотни натуральных чисел всех простых чисел. В его основе лежит прием, известный под названием «решето Эратосфена». В соответствии с этим алгоритмом вначале формируется множество BEGINSET, состоящее из всех целых чисел в диапазоне от 2 до N. В множество PRIMERSET (оно будет содержать искомые простые числа) помещается 1. Затем циклически повторяются следующие действия:
· взять из BEGINSET первое входящее в него число NEXT и поместить его в PRIMERSET;
· удалить из BEGINSET число NEXT и все другие числа, кратные ему, т.е. 2*NEXT, 3*NEXT и т.д.
Цикл повторяется до тех пор, пока множество BEGINSET не станет пустым.
Эту программу нельзя использовать для произвольного N, так как в любом множестве не может быть больше 256 элементов:
Program Primer_numbers_detect;
{Выделение всех простых чисел из первых N целых}
const
N = 255; {Количество элементов исходного множества}
