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

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

Определение 1

Структурой данных называется множество элементов данных и внутренних связей между ними.

Существуют простые и интегрированные структуры данных. Простые структуры данных сводятся к битам и организуются непосредственно из битов. К простым структурам относятся:

• числовые;
• битовые;
• символьные;
• логические;
• указатели.

Интегрированные структуры данных организуются из простых и других интегрированных структур.

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

Определение 2

Изменчивостью структуры называется изменение числа элементов и связей между ними.

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

• Статические (векотр, массив, множество, запись, таблица);
• Динамические (стек, очередь, строка, линейные связанные списки, разветвленные связанные списки, графы, деревья.).

Элементы в структуре могут быть упорядоченными и неупорядоченными. В соответствии с этим признаком структуры делятся на

• Нелинейные(многосвязный список, граф, дерево);
• Линейные с последовательным распределением (вектор, строка, массив, стек, очередь);
• Линейные с произвольным связным распределением (односвязный, и двусвязный список).

Простые структуры и типы данных

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

Целый тип используется для представления количества дискретных объектов. Целые числа могут быть беззнаковыми или отрицательными. Внутреннее представление целого числа может занимать 1, 2 или 4 байта.

Вещественные числа представляются в виде формата с плавающей точкой . Число с плавающей точкой представляется с помощью двух целый чисел – порядка и матиссы, а также знака.

В случае двоичной системы счисления B=2.

Десятичный тип поддерживают не все языки программирования. Число такого типа представляется в виде m десятичных цифр из которых d цифр находятся справа от десятичной точки.

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

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

Символьный тип позволяет представить данные в виде последовательности символов некоторого заранее предопределенного множества. Каждый символ множества хранится в памяти в виде последовательности битов. Соответствие символов и таких последовательностей называется кодировкой. Различные кодировки представляют символы в виде битовых последовательностей различной длины.

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

Примеры статических структур

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

Пример 1

Пусть дан массив с именем A.

Тогда элемент А равен 30.

Пример 2

Двумерный массив – это массив, каждый элемент которого сам является одномерным массивом.

В двумерном массиве у каждого элемента есть два индекса.

Определение 4

Записи (хеш-массивы, ассоциативные массивы) – это массивы, которые индексируются не натуральными числами, а строками.

Индекс элемента в таком массиве называется ключом. Для обращения к элементу используется имя массива и индекс.

Пример 3

Пусть дан хеш-массив с именем B.

Тогда элемент массива B[‘овощ’] равен ‘огурец’.

Примеры динамических структур

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

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

Для того чтобы извлечь элемент, нужно сначала последовательно извлечь все элементы, добавленные после него. Элемент, добавленный первым, можно извлечь только в самую последнюю очередь.

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

• Перевод

Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью 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) ║ ╚═══════════╩═════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Стеки

Стек организован по принципу 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) ║ ╚═══════════╩═════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Очереди

Так устроена очередь

Очередь устроена по принципу 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) ║ ╚═══════════╩═════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Множества

Множество хранит значения данных без определенного порядка, не повторяя их. Оно позволяет не только добавлять и удалять элементы: есть ещё несколько важных функций, которые можно применять к двум множествам сразу.

• Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без дубликатов).
• Пересечение анализирует два множества и  создает еще одно из тех элементов, которые присутствуют в обоих изначальных множествах.
• Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в другом.
• Подмножество выдает булево значение, которое показывает, включает ли одно множество все элементы другого множества.

Упражнения от freeCodeCamp

Map

• добавлять пары в коллекцию;
• удалять пары из коллекции;
• изменять существующей пары;
• искать значение, связанное с определенным ключом.

Так устроена структура map

Упражнения от freeCodeCamp

Хэш-таблицы

Так работают хэш-таблица и хэш-функция

Хэш-таблица - это похожая на Map структура, которая содержит пары ключ/значение. Она использует хэш-функцию для вычисления индекса в массиве из блоков данных, чтобы найти желаемое значение.

