Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.
«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», - Линус Торвальдс, создатель Linux.
В этой статье я покажу вам 10 самых распространенных структур данных. Для каждой из них приведены видео и примеры их реализации на JavaScript. Чтобы вы смогли попрактиковаться, я также добавил несколько упражнений из бета-версии новой учебной программы freeCodeCamp.
В статье я привожу примеры реализации этих структур данных на JavaScript: они также пригодятся, если вы используете низкоуровневый язык вроде С. В многие высокоуровневые языки, включая JavaScript, уже встроены реализации большинства структур данных, о которых пойдет речь. Тем не менее, такие знания станут серьезным преимуществом при поиске работы и пригодятся при написании высокопроизводительного кода.
Так устроен связный список
Связный список состоит из группы узлов, которые вместе образуют последовательность. Каждый узел содержит две вещи: фактические данные, которые в нем хранятся (это могут быть данные любого типа) и указатель (или ссылку) на следующий узел в последовательности. Также существуют двусвязные списки: в них у каждого узла есть указатель и на следующий, и на предыдущий элемент в списке.
Основные операции в связном списке включают добавление, удаление и поиск элемента в списке.
Временная сложность связного списка
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════════════╩═══════════════╝
Стек организован по принципу LIFO (Last In First Out, «последним пришёл - первым вышел») . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него.
Так устроен стек
В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).
Временная сложность стека
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════════════╩═══════════════╝
Так устроена очередь
Очередь устроена по принципу FIFO (First In First Out, «первый пришёл - первый вышел»). Это значит, что удалить элемент можно только после того, как были убраны все ранее добавленные элементы.
Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue ) и удалять первый элемент (dequeue ).
Временная сложность очереди
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════════════╩═══════════════╝
Множество хранит значения данных без определенного порядка, не повторяя их. Оно позволяет не только добавлять и удалять элементы: есть ещё несколько важных функций, которые можно применять к двум множествам сразу.
Так устроена структура map
Так работают хэш-таблица и хэш-функция
Хэш-таблица - это похожая на Map структура, которая содержит пары ключ/значение. Она использует хэш-функцию для вычисления индекса в массиве из блоков данных, чтобы найти желаемое значение.
Обычно хэш-функция принимает строку символов в качестве вводных данных и выводит числовое значение. Для одного и того же ввода хэш-функция должна возвращать одинаковое число. Если два разных ввода хэшируются с одним и тем же итогом, возникает коллизия. Цель в том, чтобы таких случаев было как можно меньше.
Таким образом, когда вы вводите пару ключ/значение в хэш-таблицу, ключ проходит через хэш-функцию и превращается в число. В дальнейшем это число используется как фактический ключ, который соответствует определенному значению. Когда вы снова введёте тот же ключ, хэш-функция обработает его и вернет такой же числовой результат. Затем этот результат будет использован для поиска связанного значения. Такой подход заметно сокращает среднее время поиска.
Временная сложность хэш-таблицы
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(1) ║ O(n) ║
║ Insert ║ O(1) ║ O(n) ║
║ Delete ║ O(1) ║ O(n) ║
╚═══════════╩═════════════════╩═══════════════╝
Двоичное дерево поиска
Дерево - это структура данных, состоящая из узлов. Ей присущи следующие свойства:
Временная сложность двоичного дерева поиска
╔═══════════╦═════════════════╦══════════════╗
║ Алгоритм ║Среднее значение ║Худший случай ║
╠═══════════╬═════════════════╬══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(log n) ║ O(n) ║
║ Insert ║ O(log n) ║ O(n) ║
║ Delete ║ O(log n) ║ O(n) ║
╚═══════════╩═════════════════╩══════════════╝
Так устроено префиксное дерево
Каждый узел в языковом префиксном дереве содержит одну букву слова. Чтобы составить слово, нужно следовать по ветвям дерева, проходя по одной букве за раз. Дерево начинает ветвиться, когда порядок букв отличается от других имеющихся в нем слов или когда слово заканчивается. Каждый узел содержит букву (данные) и булево значение, которое указывает, является ли он последним в слове.
Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.
Так устроены минимальная и максимальная кучи
Двоичная куча может быть минимальной или максимальной. В максимальной куче ключ любого узла всегда больше ключей его потомков или равен им. В минимальной куче всё устроено наоборот: ключ любого узла меньше ключей его потомков или равен им.
Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.
Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.
Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.
Граф в виде матрицы смежности
Список смежности можно представить как перечень элементов, где слева находится один узел, а справа - все остальные узлы, с которыми он соединяется.
Матрица смежности - это сетка с числами, где каждый ряд или колонка соответствуют отдельному узлу в графе. На пересечении ряда и колонки находится число, которое указывает на наличие связи. Нули означают, что она отсутствует; единицы - что связь есть. Чтобы обозначить вес каждой связи, используют числа больше единицы.
Существуют специальные алгоритмы для просмотра рёбер и вершин в графах - так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search ) и в глубину (depth-first search ). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.
Тема этой статьи снова касается теории программирования , поэтому придется прибегнуть к различным классификациям и оперировать математическими терминами. Структуры данных – это практически первое, о чем рассказывают в ходе учебных . Оценка сложности алгоритмов – второе. Может показаться, что эти два вопроса мало связаны, но это не так, и по ходу повествования станет ясно почему. Я не буду углубляться в детали, поскольку практика показывает, что в процессе приобретения опыта в в голове остается только самое важное. По-моему, так происходит в любой сфере деятельности. Я постараюсь изложить то, что осталось по этим вопросам в голове у меня.
Структура данных – это форма хранения и представления информации. Определение весьма расплывчато, поэтому специалисты используют различные формы классификации и уточнений. Структуры данных бывают простыми и сложными: представляют атомарную единицу информации или набор однотипных данных. Простые структуры данных характеризуются , например, целочисленный, вещественный, логический, текстовый тип и т.д. Сложные структуры данных делятся на динамические и статические наборы. Динамические в процессе своего жизненного цикла позволяют изменять свой размер (добавлять и удалять элементы), а статические - нет. И наконец, по организации взаимосвязей между элементами сложных структур данных существует следующая классификация:
Приведенная классификация далеко не полная. Элементами сложных структур данных могут выступать как экземпляры простых, так и экземпляры сложных структур данных, например структура данных лес – это список непересекающихся деревьев. Теперь постараюсь дать краткое описание перечисленным классам сложных структур данных. Первый уровень классификации построен на основе различий в способе адресации и поиска отдельных элементов в наборе сложной структуры данных.
Элемент линейной структуры данных характеризуется порядковым номером или индексом в линейной последовательности элементов.
Массив – это в статическая линейная структура однотипных данных, оптимизированная для операций поиска элемента по его индексу. Однозначное местоположение элемента в памяти обеспечивается именно однотипностью элементов в массиве и определяется произведением его индекса на размер памяти, занимаемой одним элементом.
Линейный массив.
Адрес(элемент(index)) = размер_ячейки * index.
Список – это динамическая линейная структура данных, в которой каждый элемент ссылается либо только на предыдущий – однонаправленный линейный список , либо на предыдущий и следующий за ним – двунаправленный линейный список . Достоинство этой структуры данных, помимо возможности изменять размер, - это простота реализации. Также, благодаря наличию ссылок, каждый элемент в списке, в отличие от массива, может занимать разный объем памяти. Адрес первого элемента в линейном списке однозначно определяется адресом самого списка.
Связанный список – это вариант обычного линейного списка, оптимизированный для операций добавления и удаления элементов. Оптимизация заключается в том, что элементы связанного списка не обязаны в памяти располагаться друг за другом. Порядок элементов определяется ссылкой на первый элемент (не обязан быть в самом начале выделенной для списка памяти) и последовательностью ссылок на остальные элементы списка.
Связанный список.
Стек – это динамическая линейная структура данных, для которой определены всего две операции изменения набора элементов: добавление элемента в конец и удаление последнего элемента. Еще говорят, что стек реализует принцип LIFO (Last in, First Out) – последним пришел и первым ушел. Например, в ходе выполнения программного кода, вычислительная машина при необходимости вызвать процедуру или функцию сначала заносит указатель на место ее вызова в стек, чтобы при завершении выполнения ее кода корректно вернуться к следующей после точки вызова инструкции. Такая структура данных называется стеком вызовов подпрограмм.
Стек.
Очередь – очень похожая не стек, динамическая структура данных, с той лишь разницей, что она реализует принцип FIFO (First in, First out) – первым пришел и первым ушел. За примерами в реальной жизни, как понятно из названия, далеко ходить не надо. В программировании с помощью очередей, например, обрабатывают события пользовательского интерфейса, обращения клиентов к и прочие информационные запросы.
Очередь.
Хэш-таблица – наиболее сложный из динамических линейных структур данных тип. Хэш-таблица оптимизирована для быстрого поиска элементов за счет вычисления адреса элемента, как значения хэш-функции. Аргументом хэш-функции является некий ассоциированный с элементом ключ, например, его порядковый номер. Чтобы гарантировать уникальные значения хэш-функции для уникальных значений ключа (исключить коллизии) хэш-таблица, помимо хитрых алгоритмов, также щедро использует оперативную память. Применение хэш-таблиц должно быть оправдано и тщательно продумано.
Элемент в иерархической структуре данных характеризуется ссылкой на вышестоящий в иерархии элемент (или ссылками на нижестоящие элементы) и (необязательно) порядковым номером в линейной последовательности своего уровня (иерархические списки).
Деревья – динамическая иерархическая структура данных, представленная единственным корневым узлом и его потомками. Максимальное количество потомков каждого узла и определяет размерность дерева . Отдельно выделяют двоичные или бинарные деревья , поскольку они используются в алгоритмах сортировки и поиска: каждый узел двоичного дерева поиска соответствует элементу из некоторого отсортированного набора, все его “левые” потомки – меньшим элементам, а все его “правые” потомки – большим элементам. Каждый узел в дереве однозначно идентифицируется последовательностью неповторяющихся узлов от корня и до него – путем. Длина пути и является уровнем узла в иерархии дерева. Для двоичных или бинарных деревьев выделяют следующие виды рекурсивного обхода всех его элементов (в фигурных скобках указан порядок посещения элементов каждого узла, начиная с корня):
Чтобы вывести элементы в порядке их возрастания, дерево поиска следует обойти в симметричном порядке. Чтобы элементы оказались в обратном порядке, в процессе обхода необходимо поменять порядок посещения поддеревьев.
Двоичное (бинарное) дерево.
Иерархический список – симбиоз линейного списка и дерева. Каждый элемент списка может быть также началом списка следующего подуровня иерархии. Пример иерархического списка – структура интернет форумов: последовательность сообщений образует линейный список, в то время как сообщения, являющиеся ответами на другие сообщения, порождают новые потоки обсуждения.
Иерархический список.
Элемент в сетевой структуре данных характеризуется набором связей с другими - соседними элементами. В таких структурах данных ни начальный, ни корневой элементы явно не выделены.
Граф – динамическая сетевая структура данных, представленная набором вершин и ребер – связей между вершинами. Каждая вершина может быть связана с любым числом других вершин или с самой собой. Здесь уже нет никакой четкой иерархии. Если рассматривать узлы дерева, как вершины графа, а связи между узлами дерева разных уровней иерархии, как ребра графа, то само дерево можно считать графом, не содержащим циклов или ациклическим графом. Если для каждого ребра графа определено направление, то это ориентированный граф. Помимо направления каждое ребро графа может иметь свой вес. С помощью графа, например, моделируются транспортные сети и решаются задачи на оптимизацию транспортных потоков. Загруженность или, наоборот, пропускная способность транспортных магистралей задается весом соответствующих ребер.
 Граф. |  Ориентированный граф. |
