Структуры данных. Классификация структур данных.

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

способом объединения отдельных компонент в единую структуру
способами обработки как отдельных компонент структуры так и всей структуры в целом.

Например, классическая структура МАССИВ есть объединение однотипных компонент, причем каждая компонента имеет фиксированный порядковый номер-индекс размещения в массиве. Доступ к элементам массива выполняется именно по этому индексу. Аналогично, структура ЗАПИСЬ является объединением разнотипных компонент-полей, доступ к которым выполняется по имени поля.
Обе эти стандартные структуры служат основой построения других важных структур, широко используемых в различных приложениях: стеки, очереди, списки, деревья, графы. Каждая из них имеет свои особенности объединения компонент и особенности обработки. Основные структуры данных представлены на следующей схеме.
Большинство дополнительных структур данных можно реализовать двумя способами:

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

Каждый из этих способов имеет свои преимущества и недостатки, которые будут рассмотрены в последующих разделах при детальном описании каждой из структур данных.
Поскольку весьма часто возможны несколько способов реализации одной и той же структуры данных, возникает вопрос о едином унифицированном способе описания подобных структур. Такое описание принято называть абстрактным типом данных (АТД).
АТД – это формализованное описание (модель), определяющее организацию и набор возможных операций с описываемыми данными. Важность АТД определяется тем, что они позволяют отделить описание данных от их реализации и скрыть от пользователя детали реализации, оставив ему только открытый слой взаимодействия с данными – так называемый интерфейс. Даже простейшие встроенные типы данных можно описать в терминах АТД, хоть это и не имеет большого практического значения, т.к. простейшие типы встроены в сам язык программирования. Понятие АТД получило свое дальнейшее развитие в объектно-ориентированном программировании в виде фундаментального понятия “класс”, рассмотрение которого выходит за рамки данного пособия.
Прежде чем перейти к детальному описанию основных структур данных, необходимо рассмотреть вопрос использования в программах переменных указательного типа и механизма динамического распределения памяти.