Обычно хэш-функция принимает строку символов в качестве вводных данных и выводит числовое значение. Для одного и того же ввода хэш-функция должна возвращать одинаковое число. Если два разных ввода хэшируются с одним и тем же итогом, возникает коллизия. Цель в том, чтобы таких случаев было как можно меньше.

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

Временная сложность хэш-таблицы ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(1) ║ O(n) ║ ║ Insert ║ O(1) ║ O(n) ║ ║ Delete ║ O(1) ║ O(n) ║ ╚═══════════╩═════════════════╩═══════════════╝

Упражнения от freeCodeCamp

Двоичное дерево поиска

Двоичное дерево поиска

Дерево - это структура данных, состоящая из узлов. Ей присущи следующие свойства:

• Каждое дерево имеет корневой узел (вверху).
• Корневой узел имеет ноль или более дочерних узлов.
• Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.

• Каждый узел имеет до двух дочерних узлов (потомков).
• Каждый узел меньше своих потомков справа, а его потомки слева меньше его самого.

Временная сложность двоичного дерева поиска ╔═══════════╦═════════════════╦══════════════╗ ║ Алгоритм ║Среднее значение ║Худший случай ║ ╠═══════════╬═════════════════╬══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(log n) ║ O(n) ║ ║ Insert ║ O(log n) ║ O(n) ║ ║ Delete ║ O(log n) ║ O(n) ║ ╚═══════════╩═════════════════╩══════════════╝

Упражнения от freeCodeCamp

Префиксное дерево

Так устроено префиксное дерево

Каждый узел в языковом префиксном дереве содержит одну букву слова. Чтобы составить слово, нужно следовать по ветвям дерева, проходя по одной букве за раз. Дерево начинает ветвиться, когда порядок букв отличается от других имеющихся в нем слов или когда слово заканчивается. Каждый узел содержит букву (данные) и булево значение, которое указывает, является ли он последним в слове.

Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.

Упражнения от freeCodeCamp

Двоичная куча

Так устроены минимальная и максимальная кучи

Двоичная куча может быть минимальной или максимальной. В максимальной куче ключ любого узла всегда больше ключей его потомков или равен им. В минимальной куче всё устроено наоборот: ключ любого узла меньше ключей его потомков или равен им.

Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.

Упражнения от freeCodeCamp

Граф

Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.

Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.

Граф в виде матрицы смежности

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

Матрица смежности - это сетка с числами, где каждый ряд или колонка соответствуют отдельному узлу в графе. На пересечении ряда и колонки находится число, которое указывает на наличие связи. Нули означают, что она отсутствует; единицы - что связь есть. Чтобы обозначить вес каждой связи, используют числа больше единицы.

Существуют специальные алгоритмы для просмотра рёбер и вершин в графах - так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search ) и в глубину (depth-first search ). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.

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

Кольцевой список

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

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

Говоря о не вычислительной технике, можно показать ни один случай, где у информации видна явная структура. Наглядным примером служат книги самого разного содержания. Они разбиты на страницы, параграфы и главы, имеют, как правило, оглавление, то есть интерфейс пользования ими. В широком смысле, структурой обладает всякое живое существо, без нее органика навряд-ли смогла бы существовать.

Вполне вероятно, читателю приходилось сталкиваться со структурами данных непосредственно в информатике, например, с теми, что встроены в язык программирования. Часто они именуются типами данных. К таковым относятся: массивы, числа, строки, файлы и т. д.

Методы хранения информации, называемые «простыми», т. е. неделимыми на составные части, предпочтительнее изучать вместе с конкретным языком программирования, либо же глубоко углубляться в суть их работы. Поэтому здесь будут рассмотрены лишь «интегрированные» структуры, те которые состоят из простых, а именно: массивы, списки, деревья и графы.

Массивы.

Массив – это структура данных с фиксированным и упорядоченным набором однотипных элементов (компонентов). Доступ к какому-либо из элементов массива осуществляется по имени и номеру (индексу) этого элемента. Количество индексов определяет размерность массива. Так, например, чаще всего встречаются одномерные (вектора) и двумерные (матрицы) массивы.

