 |
Структуры данных, хранение данных
|
|
|
|
Доступность информации есть важнейшее свойство информации, которое требуется обеспечить, особенно когда работать приходится с большим количеством данных. Обеспечить доступность помогает упорядочивание. Как, например, имея большое количество книг, мы раскладываем их по полкам: полка для книг по математике, полка для книг по физике и т.д., в рамках книжного шкафа мы создаем структуру, облегчающую поиск.
Для упорядочивания данных применяют структуры данных. Основных структур три линейная (список), табличная, иерархическая (дерево). Часто основные структуры комбинируются, например, элементами иерархической структуры могут быть линейные, а элементами линейной могут быть таблицы.
Линейная структура. Линейная структура данных (или список) - это упорядоченная структура, в которой адрес данного однозначно определяется его номером (индексом). Примером линейной структуры может быть список учебной группы или дома, стоящие на одной улице. Упорядоченность линейной структуры делает простым поиск, например, стоя на улице Горького легко найти дом номер 10.
В списках, как правило, новый элемент начинается с новой строки. Если элементы располагаются в строчку, нужно внести разделительный знак между элементами. Поиск осуществляется по разделителям (чтобы найти, например, десятый элемент, надо отсчитать девять разделителей).
Если элементы списка одной длины, структура называется вектором данных, разделители не требуются. При длине одного элемента – d (байтов, символов и т.п.), зная номер элемента - n, его начало определяется соотношением d (n-1)
Табличная структура данных. Табличная структура данных - это упорядоченная структура, в которой адрес данного однозначно определяется двумя числами - номером строки и номером столбца, на пересечении которых находится ячейка с искомым элементом.
|
|
|
Если элементы располагаются в строчку, нужно внести два разделительных знака - разделитель между элементами строки и разделитель между строками.
Поиск, аналогично линейной структуре, осуществляется по разделителям. Если элементы таблицы одной длины, структура называется матрицей данных, разделители в ней не требуются. При длине одного элемента - d, зная номер строки -m и номер столбца n, и зная число строк и столбцов M,N, найдем адрес его начала.
d [N(m-1)+(n-1)]
Таблица может быть и трехмерная, тогда три числа характеризуют положение элемента и требуются три типа разделителей, а может быть и n-мерная.
Иерархическая структура. Нерегулярные данные, которые трудно представляются в виде списка или таблицы, могут быть представлены в иерархической структуре, в которой адрес каждого элемента определяется путем (маршрутом доступа), идущим от вершины структуры к данному элементу.
Иерархическую структуру образуют, например, почтовые адреса (см. рис. 1.6.)
Россия
 |
