Для записи в конец файла необходимо, чтобы была установлена ситуация Eof (логическая функция Eof возвращала TRUE). Чтение файла возможно при отсутствии ситуации Eof.
Типы данных
Тип это множество значений, которые может принимать переменная, выражение или функция.
Стандартными простыми типами данных языка ПАСКАЛЬ являются:
· 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’].
Отметим, что имеется 210 возможных значений переменной X. Действительно, элемент ‘0’ может как входить, так и не входить во множество. Элемент ‘1’ также может входить или не входить, то есть имеются 4 варианта присутствия элементов ‘0’ и ‘1’. При добавлении элемента ‘2’ окажется 8 вариантов присутствия этих трех элементов и т. д. Строгое доказательство можно было бы провести по индукции.
Операциями над множествами являются ‘*’- пересечение, ‘+’ - объединение, ‘-‘ - разность, IN – принадлежность одного элемента, ’<=’ и ‘>=’ – вложение одного множества в другое.
|
|
|
В ПАСКАЛе множества представляются в памяти строками битов, каждая из которых имеет длину, равную количеству элементов базового типа. Если некоторый элемент базового типа присутствует, соответствующий бит устанавливается в 1. Так в результате приведенного выше оператора присваивания переменной X будет соответствовать строка ’0010100001’. Подобное представление экономит оперативную память и обеспечивает эффективность множественных операций, так как все указанные операции выполняются в виде логических операций над строками битов. Например, объединение множеств реализуется операцией OR над соответствующими строками битов.
В библиотеке шаблонов STL языка С++ имеются классы для работы с множествами. Обычно множества в STL реализуются с помощью сбалансированных деревьев поиска.
Рассмотрим в качестве примера использования множеств следующую задачу. С клавиатуры компьютера поступает строка символов. Требуется выделить первое целое положительное число, заключенное между нецифровыми символами.
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, может быть распределена для некоторого другого указателя.
Линейные списки
Стеки
Линейным списком называется упорядоченная структура, каждый элемент которой связан со следующим элементом. Наибольшее распространение получили два вида линейных списков: стеки и очереди.
Стек это список типа LIFO (последним пришел – первым вышел). Стек имеет одну точку доступа, которая называется вершиной.
Аналогом стека является стопка книг, в которой дополнение и изъятие книг происходит сверху. Другим примером может служить обойма с патронами (магазин), в которой зарядка и подача для стрельбы выполняется с одного конца. Именно этим примером объясняется бывшее в употреблении русскоязычное название стека “магазин”.
Широкое применение нашли стеки в программировании. Иногда они реализуются аппаратным образом. Через стеки передаются параметры при обращении к процедурам. Если имеется цепочка вызова вложенных процедур, то локальные переменные могут сохраняться в стеке, который расширяется при загрузке процедуры и сокращается при возврате из нее. В Ассемблере имеется регистр стека и соответствующие команды для работы с ним.
Стеки могут представляться как в статической, так и динамической памяти. В статическом представлении стек задается одномерным массивом, величина которого определяется с запасом. Пусть он описан в виде Var Stack[1..N] of T, где T – тип элементов стека. Вершина стека задается индексом массива Top.
Дополнение в стек производится командами
Top:= Top+1;
Stack[Top]:=NewElement;
Удаление из стека выполняется командой Top:= Top-1.
Для обработки возможных ошибок при дополнении необходимо проверять выход за границы массива, а при удалении проверять непустоту стека.
Рассмотрим подробнее организацию стека в динамической памяти. Ниже приведен текст программы, позволяющей выполнять операции дополнения, удаления и выдачи на экран элементов стека.
Program StekWork; { процедуры работы со стеком }
Uses Crt;
Type
Ukaz=^Stek;
Stek=record
Name: string;
Next: ukaz
end;
Var
Top, Kon: ukaz;
Rname: string;
C, Pr: char;
B: boolean;
N: integer;
Procedure SozdDob;
{создание стека и добавление элементов}
Var B: boolean;
Begin
B:=True;
While B do
Begin
Write('Введите очередной элемент ');
ReadLn(Rname);
if Rname='конец' then B:=False
else
begin
New(Kon);
{создание элемента, на который указывает Kon}
Kon^.Next:=Top;
Kon^.Name:=Rname;
Top:=Kon
end
end;
End;
Procedure Udal; {удаление из стека}
Begin
if Top=Nil then
WriteLn('Удаление из пустого стека !!!')
else
begin
Kon:=Top;
Top:=Top^.Next;
Dispose(Kon);
{ удаление бывшей вершины стека }
end
End;
Procedure Pech; {выдача содержимого стека на экран}
Begin
if Top=Nil then
WriteLn(' Стек пуст !!!')
else
begin
Kon:=Top;
WriteLn(' Состояние стека: ');
While Kon<>Nil do
begin
WriteLn(Kon^.Name);
Kon:=Kon^.Next
end
end
End;
{ НАЧАЛО ОСНОВНОЙ ПРОГРАММЫ }
Begin
ClrScr;
Top:=Nil;
B:=True;
While B do
begin
WriteLn(' Выберите режим работы:');
WriteLn('1-добавление в стек');
WriteLn('2-удаление из стека');
WriteLn('3-выдача на экран');
WriteLn('4-конец работы');
ReadLn(N);
case N of
1: SozdDob;
2: Udal;
3: Pech;
4: B:=False
end
end
End.
Иногда приходится вставлять элементы в середину списка. При статическом описании в этом случае приходится сдвигать часть массива. Это достаточно трудоемкая операция, особенно если она повторяется в цикле.
Для демонстрации гибкости динамических структур данных рассмотрим следующую простую задачу. Имеется стек, описанный в предыдущем примере. Требуется вставить элемент с именем NewName после элемента KeyName. Пусть переменные P и Q имеют тип Ukaz.
P:=Top; B:=True;
While (P<>Nil) and B do
if P^.Name = KeyName then
Begin
B:=False; {для выхода из цикла}
New(Q);
Q^.Name:= NewName;
Q^.Next:=P^.Next;
P^.Next:=Q
End
else P:= P^.Next;
А теперь видоизменим задачу. Пусть вставка требуется перед элементом KeyName. На первый взгляд кажется, что сейчас придется сохранять указатель на предыдущий элемент либо анализировать вместе с текущим и следующий элемент, но указатели позволяют выбрать более простое и красивое решение. Изменения касаются последних трех операторов, следующих после New(Q).
Q^:= P^;
P^.Name:=NewName;
P^.Next:=Q;
Первый оператор обеспечивает копирование элемента KeyName на место вновь организуемого элемента. При этом автоматически обеспечивается связь с элементом, стоявшим ранее после KeyName, так как поле указателя Next также копируется. Остается откорректировать старый элемент KeyName. В качестве упражнения предлагается проследить, потребуются ли изменения в том случае, когда элемент KeyName находится в вершине стека.
Рассмотрим более содержательную задачу. С клавиатуры вводится строка, представляющая собой математическое выражение с вложенными скобками трех видов: “{}”, “[]” и “()”. Старшинство скобок не задано, то есть любая пара скобок может быть вложена в любую другую. Требуется проверить синтаксическую правильность расстановки скобок, что определяется следующим правилом: каждой закрывающей скобке должна предшествовать открывающая того же вида и того же уровня вложенности.
Для решения этой задачи можно использовать стек. Выражение сканируется по символам. Каждая открывающаяся скобка заносится в стек. При встрече закрывающей скобки проверяется символ из вершины стека. Он должен быть открывающей скобкой того же вида. Наконец, по завершению просмотра стек должен быть пустым.
Program Syntax;
{ анализ вложенности скобок, стек на указателях }
Type
Ukaz=^Stek;
Stek=record { элемент стека }
Ch: char; { символ (открывающие скобки) }
Next:ukaz { следующий элемент }
end;
Var
Top, Kon: ukaz;
Vir: string[80]; { исходное выражение }
I, N: integer;
A, B, Pr: char;
Procedure Dob;
{ добавление в стек; A-добавляемый символ }
Begin
New(Kon);
Kon^.Next:=Top;
Kon^.Ch:=A;
Top:=Kon
End;
Procedure Udal(var Pr:char);
{ исключение из стека; Pr='e'-признак ошибки }
Begin
Pr:='o';
if Top=Nil then Pr:='e'
else
case A of
')': if Top^.Ch<>'(' then Pr:='e';
']': if Top^.Ch<>'[' then Pr:='e';
'}': if Top^.Ch<>'{' then Pr:='e';
end;
if Pr<>'e' then
begin { удаление элемента из вершины }
Kon:=Top;
Top:=Top^.Next;
Dispose(Kon);
end
End;
Begin { начало основной программы }
WriteLn('Введите выражение');
ReadLn(Vir);
Top:=Nil;
N:=Length(Vir); { длина выражения }
For I:=1 to N do
begin
A:=Vir[I]; { очередной символ }
case A of
'(','[','{': Dob;
{ добавление в стек открывающей скобки }
')',']','}':
begin
Udal(Pr);
{ проверка вершины стека; удаление, если нет ошибки }
if Pr='e' then
begin
WriteLn('Ошибка в позиции ', I);
ReadLn; { пауза }
Exit { выход из программы }
end
end
end
end;
if Top<>Nil then
{ в конце не пустой стек }
WriteLn('Нет последних закрывающих скобок')
else
WriteLn('Все в порядке !!!');
ReadLn { заключительная пауза }
End.
Эта программа легко корректируется (на уровне контекстной замены) для случая статического представления стека с помощью массива. Приведем описание переменных и процедур данной версии программы.
Program Syntax; {анализ вложенности скобок, стек - массивом}
Var
Stek:array [1..80] of char;
Top, Kon: integer;
Vir: string[80]; { исходное выражение }
I, N: integer;
A, B, Pr: char;
Procedure Dob;
{ добавление в стек; A-добавляемый символ }
Begin
Top:=Top+1;
Stek[Top]:=A
End;
Procedure Udal(var Pr:char);
{ исключение из стека; Pr='e'-признак ошибки }
Begin
Pr:='o';
if Top=0 then Pr:='e'
else
case A of
')': if Stek[Top]<>'(' then Pr:='e';
']': if Stek[Top]<>'[' then Pr:='e';
'}': if Stek[Top]<>'{' then Pr:='e';
end;
if Pr<>'e' then Top:=Top-1;
{ удаление элемента из вершины }
End;
Программа может быть усовершенствована. В приведенном варианте не анализируется допустимость символов выражения, не проводится анализ характера ошибки, не предусматривается иерархия скобок разного типа, просмотр выполняется до первой ошибки и т.п.
Дата добавления: 2018-11-24; просмотров: 187; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!