Структуры данных как способы представления АТД.

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

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

Среди вышеприведенных базовых структурных типов данных - записи (структуры) являются статическими типами, а файлы динамическими (но ограниченно - допустимо только добавление компонентов в конец файла). Массивы имеют промежуточный статус. В классическом Pascal допускаются только статические массивы, а в Java и С# массив объявляется как динамический, но в периоде выполнения должен быть инициализирован (создан), после чего фактически становится статическим.

АТД «Граф» может быть определен как статический тип данных, не допускающий операции добавления и удаления вершин и ребер, и представлен, например, статической матрицей смежности[16]. Но для каких-то приложений АТД «Граф» необходим как динамический тип данных с операциями, позволяющими изменять количество компонентов (вершин) и связи между ними (ребра). В этом случае для представления графа потребуется связная динамическая структура данных (реализуемая на основе указателей).

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

Последовательность можно определить как рекурсивный тип данных - как пару (заголовок, хвост), где заголовок – первый элемент последовательности, а хвост – последовательность остальных её элементов. Но это скорее итерация, чем полноценная рекурсия, однако, если:

§ «Последовательность» – это либо пустая последовательность (), либо (s₁, s₂,… s_k).

§ Где s_i – либо «атом» (элемент базового типа), либо «Последовательность».

то мы получаем рекурсивный (по существу) тип данных (и соответствующую рекурсивную структуру данных – значений этого типа), известный как LISP-список.

Отметим, что LISP-список:

§ Это (фактически) дерево, поскольку - это последовательность элементов (братьев в дереве), которые могут быть LISP-списками (быть корнями поддеревьев).

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

§ В состав операций LISP-списка входят – операция «Получить заголовок» (CAR, HEAD), «Получить хвост» (CDR, TAIL) и «Добавить в список новый элемент в качестве первого» (CONS).

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