Абстрактный тип данных (АТД) – это математическая модель и набор операторов, определенных в рамках данной модели.

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

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

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

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

В общем случае между логической и соответствующей ей физической структурами существует различие. Известны процедуры, выполняющие отображение логической структуры в физическую и, наоборот. Кроме того, эти процедуры обеспечивают доступ к физическим структурам и выполнение над ними различных операций.

Различают:

- простые (базовые, примитивные) структуры (типы) данных,

- интегрированные (структурированные, композитные, сложные).

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

Связные и несвязные структуры данных

В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать:

 - несвязные структуры (векторы, массивы – плюс быстрый поиск, минус – фиксированный размер строки, стеки – последний вошол и пследний вышел, мейн лежит внизу, пака он не завершится, то не завершится и сама программа, очереди – последний вошол, паследний и вышел)

 - связные структуры (связные списки).  Быстрая вставка данных и их удаление, не фиксированный размер. Занимает больше памяти, тк хранит не только данные ячейки, но и адрес на них. Плюс медленный поиск

Массив для хранения, а список для манипуляций

Статические, полустатические и динамические структуры, привести классификацию.

По признаку изменчивости различают структуры:

- статические,

- полустатические,

- динамические.

В зависимости от упорядоченности элементов структуры данных делят:

- на линейные,

- нелинейные.

 По признаку взаимного расположения элементов в памяти линейные структуры можно разделить:

- на структуры с последовательным распределением элементов в памяти (векторы, строки, массивы, стеки, очереди)

 - структуры с произвольным связным распределением элементов в памяти (односвязные, двусвязные списки).

Информация по каждому типу однозначно определяет:

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

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

- множество допустимых операций, которые применимы к объекту описываемого типа.

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

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

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