1. Типы данных

Стандартными простыми типами данных языка ПАСКАЛЬ являются:

• INTEGER - целый тип;

• REAL – вещественный;

• BOOLEAN – логический;

• CHAR – символьный.

Типы INTEGER и REAL имеют несколько разновидностей, например, WORD (слово) или DOUBLE (двойная точность).

Стандартными операциями для типа INTEGER являются ‘+’, ‘-‘, ‘*’, DIV (деление нацело), MOD (деление по модулю); получаемые значения точные.

Стандартными операциями для типа REAL являются ‘+’, ‘-‘, ‘*’, ‘/’; получаемые значения приближенные.

Для типа Boolean определены логические операции OR, AND, NOT, XOR; возможные значения TRUE (истина) и FALSE (ложь). Данный тип имеют выражения с операциями сравнений, например, X=Y или (A<5) OR (A>7).

Для типа CHAR определены операции сравнений. Например, логическое выражение (X>=’A’) AND (X<=’z’), где переменная X имеет тип CHAR, истинно в том случае, когда значением переменной X является латинская буква.

Широко применяются функции преобразования типов INTEGER и CHAR друг в друга. Функция Ord(С) дает порядковый номер или код символа С (целое число в диапазоне от 0 до 255), а функция Chr(I) возвращает символ, имеющий код I.

Примеры:

• Ord (Chr (I)) имеет значение I;

• Chr (Ord(C)) имеет значение С;

• Chr (7+Ord (‘0’)) равно ‘7’.

Последний пример объясняется тем, что цифры имеют последовательные коды.

Перечислимый тип данных описывается в виде T=(C1, C2,…,Cn), где C1, C2,…,Cn дают список возможных значений. Например, возможно описание

Type Season=(Winter, Spring, Summer, Autumn);

Применение перечислимого типа сдерживается отсутствием средств ввода-вывода переменных этого типа.

Ограниченный (интервальный) тип задает диапазон возможных значений в виде T=MIN..MAX. Например, переменные типа Letter=’A’..’z’ могут принимать значения прописных и строчных букв латинского алфавита.

Фундаментальными структурами данных являются:

• ARRAY - массив;
• STRING – строка;
• RECORD – запись;
• SET – множество;
• FILE – файл;
• ^ - указатель.

Массив представляет собой множество однотипных компонент. Одномерный массив X можно описать в виде

Type A = array [MIN..MAX] of T;

Var X: A;

Здесь MIN и MAX – константы, определяющие наименьшее и наибольшее значения индекса. Отдельный элемент массива обозначается X[I], где I - индекс элемента, задающий его порядковый номер.

Двумерный массив описывается подобным образом, но имеет два индекса. В различных языках допускаются различные операции над массивами. В Паскале допустима операция присваивания X:=Y, где X и Y – одинаково описанные массивы. В языке Си подобная операция недопустима.

Строку можно считать частным случаем массива. Элементы этого массива – отдельные буквы, в нулевом элементе содержится фактическая длина строки. Строки могут сравниваться между собой. Например, строка ‘Абрамов’ меньше, чем строка ’Абросимов’.

Запись представляет собой объединение разных типов элементов, рассматриваемых как одно целое. Например, анкетные данные студента могут быть описаны следующим типом записи

Anketa=record

Name: string;

Age: integer;

Adres: string

end;

Множественный тип описывается как T = set of T1, где T1 является базовым типом в виде диапазона либо перечисления значений. Элементы множества не повторяются и не упорядочены. Например, переменные типа T=set of ‘0’..’9’ могут принимать значения любого набора цифровых символов. Если переменная X имеет тип T, то возможен оператор присваивания X:=[‘2’, ’4’, ’9’].

Отметим, что имеется 2¹⁰ возможных значений переменной X. Действительно, элемент ‘0’ может как входить, так и не входить во множество. Элемент ‘1’ также может входить или не входить, то есть имеются 4 варианта присутствия элементов ‘0’ и ‘1’. При добавлении элемента ‘2’ окажется 8 вариантов присутствия этих трех элементов и т. д. Строгое доказательство можно было бы провести по индукции.

Операциями над множествами являются ‘*’- пересечение, ‘+’ - объединение, ‘-‘ - разность, IN – принадлежность одного элемента, ’<=’ и ‘>=’ – вложение одного множества в другое.