Краснодарский край Ростовская область Ставропольский край
Семикорокорский район Ростов Красносулинский район Белокалитвенский район
Ворошиловский Большая Садовая Будёновский
Рис. 1.6. Пример иерархической структуры.
Адрес одного из домов, расположенных, к примеру на улице Большая Садовая, может выглядеть следующим образом:
Россия\ Ростовская область\ Ростов\ ул Большая Садовая \д 1
В линейной и табличной структурах облегчен поиск они проще, чем иерархическая структура, но, если, например, в линейной структуре появляется новый элемент, то упорядоченность сбивается. Как, если в списке студентов появляется новый человек, то список, расположенный по алфавиту нарушается.
|
|
|
В иерархической структуре введение нового элемента не нарушает структуры дерева, недостатком ее является трудоемкость записи адреса и сложность упорядочения.
При хранении данных решаются две задачи:
- как сохранить данные;
- как обеспечить быстрый удобный доступ к ним.
В компьютерных технологиях единицей хранения данных является объект переменной длины, называемый файлом.
Файл - это поименованная область на внешнем носителе, содержащая данные произвольной длины (любое число байтов, может быть и нуль), обладающая уникальным собственным именем.
На ранних этапах развития компьютерных систем файлы содержали данные одного типа (текстовые, графические, звуковые файлы). Современные файлы могут содержать данные различных типов. Например, в текстовом файле могут содержаться фотографии, элементы программного кода.
Имя файла имеет особое значение - оно фактически несет в себе адресные функции в иерархических структурах. Кроме того, имя может иметь расширение, в котором хранятся сведения о типе данных. Это важно, поскольку при автоматической обработке по типу файла может запускаться приложение (программа), работающее с ним. В настоящее время самые рядовые компьютеры на жестком диске сотни тысяч файлов, и для доступа к ним используется определенного вида программное обеспечение, решающее задачу централизованного управления данными.
Системы управления данными называются файловыми системами. Именно файловая система, а не пользователь, берет на себя задачи распределения внешней памяти, отображение имен файлов в соответствующие адреса во внешней памяти и обеспечение доступа к данным. Благодаря этому, работа с файлами во многом стала напоминать работу с обычными документами.
Информация любого типа хранится в виде файлов, выступающих в роли логически завершенных именованных совокупностей данных. Под логической завершенностью здесь понимается, что создатель файла сознательно выделил для хранения некоторую порцию информации в отдельный блок. Учитывая универсальный характер электронных носителей, в роли “документа” в файловой системе может выступать текст или его часть, компьютерная программа или данные к ней, графический или звуковой образ и т.п.
|
|
|
Для пользователя файл является основным и неделимым элементом хранения данных, который можно найти, изменить, удалить, сохранить или переслать на устройство или на другой компьютер, но только целиком.
С физической точки зрения, файл — это всего лишь последовательность байтов. Способ использования или отображения этой последовательности (интерпретация!) определяется типом файла — текстовый, звуковой, исполняемый модуль программы и т.п.
Естественно, что для хранения различных видов информации, необходимо использовать по-разному устроенные файлы. Способ организации данных в файле (структура файла) называют его форматом.
Некоторые форматы файлов стандартизированы и должны поддерживаться любой операционной системой и работающими в ней приложениями (например, графические файлы, определенные спецификациями GIF или JPEG). Наряду с этим всегда имеются форматы, специфичные только для данной системы (например, исполняемые файлы MS DOS или Windows). Кроме того, есть еще форматы, разработанные для конкретных приложений, работающих под управлением данной операционной системы (например, формат.xls, используемый MS Excel). И, наконец, в некоторых случаях при разработке приложений новые форматы приходится создавать самим программистам.
Структура файла может быть тривиальной. Например, текст может сохраняться в виде последовательности байтов, прямо соответствующих составляющим его литерам (формат plain text или ASCII-файл). Однако в большинстве случаев вместе с данными приходится сохранять и некоторую дополнительную информацию.
Но сохранение — это только часть проблемы. Слово "договариваемся" было выделено нами не случайно: сформулированными правилами должна будет пользоваться не только программа, сохраняющая таблицу, но и любая другая, которой потребуется прочесть данные для таблицы. Т.е. наш уговор — это взаимное соглашение о формате. Только в этом случае от разработанного формата будет реальная польза. Таким образом, формат файла определяет способ правильной интерпретации хранимых данных.
|
|
|
Размещение в начале файла блока служебной информации, часто используется в многочисленных форматах, например, в файлах баз данных или графических данных.
| ЗАГОЛОВОК (служебная инфомация) | Собственно сохраняемые данные |
Часто заголовок файла включает идентификатор формата файла. Программы, которые предназначены для просмотра файлов определенного типа, начинают свою работу с чтения служебной информации и проверки, возможности восприятия формата предложенного им файла.
Современные программные системы, как уже было сказано, позволяют одновременно включать в файл данные разных видов, а это требует разработки очень сложных форматов. Например, работая с программой MS Word, мы можем включать в один документ текст, картинки, таблицы, созданные в Excel, и многое другое. Комбинации этих элементов в своем числе практически бесконечны, и придумать простой формат, который позволил бы хранить все это вместе, невозможно. Например, для хранения документов MS Office строятся так называемые структурированные хранилища — фактически целые файловые системы, спрятанные в едином с точки зрения пользователя файле.
Подавляющей части пользователей практически ничего не нужно знать о внутреннем устройстве файлов, с которыми они работают. Этот уровень абстракции интерфейса операционных систем — одно из самых больших достижений компьютерных технологий.
Попутно заметим, что наличие разных форматов для хранения данных одного и того же типа затрудняет переносимость их из среды одного приложения (программы) в среду другого. Проблема обычно решается использованием специальных программ, называемых конверторами.
|
|
|
