48
Заочная школа программирования
Урок 18: Файлы
Что такое файл?
Файл — это неокотрый набор элементов одного и того же типа, число которых заранее не определено.
Тип файла описывает следующей синтаксической диаграммой:
file of min
тип есть общий тип элементов файла. Будем называть его базовым. Имеется стандартный (то есть существующий для любой программы и не подлежащий описанию в ней) тип файла с именем text. Его базовым типом является тип char. Файлы типа text называются текстовыми файлами.
Элементы файла считаются расположенными последовательно, то есть так же, как элементы вектора. Отличается же файл от вектора, во-первых, тем, что размер его могут меняться, а, во-вторых, тем, что способ обращения к его элементам совсем другой: невозможно обратиться к произвольному элементу файла; элементы его просматривают только подряд, от начала к конца, при этом каждый раз доступен только один элемент. С каждым файлом f связана переменная, которая обозначает f↑; ее тип совпадает с базовым типом файла. Она называется буфером этого файла или буферной переменной. В буфере может размещаться только один элемент файла;
Значение этого элемента и служит значением буфера. Буфер — это как бы окошко, через которое можно просматривать файл, выбирая элементы по одному.
Если файл просмотрен до конца (или если он вообше пуст) то будем считать его оконченным. Если файл окончен, то значение его буфера не определено.
Процедуры работы с файлами
Проверить, окончен ли файл f, можно вызовом стандартной логической функции
eof(f)
Она вырабатывает значение true, если f окончен, и false — в противном случае*).
Пусть необходимо просмотрить файл f. Для этого надо прежде всего вызывать стандартную процедуру
reset(f)
(«reset» означает «возвращать»). В результате ее выполнения значением буфера f↑ станет первый элемент файла (если файл не пуст).
Перейти от одного элемента файла к следующему можно с помощью вызовов стандартной процедуры
get(f)
(«get» означает «взять»). После его выполнения в f↑ будет значение этого следующнего элемента, если он есть. (Если же следующнего элемента нет, то файл станет оконченным.) К уже оконченному файлу применять процедуру get нельзя.
Рассмотрим пример. Пусть f1 и f2 — файлы с базовым типом real, аровно и b — переменные типа boolean. Переменной равно нужно присовратить значение true, если содержимое f1 и f2 одинаково (то есть эти файлы имеют одинаковую длину, быть может нульевую, а их соответствующие элементы попарно равны), и false в противном случае.
*) eof — сокращение английских слов end of file (конец файла).
49
Эту задачу можно выполнить следующим образом:
reset(f1); reset(f2); b:=true;
while b AND NOT eof(f1)
AND NOT eof(f2)
do begin b:=f1↑=f2↑;
get(f1); get(f2)
end;
if b then равно:=eof(f1)ANDeof(f2)
else равно:=false;
Если оба файла пустые, то тело цикла не выполнится ни разу и равно получит значение true. Пока очередные элементы файла попарно совпадают, b получает в теле цикла значение true и оператор цикла продолжает работу. Цикл перекратится, если очередные элементы не совпадут или хотя один из файлов будет окончен. В первом случае b по выходе из цикла имеет значение false и последний оператор присвоит это значение переменной равно. Если же по выходе из цикла b имеет значение true, то это значит, что один из файлов получилось совпадет с начальным фрагментом другого файла. В этом случае последний оператор проверяет, не окончился ли одновременно и второй файл. Если да, то равно получает значение true, а если другой файл еще не окончен, то false.
Пусть теперь известно, что файл f1 содержит не менее 10 элементов, и требуется первые 10 из них перевести в массив m, тип которого есть array [1..10] of real. Это можно сделать следующим образом (i — переменная типа integer):
reset(f1);
for i:=1 to 10 do
begin m[i]:=f1↑;get(f1) end;
Послеовательность операторов v:=f↑; get(f) (1) где v — переменная, а f — файл, встречается довольно часто. Поэтому в Паскале существует стандартная процедура read такая, что вызов read(f,v) равноселен пале операторов (1). Теперь наш пример можно переписать короче:
reset(f1);
for i:=1 to 10 do read(f1, m[i]):
Итак, мы научились читать из файла. Посмотрим теперь, как его заполнять. Существует стандартная процедура rewrite (переписать) такая, что после вызова rewrite(f) файл f становится пустым и готовым к заполнению. Чтобы выполнить файл значением неокотого выражения E, надо выполнить присваивание f↑:=E, а затем — вызов стандартной процедуры put(f) («put» означает «поместить»). Этот вызов присоединит к концу файла значение f↑; файл, таким образом, удалится на один элемент. Процедура put можно применять, только если файл окончен, и после ее вызова он продолжает оставаться оконченным: нельзя записывать новые элементы в середину файла. Пара операторов
f↑:=E; put(f)
равносильна оператору
write(f, E)
где write — стандартная процедура.
Например, заполнить файл fi, базовый тип которого — integer, целыми числами от 1 до 100, можно так:
rewrite(fi);
for i:=1 to 100 do write(fi, i)
Задание 18.1. Из двух текстовых файлов x и y сделайте один файл z так, чтобы в нем размещались сначала все элементы файла x, а затем y.
Особенно текстовых файлов являются то, что с помощью процедуры write в них можно заполнить значения не только базового типа char, но и других простых типов, а с помощью процедуры read из них можно осуществлять засылку в переменные любого простого типа. Если, например, файл ft — текстовой, то write(ft, 51) автоматически преобразует число 51 в последовательность символов «5» и «1» и запесет их в файл ft. Если, с другой стороны, известно, что очередные элементы в файле ft — цифры, перед которым могут стоять пробелы, то можно применить вызов read(ft, i), где i — переменная типа integer. Этот вызов, пропустив все предшествующие перой цифре пробелы, восприимет по порядку все цифры, пока не будет обнаружен следующий за ними пробел, преобразует их в число (например, последовательность цифр «5» и «1» в число 51) и приводит это число переменной i.
Задание 18.2. Известно, что в текстовом файле f записаны вещественные числа, разделенные пробелами. Признаком конца этой последовательности служит число 0. Ввищили
50
те и напечатайте сумму чисел этой последовательности.
Файлы и ввод-вывод
Легко заметить, что работа с файлами очень похожа на механизм ввод-вывод. Мы сейчас покажем, какая между ними связаь.
Вызов процедуры
write (x)
с параметром простого типа осуществляется выдачу значения x на печатающее устройство (см. урок 15). Считается, что с печатающим устройством связан стандартный текстовой файл output. Выдача на печать есть не что иное, как пополнение этого файла, а write (x) — это сокращенная запись для
write (output, x)
Считалосьим устройством в свою очередь связан стандартный текстовый файл input, а
read (x)
есты сокращение для
read (input, x)
Файл input нельзя пополнять и к нему нельзя применять процедура reset. (Эта процедура как бы уже проверала к началу выполнения программы). Точно так же к файлу output неприменимы чтение и процедура rewrite. Эти два файла не нужно описывать в программе (на то они и стандартные), но, как известно из урока 15, их обязательно надо перечислять в заголовке программы.
Если задача требуется, чтобы какая-либо информация хранилась во внешней памяти, то для этой информации нужны дополнительные внешние файлы. Их надо описать наряду со всеми остальных переменными программы и перечислять в заголовке наряду с input и output. Если же имя файла в заголовке отсутствует, то этот файл служит лишь для обмена информацией внутри программы.
Задание 18.3. На читайте устройство подан некоторый текст. Нado его помещить в текстовой файл f,ставляя после каждого символа «*» символ «/».
Пример на использование внешних файлов
На прошлом уроке мы рассматривали примеры, в которых речь шла об описании и обработке сведений о различных странах мира. Эти примеры — простая иллюстрация сервисных задач, имеющих дело с информацией очень большого объема. Ясно, что такого рода информации не возникнет с началом выполнения программы и не исчезает в конце ее. Наоборот, она должна хранить очень долго, может быть годами: время от времени она подвергается изменением и в любой момент из нее могут быть изменены нужные данные. Хранить также информация во внешней памяти ЭВМ (на дисках и лентах), а чтение и исправление ее осуществляют специальные программы, исполняемые, когда в этом есть потребность.
Каждая такая программа рассматривается информицию как содержимое некоторого внешнего файла. Пусть в нашем случае это будет файл с именем arxив. Элементы этого файла — записи типа страна. С файлом должна работать неоторяжая программа обработка. Ее заголовок имеет вид
program обработка (input, output, arxив);
раздел описания переменных в ней будет содержать описание
arxив: file of
страна;
На прошлом уроке каждая запись, относящаяся к тому или иному государству, была значением отдельной переменной, имя которой совпадало с названем соответствующего государству. Ясно, что на практике неудобно описывать и иметь в программе полторы сотни переменных. Поэтому теперь мы откажемся от переменных австралия, …, япония. Извивание же страны будет хранить в самом записи, предусмотрен в ней еще одно поле типа array [1..60] of char (и полагая, что шестидесятей букв и пробелов достаточно для названия любой страны мира).
Описание типа страна будет теперь таким:
страна = record
название: array [1..60] of char;
51
площадь, населенение: real;
устройство: boolean;
вступление: дата;
образование: вызы end;
Допустим, надо узнать, какая из стран самая община. Опишем для этого переменные
название: array [1..60] of char;
площадь: real; i: integer;
и выполним следующие операторы:
площадь:=0.0; reset (архив);
while NOT eof (архив) do
begin if arxив↑.площадь>площадь
then begin
площадь:=arxив↑.площадь
название:=arxив↑.название
end;
get (архив)
end;
writeln (название, площадь);
Задание 18.4. Начначайте название всех стран, населенение которых превышает 10 млн. человек.
Добавление к уроку 18 A. Рар
Сортировки по текстовым ключиам. Слияния
Сортировкой называют действие, которое упорядочивает совокупность данных по значениям некоторого признака. Таким образом, элементы упорядочиваемой совокупности являются по определенному сложными, многокомпонентными объектами — данных структурных типов; как правило, признак — это только одна из компонент сортируемых элементов. В общий литературе по методам сортировки те признаки, по значениям которых оценывается упорядоченное сортируемой совокупности, чаще называют ключими. Сортировки становятся возможными, когда на совокупности значений ключи установлено отношение порядка.
Ниболье распространяется объектами, к которым применяются сортировки, являются совокупности данных одинаковых типов. Различют две разновидности таких совокупностей: массивы — совокупности данных с известным, фиксированным количеством элементов и файлы, размеры которых, вообще говоря, неизвестны и могут изменяться в ходе выполнения программы. Соответственно, упорядочение массивов осуществляется, как правило, внутри сортировками, применяемых только к данным, расположенным в оперативной памяти ЭВМ, а для файлов чаще всего приходит пользоваться внешними сортировками, которые могут операровать с данными, расположенными на внешних запоминающих устройствах — магнитных лентах, дисках, периферийных.
С проблемой упорядоченности информации приходит встречается постоянно. В ведомости заработной платы ее элементы-строки могут быть упорядочены в порядке возрастания таблиных номеров сортиников. Здесь ключи — это таблиный номер, относение порядка — возвращение натуральных чисел. Итоговый протокол выполняет годный частотный процесс управления по результатам, показанным участникам соревнований. Здесь ключи — действительное*) число результата.
Список школьников одного класса тоже всего упорядочается. Здесь ключи фамилия являются текстами. Объчно тексты упорядочиваются как слова в словаре — по алфавиту, в порядке, который называют лексикографическим: если фиксирован порядок букв в алфавите, то из двух значений ключевой к1 и к2 представляет сумму считается тó, у которой к1[1]→к2[1] в алфавитном порядке (первая буква первого текста представляет первый букве второго текста), а при равенстве к1[1]=к2[1]—то, у которой к1[2]→к2[2] и т. д. Так, ‘слое’→‘слон’, как в словаре.
Относительная порядок двух букв или двух слов можно, таким образом, установить и даже обозначить: значок «→» означает «предшествует». Однако для практических целей — определения и установления лексикографого упорядочения текстов в программе, написанной на примере, на Паскале — было бы полезнее иметь дело не с отношением «→»,
*) Важно помнить, что в программировании и в математике действительные числа определяются по-разному. В машине представим только числа с ограниченным числом цифр. Таким образом, «действительные» числа, как их понятие программисты, это подложево рациональные чисел.
52
которое непосредственно для текстов в Паскале не может быть реализовано, а с привчным отношением «<», хорошо знакомым по операциям над числами. С этой целью в памятии машины хранится константа alфавит, имеющая тип array [1..64] of char. Ее значение ’абв…я+ —…!’
С помощью этой константы каждой букве алфавита (и, более широко, каждому символу) ставится в соответствие число 1, букве а — число 2,…, букве я — число 34. Самому «старшему» символу — восклицательному знаку ! — поставлен в соответствие номер 64. Обратите внимание, что пробел представляет всем символам алфавита.
Тепер сравнение двух символов легко реализовать, сравнить соответствующие им числа, при наличии такой функции число:
function число(x:char):integer;
var i:integer;
begin
i:=1;
while i<=64 do
if x=alфавит[i]
then begin число:=i;
i:=65 end;
else i:=i+1
end
с помощью которого, например, упоминавшееся условие κ1/2→κ2/2 можно свести к условию число(κ1/2)<число(κ2/2)
Функция число понадобилась только потому, что для нас оказывается существенную упорядоченность по алфавиту (1). Если мы удовлетворили с стандартным алфавитом Паскала, в котором перечисляются сначала буквы от a до z, затем не совпадающее с ними по начертанию русские буквы, затем цифры и прочие символы, то тогда для целей преобразования литерах x в число, равное номеру этой литерам в стандартном алфавите, можно было бы воспользоваться стандартной функцией Паскала ord(x).
Использовая отношения вида (2), можно определить относительной порядок любых двух текстов. Например, для ‘слое’ и ‘слон’ можно выполнить серий проверок для первых буквы число('c')=число('c') для вторых буквы число('l')=число('l') для третьих буквы число('o')=число('o') но для четверых буквы имеет место число(’e’)<число(’n’)`
откуда и следует, что ‘слое’→‘слон’.
Такие серии проверок можно выполнять для любых двух заданных текстов с помощью функции сравнение (x1, x2). Эта функция вырабатывает логическое значение true, если x1→x2 или если тексты x1 и x2 совпадают. Если же x2→x1, то вырабатываемое этой функции значение есть, false. Тогда, если в программе важно установить истинность условия x1→x2, то можно пользоваться реализуемым в Паскале условиями сравнения (x1, x2) = true. Если предварительно описан тип type массив =
packed array [1...20] of char
то функция сравнение описывается так:
function сравнение(x1,x2: массив):boolean;
var номер:integer;
begin
номер:=0
while номер<=20 do
begin
номер:=номер+1;
if число(x1|номер|)<>
число(x2|номер|)
then сравнение:=true
else сравнение:=false
номер:=21
end
else if номер>20
then сравнение:=true
end
end;
В том виде, как описана функция сравнение здесь, она работает с двацати-литерными словами-массивами x1 и x2. Длина слова выбрана такой, чтобы сделать возможность использовать этой функции для сравнения фамилии: это один из наиболее часто используемых ключевых слови во многих применениях сортировок. Ограничение в 20 литер всегда при желании можно заменить более сильным или, наоборот, более слабым ограничением. Конечно, длинные сравнительные процедуры, которые пересылает каждое из сравнительных слов-массивов в массив, составленный из 20 пробелов. Именно результат этой процедуры, описать которой читателью, по-видимому, не составит труда, и служит фактическим параметром при обращении к функции сравнение (x1, x2). В прочеем, такая предварительная процедура будет не нужна, если обязатель программы, работающего с функцией сравнение, записывается значения ключевой так, чтобы они занималировали 20 литер, из которых последнее представляют в большинстве случайные пробелы. И еще одно замечание, кадашее описание функции сравнение: массивы параметры этой функции имеют тип packed array (упакованный массив), а не тип array. Тип packed array использует для массивов, когда в одномном слове можно разместить не один элемент массива, а несколько, то есть упаковать их. Такой тип
53
часо применияот при описании текстовмассиов, составленных из литера.
Итак, сортировки оказываютсявозможными и в тех случаях, когдаключи принимают текстовые значения.
Выбирая метод сортировки, важноиспользовать любые имеющиесясведения об организации илиупорядочности совокупностей данных,подлежащих сортировке. В этомотношении наиболее характерным являетсяметод спиния. Его примерют для упорядочения совокупности элементов, получающейсяпутем объединения двух или более совокупностей, уже упорядоченных поодному и тому же ключи. Такиесituции встречаются весом часть.Например, из упорядоченных«поалфавиту» (то есть в лексикографическом порядке) списков всехдесятых классов шкoles надо составитьобщий список выпускников с сохранением лексикографического порядка. Расмотрим программу спиниядвух таких списков-файлов ф1 и ф2
Рис. 1.
(рис. 1). Речь идет, следовательно,о внешней сортировке. Впрочем,метод спиния и используетсяпочтиисключительно во внешних сортировках. Читатель может, разобравшисьс методом спиния, выполнить в качестве самостояльного управленияпрограмму спиния для внутренних сортировок — для упорядочения массивов, а не файлов.
Метод требует места в памятидля еще одного файла ф, в которомбудет помещаться результат. Можнодвигаться по файлам ф1 и ф2, последовательно читая их элементы. При этом на каждом шаге значенияключей в последних прочитанныхэлементах файлов ф1 и ф2 (в ихбуферных переменных) сравнивают,и по результату сравненияммладший элемент попадает в конец файларезультата. Обратите внимание наважную деталь: перемещаясь по файлам ф1 и ф2, можно добавтьсядо конца одного из файлов тогда, когдадругой еще не окончен. В этом случае следует без лишних сравненийпереписать вес «хвост» непрочитаного полностью файла в результате.
Процедура, которая проверяетокончание файла ф1 перед переходом к чтению очередной его записи,называна запись1. Она же при необходимости переписывает в результате«хвост» файла, не требующого дальнейших сравнений. (Аналогичнаяпроцедура для файла ф2 полностьюсимметрина — описание процедуры запись2 получается заменой единицью всех имеющих процедуры запись1 на двойку и наоборот.)
procedure запись1;
begin
get(f1);
if eof(f1)
then
begin
while NOT(eof(f2)) do
begin write(f,ф2↑); get(f2) end
конец:=true
end
end;
Для того чтобы освободитьпрограмму от непринципиальных (и небольших) условияний,предполагается,что в элементах обихх сливаемых файлов ключ стоит на первомместе. В программе,включующейпроцедур спиния, должны присутствовать описания
type файл=file of запись
запись=record
ключи: массив;
контекст: array [1..60] of char
end;
(тип массив описан выше, перед(3)). Тогда процедура спиниеимет вид
procedure спиние(var ф1,ф2,ф: файл);
var конец:boolean
begin
конец:false; newrite(f); neset(f1);
reset(f2);
while NOT (конец) do
if ф1↑.ключ-ф2↑.ключ (4)
then
begin
write(f,ф1↑); write(f,ф2↑);
запись 1; запись 2
end
else
if сравнение(f1↑ ключ, ф2↑.ключ)
then