Множества представляются в памяти строками битов, каждая из которых имеет длину, равную количеству элементов базового типа. Если некоторый элемент базового типа присутствует, соответствующий бит устанавливается в 1. Так в результате приведенного выше оператора присваивания переменной X будет соответствовать строка ’0010100001’. Подобное представление экономит оперативную память и обеспечивает эффективность множественных операций, так как все указанные операции выполняются в виде логических операций над строками битов. Например, объединение множеств реализуется операцией OR над соответствующими строками битов.

Рассмотрим в качестве примера использования множеств следующую задачу. С клавиатуры компьютера поступает строка символов. Требуется выделить первое целое положительное число, заключенное между нецифровыми символами.

Program Test;

Uses Crt;

Var

Ch: char; { текущий символ }

Sum: integer; { результат }

R: set of ‘0’..’9’;

Begin

ClrScr; { очистка экрана}

R:=[‘0’..’9’]; { инициализация }

Sum:=0;

While not (Ch in R) do { сканирование нецифровых символов}

begin

Write(ch);

Ch:=ReadKey { новый символ }

end;

While Ch in R do { сканирование цифровых символов}

begin

Sum:=10*Sum+Ord(Ch) – Ord(‘0’); {формирование числа}

Write(Ch);

Ch:=ReadKey { новый символ }

end;

WriteLn(‘Sum=’, Sum);

ReadLn { пауза до нажатия Enter}

End.

Распространенной ошибкой является пропуск инициализации переменной множественного типа.

Файл рассматривается как неограниченная совокупность элементов одного типа. Отличие от массива состоит в неограниченности. Фактический размер файла может изменяться в процессе работы программы. Если массивы находятся в оперативной памяти, то файлы размещаются на внешних носителях. Обычно прежде всего рассматриваются последовательные файлы. Увеличение длины таких файлов происходит с конца.

В ПАСКАЛе имеется понятие типизированного файла, тип которого описывается как T=file of T1. Сам файл задается файловой переменной типа T. В каждый момент доступна лишь одна компонента или запись файла, что определяется механизмом доступа.

Основными операциями над файлами являются:

• Rewrite – построение пустого файла;

• Write – запись очередной компоненты;

• Reset – открытие файла на чтение;

• Read – чтение в память очередной записи и продвижение к следующей;

• Seek – установка файла на заданный номер записи;

• Close – закрытие файла.

Для записи в конец файла необходимо, чтобы была установлена ситуация Eof (логическая функция Eof возвращала TRUE). Чтение файла возможно при отсутствии ситуации Eof.

Операция Seek совместно с последующей операцией Read или Write позволяет получить прямой доступ к любой записи файла.

Особым видом файлов являются текстовые файлы, описываемые типом Text и состоящие из строк длиной от 0 до 255 символов. Операции Read и Write позволяют читать и писать отдельные символы, операции ReadLn и WriteLn предназначены для работы с целыми строками.

При размещении на диске каждая строка текстового файла отделяется парой символов с шестнадцатиричнами кодами 0D и 0A - конец строки и возврат каретки. Этим достигается экономия дисковой памяти. Вместе с тем для текстовых файлов недоступна операция Seek.

Для иллюстрации работы с текстовыми файлами рассмотрим следующую задачу. Требуется подсчитать число слов в заданном текстовом файле. Слова отделяются пробелами. Возможны переносы слов со строки на строку. Имя файла необходимо задать в командной строке.

Program Word;

Var

F: text; { исходный файл }

S, Name: string;

M, N, I, Kol: integer;

B: boolean;

Procedure Soob(Mess: string);

Begin

WriteLn(Mess);

ReadLn; { пауза }

Halt { конец программы }

End;

Begin { основная программа }

if ParamCount<1 then Soob('Не указан исходный файл')

{ в командной строке нет параметров }

else Assign(F, ParamStr(1));

Name:=ParamStr(1);

{$I-} { отключение прерывания при ошибке ввода }

Reset(F);

{$I+} { восстановление системной реакции на ошибку }

if IoResult<>0 then Soob('Ошибка открытия файла '+Name);

Kol:=0;

While not Eof(F) do

begin

ReadLn(F, S);

M:=Length(S); { длина очередной строки }

N:=1; B:=True;

While B do

Begin

While (S[N]=' ') and (N<=M) do N:=N+1;

{ пропуск пробелов }

While (S[N]<>' ') and (N<=M) do N:=N+1;

{ очередное слово }

if (S[N-1]<>'-') and (S[N-1]<>' ') and (M>0)

{ не пустая строка, нет переноса и пробелов в конце }

then Kol:=Kol+1;

if N>M then B:=False { признак выхода из цикла }

end

end;

WriteLn('Количество слов ', Kol);

ReadLn { заключительная пауза }

End.