Первые имеют один индекс, вторые – два. Пусть одномерный массив называется A, тогда для получения доступа к его i-ому элементу потребуется указать название массива и номер требуемого элемента: A[i]. Когда A – матрица, то она представляема в виде таблицы, доступ к элементам которой осуществляется по имени массива, а также номерам строки и столбца, на пересечении которых расположен элемент: A, где i – номер строки, j – номер столбца.

В разных языках программирования работа с массивами может в чем-то различаться, но основные принципы, как правило, везде одни. В языке Pascal, обращение к одномерному и двумерному массиву происходит точно так, как это показано выше, а, например, в C++ двумерный массив следует указывать так: A[i][j]. Элементы массива нумеруются поочередно. На то, с какого значения начинается нумерация, влияет язык программирования. Чаще всего этим значением является 0 или 1.

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

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

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

Списки.

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

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

В односвязном списке, приведенным выше, начальным элементом является Head list (голова списка [произвольное наименование]), а все остальное называется хвостом. Хвост списка составляют элементы, разделенные на две части: информационную (поле info) и указательную (поле next). В последнем элементе вместо указателя, содержится признак конца списка – nil.

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

Двусвязный список

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

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

Кольцевой список

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

Кроме различия по связям, списки делятся по методам работы с данными. О некоторых таких методах сказано далее.

Стек.

Стек

Стек характерен тем, что получить доступ к его элементом можно лишь с одного конца, называемого вершиной стека, иначе говоря: стек – структура данных, функционирующая по принципу LIFO (last in - first out, «последним пришёл - первым вышел»). Изобразить эту структуру данных лучше в виде вертикального списка, например, стопки каких-либо вещей, где чтобы воспользоваться одной из них нужно поднять все те вещи, что лежат выше нее, а положить предмет можно лишь на вверх стопки.

В показанном односвязном списке операции над элементами происходят строго с одного конца: для включения нужного элемента в пятую по счету ячейку необходимо исключить тот элемент, который занимает эту позицию. Если бы было, например 6 элементов, а вставить конкретный элемент требовалось также в пятую ячейку, то исключить бы пришлось уже два элемента.

Очередь.

Структура данных «Очередь» использует принцип организации FIFO (First In, First Out - «первым пришёл - первым вышел»). В некотором смысле такой метод более справедлив, чем тот, по которому функционирует стек, ведь простое правило, лежащее в основе привычных очередей в различные магазины, больницы считается вполне справедливым, а именно оно является базисом этой структуры. Пусть данное наблюдение будет примером. Строго говоря, очередь – это список, добавление элементов в который допустимо, лишь в его конец, а их извлечение производиться с другой стороны, называемой началом списка.

Дек

Дек (deque - double ended queue, «двухсторонняя очередь») – стек с двумя концами. Действительно, несмотря конкретный перевод, дек можно определять не только как двухстороннюю очередь, но и как стек, имеющий два конца. Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец, и то же самое справедливо для операции извлечения.

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

Графы.

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

Граф – совокупность точек, соединенных линиями. Точки называются вершинами (узлами), а линии – ребрами (дугами).

Как показано на рисунке различают два основных вида графов: ориентированные и неориентированные. В первых ребра являются направленными, т. е. существует только одно доступное направление между двумя связными вершинами, например из вершины 1 можно пройти в вершину 2, но не наоборот. В неориентированном связном графе из каждой вершины можно пройти в каждую и обратно. Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

Ребра графа необязательно должны быть прямыми, а вершины обозначаться именно цифрами, так как показано на рисунке. К тому же встречаются такие графы, ребрам которых поставлено в соответствие конкретное значение, они именуются взвешенными графами, а это значение – весом ребра. Когда у ребра оба конца совпадают, т. е. ребро выходит из вершины F и входит в нее, то такое ребро называется петлей.

Графы широко используются в структурах, созданных человеком, например в компьютерных и транспортных сетях, web-технологиях. Специальные способы представления позволяют использовать граф в информатике (в вычислительных машинах). Самые известные из них: «Матрица смежности», «Матрица инцидентности», «Список смежности», «Список рёбер». Два первых, как понятно из названия, для репрезентации графа используют матрицу, а два последних – список.

Деревья.

