Реферат: Концепция данных (продолжение) Тип множества Кроме типов array и record в средствах структурирования данных Стандарта языка предусмотрена еще одна структура множество или тип set который иногда называют

Программирование


5. КОНЦЕПЦИЯ ДАННЫХ (продолжение)


Тип множества


Кроме типов array и record в средствах структурирования данных Стандарта языка предусмотрена еще одна структура – множество или тип set. который иногда называют множественным типом. Конструкция, определяющая тип set, имеет вид:


< тип set> ::= set of <базовый тип>

<базовый тип> ::= <скалярный тип>


Если тип множества – тип Т, а базовый тип – Т0, то тип Т является множеством-степенью своего базового типа, т. е множеством всех его подмножеств, в том числе и пустого. Особенность типа состоит в том, что набор элементов-компонент, на которые не накладывается никакое отноше­ние порядка.

Кардинальное число типа card(T)=2card(To), поскольку каждому значе­нию типа Т0 в множестве соответствует двоичный признак: “присутствует” или “отсутствует”. Поэтому для эффективной и экономной по форме пред­ставления в памяти организации данных типа Т кардинальное число типа Т0 должно быть небольшим (чаще всего это либо перечислимый тип, либо отрезок типа). В различных версиях систем программирова­ния для языка Паскаль мощность множества ограничена величинами от 32 до 256 элементов (числа кратные байту). Это связано с тем, что множество в машине обычно отображается двоичным словом, разряды которого поставлены в соответ­ствие значениям базового типа. Присутствие или отсутствие элемента в переменной множественного типа ко­дируется соответственно нулем или единицей. Кроме экономного использования памяти такое представление множества позволяет достаточно быстро выполнять операции над экземплярами типа. Затрачиваемое на такие операции время оказывается соизмеримым с временем выполнения аддитивных операций над переменными типа Integer.

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


type

Letter= a .. z;

LetterSet= set of Letter;

CharSet= set of Char;

IntSet= set of 1..50;

NumberSet= set of (0,1,2,3,4,5,6,7,8,9);

var

S1: LetterSet;

S2: CharSet;

. . .

При описании типов IntSet и NumberSet использовалось непосредственное описание базового типа.

Значения констант или переменных этого типа представляют собой перечисление (через запятую) элементов множества, заключенных в квад­ратные скобки. Значениями переменных типа S1 и S2 могут быть, напри­мер, [a,b,f.d] и [1,’,d, ‘’’’].

Для множественного типа определены следующие элементарные опера­ции: пересечение (*), объединение (+), разность (-) и принад­лежность множеству (in). Пересечение и объединение двух множеств часто называют умножением и сложением. Соответствующим образом определены и приоритеты операций: пересечение имеет приоритет перед операциями объединения и разности, которые в свою очередь имеют приори­тет перед операцией принадлежности. Так, пересечение множеств [a,b,c]*[a,b,c,d,f] есть [a,b,c], объединение [a,b,]+[b,d,f] есть [a,b,d,f], a раз­ность [a,b,c]-[b,d,f] есть [a,c].

Операция принадлежности относится к классу операций отношения. Слева от in обычно записывается выражение, а правым операндом является выражение множественного типа, производного от типа левого операнда. Например, если выполнен оператор S1:=[p,q,r,s], то условие [r,s,] in S1 имеет значение True, а [r,s,5] in S1 имеет значение False. Кроме того, усло­вие [p,q,r,s] - [r,s,5] in S1 также будет иметь значение True.

При использовании операции in константа множественного типа может быть и не описана в разделе переменных. Например, отношение x in [1 .. 9] , встретившее в тексте программы без предварительного описания множества цифр, определено. Кроме того, операцию in нельзя записать с отрицанием в виде x not in [1 ..9]. Это две операции, которые следуют подряд. Поэтому правильная запись отношения должна иметь вид not (x in [1 .. 9]).


Таблица 5.1 . Соответствие между обозначениями операций.

^ Обозначение или операция

традиционное обозначение

обозначение в языке Паскаль

множество

