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

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

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

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

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

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

Большинство дополнительных структур данных можно реализовать двумя способами:

· статически на основе массива

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

Структуры данных

файлы

линейные

нелинейные

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

Поскольку весьма часто возможны несколько способов реализации одной и той же структуры данных, возникает вопрос о едином унифицированном способе описания подобных структур. Такое описание принято называть абстрактным типом данных (АТД).

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

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