Структурированные типы данных

Описанные выше типы данных называют простыми. Основной признак, по кото­рому можно определить величину простого типа, таков: одно имя – одно значение.

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

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

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

Если все элементы, образующие структуру, однотипны (например – целые числа или символы), то структура является однородной; если же в ней «перепутаны» элементы разной природы (например, числа чередуются с символами), то неодно­родной.

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

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

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

Массивы

Самым традиционным и широко известным из структурированных типов дан­ных является массив (иначе называемый регулярным типом) – однородная упорядо­ченная статическая структура прямого доступа.

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

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

Рис. 3.1. Одномерный массив – набор элементов (компонентов)

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

Рис. 3.2. Графический образ двухмерного массива

Записи, множества, файлы

Обобщением массива является комбинированный тип данных – запись, являю­щаяся неоднородной упорядоченной статической структурой прямого доступа. Запись – набор именованных компонент – полей (часто разного типа), объеди­ненных одним общим именем и идентифицируемых (адресуемых) с помощью как имени записи, так и имен полей (см. рис. 3.3.).

Рис. 3.3. Иллюстрация «записи»

Запись «В» состоит из трех полей, имеющих последовательно типы «текст», «целое число», «вещественное число». 1-е поле – название детали, 2-е – условный номер по каталогу, 3-е – длина. При работе с одной единственной записью (что бывает нечасто), имя поля можно использовать как обычную переменную, т.е. можно изменять значение поля с помощью операции присваивания или любых других операций, доступных над величинами данного типа. Если же данная запись – лишь часть набора данных, то имя поля состоит из двух частей и называ­ется составным именем поля (на рис. 3.3 составные имена В.name, В.number, В.length).

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

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

Существенно иные возможности дает структура данных, моделирующая свойст­ва математического объекта – множества.

Над множеством могут быть выполнены следующие операции:

1) объединение множеств (операция сложения ‘+’);

2) пересечение множеств (операция умножения ‘*’);

3) теоретико-множественная разность (вычитание множеств ‘-’);

4) проверка принадлежности элемента множеству.

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

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

Понятие «файл» при всей своей привычности употребляется в информатике в нескольких не совсем совпадающих смыслах. Здесь мы остановимся лишь на представлении о файле как однородной упорядоченной динамической структуре последовательного доступа – очереди.

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

1) новые компоненты могут добавляться лишь в «хвост» очереди;

2) значения компонент могут читаться (извлекаться) лишь в порядке следования компонент от «головы» к «хвосту» очереди.

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

Исторически слово «файл» стало впервые применяться в информатике для обозначения последовательного набора каких-либо данных или команд (про­грамма), хранящихся на внешнем запоминающем устройстве. Несколько позже были осознаны абстрактные, не зависящие от магнитных дисков и лент, свойства очереди как структуры данных, полезные при решении многих задач обработки информации. Такой принцип извлечения и добавления компонент к очереди часто называется «первым вошел – первым вышел» (английская аббревиатура -«FIFO») (см. рис. 3.4.).

Рис. 3.4. Иллюстрация «очереди»

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

Стек

Существует (и часто используется) и другая структура данных, в которой тот элемент, который первый в нее помещался, выходит последним и, наоборот, тот, который последним входит, выходит первым (английская аббревиатура «LIFO»). Такая структура получила название стек (или магазин – по сходству с магазином стрелкового оружия) (см. рис. 3.5.).

Рис. 3.5. Иллюстрация «стека»

Иерархическая организация данных

Во всех рассмотренных выше структурах отдельные элементы (компоненты, по­ля, составляющие) структуры были формально равноправны. Существует, однако, широкий круг задач, в которых одни данные естественным образом «подвязаны» к другим. В этом случае возникает соподчиненная (иерархическая) структура данных. Ограничимся конкретным примером. Представим себе генеалогическое дерево, корень которого – имя человека, на следующем уровне – имена его родителей, еще на следующем – имена родителей родителей и т.д. Такая структура называется двоичным деревом (см. рис. 3.6.).

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

Рис. 3.6. Структура типа «двоичное дерево», пара ближайших по горизонтали кружков – мужское и женское имя

Операции с данными

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

В структуре возможных операций с данными можно выделить следующие основные:

 сбор данных — накопление информации с целью обеспечения достаточной пол­ноты для принятия решений;

 формализация данных — приведение данных, поступающих из разных источ­ников, к одинаковой форме, чтобы сделать их сопоставимыми между собой, то есть повысить их уровень доступности;

 фильтрация данных — отсеивание «лишних» данных, в которых нет необходи­мости для принятия решений; при этом должен уменьшаться уровень «шума», а достоверность и адекватность данных должны возрастать;

 сортировка данных — упорядочение данных по заданному признаку с целью удобства использования; повышает доступность информации;

 архивация данных — организация хранения данных в удобной и легкодоступ­ной форме; служит для снижения экономических затрат по хранению данных и повышает общую надежность информационного процесса в целом;

 защита данных — комплекс мер, направленных на предотвращение утраты, вос­произведения и модификации данных;

 транспортировка данных — прием и передача (доставка и поставка) данных между удаленными участниками информационного процесса; при этом источник дан­ных в информатике принято называть сервером, а потребителя — клиентом;

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

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