Элемент в табличной структуре данных характеризуется двумерным индексом: индексом строки и индексом столбца, на пересечении которых он находится. Примерами табличных структур данных являются и таблицы .
Под оценкой сложности алгоритмов подразумевают не интеллектуальные усилия, которые затратили авторы при их разработке, а зависимость количества элементарных операций, выполняемых вычислительной машиной от объема обрабатываемой информации. Например, как будет зависеть число сравнений двух чисел от длины исходной последовательности в процессе работы алгоритма сортировки. Я намеренно немного сузил определение, поскольку в дальнейшем речь будет идти только о количестве элементарных операций. На самом деле сложность алгоритма определяется не только количеством операций, но и объемом привлеченных для решения задачи вычислительных ресурсов, и в первую очередь, оперативной памяти. Чем проще алгоритм, тем он, скорее всего, дольше работает. Сложные и быстрые алгоритмы зачастую используют вспомогательные структуры данных, и, как следствие, расходуют дополнительную память. Закон сохранения энергии или “за все надо платить”. Один из примеров “предельной оптимизации” был рассмотрен ранее – это хэш-таблица. Я лично не знаю, как устроена хэш-таблица и как выглядят хэш-функции (догадываюсь, что не просто), но зато время поиска элементов по ключу практически не зависит от размера таблицы. Далее немного теории.
Оценку сложности алгоритмов проводят с использованием аппарата математического асимптотического анализа и выведения асимптотической оценки сложности.
Асимптотическая оценка сложности обозначается греческой буквой Θ (тета).
f(n) = Θ(g(n)), если существуют c1, c2>0 и n0 такие, что c1*g(n)n0.
Функция g(n) является асимптотически точной оценкой сложности алгоритма - функции f(n), приведенное неравенство называется асимптотическим равенством, а само обозначение Θ символизирует множество функций, которые растут “так же быстро”, как и функция g(n) – т.е. с точностью до умножения на константу. Как следует из приведенного неравенства, оценка Θ являет собой одновременно и верхнюю и нижнюю оценки сложности. Не всегда есть возможность получить оценку в таком виде, поэтому верхнюю и нижнюю оценки иногда определяют отдельно.
Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n).
f(n)= Ο(g(n)), если существует c>0 и n0 такие, что 0n0.
Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n).
f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0n0.
Как следствие: асимптотическая оценка существует только в том случае, если совпадают нижняя и верхняя оценки сложности алгоритма. В практике анализа алгоритмов чаще всего под оценкой сложности понимают верхнюю оценку сложности. Это вполне логично, поскольку наиболее важна оценка времени, за которое алгоритм гарантировано закончит работу, а не время, в пределах которого он точно не завершится.
Ну и в заключении я приведу оценки сложности основных операций с линейными структурами данных, а именно добавление, удаление и поиск элемента по индексу или ключу. Элементарными операциями, в данном случае, являются операции сравнения, перебора, вычисления адреса или перестановки элементов набора структуры данных. В сводной таблице, помимо верхней оценки сложности, также приведены соответствующие перечисленным структурам данных компоненты библиотеки . Таким образом, основные линейные структуры данных уже есть в готовом виде и доступны всем разработчикам программного обеспечения на платформе .
Первоначально процесс программирования предусматривал запись программистом всех алгоритмов непосредственно на машинном языке. Такой подход усугублял и без того трудную задачу разработки алгоритмов и слишком часто приводил к ошибкам, которые необходимо было обнаружить и исправить [процесс, известный как отладка] до того, как работу можно было считать законченной.
Первым шагом на пути к облегчению задачи программирования был отказ от использования цифр для записи команд и операндов непосредственно в той форме, в которой они используются в машине. С этой целью при разработке программ стали широко применять мнемоническую запись различных команд вместо их шестнадцатеричного представления. Например, вместо цифрового кода команды загрузки регистра программист мог теперь написать LOD, а вместо кода команды копирования содержимого регистра в память мог использовать мнемоническое обозначение STO. Для записи операндов были разработаны правила, в соответствии с которыми программист мог присваивать некоторым областям памяти описательные имена [их часто называют идентификаторами] и использовать их при записи команд программы вместо адресов соответствующих ячеек памяти. Такие идентификаторы обычно называют переменными. Это подчеркивает, что, изменяя значение, размещенное в данном участке памяти, мы изменяем значение, связанное с идентификатором, присвоенным этому участку по ходу выполнения программы.
При объявлении в программе переменной обычно одновременно определяют и их тип. Тип данных определяет как интерпретацию конкретных данных, так и операции, которые можно с ними выполнять. К типам данных относятся Integer [целый], Real [действительный], Character [символьный] и Boolean [логический].
Тип Integer используется для обозначения числовых данных, являющихся целыми числами. В памяти они чаще всего представляются в двоичном дополнительном коде. С данными типа Integer можно выполнять обычные арифметические операции и операции сравнения.
Тип Real предназначен для представления числовых данных, которые могут содержать нецелые величины. В памяти они обычно хранятся как двоичные числа с плавающей точкой. Операции, которые можно выполнять с данными Real, аналогичны операциям, выполняемым с данными типа Integer. Однако, что манипуляции, которые следует выполнить, чтобы сложить два элемента данных типа Real, отличаются от манипуляций, необходимых для выполнения действий с переменными типа Integer.
Тип Character используется для данных, состоящих из символов, которые хранятся в памяти в виде кодов ASCII или UNICODE. Данные этого типа можно сравнивать друг с другом [определять, какой из двух символов предшествует другому в алфавитном порядке]; проверять, является ли одна строка символов другой, а также объединять две строки в одну, более длинную строку, дописывая одну из них после другой [операция конкатенации].
Boolean относится к данным, которые могут принимать только два значения True [истина] и False [ложь]. Примером таких данных может служить результат операции сравнения двух чисел. Операции с данными типа Boolean включает проверку, является ли текущее значение переменной True или False.
Основная память машины организована в виде отдельных ячеек с последовательно увеличивающимися адресами. Однако часто эти ячейки используются как основа для реализации иных способов размещения данных. Например, текст обычно рассматривается как длинная строка символов, тогда как информация о продажах может рассматриваться как прямоугольная таблица с числовыми значениями, каждое из которых представляет число сделок, заключенных определенным работником в определенный день. Задача состоит в том, чтобы предоставить пользователю средства, позволяющие оперировать подобными абстрактными структурами, вместо того чтобы вникать в детали истинной организации данных в основной памяти машины. Для правильного использования компьютера необходимо хорошо знать структурные взаимосвязи между данными, основные методы представления структур внутри компьютера, а также методы работы с ними. Для связей между данными в компьютере используются следующие информационные структуры: массив, запись, список, дерево, стек, очередь.
Массив - это структура, содержащая в себе несколько однотипных элементов. Для упорядочивания элементов массива используются индексы. Индексы записываются в скобках после имени массива. Массив с одним индексом называется одномерным, с двумя - двумерным и т.д.
Запись - это структура, состоящая из элементов не обязательно одного типа. Отдельные элементы записи называют полями. Поле в свою очередь тоже может быть записью.
record Student (
FirstName,
LastName,
Group
)
Список - это множество записей, каждая из которых содержит специальное поле - указатель . Указатель связывает запись с какой-либо другой записью или содержит значений Null, которое говорит о том, что значение указателя не определено.
Записи в односвязном списке имеют по одному указателю, при этом они связанны в цепочку:
Стрелка на рисунке говорит о содержимом указателя, а слово Data обозначает совокупностей полей, в которых хранятся данные. Список можно организовать с помощью двумерного массива, все элементы которого с первым индексом, равным 0, предназначены для хранения данных, а элементы с первым индексом, равным 1, являются указателями.
В данном списке записи, содержащие буквы английского алфавита, выстроены в алфавитном порядке. Первая запись в списке содержит символ "A", вторая - "B" и т.д.
Для работы со списком нужно уметь выполнять три основных операции:
Pass() - обход или перемещение вдоль списка;
Add() - добавление новой записи в список;
Delete() - удаление записи из списка.
Кроме операций для работы со списком нужны еще две переменные:
переменная Head, в которой хранится информация о первой записи в списке
переменная Current, которая указывает на текущую запись в списке
В таблице сведены описания некоторых операций над списком, пример реализации которого приведен выше.
| Название операции | Псевдокод |
| Перейти вдоль списка на один шаг |
function Pass(Current) { |
|
function Add(Current, New) { |
|
| Добавить в список запись, на которую указывает переменная New |
function Delete(Current) { |
Записи в двусвязном списке связаны между собой в цепочку, но при этом имеют два поля-указателя. Одно из них указывает на предыдущий элемент в списке, другое - на следующий элемент. Такая структура позволяет перемещаться по списку в двух направлениях: вперед и назад.
Кольцевым называется список, последняя запись которого указывает на первую. В этих списках отсутствует запись с пустым указателем.
Дерево - это разветвленный список, каждая запись которого может содержать несколько указателей. Записи, входящие в дерево, называются узлами. Узлы, у которых все указатели пустые, называются листьями. Верхний начальный узел дерева называется корневым узлом. Во многих задачах достаточно использовать двоичные [бинарные] деревья, узлы которых имеют не более двух указателей.
Пример. Требуется вычислить математическое выражение (3+7)*(2/(3-1)). Представим это выражение в виде дерева:
Каждый узел этого дерева представляет собой запись следующего вида:
record Node (
Operation
Number
LeftPointer
RightPointer
)
Листья дерева содержат числа, остальные узлы - символы операций.
Реализовав описанное дерево на двумерном массиве, мы получим следующую картину:
Для вычисления значения дерева нужно вычислить значения правого и левого поддеревьев, а потом над ними выполнить результирующую операцию. Псевдокод алгоритма решающего поставленную задачу будет иметь вид:
function Calculate (Current) {
if (M=Null) then
Result:= M;
else {
R1:=Calculate(M);
R2:=Calculate(M);
Result:=R1(M)R2;
}
return (Result);
}
Стек - это структура данных, организованная по принципу "последним пришел - первым ушел" . Доступ к данным, хранящимся в стеке, осуществляется через вершину. Данные помещаются в стек последовательно Элемент, помещенный в стек самым первым, оказывается на дне и для того чтобы его извлечь из стека, необходимо сначала извлечь все данные, которые были помещены в стек позже.
При работе со стеком возможны две аварийные ситуации: попытка прочитать данные из пустого стека; попытка занести в стек элемент, когда количество элементов в стеке достигло максимально допустимого количества.
Очередь - это структура данных, организованная по принципу "первым пришел - первым ушел" . В очереди переменное количество данных. При постановке в очередь данные добавляются в хвост, при извлечении берутся из головы.
Хеширование - это метод, обеспечивающий прямой доступ к записям без использования каких-либо дополнительных структур. Процесс можно кратко описать следующим образом. Пространство, где хранятся данные, делится на несколько сегментов. Записи распределяются по этим сегментам согласно некоторому алгоритму, называемому алгоритмом хеширования, преобразующему значение поля ключа в номер сегмента. Каждая запись хранится в сегменте, определяемом этим процессом. Следовательно, запись можно извлечь, применив алгоритм хеширования к значению ее поля ключа и считав записи соответствующего сегмента. Структура данных, сконструированная таким способом, называется хеш-таблицей.
Например, если необходимо организовать хеш-таблицу для хранения прописных букв английского алфавита, то в качестве ключей можно выбрать ASCII-коды символов, а алгоритм хеширования будет отрезать младшие пять битов и формировать на их основе индекс элемента массива для хранения символа:
В общем случае, алгоритм хеширования должен по значению ключа производить значение индекса в границах массива и равномерно распределять ключи по элементам массива. Невыполнение последнего требования приводит к возникновению ситуаций, когда несколько записей попадает в один и тот же сегмент. Данные ситуации называются коллизиями.
Понятие модели данных
Модели данных
Модель данных является инструментом моделирования произвольной предметной области.
Модель данных – это совокупность правил порождения структур данных в базе данных, операций над ними, а также ограничений целостности, определяющих допустимые связи и значения данных, последовательность их изменения . Итак, модель данных состоит из трёх частей:
Здесь можно провести аналогию с языками программирования, в которых тоже есть предопределённые типы структур данных, такие как скалярные данные, вектора, массивы, структуры (например, тип struct в языке Си) и т.д.
Такими операциями являются: создание и модификация структур данных, внесение новых данных, удаление и модификация существующих данных, поиск данных по различным условиям.
Правила целостности определяются типом данных и предметной областью. Например, значение атрибута Счётчик является целым числом, т.е. может состоять только из цифр. А ограничения предметной области таковы, что это число не может быть меньше нуля.
Теперь рассмотрим подробнее наборы, составляющие модель данных.
Структуризация данных базируется на использовании концепций "агрегации" и "обобщения". Один из первых вариантов структуризации данных был предложен Ассоциацией по языкам обработки данных (Conference on Data Systems Languages, CODASYL) (рис. 2.1).
Рис.2.1 Композиция структур данных по версии CODASYL
Элемент данных – наименьшая поименованная единица данных, к которой СУБД может обращаться непосредственно и с помощью которой выполняется построение всех остальных структур. Для каждого элемента данных должен быть определён его тип.
Агрегат данных – поименованная совокупность элементов данных внутри записи, которую можно рассматривать как единое целое. Агрегат может быть простым (включающим только элементы данных, рис. 2.2,а) и составным (включающим наряду с элементами данных и другие агрегаты, рис. 2.2,б).
Рис.2.2 Примеры агрегатов: а) простой и б) составной агрегат
Запись – поименованная совокупность элементов данных или эле-ментов данных и агрегатов. Запись – это агрегат, не входящий в состав никакого другого агрегата; она может иметь сложную иерархическую структуру, поскольку допускается многократное применение агрегации. Различают тип записи (её структуру) и экземпляр записи, т.е. запись с конкретными значениями элементов данных. Одна запись описывает свойства одной сущности ПО (экземпляра). Иногда термин "запись" за-меняют термином "группа".
Пример записи, содержащей сведения о сотруднике, приведён на рис. 2.3.
Рис.2.3 Пример записи типа СОТРУДНИК
Эта запись имеет несколько элементов данных (Номер пропуска, Должность, Пол и т.д.) и три агрегата: простые агрегаты ФИО и Адрес и повторяющийся агрегат Телефоны . (Повторяющийся агрегат может включаться в запись произвольное число раз).
Среди элементов данных (полей записи) выделяются одно или несколько ключевых полей . Значения ключевых полей позволяют классифицировать сущность, к которой относится конкретная запись. Ключи с уникальными значениями называются потенциальными . Каждый ключ может представлять собой агрегат данных. Один из ключей назначается первичным, остальные являются вторичными. Первичный ключ идентифицирует экземпляр записи, его значение должно быть уникальным и обязательным для записей одного типа. Для примера на рис. 2.3 потенциальными ключами являются поля № пропуска и Паспорт , а первичным ключом целесообразнее выбрать поле № пропуска , т.к. оно явно занимает меньше памяти, чем паспортные данные.
Набор (или групповое отношение ) – поименованная совокупность записей, образующих двухуровневую иерархическую структуру. Каждый тип набора представляет собой связь между двумя или несколькими типами записей. Для каждого типа набора один тип записи объявляется владельцем набора, остальные типы записи объявляются членами набора. Каждый экземпляр набора должен содержать только один экземпляр записи типа владельца и столько экземпляров записей типа членов набора, сколько их связано с владельцем. Для группового отношения также различают тип и экземпляр.
Групповые отношения удобно изображать с помощью диаграммы Бахмана, которая названа так по имени одного из разработчиков сетевой модели данных. Диаграмма Бахмана – это ориентированный граф, вершины которого соответствуют группам (типам записей), а дуги – групповым отношениям (рис. 2.4).
Рис. 2.4 Пример диаграммы Бахмана для фрагмента БД "Город"
Здесь запись типа ПОЛИКЛИНИКА является владельцем записей типа ЖИТЕЛЬ диспансеризация . Запись типа ОРГАНИЗАЦИЯ также является владельцем записей типа ЖИТЕЛЬ и они связаны групповым отношением работают . Записи типа РЭУ и типа ЖИТЕЛЬ являются владельцами записей типа КВАРТИРА с отношениями соответственно обслуживают и проживают . Таким образом, запись одного и того же типа может быть членом одного отношения и владельцем другого.
База данных – поименованная совокупность экземпляров групп и групповых отношений. Это самый высокий уровень структуризации данных.
Примечание : структуризация данных по версии CODASYL используется в сетевой и иерар-хической моделях данных. В реляционной модели принята другая структуризация данных, основанная на теории множеств.
Данные, хранящиеся в памяти ЭВМ, представляют собой совокупность нулей и единиц (битов). Биты объединяются в последовательности: байты, слова и т.д. Каждому участку оперативной памяти, который может вместить один байт или слово, присваивается порядковый номер (адрес).
Какой смысл заключен в данных, какими символами они выражены - буквенными или цифровыми, что означает то или иное число - все это определяется программой обработки. Все данные, необходимые для решения практических задач, подразделяются на несколько различных типов, причем понятие тип связывается не только с представлением данных в адресном пространстве, но и со способом их обработки .
Любые данные могут быть отнесены к одному из двух типов: основному (простому), форма представления которого определяется архитектурой ЭВМ, или сложному, конструируемому пользователем для решения конкретных задач.
Данные простого типа это - символы, числа и т.п. элементы, дальнейшее дробление которых не имеет смысла. Из элементарных данных формируются структуры (сложные типы) данных.
Некоторые структуры:
· Массив (функция с конечной областью определения) - простая совокупность элементов данных одного типа, средство оперирования группой данных одного типа. Отдельный элемент массива задается индексом. Массив может быть одномерным, двумерным и т.д. Разновидностями одномерных массивов переменной длины являются структуры типа кольцо, стек, очередь и двухсторонняя очередь .
· Запись (декартово произведение) - совокупность элементов данных разного типа. В простейшем случае запись содержит постоянное количество элементов, которые называют полями . Совокупность записей одинаковой структуры называется файлом . (Файлом называют также набор данных во внешней памяти, например, на магнитном диске). Для того, чтобы иметь возможность извлекать из файла отдельные записи, каждой записи присваивают уникальное имя или номер, которое служит ее идентификатором и располагается в отдельном поле. Этот идентификатор называют ключом .
Такие структуры данных как массив или запись занимают в памяти ЭВМ постоянный объем, поэтому их называют статическими структурами. К статическим структурам относится также множество .
Имеется ряд структур, которые могут изменять свою длину - так называемые динамические структуры . К ним относятся дерево, список, ссылка.
Важной структурой, для размещения элементов, которой требуется нелинейное адресное пространство, является дерево . Существует большое количество структур данных, которые могут быть представлены как деревья. Это, например, классификационные, иерархические, рекурсивные и др. структуры. Более подробно о деревьях рассказано в параграфе 1.2.1.
Рис. 1.1. Классификация типов данных
Выше мы рассмотрели несколько типов структур, являющихся совокупностями элементов данных: массив, дерево, запись. Более сложный тип данных может включать эти структуры в качестве элементов. Например, элементами записи может быть массив, стек, дерево и т.д.
Существует большое разнообразие сложных типов данных, но исследования, проведенные на большом практическом материале, показали, что среди них можно выделить несколько наиболее общих. Обобщенные структуры называют также моделями данных , т.к. они отражают представление пользователя о данных реального мира.
Любая модель данных должна содержать три компоненты:
1. структура данных - описывает точку зрения пользователя на представление данных.
2. набор допустимых операций , выполняемых на структуре данных. Модель данных предполагает, как минимум, наличие языка определения данных (ЯОД), описывающего структуру их хранения, и языка манипулирования данными (ЯМД), включающего операции извлечения и модификации данных.
3. ограничения целостности - механизм поддержания соответствия данных предметной области на основе формально описанных правил.
В процессе исторического развития в СУБД использовалось следующие модели данных:
· иерархическая,
· сетевая,
· реляционная.
В последнее время все большее значение приобретает объектно-ориентированный подход к представлению данных.
Вопросы представления данных тесно связаны с операциями, при помощи которых эти данные обрабатываются. К числу таких операций относятся: выборка, изменение, включение и исключение данных. В основе всех перечисленных операций лежит операция доступа , которую нельзя рассматривать независимо от способа представления.
В задачах поиска предполагается, что все данные хранятся в памяти с определенной идентификацией и, говоря о доступе, имеют в виду, прежде всего, доступ к данным (называемым ключами), однозначно идентифицирующим связанные с ними совокупности данных.
Пусть нам необходимо организовать доступ к файлу, содержащему набор одинаковых записей, каждая из которых имеет уникальное значение ключевого поля. Самый простой способ поиска - последовательно просматривать каждую запись в файле до тех пор, пока не будет найдена та, значение ключа которой удовлетворяет критерию поиска. Очевидно, этот способ весьма неэффективен, поскольку записи в файле не упорядочены по значению ключевого поля. Сортировка записей в файле также неприменима, поскольку требует еще больших затрат времени и должна выполняться после каждого добавления записи. Поэтому, поступают следующим образом - ключи вместе с указателями на соответствующие записи в файле копируют в другую структуру, которая позволяет быстро выполнять операции сортировки и поиска. При доступе к данным вначале в этой структуре находят соответствующее значение ключа, а затем по хранящемуся вместе с ним указателю получают запись из фала.
Существуют два класса методов, реализующих доступ к данным по ключу:
· методы поиска по дереву,
· методы хеширования.
Определение: Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:
1. между узлами имеет место отношение типа "исходный - порожденный";
2. есть только один узел, не имеющий исходного узла. Он называется корнем;
3. все узлы за исключением корня имеют только один исходный; каждый узел может иметь несколько порожденных узлов;
4. отношение "исходный - порожденный" действует только в одном направлении, т.е. ни один потомок некоторого узла не может стать для него предком.
Число порожденных отдельного узла (число поддеревьев данного корня) называется его степенью . Узел с нулевой степенью называют листом или концевым узлом. Максимальное значение степени всех узлов данного дерева называется степенью дерева .
Если в дереве между порожденными узлами, имеющими общий исходный, считается существенным их порядок, то дерево называется упорядоченным . В задачах поиска почти всегда рассматриваются упорядоченные деревья.
Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказывается меньше ключа, поиск продолжается в левом поддереве, а в случае, когда больше ключа - в правом поддереве. Увеличив уровень на 1, повторяют сравнение, считая текущий узел корнем.
Пример: Пусть дан список студентов, содержащий их фамилии и средний бал успеваемости (см. таблицу 1.1). В качестве ключа используется фамилия студента. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычисляться как ([номер_записи ] -1) * [длина_записи ] . Пусть аргумент поиска "Петров". На рисунке 1.2 показано одно из возможных для этого набора данных бинарное дерево поиска и путь поиска.
|
Таблица 1.1 |
|
|
Васильев |
|
|
Кузнецов |
|
|
Тихомиров |
|
Рис. 1.2. Поиск по бинарному дереву
Заметим, что здесь используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.
Бинарные деревья особенно эффективны в случае, когда множество ключей заранее неизвестно, либо когда это множество интенсивно изменяется. Очевидно, что при переменном множестве ключей лучше иметь сбалансированное дерево .
Определение: Бинарное дерево называют сбалансированным (balanced ), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1.
При поиске данных во внешней памяти очень важной является проблема сокращения числа перемещений данных из ВЗУ в оперативную память. Поэтому, в данном случае по сравнению с бинарными деревьями более выгодными окажутся сильно ветвящиеся деревья - т.к. их высота меньше, то при поиске потребуется меньше обращений к внешней памяти. Наибольшее применение в этом случае получили В-деревья (В - balanced )
Определение: В-деревом порядка n называется сильно ветвящееся дерево степени 2n+1, обладающее следующими свойствами:
Для такого дерева:
· сравнительно просто может быть организован последовательный доступ, т.к. все листья расположены на одном уровне;
· при добавлении и изменении ключей все изменения ограничиваются, как правило, одним узлом.
Рис. 1.3.Сбалансированное дерево
В -дерево, в котором истинные значения содержатся только в листьях (концевых узлах), называется В+- деревом . Во внутренних узлах такого дерева содержатся ключи-разделители, задающие диапазон изменения ключей для поддеревьев.
Подробнее о различных видах сбалансированных деревьев, а также методах их реализации можно прочитать в литературе, список которой приведен в конце страницы. Следует отметить, что B - деревья наилучшим образом подходят только для организации доступа к достаточно простым (одномерным) структурам данных. Для доступа к более сложным структурам, таким, например, как пространственные (многомерные) данные в последнее время все чаще используют R -деревья.
R -дерево (R -Tree ) это индексная структура для доступа к пространственным данным, предложенная А. Гуттманом (Калифорнийский университет, Беркли). R-дерево допускает произвольное выполнение операций добавления, удаления и поиска данных без периодической переиндексации.
Для представления данных используются записи, каждая из которых имеет уникальный идентификатор (tuple-identifier ). В каждом концевом узле (листе) дерева содержится запись вида (I,tuple-identifier ) , где I - n -мерный параллелепипед, содержащий указатели на пространственные данные (его также называют minimal bounding rectangle , MBR), а каждый элемент в tuple-identifier содержит верхнюю и нижнюю границу параллелепипеда в соответствующем измерении.
Неконцевые узлы содержат записи вида (I, childnode-pointer ) , где I минимальный ограничивающий параллелепипед для MBR всех узлов, производных по отношению к данному. Childnode-pointer - это указатель на производные узлы.
Пусть M и m <= M/2 соответственно максимальное и мимимальное количество элементов, которое может быть размещено в узле. Тогда свойства R-дерева можно описать следующим образом:
· R-Tree является сильно сбалансированным деревом, т.е. все листья находятся на одном уровне.
· Корневой узел имеет, как минимум, двух потомков.
· Для каждого элемента (I, childnode-pointer ) в неконцевом узле I является наименьшим возможным параллелепипедом, т.е. содержит все параллелепипеды производных узлов.
· Каждый концевой узел (лист) содержит от m до M индексных записей.
· Для каждой индексной записи (I, tuple-identifier ) в концевом узле I является параллелепипедом, который содержит n -мерный объект данных, на который указывает tuple-identifier .
Этот метод используется тогда, когда все множество ключей заранее известно и на время обработки может быть размещено в оперативной памяти. В этом случае строится специальная функция, однозначно отображающая множество ключей на множество указателей, называемая хеш-функцией (от английского слова "to hash " - резать, измельчать). Имея такую функцию можно вычислить адрес записи в файле по заданному ключу поиска. В общем случае, ключевые данные, используемые для определения адреса записи, организуются в виде таблицы, называемой хеш-таблицей.
Если множество ключей заранее неизвестно или очень велико, то от идеи однозначного вычисления адреса записи по ее ключу отказываются, а хеш-функцию рассматривают просто как функцию, рассеивающую множество ключей во множество адресов.
