В информатике структура данных представляет собой набор значений данных, взаимосвязь между этими значениями и функциями или операциями, которые можно применять к данным.
Чтобы полностью понять изложенную выше концепцию, нам необходимо понять концепцию типов данных.
Тип данных относится к определенному типу данных, то есть к набору возможных значений и основных операций над этими значениями. Он сообщает системному компилятору или интерпретатору, как программист собирается использовать данные.
Типы данных состоят из двух основных вещей
- домен (набор значений)
- набор операций, которые могут быть применены к значениям
Почти все языки программирования явно включают понятие типов данных, хотя в разных языках может использоваться разная терминология.
Общие типы данных включают
- Целое число
- Число с плавающей запятой
- Характер
- Нить
- логический
Абстрактные типы данных (ADT)
Любые данные, не определяющие реализацию, являются абстрактным типом данных. Например, стек (который является абстрактным типом данных) может быть реализован как массив (непрерывный блок памяти, содержащий несколько значений) или как связанный список (набор несмежных блоков памяти, связанных указателями).
ADT могут обрабатываться кодом, который не знает и не «заботится» о том, какие базовые типы в них содержатся.
Примеры включают
- Очередь (список в порядке поступления)
- Набор (может хранить определенные значения без какого-либо определенного порядка и без повторяющихся значений)
- Стек (структура данных «последний пришел – первый ушел»)
- Дерево (иерархическая структура)
- График
- Список
- Хэш, словарь, карта или массив ассоциаций; простая гибкая вариация записи, в которой пары имя-значение могут быть добавлены и обнаружены свободно
- Умный указатель (абстрактный аналог указателя)
Таким образом, структуры данных также можно назвать реализацией абстрактного типа данных в конкретном языке программирования. Структуры данных также могут называться «агрегатами данных».
ADT можно разделить на 2
- Линейные структуры данных
- Нелинейные структуры данных
Линейные структуры данных хранятся и доступны линейно в памяти компьютера, например, списки, стеки, очереди и массивы.
Нелинейные структуры данных не хранятся линейно в памяти компьютера, но элементы данных могут обрабатываться с использованием некоторых методов или правил.