{ ... }

[ ... ]

пересечение



*

объединение



+

содержит



>=

содержится в



<=

принадлежит



in

пустое множество



[ ]


Другие операции отношения применительно к множествам означают тождественность (=), нетождественность (<>), “содержится в” (<=) и “содержит” (>=). Соответствие между традиционными символами операций, применяемыми в теории множеств, и символами языка Паскаль приведено в таблице 5.1.


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


В качестве примера работы с множествами ниже рассматривается две простых комбинаторных задачи. Первая из них моделирует “лототрон” т.е. случайную выборку m из контейнера, содержащего n шаров, пронумерованных от единицы до n. Множество шаров в этом случае удобно представить описаниями вида:


type

Namber=1..255;

Container =set of Number;

var

Selection : Container;

Ball : Number;


Решение задачи сводится к генерации случайного числа (номера шара) в интервале от 1 до n с проверкой условия принадлежности очередного шара множеству ранее выбранных, причем на первом шаге это множество пустое. Выбору шара соответствует вывод его номера на экран.


Для генерации случайных чисел в интервале (0, ... ,n) обычно используется стандартная функция Random(N). Здесь интервал не вполне удобен, но привести его к нужному виду можно, суммируя случайное значение с константой. В примере это единица. Кроме того, генерируемые числа являются “псевдослучайными”, так как генерируются программой, реализующей детерминированный алфавитный оператор,. “Случайность” определяется только так называемой базой (см последний пример раздела 2). Поэтому для установки новой базы используется еще одна стандартная функция без параметров – Randomize.


С учетом примечания текст соответствующей программы имеет вид:


program Prim5_1;

uses Crt;

type

Namber=1..255;

Container =set of Number;

var

Selection : Container;

I,M,N,Ball : Number;

begin

ClrScr;

Write{‘Всего шаров, но не более 255 ’};

ReadLn(N);

Write{‘Количество шаров в выборке ’};

ReadLn(M);

Selection :=[];

for I:=1 to M do

begin

Ball := Random(N-1)+1;

Randomize;

if not (Ball in Selection)

then

begin

Selection := Selection + [Ball];

Write(Ball : 3)

end

end;

ReadKey

end.{ Prim5_1}


Другая программа моделирует все возможные варианты выборки из контейнера необходимого количества шаров. Число возможных вариантов выборок достаточно велико и его легко подсчитать с помощью соответствующих биноминальных коэффициентов. В задаче же ставится другая цель – генерации самих выборок. Основная сложность решения такой задачи заключается в том, что ранее полученные варианты невозможно запоминать – их слишком много. Поэтому в процессе генерации необходимо выполнять некоторое правило, определяющее последовательность формирования вариантов. Это правило проще всего пояснить простым примером, который затем индуктивно “распространить” на более сложный случай. Пусть требуется перебрать все перестановки из 4 шаров по два. Тогда варианты перестановок можно строить следующим образом: сначала “склеить” единицу с оставшимися номерами (12,13,14), затем двойку (21,23,24), тройку (31,32,34), и, наконец, четверку (41,42,43).

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


Ввод 4 3

Вывод

1










2










3







4




3










2







4




4










2







3

2










1










3







4




3










1







4

3










1










2







4




2










1







4




4










1







2

4










1










2







3




2










1







3




3










1







2



program Prim5_1;

uses Crt;

type

Quantity=0..255;

Namber=1..255;

Container=set of Number;

var

QBall, LCh : Quantity;

procedure Choice (Box : Container; LongChoice :

Number; UsesBall : Quantity);

var

Ball: Number;

begin

if UsesBall < LongChoice

then

for Ball :=1 to QBall do

if Ball in Box

then

begin

WriteLn (Ball : 3*UsesBall);

Choice (Box-[Ball], LongChoice,

UsesBall+1)

end

end;{Choice}

begin

ClrScr;

Write ('Количество шаров - ');

ReadLn (QBall);

Write ('Количество шаров в выборке - ');

ReadLn (LCh);

if QBall>=LCh

then

