Основные структуры данных

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

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

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

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

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

Адрес каждого элемента определяется путем доступа, ведущим от вершины структуры к данному элементу. Например, система почтовых адресов: страна − край − город − улица − дом − квартира − адресат.

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

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

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

Номер факультета: 3

Номер курса (на факультете): 2

Номер специальности (на курсе): 2

Номер группы в потоке одной специальности: 1

Номер учащегося в группе: 19

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