Структуры данных. Организация и обработка файловых структур

Конспект лекций

Лекция 12

Организация и обработка файловых структур

Научный редактор доц., д-р техн. наук Л.Г. Доросинский

Екатеринбург

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

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

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

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

Файл – это именованный объект, хранящий данные (программы, данные или другая информация) на каком-либо носителе (дискета, CD, винчестер…). Файл, как и массив, - это совокупность данных, потому они немного похожи. Существенные различия:

1. файлы, в отличие от массивов, располагаются не в оперативной памяти, а на жестких дисках или на внешних носителях, хотя файл может располагаться на так называемом электронном диске (в оперативной памяти);

2. файл не имеет фиксированной длины, т.е. может увеличиваться и уменьшаться;

3. перед работой с файлом его необходимо открыть, а после работы – закрыть.

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

Type T = file of Tо

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

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

Говоря о файлах, нельзя не сказать о файловой системе.

Файловая система – это совокупность файлов и управляющей информации на диске для доступа к файлом. Или по другому – это совокупность программных средств для доступа к файлам. Существует довольно много файловых систем, в качестве примера рассмотрим файловую систему MS-DOS.

В ней имена файлов состоят из двух частей, разделенных точкой: имя файла и расширение. Поле имени может содержать не более 8 произвольных символов из набора разрешенных для использования в имени файла. Поле расширения может содержать не более 3 символов из того же набора. Расширение обычно указывает на тип хранимой информации или на структуру файла, может вообще отсутствовать. Примеры наиболее распространенных расширений: exe, com, bat, txt, doc, htm, mp3 и т.д.

Файлы хранятся в каталогах. Каталоги могут называться по той же системе, что и файлы. Допускаются вложенные каталоги (подкаталоги).

Основные технические характеристики устройств внешней па­мяти - это емкость, время доступа, скорость передачи данных и форма доступа; важнейшая экономическая характеристика - стои­мость хранения в пересчете на единицу данных (например, стои­мость хранения одного бита).

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

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

Скорость передачи данных измеряется числом единиц данных, передаваемых между устройством внешней памяти и, например, основной памятью ЭВМ в единицу времени. Знаниё этой характеристики позволяет вычислить длительность передачи известного объема данных и длительность операции ввода — вывода отмомента ее инициирования до завершения передачи данных.

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

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

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

Существуют три основных формата записей – формат фиксированной длины, формат переменной длины и формат неопределенной длины.

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

Различают два типа файлов: текстовые и бинарные.

Текстовые файлы могут быть просмотрены и отредактированы с клавиатуры любым текстовым редактором и имеют очень простую структуру: последовательность ASCII – символов. Эта последовательность символов разбивается на строки, каждая из которых заканчивается двумя кодами: 13, 10 (0xD, 0xA). Примеры известных текстовых файлов: *.bat, *.c, *.pas.

Бинарные файлы – это файлы, которые не имеют структуры текстовых файлов. Каждая программа для бинарных файлов определяет собственную структуру.

Библиотека языка С содержит функции для работы как с текстовыми, так и с бинарными файлами.

Дата добавления: 2014-01-07