Choice([1..QBall], LCh, 0)

else

WriteLn('Ошибка в исходных данных');

ReadKey

end.{ Prim5_1}


Структура данных типа set оказывается безусловно полезной в случаях, когда задача легко формулируется в терминах множеств и, кроме того, позволяет существенно упростить программирование “длинных” условных выражений, связанных с проверкой на принадлежность. К последним, например, относятся, задачи анализа текстов и, в частности задача сканирования текстов программ с целью выделения лексем и других конструкций языка при трансляции.

В программе Prim5_3 в качестве еще одного примера использования типа set рассматривается задача поиска простых чисел в диапазоне 2, ... ,n, где n2. Из-за простоты решения (не используются операции умножения и деления) в основу поиска положен метод, известный под названием ”решето Эратосфена”. Тогда алгоритм поиска простых чисел сводится к следующему.

Поместить все числа заданного диапазона в решето (Sieve).

Изъять из решета наименьшее среди оставшихся в нем чисел и поместить его среди простых (Primes).

Удалить из решета все числа, кратные данному.

Если решето не пустое, то вернуться к пункту 2, иначе вычисления прекратить.

Решето и множество простых чисел можно описать как:

var Sieve, Primes : set of 2 .. 255;

и, учитывая, что простые числа (кроме двойки) есть нечетные числа, представить фрагмент программы их поиска в виде:


program Prim5_3;

uses Crt;

type

Number=2..255;

var

Sieve, Primes : set of Number;

Next, C, K : Number;

begin

ClrScr;

Sieve :=[2..255];

Primes :=[ ];

Next :=2;

repeat

while not (Next in Sieve) do

Next := Succ(Next);

Primes := Primes+[Next];

C := 2*Next -1; {C - новое простое, нечетное}

K := Next;

while I <=255 do {исключение кратных из решета}

begin

Sieve := Sieve - [K];

K :=K+C

end

until Sieve =[ ];

ReadKey

end; { Prim5_3}


5.2. Последовательный файл


^ Определение операций с последовательностями

Общее свойство рассматриваемых ранее простых структурированных типов данных (array, record, set) заключается в том, что их кардинальное число конечно. Поэто­му такие данные достаточно легко отображаются в памяти ЭВМ и часто называются фундаментальными.

Большинство усложненных структур, таких как последовательности, деревья, графы и т.д. характеризуются тем, что их кардинальные числа бесконечны. Это отличие усложненных структур от структур с конечным кардинальным числом не позволяет заранее определить объем памяти для размещения таких данных.

Некоторую последовательную структуру с неопределенным кардиналь­ным числом можно рекурсивно описать, например, используя понятие последовательности с типом компонент (базовым типом) Т0 . Это либо :


пустая последовательность,

конкатенация последовательности (с базовым типом Т0) и значения типа Т0..


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

Отсюда вытекает, что необходимый для размещения структуры усложненного типа объем памяти неизвестен во время трансляции и мо­жет изменяться во время выполнения программы. Это требует динамиче­ского распределения памяти, при котором память занимается, если соответ­ствующие значения "растут", и, возможно, освобождается, когда они "убывают".

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

Для “работы” с такими структурами в современные языки программирования обычно встраивается только механизм, позволяющий динамически распределять память. Этот механизм обычно основывается на том, что все усложненные структуры состоят либо из неструктурированных элементов (простых типов данных), либо из фундаментальных структур. Если в языке имеются средства для динамического размещения компонент и указания связей между ними, то в нем могут создаваться произвольные структуры с помощью явных операций, определяемых программистом.

При этом существует структура, которая является усложненной, поскольку ее кардинальное числе не ограничено, но так широко и часто используется, что ее, как правило, включают в число фундаментальных. Это – последовательность или файл. Особая значимость структуры объясняется тем, что с ее помощью осуществляется связь программы с “внешним миром”, т.е. обеспечиваются ввод и вывод информации, а также хранение необходимой информации в то время, когда программа не активизирована. Иными словами файловая переменная не уничтожается после выполнения программы и затем может существовать как независимая от нее переменная с некоторым присвоенным ей именем. Поэтому для большинства программ справедливо утверждение о том, что если в результате выполнения программы не создан файл (результаты не сохранены), то ее выполнение не имеет смысла.

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