Неупорядоченное дерево

Дерево как математический объект это абстракция из соименных единиц, встречающихся в природе. Схожесть структуры естественных деревьев с графами определенного вида говорит о допущении установления аналогии между ними. А именно со связанными и вместе с этим ациклическими (не имеющими циклов) графами. Последние по своему строению действительно напоминают деревья, но в чем то и имеются различия, например, принято изображать математические деревья с корнем расположенным вверху, т. е. все ветви «растут» сверху вниз. Известно же, что в природе это совсем не так.

Поскольку дерево это по своей сути граф, у него с последним многие определения совпадают, либо интуитивно схожи. Так корневой узел (вершина 6) в структуре дерева – это единственная вершина (узел), характерная отсутствием предков, т. е. такая, что на нее не ссылается ни какая другая вершина, а из самого корневого узла можно дойти до любой из имеющихся вершин дерева, что следует из свойства связности данной структуры. Узлы, не ссылающиеся ни на какие другие узлы, иначе говоря, ни имеющие потомков называются листьями (2, 3, 9), либо терминальными узлами. Элементы, расположенные между корневым узлом и листьями – промежуточные узлы (1, 1, 7, 8). Каждый узел дерева имеет только одного предка, или если он корневой, то не имеет ни одного.

Поддерево – часть дерева, включающая некоторый корневой узел и все его узлы-потомки. Так, например, на рисунке одно из поддеревьев включает корень 8 и элементы 2, 1, 9.

С деревом можно выполнять многие операции, например, находить элементы, удалять элементы и поддеревья, вставлять поддеревья, находить корневые узлы для некоторых вершин и др. Одной из важнейших операций является обход дерева. Выделяются несколько методов обхода. Наиболее популярные из них: симметричный, прямой и обратный обход. При прямом обходе узлы-предки посещаются прежде своих потомков, а в обратном обходе, соответственно, обратная ситуация. В симметричном обходе поочередно просматриваются поддеревья главного дерева.

Представление данных в рассмотренной структуре выгодно в случае наличия у информации явной иерархии. Например, работа с данными о биологических родах и видах, служебных должностях, географических объектах и т. п. требует иерархически выраженной структуры, такой как математические деревья.

Тема этой статьи снова касается теории программирования , поэтому придется прибегнуть к различным классификациям и оперировать математическими терминами. Структуры данных – это практически первое, о чем рассказывают в ходе учебных . Оценка сложности алгоритмов – второе. Может показаться, что эти два вопроса мало связаны, но это не так, и по ходу повествования станет ясно почему. Я не буду углубляться в детали, поскольку практика показывает, что в процессе приобретения опыта в в голове остается только самое важное. По-моему, так происходит в любой сфере деятельности. Я постараюсь изложить то, что осталось по этим вопросам в голове у меня.

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

Структура данных – это форма хранения и представления информации. Определение весьма расплывчато, поэтому специалисты используют различные формы классификации и уточнений. Структуры данных бывают простыми и сложными: представляют атомарную единицу информации или набор однотипных данных. Простые структуры данных характеризуются , например, целочисленный, вещественный, логический, текстовый тип и т.д. Сложные структуры данных делятся на динамические и статические наборы. Динамические в процессе своего жизненного цикла позволяют изменять свой размер (добавлять и удалять элементы), а статические - нет. И наконец, по организации взаимосвязей между элементами сложных структур данных существует следующая классификация:

• Линейные
  • Массив
  • Список
  • Связанный список
  • Очередь
  • Хэш-таблица

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

Линейные структуры данных

Элемент линейной структуры данных характеризуется порядковым номером или индексом в линейной последовательности элементов.

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

