Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 10
Текст из файла (страница 10)
Последовательный файл тура называется последовательным ерайгом или просто фай- лом. По аналогии с определениями типа для массивов и мно- жеств файловый тип определяется так: (ур е Т = 1!(е о( Т, ! (1.45) Это значит, что любой файл типа Т состоит нз 0 или более компонент типа Т,. Примеры: гуре 1ех1 = 1!!е о1 сйа« (уре десй = $!!е о( са«д Смысл последовательного доступа заключается в том, что в каждый момент доступна лишь одна определенная компонента последовательности. Эта компонента определяется гекушей позицией механизма доступа. Позиция с помощью файловых операций может меняться, определяя либо следующую компоненту (см, де1), либо первую компоненту всей последовательности (см.
«евер). Формально мы определим позицию файла, считая, что файл состоит нз двух частей: части хс слева от текугцей позиции и части хе справа от нее. Очевидно, что всегда справедливо равенство (инвариант) х = — хс дг хл (1.46) Второе, более важное следствие последовательного доступа заключается в том, что процессы формирования и просмотра последовательности не могут произвольно чередоваться.
Таким образом, файл вначале строится при помощи последовательного добавления компонент (в конец), а затем может последовательно просматриваться от начала до конца. Поэтому принято считать, что файл находится в одном из двух состояний; либо формирования (записи), либо просмотра (чтения). Преимущество строго последовательного доступа особенно огцутимо, если файлы размещаются иа вспомогательных запоминающих устройствах, т. е, если происходит обмен между устройствами.
Последовательный доступ — единственный метод, позволяющий успешно скрывать от программиста сложность механизмов такого обмена. В частности, он допускает применение буферизации — простого приема, который ооеспечивает оптимальное использование ресурсов сложной вычислительной системы.
Некоторые запоминающие устройства на самом деле допускают только последовательный доступ к находящейся на них информации. Очевидно, что к таким устройствам отно- !. Фундаментальные структуры данных сятся все виды лент. Но даже на магнитных барабанах и дисках каждая отдельная дорожка представляет собой запоминающее устройство с последовательным доступом. Строго последовательный доступ — основное свойство всех устройств с механическим перемещением, а также некоторых других. 1 11 1.
Эпементарные операции над файпамн Теперь мы попытаемся сформулировать абстрактное понятие последовательного доступа с помощью некоторого мн<>- жества элементарных операций нид файлами, которые имеются в распоряжении программиста. Они определяются в терминах понятий последовательности и конкатенации. Существует операция, инициализирующая процесс формирования файла, операция, инициализирующая просмотр, операция, добавляющая компоненту в конец последовательности, и операция, позволяющая прн просмотре переходить к следующей компоненте. Две последние здесь определяются в форме, предполагаюгцей наличие явной вспомогательной переменной, которая представляет собой буфер.
Мы считаем, что такой буфер автоматически связывается с каждой файловой переменной х, и обозначаем его через хт. Ясно, что если х — типа Т, то хТ принадлежит его базовому типу Ть. 1. Построение пустой последовательности. Операция гер гссе (х) означает присваивание х:=( ) Эта операция используется для уничтожения текущего значения к и инициации процесса построения новой последовательности, она соответствует разметке ленты. 2. Увеличение последовательности. Операция рсп(х) (!.48) означает прнсваивание а( )> которое фактически добавляет значение хг к последова» тельности х.
3. Инициация просмотра. Операция гезе1(х) (1.49) означает одновременные присваивания хь:=-( ) ха '=х х Т := )1гз((х) ББ 1.11. Последовательный файл Эта операция используется для инициации процесса чтения последовательности. 4. Переход к следующей компоненте. Операция де1(х) (1.50) означает одновременные присваивания хх:= хь с1 (11ге1 (хл)) х„:= гез1 (хл) х 1:= — '1(гз1 (гезу (хя)) Заметим, что 1(ге1(е) определено только при з ~ ( )„ Операции гетиг11е н геве1 не зависят от позиции буфера файла перед нх выполнением. В любом случае они возвращают его к началу файла. При просмотре последовательности необходимо иметь возможность распознавать ее конец, поскольку при достижении конца последовательности операция х 1:= )1гз1 (хя) становится неопределенной. Достижение конца файла, очевидно, равнозначно тому, что правая часть хн пуста.
Поэтому мы вводим предикат ео)(х)=ха — — ( ) (1.51) который означает, что достигнут конец файла (епб о1 111е). Следовательно, операция де1(х) может выполняться только при ео((х) = 1а(ее. В принципе все действия с файлами можно выразить с помощью четырех основных файловых операций. На практике же часто бывает естественно объединять операции продвижения по файлу (ле1 или ри1) с обращением к буферной переменной.
Поэтому мы введем еще две процедуры, которые можно выразить в терминах основных операций. Пусть и— переменная, а е — выражение базового типа То файла. Тогда геий(х, о) эквивалентно и:=х Т'; де1(х) тег11е(х, е) эквивалентно х 1: = е; ри1 (х) Преимущество использования геас( и итг(1е вместо ие1 и ри( связано не только с краткостью, но и с простотой концепции, поскольку теперь можно игнорировать существование буферной переменной хт, значение которой может быть и неопределенным. Однако буферная переменная бывает полезна для «заглядывания вперед».
й Фуада.нентахьные структуры данных Для выполнения этих двух процедур необходимы следующие условии: — ео~ (х) для геас((х, о) ео) (х) для вг)(е (х, е) Г!ри чтении файла предикат ео((х) становится истинным, как только прочитана последняя компонента файла х. На этом основаны две схемы программ для последовательного формирования и обрабогки файла х. Дополнительными параметрами в этих схемах являются операторы тт и 5 и предикат р. Запись файла х: (1.52) Чтение файла х: гееег(ее); нЫ!е — е Ьей(а евд (1.53) тат.2.
Файлы со сложной структурой При решении многих прикладных задач необходимо в большие файлы ввести некоторую подструктуру. Например, книга, хотя и может рассматриваться как единая последовательность букв, подразделяется на главы и абзацы. Назначение подструктуры — задание неких явных точек отсчета, некоторых координат, которые позволят легче ориентироваться в длинной последовательности информации, Существующие запоминающяе устройства часто дают определенные средства для представления таких точек отсчета (например, маркеры магнитной ленты) и позволяют находить нх со скоростью болыпей, чем скорость просмотра информации между этими точками. В рамках принятой нами системы обозначений естественный способ ввести первый уровень подструктуры — это рассматривать подобный файл как последовательность элементов, которые в свою очередь являются последовательностями, т.
е. как файл файлов. Предположим, что конечные элементы !.)!. Последовательный файл илн единицы принадлежат к типу (у, тогда подструктуры будут типа Т'= т)1е о!0 а весь файл — типа Т = !Пе о! Т' Очевидно, что таким образом можно строить файлы с любым уровнем вложенности. В общем виде тип Т„можно определить с помошью рекурсивного соотношения Т! — — В!ео(Т! о (= )..и и Т,= У.
Такие файлы часто называют многоуровневыми файлами, а компоненту типа Т, называют сегментом «~ г-го уровня. Примером многоуровневого файла является книга, в которой уровням сегментации соответствуют главы, разделы, абзацы и строки. Но наиболее обший случай — это файл с одним уровнем сегментации. Такой файл, сегментироваиный на одном уровне, никоим образом не идентичен массиву файлов. Прежде всего число сегментов файла может меняться, и файл по-прежнему может увеличиваться только с конца.
В рамках введенных выше обозначений и при определении файла как х: т))е о! г)!е о! (! ху будет обозначать доступный в текущий момент сегмент, а хуу — доступную в текуший момент единичную компоненту, Соответственно риМ(хТ) и йе)(хф) ссылаются на единичную компоненту, а ри((х) и пег(х) означают операции добавления очередного сегмента и перехода на очередной сегмент. Сегментированные файлы удовлетворительно реализуются практически на всех запоминающих устройствах с последовательным доступом, включая ленты. Сегментация не меняет их важнейшего свойства — последовательного доступа либо к отдельным компонентам, либо (возможно, при помощи более быстрого механизма пропуска) к сегментам.
Другие запоминающие устройства, а именно магнитные барабаны и диски, обычно содержат некоторое количество дорожек, каждая из которых представляет собой запоминающее устройство с последовательным доступом, но которое обычно слишком мало, чтобы вместить целый файл. Таким образом, на дисках файлы обычно распределяются на несколько дорожек и содержат соответствующую библиотечную информацию, связывающую эти дорожки. Очевидно, что *) Слово «сегиент» встречвегсв, пожалуй, только в этой кннге.— Прим. ред. 1. Фундаментальные структуры данных 58 указатель начала каждой дорожки служит естественным маркером сегмента, и, возможно, обращение к нему легче и непосредственнее, чем к маркерам на каком-либо последовательном устройстве.
Для адресации дорожек, с которых начинаются сегменты, и обозначения текущей длины сегментов может использоваться, например, индексированная таблица в основной памяти (рис. 1.10). Это приводит нас к так называемым индгксировпннььк файлам (иногда также называемым файлами с прямым достуаолт). В настоящее время барабаны и диски организованы Рнс. 1.1О.
Индексирапаппый Файл с пятью сетыептамя. таким образом, что каждая дорожка содержит много физических меток, с которых может начинаться чтение или запись. Поэтому нет необходимости, чтобы каждый сегмент занимал ее целиком, поскольку это может привести к неэкономному расходованию памяти, если сегменты коротки по сравнению с длиной дорожки. Область памяти между двумя метками называется физическим сегментом или секторолт в отличие от логического сегмента, который являетси понятием, относящимся к структуре данных программы. Разумеется, каждый физический сегмент содержит самое большее один логический сегмент, а каждый логический сегмент (даже пустой) занимает по меньшей мере один физический сегмент.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