К внешней памяти с последовательным доступом относятся все виды лент (здесь и далее при обсуждении операций уместна аналогия с обычным бытовым магнитофоном). Отдельные дорожки магнитных или оптических дисков также должны рассматриваться как устройства с последовательным доступом (в качестве аналога можно упомянуть грампластинку). В общем случае строго последовательный доступ – основное свойство всех запоминающих устройств с механическим перемещением носителя информации и (или) считывающей (записывающей) “головки”. Кроме того, к устройствам с последовательным доступом относятся практически все устройства ввода-вывода (клавиатура, видеотерминал, печатающие устройства и т.п.).

Для описания абстрактного понятия последовательности можно использовать следующую терминологию и нотацию. Пусть:


< > обозначает пустую последовательность.

i> обозначает последовательность, состоящую из единственной компоненты хi, которая называется единичной последовательностью.

Если X= 1, ..., xm> и y = 1 , ..., yn > – последовательности, то X Y = есть конкатенация X и Y.

Если X = – непустая последовательность, то first (x) =1> обозначает первый элемент x.

Если x= 1, ..., xm> – непустая последовательность, то rest (x) = 2, ..., xm> есть последовательность x без первой компоненты. Следовательно, существует инвариантное соотношение

& = x.


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

Для утверждения того, что вводимая в качестве базового типа последовательность допускает применение только ограниченного множества операторов, которые определят строго последовательный доступ к компонентам, эта структура и называется последовательным файлом или просто файлом.

По аналогии с описаниями типа массива и множества тип файла с базовым типом Т0 определяется как type Т = File of Т0 , например:


type Spis=file of Person;


Это означает, что любой файл типа Т (в примере это Spis) состоит из 0 или более компонент типа Т0(Person).

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

Формально определить позицию файла можно, считая, что файл состоит из двух частей: части xL слева от текущей позиции и части xR справа от нее. Очевидно, что всегда справедливо равенство (инвариант) X = xL & xR.

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

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

В соответствии с этим для “работы” с файлами необходим и достаточен набор операций, включающий:


операцию, инициализирующую формирование или просмотр (по аналогии с магнитофоном – перемотку ленты);

операцию, добавляющую компоненту в конец последовательности (в режиме записи);

операцию, позволяющую при просмотре переходить к следующей компоненте (чтение).


Две последние операции обычно определяются в форме, предполагающей наличие явной вспомогательной переменной (аналог считывающей или записывающей головки физического устройства для магнитной записи), которая представляет собой буфер файла. Такой буфер (иногда его называют окном) автоматически связывается с компонентой файла <хi>, обозначается как х и принадлежит тому же базовому типу Т0 (понятие буфера поясняется рис.5.1).



Таким образом, операция построения пустой последовательности (ReWrite(X)) означает присваивание X:=< >

Эта операция используется для уничтожения (стирания) текущего значения x и инициализации процесса построения новой последовательности. Для увеличения последовательности (записи новой компоненты) используется операция Put(X), которая означает присваивание

X:=X & <х>,

фактически дополняя последовательности X значением х .

Инициация просмотра – это операция Reset(X), которая означает одновременные присваивания

XL=< >,

XR:=X,

х:=


и используется для инициации процесса чтения последовательности.

Переход к следующей компоненте в этом случае осуществляется с помощью операции ^ Get(X), которая означает присваивания


XL :=XL & R)>,

XR :=Rest(XR),

х:=R))>.

При этом важно отметить, что <First(X)> определено только при X  < >.

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

х:=R))>

становится неопределенной. Достижение конца файла, очевидно, равнозначно тому, что правая часть xR пуста. Определить это можно с помощью предиката (условия) Eof(X), который соответствует xR =< > и означает, что достигнут конец файла (end of file). Следовательно, операция Get(X) может выполняться только при Eof(X)=False.


