При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.
Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов STL языка C++.
Фундаментальными строительными блоками для большей части структур данных являются массивы, записи (см. конструкцию struct в языке Си и конструкцию record в языке Паскаль), размеченные объединения (см. конструкцию union в языке Си) и ссылки.
Линейные структуры данных (Linear data structures)
Список (List)
Массив (Array)
Битовые поля (Bitmaps)
Изображения (Images)
Поля высот (Heightfields)
Параллельный массив (Parallel array)
Дерево отрезков
Дерево Фенвика
Связный список (Linked list)
Список с пропусками (Skip list)
Развёрнутый связный список (Unrolled linked list)
XOR-связный список (Xor linked list)
V-список (VList)
Ассоциативный массив (Associative array a.k.a. dictionary or map) — также известен как словарь или карта
Хеш-таблица (Hash table)
Стек (Stack a.k.a. LIFO Last in, first out) — также известен как ЛИФО
Очередь (Queue a.k.a. FIFO First in, first out) — также известен как ФИФО
Очередь с приоритетом (Priority queue), одна из реализаций - - Двоичная куча, см. ниже
Дек (Deque) — двусвязная очередь
Буферное окно (Buffer gap)
Граф (Graph)
Список рёбер (Adjacency list)
Представление графа в разорванном виде (Disjoint-set data structure)
Представление графа в виде стеков (Graph-structured stack)
Сценограф (Scene graph)
Деревья
2-3 дерево
Красно-чёрное дерево
BSP дерево
M-Way Tree
B-дерево
Двоичное дерево поиска (Binary search tree)
Самобалансирующееся дерево поиска (Self-balancing binary search tree)
АВЛ-дерево (AVL tree)
Дерево Фибоначчи
Красно-чёрное дерево (Red-black tree)
Дерево со штрафами (Scapegoat tree)
Расширяющееся дерево (Splay tree)
Дерево ван Емде Боаса (van Emde Boas tree)
Дерево остатков (Radix tree)
Интервальное дерево (Interval tree)
Куча (Heap)
Двоичная куча (Binary heap)
Биномиальная куча (Binomial heap)
Фибоначчиева куча (Fibonacci heap)
Сливаемая куча (Mergable heap)
2-3-куча (2-3 heap)
Мягкая куча (Soft heap)
Дерево разбора (Parse tree)
Квад-дерево (Quadtree) и Окт-дерево (Octree)
Суффиксное дерево (Suffix tree)
Префиксное дерево (Trie)
Патриция (дерево) (Patricia trie)
Другие структуры данных
Помеченное объединение (Tagged union)
Объединение (Union)
Таблица (Table)
Абстрактные структуры данных
Абстрактные структуры данных предназначены для удобного хранения и доступа к информации. Они предоставляют удобный интерфейс для типичных операций с хранимыми объектами, скрывая детали реализации от пользователя.
Пример: Языки программирования высокого уровня(Паскаль, Си..) предоставляют удобный интерфейс для чисел: операции +, *, = .. и т.п, но при этом скрывают саму реализацию этих операций, машинные команды.
Конкретные реализации АТД называются структурами данных.
В программировании абстрактные типы данных обычно представляются в виде интерфейсов, которые скрывают соответствующие реализации типов. Программисты работают с абстрактными типами данных исключительно через их интерфейсы, поскольку реализация может в будущем измениться. Такой подход соответствует принципу инкапсуляции в объектно-ориентированном программировании. Сильной стороной этой методики является именно сокрытие реализации. Раз вовне опубликован только интерфейс, то пока структура данных поддерживает этот интерфейс, все программы, работающие с заданной структурой абстрактным типом данных, будут продолжать работать. Разработчики структур данных стараются, не меняя внешего интерфейса и семантики функций, постепенно дорабатывать реализации, улучшая алгоритмы по скорости, надежности и используемой памяти.
Различие между абстрактными типами данных и структурами данных, которые реализуют абстрактные типы, можно пояснить на следующем примере. Абстрактный тип данных список может быть реализован при помощи массива или линейного списка, с использованием различных техник динамического выделения памяти. Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализации.
Абстрактные типы данных позволяют достичь модульности программных продуктов и иметь несколько альтернативных взаимозаменяемых реализаций отдельного модуля.
Список
Стек
Очередь
Ассоциативный массив
Очередь с приоритетом
Базы данных
| База данных 1) структурированный организованный набор данных, описывающий характеристики каких-либо физических или виртуальных систем 2) структурированная организованная совокупность блоков информационных элементов, представленных на машиночитаемых носителях, характеризующих актуальное состояние некоторой предметной области и предназначенных и пригодных для оперативного решения пользовательских задач с использованием средств вычислительной техники |
Обращение к базам данных осуществляется с помощью системы управления базами данных (СУБД).
База данных обладает следующими признаками:
- база данных содержит множество данных, необходимых для решения конкретных задач многих пользователей
- данные в БД структурированы и связаны между собой, при этом структура данных не зависит от программ, использующих их
- данные представлены на машиночитаемых носителях в форме, пригодной для их оперативного использования с применением СУБД
Использование БД характерузуется следующими свойствами:
- оперативность
- полная доступность
- гибкость
Можно изменять состав и форму выдачи данных, вносить изменения в саму БД.
- целостность данных
Все значения данных правильно отражают ПО и подчиняются правилам взаимной непротиворечивости. Для поддержания целостности необходимы проверка и восстановление или корректировка.
- защищенность БД
Наличие средств, обеспечивающих предотвращение доступа к информации лиц, не имеющих соотв. разрешения, умышленного разрушения или изменения данных.
- безопасность БД
Содержащиеся в БД данные не причинят вреда пользователю при правильном их применении.
- эффективность (степень соответствия результатов использования затратам на создание)
СУБД
| Система управления базами данных комплекс программных и лингвистических средств, предназначенный для создания, ведения и эксплуатации баз данных многими пользователями. |
Основные функции СУБД:
- управление данными во внешней памяти
- управление данными в оперативной памяти
- журнализация изменений, резервное копирование и восстановление базы данных после сбоев
- поддержка языков БД (язык определения данных, язык манипулирования данными) (!)
Компоненты СУБД:
- ядро (отвечает за управление данными во внешней и оперативной памяти и журнализацию)
- процессор языка базы данных
- подсистема поддержки времени исполнения (интерпретирует программы манипуляции данными, создающие пользовательский интерфейс с СУБД)
- сервисные программы (внешние утилиты) (обеспечивают ряд дополнительных возможностей по обслуживанию информационной системы)
- словарь данных содержит информацию о структуре БД.
- индексы служат для быстрого поиска данных с конкретными значениями (атрибутами)
- данные
Классификация СУБД:
По модели данных:
Иерархические
Сетевые
Реляционные
Объектно-реляционные
Объектно-ориентированные
По организации хранения данных:
- локальные (все части локальной СУБД размещаются на одном компьютере)
- распределённые (части СУБД могут размещаться на двух и более компьютерах)
По способу доступа:
- файл-серверные
Файлы передаются на рабочие станции, где производится их обработка. На сервере происходит только хранение данных.
В файл-серверных СУБД файлы данных располагаются централизованно на файл-сервере. Ядро СУБД располагается на каждом клиентском компьютере. Доступ к данным осуществляется через локальную сеть. Синхронизация чтений и обновлений осуществляется посредством файловых блокировок. Преимуществом этой архитектуры является низкая нагрузка на ЦП сервера, а недостатком — высокая загрузка локальной сети.
На данный момент файл-серверные СУБД считаются устаревшими.
Примеры: Microsoft Access, Paradox, dBase.
- клиент-серверные
Сервер обеспечивает не только хранение данных, но и основной объем обработки данных.
Спецификой архитектуры клиент-сервер является использования языка запросов SQL.
Такие СУБД состоят из клиентской части (которая входит в состав прикладной программы) и сервера. Клиент-серверные СУБД, в отличие от файл-серверных, обеспечивают разграничение доступа между пользователями и мало загружают сеть и клиентские машины. Сервер является внешней по отношению к клиенту программой, и по надобности его можно заменить другим. Недостаток клиент-серверных СУБД в самом факте существования сервера (что плохо для локальных программ — в них удобнее встраиваемые СУБД) и больших вычислительных ресурсах, потребляемых сервером.