Указатель представляет собой ссылку на однотипные данные. Фактически это адрес, где располагаются данные.

Обычные переменные, массивы, записи, рассмотренные выше, являются статическими типами данных. Они имеют один размер и формат во время выполнения блока, где используются. Память для них выделяется на этапе компиляции программы. Статические данные имеют недостатки, проявляющиеся в сложных программах. Во-первых, выделенную под статические переменные память невозможно освободить до выхода из блока. Во-вторых, статические данные не обладают достаточной гибкостью при необходимости изменения их структуры в процессе выполнения программы.

Указатели служат для организации динамических структур данных, не имеющих отмеченных недостатков. Компилятор выделяет память только под указатель на соответствующий тип данных. В процессе выполнения программы происходит инициализация указателя, то есть в свободной области оперативной памяти, называемой кучей (heap), выделяется необходимая область, и указатель связывается с этой областью. После использования память может быть возвращена в кучу, то есть распределением динамической памяти занимается сам программист. Наряду с удобством это налагает дополнительную ответственность и является источником многих ошибок.

Тип указателя в ПАСКАЛе описывается в виде T=^T1, где T1 задает тип данных, с которыми связан указатель. Выделение памяти под переменные типа T выполняется функцией New, а освобождение памяти – функцией Dispose. При обращении к памяти, связанной с указателем, знак ‘^’ ставится после идентификатора переменной. Указатели одного типа могут присваиваться друг другу, проверяться на равенство или неравенство. Имеется специальное значение Nil для пометки пустого указателя. Арифметические действия с указателями в ПАСКАЛе запрещены, но являются типичными в Си.

Рассмотрим простой пример. Пусть требуется ввести значения массива из 10 целых чисел и вывести их на экран в обратном порядке с использованием динамической памяти.

Program Ptr;

Type

m=array[1..10] of integer;

u=^m;

Var

I: integer;

D: u;

Begin

New(D); { инициализация указателя}

For I:=1 to 10 do

begin

Write('Введите очередное целое число ');

ReadLn(D^[I])

end;

For I:=10 downto 1 do WriteLn(D^[I]);

Dispose(D); { освобождение памяти }

ReadLn

End.

Невнимательная работа может привести к ошибкам, связанным с потерянными указателями. Пусть, например, выполняется оператор P1:=P2, где P1 и P2 – указатели одного типа. В результате оба указателя будут связаны с одной и той же областью памяти. Если значение P1 не сохранено, то область памяти, которая была связана с указателем P1, освободить невозможно. При выполнении приведенного оператора в цикле это может привести к нехватке динамической памяти и аварийному завершению программы. Если же после оператора присваивания выполняется оператор Dispose(P2), а через некоторое время происходит обращение к P1^, то вероятна ошибка, так как в промежутке между последними операторами память, которая была связана с P1, может быть распределена для некоторого другого указателя.

2. Линейные списки

2.1. Стеки

Линейным списком называется упорядоченная структура, каждый элемент которой связан со следующим элементом. Наибольшее распространение получили два вида линейных списков: стеки и очереди.

Стек это список типа LIFO (последним пришел – первым вышел). Стек имеет одну точку доступа, которая называется вершиной.

Аналогом стека является стопка книг, в которой дополнение и изъятие книг происходит сверху. Другим примером может служить обойма с патронами (магазин), в которой зарядка и подача для стрельбы выполняется с одного конца. Именно этим примером объясняется бывшее в употреблении русскоязычное название стека "магазин”.

Широкое применение нашли стеки в программировании. Иногда они реализуются аппаратным образом. Через стеки передаются параметры при обращении к процедурам. Если имеется цепочка вызова вложенных процедур, то локальные переменные могут сохраняться в стеке, который расширяется при загрузке процедуры и сокращается при возврате из нее. В Ассемблере имеется регистр стека и соответствующие команды для работы с ним.

Стеки могут представляться как в статической, так и динамической памяти. В статическом представлении стек задается одномерным массивом, величина которого определяется с запасом. Пусть он описан в виде Var Stack[1..N] of T, где T – тип элементов стека. Вершина стека задается индексом массива Top.

Дополнение в стек производится командами

Top:= Top+1;

Stack[Top]:=NewElement;

Удаление из стека выполняется командой Top:= Top-1.

Для обработки возможных ошибок при дополнении необходимо проверять выход за границы массива, а при удалении проверять непустоту стека.

Рассмотрим подробнее организацию стека в динамической памяти. Ниже приведен текст программы, позволяющей выполнять операции дополнения, удаления и выдачи на экран элементов стека.