Структуры данных. Файловая структура

                                    1.3.4.1. Структуры данных

Если данные хранятся не как попало, а в организованной структуре, то каждый элемент данных приобретает новое свойство (параметр), который называется адресом.

При создании любой структуры данных решается два вопроса: как разделяются элементы данных между собой и как разыскиваются необходимые элементы.

(Если данные хранятся не как попало, а в организованной структуре, то каждый элемент данных приобретает новое свойство (параметр), который называется адресом.)

 Существует три основных типа структур данных: линейная, табличная и иерархическая структура.

Например, проставляя номера на отдельных страницах рассыпанной книги, мы создаем структуру списка.

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

В этом случае для разделения элементов используются специальные знаки-разделители (например, знаки окончания строки или абзаца).

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

Если длина любого элемента a (например, букв или байтов), то для розыска элемента с номером n достаточно отсчитать a×(n–1) длин элементов данных. Следующим будет необходимый нам элемент, длина которого также равна a, поэтому нет необходимости определять окончание этого элемента.

Линейная структура – это список и представляет собой упорядоченную структуру, в которой местоположение (адрес) элемента однозначно определяется его номером. Таким образом, список отличается тем, что каждый элемент однозначно определяется своим номером (например, проставляя номера на отдельных страницах рассыпанной книги, мы создаем структуру списка) в массиве. Линейные структуры могут быть последовательного доступа (если элементы имеют разную длину) (линейные структуры последовательного доступа используются, когда элементы могут иметь разную длину. В этом случае для разделения элементов используются специальные знаки-разделители например, знаки окончания строки или абзаца. В таких структурах для розыска элемента с номером n необходимо просмотреть список, начиная с самого начала, и пересчитать встретившиеся разделители) или прямого доступа (если элементы имеют одинаковую длину) (линейные структуры прямого доступа еще называютвекторами данных. Они используются, когда элементы имеют одинаковую длину. В этом случае разделители в списке не нужны. Если длина любого элемента a (например, букв или байтов), то для розыска элемента с номером n достаточно отсчитать a×(n–1) длин элементов данных. Следующим будет необходимый нам элемент, длина которого также равна a, поэтому нет необходимости определять окончание этого элемента.)

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

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

Для доступа к элементу, имеющему адрес ячейки (m,n), надо просмотреть набор данных с самого начала и пересчитать внешние разделители (для строк). Когда будет отсчитан m–1 разделитель, надо пересчитать внутренние n–1 разделители, после чего начнется необходимый элемент, который закончится, когда встретится любой очередной разделитель.

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

Для доступа к конкретному элементу с адресом (m,n) в матрице, имеющей M строк и N столбцов, надо отсчитать a×[N×(m–1)+(n–1)] длин (здесь a – длина одного элемента). Следующим будет требуемый элемент, длина которого тоже равна a, поэтому его окончание определить нетрудно.

Табличная структура (таблицы данных, матрицы данных) – это упорядоченная структура, в которой местоположение (адрес) элемента определяется номерами строки и столбца, (такая структура отличается от линейной тем, что элементы данных определяются адресом ячейки, который состоит не из одного параметра, как в списках, а из нескольких) на пересечении которых находится ячейка, содержащая искомый элемент. В памяти компьютера обычно табличная структура представляется линейным способом, когда строки таблицы записываются последовательно друг за другом. При этом используется как последовательный доступ, (табличная структура последовательного доступа требует большее количество разделителей, чем линейная, поскольку необходимо разделять не только элементы в строке, но и строки. Для доступа к элементу, имеющему адрес ячейки (m,n), надо просмотреть набор данных с самого начала и пересчитать внешние разделители (для строк). Требует большее кол.разд.: когда будет отсчитан m–1 разделитель, надо пересчитать внутренние n–1 разделители, после чего начнется необходимый элемент, который закончится, когда встретится любой очередной разделитель) так и прямой доступ(табличная структура прямого доступа называется матрицей. В этом случае разделители не нужны, поскольку все элементы имеют равную длину и их количество известно. Разд.не нужны: для доступа к конкретному элементу с адресом (m,n) в матрице, имеющей M строк и N столбцов, надо отсчитать a×[N×(m–1)+(n–1)] длин (здесь a – длина одного элемента). Следующим будет требуемый элемент, длина которого тоже равна a, поэтому его окончание определить нетрудно).

