Понятие «структура данных». Классификация структур данных.

Понятие «структура данных»

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

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

ПО СПОСОБУ ПРЕДСТАВЛЕНИЯ В ПАМЯТИ

Рассмотреть данные можно с двух сторон:

• Физические структуры данных — отражает способ представления данных в памяти ЭВМ и называется еще структурой хранения или структурой памяти.
• Логические структуры данных — рассмотрение данных без учета их представления в памяти компьютера.

ПО ТИПУ СВЯЗЕЙ

Типы структур данных по наличию связи:

• Несвязные структуры: массивы, векторы, строки, стеки, очереди.
• Связные структуры: связные списки.

ПО СТЕПЕНИ СЛОЖНОСТИ

• Простые структуры данных — такие структуры, которые не могут быть расчленены на составные части большие, чем биты (например массивы).

• Интегрированные структуры данных — структуры данных составными частями которых являются другие структуры данных — простые или интегрированные.

ПО ТИПУ ИЗМЕНЧИВОСТИ

Речь идёт об изменении числа элементов или связей между ними

• Статические — размер памяти компьютера, отводимый для таких данных, постоянен и выделяется на этапе компиляции или выполнения программы:

  • массивы
  • множества
  • векторы

• Полустатические — они имеют переменную длину и простые способы ее изменения; изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения:

  • стек
  • очередь
  • строка

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

  • cвязные списки
  • графы
  • деревья

ПО СПОСОБУ ОРГАНИЗАЦИИ ЭЛЕМЕНТОВ

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

• Нелинейные — деревья, графы, сплетения (он же многосвязный список или плекс — объединяет в себе дерево, граф и список) пример:

  

• Линейные

  • Картезианские (прямоугольные) — структуры названы так по способу записи данных в виде прямоугольных таблиц:
    • A=(6 3) - матрица
    • В = (9, 3, 6, 5) - вектор
    • Z = {7, 6, 0, 2, 3} - множество элементов
  • Строчные - одномерные, динамически изменяемые структуры данных, различающиеся способами включения исключения элементов:
    • стек
    • очередь
    • дек (двусвязная очередь)
    • строка
  • Списковые — логический порядок данных определяется указателями. Любая списковая структура представляет собой набор элементов, каждый из которых состоит из двух полей: в одном из них размещен элемент данных или указатель на него, а в другом — указатель на следующий элемент списка.