Линейный массив.
Адрес(элемент(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.

Как следствие: асимптотическая оценка существует только в том случае, если совпадают нижняя и верхняя оценки сложности алгоритма. В практике анализа алгоритмов чаще всего под оценкой сложности понимают верхнюю оценку сложности. Это вполне логично, поскольку наиболее важна оценка времени, за которое алгоритм гарантировано закончит работу, а не время, в пределах которого он точно не завершится.

Работа с линейными структурами данных

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

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

Что включает в себя понятие структуры данных?

Этот термин может иметь несколько близких, но все же отличительных значений. Это:

• абстрактный тип;
• реализация абстрактного вида информации;
• экземпляр типа данных, к примеру, определенный список.

Если говорить о структуре данных в контексте функционального программирования, то это особенная единица, что сберегается при изменениях. О ней неформально можно сказать как о единой структуре, несмотря на то что могут иметься различные версии.

Что формирует структуру?

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

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

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

Стоит отметить, что многие языки программирования обладают установленным типом модульности, что позволяет структурам с данными безопасно использоваться в различных приложениях. Яркими примерами являются языки Java, C# и C++. Сейчас классическая структура используемых данных представлена в стандартных библиотеках языков программирования или непосредственно она встроена уже в сам язык. К примеру, хэш-таблицы встроена в Lua, Python, Perl, Ruby, Tcl и другие. Широко применяется стандартная библиотека шаблонов в C++.

Сравниваем структуру в функциональном и императивном программировании

Стоит сразу оговорится, что проектировать структуры для функциональных языков сложнее, чем для императивных, как минимум на это есть две причины:

1. Фактически все структуры часто применяют на практике присваивание, которое в чисто функциональном стиле не используется.
2. Функциональные структуры - это гибкие системы. В императивном программировании старые версии просто заменяются на новые, а в функциональном все работает, как работало. Иными словами, в императивном программировании структуры являются эфемерными, а в функциональном они постоянные.

Что включает в себя структура?

Часто данные, с которыми работают программы, сберегаются во встроенных в применяемом языке программирования массивах, константе или в переменной длине. Массив - это простейшая структура со сведениями, однако для решения некоторых задач требуется большая эффективность некоторых операций, потому применяются иные структуры (сложнее).

Простейший массив подходит для частого обращения к установленным компонентам по индексам и их изменению, а удаление элементов из средины функционирует за принципом O(N)O(N). Если вам требуется удалить элементы, чтобы разрешить определенные задачи, то придется воспользоваться иной структурой. К примеру, бинарное дерево (std::set) позволяет делать это по O(logN)O(log⁡N), однако оно не поддерживает работу с индексами, выполняется исключительно поочередный обход элементов и их поиск по значению. Таким образом, можно сказать, что структура отличается операциями, что она способна выполнять, а также скоростью их проделывания. Для примера стоит рассмотреть простейшие структуры, что не дают выгоды в эффективности, но имеют точно установленный набор поддерживаемых операций.

Стек

Это один из типов структур данных, представленный в виде ограниченного простейшего массива. Классический стек поддерживает всего лишь три опции:

• Внести элемент в стек (Сложность: O(1)O(1)).
• Извлечение элемента из стека (Сложность: O(1)O(1)).
• Проверка, пустой ли стек или нет (Сложность: O(1)O(1)).

Чтобы пояснить принцип работы стека, можно применить на практике аналогию с банкой печенья. Представьте, что на дне посудины лежит несколько печенюшек. Наверх вы можете положить еще пару кусочков или же вы можете, наоборот, взять одну печеньку сверху. Остальные печеньки будут закрыты верхними, и вы про них ничего не будете знать. Вот так дела обстоят и со стеком. Для описания понятия применяется аббревиатура LIFO (Last In, First Out), которая подчеркивает, что компонент, попавший внутрь стека последним, будет первым же и извлечен из него.

Очередь

Это еще один тип структуры данных, что поддерживает тот же набор опций, что и стек, однако у него противоположная семантика. Для описания очереди применяется аббревиатура FIFO (First In, First Out), потому как вначале извлекается элемент, что добавлен был раньше всех. Название структуры говорит за себя - принцип работы полностью совпадает с очередями, что можно увидеть в магазине, супермаркете.

Дек

Это еще один вид структуры данных, который еще называют очередью с двумя концами. Опция поддерживает следующий набор операций:

• Внести элемент в начало (Сложность: O(1)O(1)).
• Извлечь компонент из начала (Сложность: O(1)O(1)).
• Внесение элемента в конец (Сложность: O(1)O(1)).
• Извлечение элемента из конца (Сложность: O(1)O(1)).
• Проверка, пустой ли дек (Сложность: O(1)O(1)).

Списки

Данная структура данных определяет последовательность линейно связанных компонентов, для которых разрешены операции добавления компонентов в любое место списка и его удаление. Линейный список задается указателем на начало списка. Типичные операции над списками: обход, поиск конкретного компонента, вставка элемента, удаление компонента, объединение двух списков в единое целое, разбивка списка на пару и так далее. Стоит оговориться, что в линейном списке, помимо первого, имеется предыдущий компонент для каждого элемента, не включая последний. Это означает, что компоненты списка находятся в упорядоченном состоянии. Да, обработка такого списка не всегда удобна, ведь нет возможности продвижения в противоположную сторону — от конца списка к началу. Однако в линейном списке можно поэтапно пройтись по всем составляющим.

Еще существуют кольцевые списки. Это такая же структура, что и линейный список, однако она имеет дополнительную связь между первым и последним компонентами. Другими словами, следующим за последним элементом является первый компонент.

В этом списке элементы равноправны. Выделение первого и последнего - это условность.

Деревья

Это совокупность компонентов, что именуются узлами, в котором есть главный (один) компонент в виде корня, а все остальные разбиты на множество непересекающихся элементов. Каждое множество является деревом, а корень каждого древа - потомком корня дерева. Другими словами, все компоненты соединены между собой отношениями предок-потомок. Как результат можно наблюдать иерархическую структуру узлов. Если узлы не имеют потомка, то они называются листьями. Над деревом определены такие операции, как: добавление компонента и его удаление, обход, поиск компонента. Особую роль в информатике играют бинарные деревья. Что это такое? Это частный случай дерева, где каждый узел может иметь не больше пары потомков, являющихся корнями левого и правого поддерева. Если дополнительно для узлов дерева выполняется еще условие, что все значения компонентов левого поддерева меньше значений корня, а значения компонентов правого поддерева больше корня, то такое дерево именуется деревом бинарного поиска, и предназначается оно для быстрого нахождения элементов. Как же работает алгоритм поиска в таком случае? Искомое значение сравнивается со значением корня, и в зависимости от результата поиск либо завершается, либо продолжается, но исключительно в левом или правом поддереве. Общее число операций сравнения не станет превосходить высоту дерева (это наибольшее число компонентов на пути от корня до одного из листьев).

Графы

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

Графами можно описывать объекты какой угодно структуры, они являются главным средством для описания сложных структур и функционирования всех систем.

Детальней об абстрактной структуре

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

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

Анализ структур данных производится следующими объектами:

• Целые и вещественные числа.
• Логические значения.
• Символы.

Для обработки на компьютере всех элементов существуют соответствующие алгоритмы и структуры данных. Типичные объекты можно объединить в сложные структуры. Можно добавить операции над ними, правила к определенным компонентам этой структуры.

Структура организации данных включает в себя:

• Векторы.
• Динамические структуры.
• Таблицы.
• Многомерные массивы.
• Графы.

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

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

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

Мы разобрались с характеристиками структур данных, теперь стоит уделить больше внимания пониманию понятия структуры. При решении абсолютно любой задачи требуется работать с какими-то данными, чтобы произвести операции над информацией. У каждой задачи есть свой набор операций, однако некоторый набор применяется на практике чаще для решения разнообразных заданий. В таком случае полезно придумать определенный способ организации информации, что позволит выполнять эти операции как можно эффективнее. Как только такой способ появился, можно считать, что у вас появился «черный ящик», в котором будут сберегаться данные определенного рода и который станет выполнять те или иные операции с данными. Это позволит отвлечься от деталей и полностью сконцентрироваться на характерных особенностях задачи. Данный «черный ящик» может быть реализован любым образом, при этом необходимо стремиться к как можно более продуктивной реализации.

Кому это необходимо знать?

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

Не забывайте: если говорите о той или иной структуре, то имейте в виду ее логическое представление, ведь физическое представление полностью сокрыто от «внешнего наблюдателя».

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

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