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

Автоматизированная обработка больших объемов данных становится проще, если данные упорядочены (структурированы). Применяются следующие структуры данных:

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

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

Если элементы списка одной длины, структура называется вектором данных, разделители не требуются. При длине одного элемента d, зная номер элементаn, его начало определяется соотношениемd(n-1).

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

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

Если элементы таблицы одной длины, структура называется матрицейданных, разделители в ней не требуются. При длине одного элементаd, зная номер строкиmи номер столбцаn, а также строк и столбцовM,N, найдем адрес его начала:

d[N(m – 1) + (n – 1)].

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

Мой компьютер

Диск С: ДискD: ДискH:

Program files Папка 1 Папка 2 …

MS OfficeСтандартные …

MS Word MS Excel …

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

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

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

H:\Stud\tsi11\Ivanov\Text\my_file.doc

Россия \ Ростовская область \ Ростов – на – Дону \ ул. Б. Садовая \дом 1\кв. 11

1.5.9. Хранение данных

При хранении данных решаются две задачи:

• как сохранить данные;

• как обеспечить быстрый удобный доступ к ним.

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

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

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

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

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

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

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

Для хранения различных видов информации необходимо использовать по-разному устроенные файлы. Способ организации данных (структура файла) называется форматом.

Файловая система – это часть ОС компьютера и поэтому всегда несет на себе отпечаток свойств конкретной ОС. Некоторые форматы файлов стандартизированы и должны поддерживаться любой ОС и работающими в ней приложениями (например, графические файлы .GIFилиJPEG). Наряду с этим всегда имеются форматы, специфичные только для данной системы (например, исполняемые файлыMSDOSилиWindows). Есть форматы, разработанные для конкретных приложений, работающих под управлением данной ОС (например, формат .xls, используемыйMSExcel). В некоторых случаях при разработке приложений программистам приходится создавать новые форматы.

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

Если система служебных кодов определена, то для сохранения текста требуется вставка в него управляющих символов. Например, надо сохранить таблицу из шести чисел, имеющую две строки и три столбца (2 х 3):

4	1	8
2	5	11

Для хранения чисел используются ячейки фиксированного размера (например, два байта). Поэтому, если в файл записано 6 чисел, то при чтении данных из него нужно извлечь шесть раз по 2 байта. Т.к. память ПК линейна, то возникает задача, как сохранить не только сами числа, но и структуру таблицы. Очевидно, что если таблица запоминается построчно, то основным параметром, определяемым ее вид, является количество чисел в строке (т.е. количество столбцов). Поэтому, договариваемся, что первое число в файле – это длина строки таблицы, затем записывается количество строк, а далее построчно сохраняются числовые элементы таблицы. Тип данных, представляющий их, также должен быть оговорен. Число строк необходимо запомнить, чтобы знать, где остановиться при чтении информации. Таблица может быть записана в файл в виде следующей последовательности:

3

2

4

1

8

2

5

11

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

Заголовок (служебная информация)

Собственно сохраняемые данные

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

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

Вопросы для самоконтроля

1. Как представляются числа в памяти компьютера?

2. Как представляются символьные и текстовые данные?

3. Как представляются звуковые данные?

4. Как представляются графические данные?

5. Какими способами формируются графические изображения?

6. Что вы можете рассказать о моделях RGBиCMYK?

7. Что вы можете сказать об особенностях хранения данных различных типов?