Тип файла в Стандарте языка

Тип файла в Стандарте языка определяется синтаксической конструкцией:


< тип файла > ::= file of <тип компонент>


Если сравнить это правило с соответствующим определением структуры array, которая также состоит из однотипных компонент, то можно отметить, что их различия сводятся к замене зарезервированного слова array на слово file и отсутствии части правила, определяющей число компонент. Последнее связано с тем, что тип файла не имеет заранее определенного кардинального числа. Реальное число компонент в файле определяется с помощью функции Eof(f), параметром которой является имя конкретной переменной файлового типа (можно использовать аналогию со строками с завершающим нулем). Функция возвращает значение True, если не существует компоненты, которая следует за позицией буфера файла.

Над типом допустимы рассмотренные ранее операции, реализованные в виде стандартных процедур ^ ReWrite(F), Reset(F), Put(F) и get(F), фактическим параметром которых является имя переменной-файла. Семантическое толкование этих процедур сводится к следующему:

Reset(f) устанавливает окно файла f в его начало для последующего чтения; значение первой компоненты присваивается f; функция Eof(f) возвращает значение False если файл не пустой и True в противном случае; если файл пуст, f не определено;

Rewrite(f) также устанавливает окно файла f в его начало, но для последующей записи (если файл уже существовал, он уничтожается); функция Eof(f) возвращает значение True, f не определено;

Get(f) перемещает f на следующую компоненту, присваивая ему значение этой компоненты; если такой компоненты нет (Eof(f)=True), то значение f не определено; таким образом, вызов процедуры Get(f) имеет смысл только при условии Eof(f)=False;

Put(f) присваивает компоненте файла значение f, после чего перемещает его на следующую позицию; вызов процедуры возможен, если Eof(f)=True, причем после выполнения процедуры значение Eof(f)=True не изменяется, а значение f не определено.


Все действия с файлами можно выразить с помощью перечисленных четырех процедур. Однако на практике операции продвижения по файлу как правило, объединяются с обращением к буферной переменной. Поэтому в стандарте языка предусмотрены еще две процедуры (Read и Write), которые можно выразить в терминах этих основных операций. Если f – буфер файла, а X – переменная базового типа Т0, то Read(f,X) эквивалентно x:=f; Get(f), a Write(f.x) эквивалентно f:=x; Put(f).

Преимущество использования Read и Write вместо Get и Put связано не только с краткостью, но и с простотой описания операций с файлами, так как в этом случае можно игнорировать существование буферной переменной f, значение которой может быть и не определено (см. семантику Rewrite, Get и Put).

В качестве примера “работы” с файлами ниже приведены две программы, первая из которых формирует файл, записывая в него натуральный ряд чисел от 1 до n, а вторая позволяет “дописать” в этот файл еще n чисел. Особенностью второй программы является то, что уже существующий файл нельзя открыть для записи, не уничтожив имеющуюся в нем информацию, т.е. его нельзя просто дополнить. В этом случае приходится использовать вспомогательный (буферный) файл. Механизм дополнения поясняется комментариями, помещенными в текст программы.


program Prim; {формирование файла}

type

TF=file of integer;

var

I,N : Integer;

F : TF;

begin

N:=10;

ReWrite(F);

for I :=1 to N do

begin

F^:=I; {составной оператор можно заменить на Write(F,I)}

Put(F)

end

end.


program Prim {дополнение файла N компонентами}

type

TF=file of integer;

var

I,N : Integer;

F, Buf : TF;

begin

N:=10;

Reset(F); {файл F открыт для чтения}

ReWrite(Buf); {буфер-файл Buf открыт для записи}

while not Eof(F) do

begin {копирование F в Buf}

Read(F,I);

Write(Buf,I)

end;

N:=N+I;

for I:=I+1 to N do

Write (F,I); {дополнение файла Buf N компонентами}

Reset(Buf); {буфер-файл Buf открыт для чтения}

^ ReWrite(F); {файл F открыт для записи}

while not Eof(Buf) do

begin {копирование файла Buf в исходный файл F}