Граф состоит из двух множеств – множества вершин и множества рёбер (дуг), соединяющих вершины.Иерархический граф – это граф, не содержащий циклов.

Например,

Например,

Например,

Иерархическая структура – это иерархический граф. В такой структуре местоположение (адрес) каждого элемента определяется путем доступа (маршрутом), ведущим от вершины структуры к данному элементу. Подобные структуры широко применяются в различных систематизациях и классификациях. Иерархические структуры используются для представления нерегулярных данных, которые трудно представить в виде списка или таблицы. В компьютере таким способом представлена структура каталогов, структура команд   (например, путь доступа к каталогу C:\Windows\System или путь доступа к команде Пуск → Программы → Стандартные → Калькулятор.)

Иерархический граф: Граф состоит из двух множеств – множества вершин и множества рёбер (дуг), соединяющих вершины.

Например,

 

Иерархический граф – это граф, не содержащий циклов.

Например,

Например, путь доступа к каталогу

C:\Windows\System

или путь доступа к команде

Пуск → Программы → Стандартные → Калькулятор

 

Файловая структура

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

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

Это соответствует тому, как мы раскладываем документы в папки. В каждой папке может быть один документ, а может быть несколько. Если мы хотим увидеть какой-либо документ, мы берем определенную папку, открываем ее и читаем содержимое. На папке мы можем написать ее название. Если у нас их много, можем объединить их в группы и как-то назвать эти группы. Можем перекладывать папки из группы в группу, какие-то из них вообще уничтожить и т.д. Файлы соответствуют таким папкам и с ними производятся аналогичные действия.

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

Любой информационныйобъект, хранящийся во внешней памяти и имеющий название называется файлом.

ИЛИ Файл-это именованная последовательность байтов, находящаяся на носителе информации.

Каждый файл содержит информацию, которая соответствует его назначению: текст,

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

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

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

Его название состоит из двух символов: имя носителя и двоеточие. Например, корневые каталоги устройств внешней памяти С и D имеют имена соответственно C: и D:. Если на носитель не записана информация, его корневой каталог пуст.

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

Например, C:\Windows\regedit.exe означает, что файл regedit.exe находится в каталоге Windows, который находится в корневом каталоге диска C.

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

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

Таким образом, вся область памяти как бы делится на такие кластеры, и они используются для записи файлов. Размер кластера зависит от формата внешней памяти.

Наиболее часто используются две системы:

– на основе таблицы размещения файлов FAT (File Allocation Table),

– на основе главной таблицы файлов MFT (Master File Table). Эта система называется NTFS. Одним из важных преимуществ NTFS является обеспечиваемое ею разграничение прав доступа пользователей к файлам и каталогам, что повышает устойчивость системы.

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

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

Название:Название файла или каталога состоит из двух частей, разделенных точкой. Левая часть называется именем, а правая – расширением. Запрещено в названии использовать специальные знаки (слеш, знаки больше и меньше, кавычки, апостроф, запятая и т.п.). Расширение (вместе с точкой) может отсутствовать. Для удобства работы со списками файлы именуются с указанием расширений, а каталоги – без расширений.

Корневой каталог: Его название состоит из двух символов: имя носителя и двоеточие. Например, корневые каталоги устройств внешней памяти С и D имеют имена соответственно C: и D:. Если на носитель не записана информация, его корневой каталог пуст.

 

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

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

– на основе таблицы размещения файлов FAT (FileAllocationTable),

– на основе главной таблицы файлов MFT (MasterFileTable). Эта система называется NTFS. Одним из важных преимуществ NTFS является обеспечиваемое ею разграничение прав доступа пользователей к файлам и каталогам, что повышает устойчивость системы. Чаще всего используется FAT. FAT формируется на каждом носителе информации автоматически при его форматировании. Клетки этой таблицы пронумерованы и соответствуют частям размером в один кластер. В каждой клетке может содержаться ноль, номер следующего кластера данного файла либо специальный числовой код. В качестве такого кода используется maxвозможное целое число, которое может быть записано в клетке FAT.если для записи чисел используется двухбайтовое целое без знака, то таким числом является 65535. Таким образом, кластеры составляющие файла сцеплены теми ссылками, который хранятся в FAT, номер самого первого кластера записан в каталоге в качестве одного из атрибутов характеризующих файл.

Компьютерные сети