Списочные структуры

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

Двухсвязный линейный список представлен на рис. 6.10б. Каждый элемент списка, кроме первого и последнего, содержит три поля, первое и третье из которых имеют указатели на предыдущий и последующий элементы.

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

Рис. 6.10. Списочная структура данных: линейная (а), двухсвязная (б), циклическая (в)

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

1. между узлами имеет место отношение типа «исходный - порожденный».

2. Есть только один узел, не имеющий исходного – корень.

3. Все узлы, за исключением корня, имеют только один исходный.

4. Ни один порожденный узел не может стать исходным.

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

Узел иерархической структуры данных в данном случае содержит три поля: одно для размещения собственно данных и два для указателей (на подчиненный и на соседний узел).

В информатике существует ряд разновидностей деревьев.

Рис. 6.11. Древовидная структура: а) иерархическая структура, б) древовидная структура данных

Бинарное дерево

Особое значение прибрели бинарные деревья (binary tree)) упорядоченное дерево, каждая вершина которого или пустая или состоит из одного корня и двух бинарных поддеревьев.

Сетевая структура представляет собой структуру наиболее общего вида, так как способна воспроизводить большинство связей между объектами. На рис. 6.14а представлена сеть автомобильных дорог, а на рис. 6.14б структура данных, позволяющая представить эту сеть в памяти компьютера. Для этого в сети используется два типа узлов: те, что отражают название города (тип 1), и те, что отражают расстояние между ними (тип 2). На рис. 6.14в указано содержание узла типа 1, а на рис. 6.17г – типа 2.

Рис. 6.14. Сеть автомобильных дорог- а), сетевая структура данных - б), содержание узлов первого типа - в), содержание узлов второго типа - г)

С понятием «структура данных» тесно связано понятие «модель данных», что можно представить следующим образом:

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

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

Реляционная модельосновывается на понятии “отношение”, и представляется совокупностью таблиц. На рис. 6.15 приведены базовые понятия данной модели.

Рис. 6.15. Основные понятия реляционной модели базы данных

Домен – это множество значений, принимаемых свойствами (характеристиками) отражаемого объекта.

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

Кортеж – это множество элементов из доменов, составляющих одну строку отношения (таблицы).

Отношение – это множество кортежей, отражающих свойства объекта.

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

- таблица должна иметь имя (например, ДЕТАЛЬ, ПОСТАВЩИК, ПОСТАВКИ);

- таблица должна быть простой, то есть не содержать составных столбцов, например, у поставщика должен быть только один номер телефона;

- в таблице не должно быть одинаковых строк;

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

В компьютере таблицы реляционной модели обрабатываются с помощью операций реляционной алгебры.