Read(Buf,I);

Write (F,I)

end

end.


Как любая другая переменная, файлы могут быть локальными по отношению к программе или процедуре, в которой они описаны. Однако они могут уже существовать вне программы. Такие файлы называют внешними.


^ В Стандарте языка предполагалось, что внешние файлы будут передаваться в программу как параметры через заголовок программы, который определяется так:


<Заголовок программы> ::= program <имя>

program <имя> (<список параметров>)


Поскольку в современных системах программирования механизм “связывания” программы с внешними файлами носит иной характер, заголовок программы теряет смысл и как правило, игнорируется большинством трансляторов,.


^ 5.3.Текстовый файл


Файлы, базовый тип которых определен как char, называют текстовыми. Текстовые файлы являются стандартным типом с именем Text , соответствующим описанию типа:

Text=file of Char.

Выделение этого типа в качестве стандартного обусловлено тем, что тексты обычно разбиваются на строки. Способ определения перехода с одной строки на другую основывается на применении специального управляющего символа (например, в ASCII для этих целей могут использоваться два символа: cr – возврат каретки и lf – перевод строки). В общем случае применение именно этих символов для обозначения конца строки не стандартизовано, поэтому для маркировки конца строки по аналогии с предикатом eof в языке Паскаль используется предикат Eoln, а для работы с текстовыми файлами используются дополнительные процедуры WriteLn(f) и ReadLn(f), смысл которых сводится к следующему:

WriteLn(f) заканчивает текущую строку текстового файла, т.е. обычно присваивает текущей компоненте файла значение, соответствующее маркеру конца строки;

ReadLn(f) пропускает все символы, предшествующие началу следующей строки текстового файла f (f становиться равным первому символу следующей строки); процедура имеет смысл только при eof(f)=false;

eoln(f) булевская функция, которая возвращает значение true, если текущая позиция f соответствует концу строки (при этом значение f – символ пробела).

Три следующих фрагмента программ иллюстрируют формирование, чтение и копирование текстовых файлов.

Формирование текстового файла ^ F (при этом предполагается, что очередной символ текста S определяется с помощью некоторых действий, условно обозначенных Р(S), строка должна состоять из M символов, а весь текст содержит N строк).


ReWrite(F);

for I:=1 to N do

begin

for J:=1 to M do

begin

P(S);

Write (F,S)

end;

WriteLn (F)

end;


2. Чтение текстового файла F. Пусть R(S) обозначает действия, связанные с обработкой очередного символа S, а R(Str) – действия, выполняемые после чтения строки.


Reset(F);

while not Eof(F) do

begin

while not Eoln(F) do

begin

Read(F,S);

R(S)

end;

R(Str);

ReadLn(f)

end;


3. Копирование файла F в файл F1 с сохранением построчной структуры.

Reset(F);

ReWrite(F);

while not Eof(F) do

begin

while not Eoln(F) do

begin

Read(F,S);

Write (F,S)

end;

ReadLn(F);

Write (F)

end;


Стандартные файлы Input и Output

В разделе 2 на семантическом уровне уже рассматривались средства языка для ввода исходной и вывода результирующей информации. В примерах, приведенных в этом разделе, процедуры Read и Write использовались без параметра, определяющего файловую переменную. Последнее возможно благодаря тому, что в языке Паскаль предусмотрены стандартные текстовые файлы Input и Output. При этом предполагается, что файлы Input и Output связаны с определенным типом внешних устройств для каждой конкретной системы программирования (например, для систем программирования Borland Pascal соответственно клавиатурой и видеотерминалом). Они не требуют описания в разделе типов и по умолчанию используются транслятором как недостающий параметр, если имя файла в процедурах Read и Write не указано.

Таким образом, эквивалентными можно считать следующие пары операторов:

^ Read (S); Read (Input, S);

Read (S); Read (Input, S);

Write (S) Write (Output, S);

Write (S) Write (Output, S)

Eof Eof(Input)

Eoln Eoln(Input)


Файлы Input и Output не требуют применения стандартные процедуры Reset и ReWrite.

Кроме того, здесь следует отметить ранее не упоминавшееся несоответствие процедур Read и Write принятой в языке концепции типов. Несоответствие проявляется в том, что в качестве фактических параметров этих процедур допустимо использование переменных не только символьного типа, который является базовым для текстовых файлов. Это свойство (свойство полиморфизма – буквально “множества форм”) процедур ввода-вывода требует уточнения в определении самих процедур.


^ Процедура Read. Пусть v1,v2, ... ,vn –переменные символьного, целого, их отрезков или вещественного типа, а f – текстовый файл. Тогда:


Read (v1,v2, ... ,vn) эквивалентно Read (Input, v1,v2, ... ,vn);

Read (f, v1,v2, ... ,vn) эквивалентно

begin Read (f, v1,); ... ;Read (f, vn,) end;

ReadLn(v1,v2, ... ,vn) эквивалентно ReadLn (Input, v1,v2, ... ;vn);

ReadLn (f, v1,v2, ... ,vn) эквивалентно

begin Read (f, v1, ... ,vn,); ReadLn(f) end;

если параметр v символьного типа то Read (f,v) эквивалентно

begin v:=f; Get(f) end;

если параметр v целого (ограничения целого) или вещественного типа, то читается последовательность символов, представляющая в соответствии с синтаксисом языка целое или вещественное число, после чего происходит преобразование последовательности в форму, соответствующую представлению значения этого параметра в машине; при этом следующие друг за другом числа могут разделяться пробелом или признаком конца строки (в Borland Pascal это клавиша <Enter>).


^ Процедура Write. Процедура позволяет дополнить текстовый файл строками, состоящими из одного или нескольких символов. Пусть f – текстовый файл, а р1,р2, ... ,рn – параметры, вид которых уточняется последним пунктом. Тогда:

Write (p1,p2, ... ,pn) эквивалентно Write (Output, p1,p2, ... ,pn);

Write (f, p1,p2, ... ,pn) эквивалентно

begin Write (f, p1,); ... ;Write (f, pn,) end;

WriteLn(p1,p2, ... ,pn) эквивалентно writeln (output, p1,p2, ... ;pn);

WriteLn (f, p1,p2, ... ,pn) эквивалентно

begin Write (f, p1, ... ,pn,); WriteLn(f) end;

если параметр p символьного типа то Write (f,p) эквивалентно

begin p:=f; Put(f) end;

параметр p может иметь вид e или e : m или e : m : n, где e – выражение, значение которого записывается в файл, а m и n – выражения целого типа (параметры размера поля); значение e может быть целого, отрезка целого, вещественного, булевского типа или строкой (последовательностью символов в кавычках-апострофах).


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

Выражение n определяет размер дробной части и используется в случае, когда е имеет вещественное значение и должно быть представлено в естественной форме. Если размер дробной части не задан, число представляется как десятичное в нормальной форме.

Значение е булевского типа представляется стандартными именами False и True. Строки выводятся без каких либо изменений. Ввод и вывод значений переменных перечисляемого типа процедурами Read и Write не поддерживается.


5.4.Операции с файлами в Borland Pascal


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

Так, в версиях систем программирования ^ Borland Pascal, например, процедуры Put(f) и Get(f) недоступны пользователю, но значительно расширен набор стандартных процедур и функций для операций с файловой переменной. Некоторые из них иллюстрируется таблицей 5.1. (полный перечень процедур, поддерживающих работу с файлами приводится в описании модуля System).

При этом в версиях Borland Pascal существуют три типа (разновидности) файлов : текстовые, типизированные и нетипизированные.

Определение текстового файла в Стандарте и версиях Borland практически полностью совпадают, вплоть до зарезервированных имен стандартных файлов Input и Otput.

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

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

Перед использованием файловой переменной в версиях ^ Borland Pascal ее необходимо “связать” с внешним файлом. Внешним файлом обычно является поименованный файл на диске, но он также может представлять собой устройство, например, клавиатуру, видеотерминал или устройство печати.

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