Предлагаем укрепить (или получить) знания о базовых структурах данных. Эти понятия являются основой всего, что связано с программами. Вспомните азы, а если не знаете – получите их. Они пригодятся в работе, а если есть цель найти ее, то и при прохождении интервью. Укажите, что вы знаете составляющие структуры данных, их применение, и это поможет в поиске работы. Потратив немного времени, вы приятно удивите интервьюера, начальника или коллег по работе.
Основополагающие сведения о структурах данных
Классическая структура данных представляет собой определенный способ организации этих самых данных для дальнейшего эффективного использования. Это если кратко. В более развернутом виде – она представляет собой некую упаковку, в которой данные сохраняются в определенной «моделе».
Структуры данных делятся на:
- линейные (стеки, очереди, массивы) – элементы выстраиваются в последовательность либо линейный список. Также линейны и обходы узлов;
- нелинейные (графы, деревья) – данные выстраиваются без какой-либо последовательности. Также не линейны и обходы узлов.
Коснемся основных действий. Данные можно получить, найти, добавить, удалить. Для реализации этих целей существует много разнообразных структур данных. Каждая отдельно взятая более эффективна в одних вопросах и менее эффективна в других. Потому разработчик должен понимать функциональные составляющие каждой структуры. Грамотное применение функциональных свойств структуры данных ускорит решение любой поставленной задачи.
Приходится часто искать информацию – укажите одну разновидность. Если нужно постоянно что-либо вставлять – укажите другую. А если частенько приходится выполнять действия по перестановке и удалению – укажите третье решение.
Базовые термины
Перед изучением структуры данных кратко коснемся их основы – терминов, а затем перейдем к применению. К ним относятся:
- Интерфейс – определенный набор операций, поддерживающих структуру данных. Он присущ каждой структуре. Интерфейс может предоставлять только перечень поддерживаемых операций, тип принимаемых параметров и возвращает тип этих операций.
- Реализация – обеспечивает внутреннее представление структуры данных, помогает в определении алгоритмов, которые используются в операциях.
Характеристики
Важными характеристиками структур данных являются:
- Корректность – она должна грамотно реализовывать свой интерфейс.
- Сложность времени – должно использоваться минимальное количество времени на выполнение операций.
- Сложность пространства – при проведении операций память должна использоваться минимально.
Какие проблемы можно решить с помощью структуры данных
В связи с тем, что приложения становятся все более сложными, а количество составляющей информации в них постоянно растет, то возникают три проблемы:
- замедление процесса поиска в связи с ростом данных;
- ограниченная скорость процессоров. Несмотря на то, что она достаточно высокая, с ростом объема информации и она ограничивается;
- многократные запросы через поиск на веб-серверах вызывают сбои в их работе.
Структуры данных помогают в решение вышеперечисленных проблем. Данные можно организовать в структуры таким образом, что поиск будет осуществляться практически мгновенно.
Случаи выполнения
Чтобы провести сравнение временных промежутков, необходимых для выполнения различной структуры, используются следующие случаи:
- худший – сценарий, при котором для выполнения конкретной операции потребуется максимальное время, которое только возможно;
- средний – сценарий, при котором на выполнение операции отводится среднее время;
- наилучший – сценарий, который отображает кратчайший промежуток времени, необходимый для выполнения операции.
Основные виды структур
К основным видам структуры данных относятся:
Массивы
Это наипростейшие и широко используемые структуры данных, в которых элементы следуют один за другим. Представляет собой контейнер, в котором может храниться фиксированное количество однотипных компонентов.
Важнейшие термины:
- элементами называют все компоненты, хранящиеся в массиве;
- индексы – местонахождение каждого элемента в массиве выражается целым числовым индексом, используемом для его идентификации.
Размерность массива определяет количество индексов в нем. Они бывают одномерными (называют векторами) и многомерными (массив в середине массива). Массивы могут объявляться разными способами на различных языках программирования.
Некоторые структуры являются производными массивов (стеки, очереди). В массиве каждый элемент имеет индекс (положительное целое числовое значение), соответствующий тому, какую позицию в массиве он занимает.
Язык программирования определяет, с какого значения в массиве начинается нумерация. Во многих языках начальным индексом массива определен 0.
Массивы бывают:
- статическими — характеризуются однородностью данных;
- динамическими – характеризуются непостоянством размера, который может меняться в ходе выполнения программы. Это усложняет процесс, ухудшает быстроту действий, но работа с информацией становится более гибкой;
- гетерогенными – характеризуется неоднородностью данных.
Основные операции, которые поддерживаются массивами:
- Traverse – выставляет один за одним все компоненты массива;
- Insert – добавляет один или несколько элементов по указанному индексу;
- Get – производит возврат элемента по указанному индексу;
- Delete – выполняет удаление элемента по указанному индексу;
- Size – позволяет узнать общую численность элементов, содержащихся в массиве.
Списки
Список является абстрактным типом данных. Существует несколько их разновидностей. Рассмотрим наиболее популярные:
Связные (связанные) списки
Связной список представляет собой массив с конечным множеством элементов (отдельных объектов) и указателями на них.
Каждый объект содержит:
- поле информации (тип данных может быть любым);
- ссылки (указатели) на последующий узел.
Таким образом упорядоченные элементы связного списка связаны друг с другом указателями. Вместе эти группы образуют последовательность.
Как и массив, список лежит в основе понятия классической структуры данных. Их функциональные особенности часто сравнивают, т.к. большинство других структур могут быть реализованы с помощью массивов или связных списков. Последний отличается от массива структурной гибкостью. Доступ к спискам осуществляется последовательно, а к массивам – произвольно.
Связанные списки бывают следующих видов:
- Однонаправленные (односвязные) – каждый узел сохраняет адрес либо ссылку на тот узел, который числится следующим. А узел, являющийся последним, содержит последующий адрес либо ссылку как NULL. Линейные однонаправленные списки встречаются чаще всего.
- Двунаправленные (двусвязные) – имеют две ссылки, которые связаны с каждым отдельным узлом (первая указывает на последующий, вторая – на предыдущий).
- Круговые (кольцевые) – все узлы списка соединены в круг при отсутствии в последнем NULL. Является подвидом двух предыдущих видов связных списков. Они могут быть одно- или двусвязными.
Чтобы односвязный список стал круговым, необходимо в его последний узел вставить указатель на первый элемент. Чтобы двунаправленный список преобразовать в кольцевой, следует добавить две ссылки на узлы: первый и последний.
Операции, являющиеся основными:
- InsertAtEnd – вставка заданного элемента в конце списка;
- InsertAtHead – вставка заданного элемента в начало списка;
- Delete – удаление заданного элемента из списка;
- DeleteAtHead – удаление первого элемента в списке;
- Search – возвращение заданного элемента из списка
- isEmpty – в тем случае, когда список пустой, производится возврат True.
Стеки
Являются базовой структурой, в которой реализовано лишь добавление и удаление объектов в начало стека (через его вершину). Представляет собой список элементов, которые организованы по принципу LIFO (на английском языке Last In – First Out, что в переводе означает «последним зашел – первым ушел»). По тому же принципу работает в приложениях функционал «Отменить».
Отличное сравнение – стопка тарелок. Чтобы из стопки взять тарелку, необходимо вначале снять верхние тарелки. А положить тарелку можно только на верх стопки.
Основные операции:
- Push – вставка в стек элемента наверху;
- Pop – удаление верхнего элемента из стека;
- Pip – отображается содержимое;
- isEmpty – происходит возврат True в случае, когда стек пустой;
- Top – возвращает элемент сверху, не удаляя его из стека.
Чаще всего в программировании применяется:
- стек изменений в редакторе кода, позволяющий быстро делать отмену изменений и возвращаться к предыдущему состоянию;
- стек передвижения по страницам в браузере – позволяет быстро переходить по страницам.
Очереди
Является яркой аналогией с очередью в магазин. Порядок входа в него определяет то, в каком порядке была занята очередь. Первый занявший очередь зайдет первым, за ним – второй и т.д. В очереди используется принцип доступа к данным FIFO (на английском языке – First In First Out, в переводе означает «Первый вошел, первый ушел»).
Если кратко, то очередью является список, в котором добавление новых элементов допустимо строго в его конец, а извлечение – происходит строго с другого конца, который называют началом списка.
Элементы сохраняются последовательно. Но для очереди используется принцип FIFO, а не LIFO.
Выполняются операции:
- Enqueue – вставка элемента в конец очереди;
- Dequeue – удаление элемента из начала очереди;
- isEmpty – будет возвращено значение True, если очередь пуста;
- Top – возвращает первый элемент из очереди.
Дек или двухсторонняя очередь
Дек (двухсторонняя очередь) – это вид списка (стека) с двумя концами. Он позволяет добавлять и извлекать элементы с двух сторон (как в начале, так и в конце).
Дек работает одновременно по FIFO и LIFO. Потому он и относится к отдельной программной единице, которая была получена в результате суммирования стека и очереди.
Графы
Графом называют набор узлов (вершин), соединенных между собой связями (называют ребра, дуги).
Графы бывают:
- ориентированными – имеют ребра с единственно возможным направлением между парой связанных вершин;
- неориентированными – для каждой дуги переход между вершинами может происходить в любом направлении, а также из каждой вершины можно перейти в другую;
- смешанные – отличаются присутствием дуг, перечисленных выше.
Графы могут иметь различную форму:
- матрицы смежности – таблицы целых чисел, в которой каждая строка либо столбец являются другим узлом на графе. В месте пересечения столбца и строки находится число, указывающее на отношение. Нули указывают, что ребер нет, а единицы – что связи есть;
- матрицы инцидентности;
- списка смежности – представлен списком, в котором левая сторона выступает вершиной, а правая – перечнем всех иных узлов, соединенных с ней;
- списка ребер.
В графах используются алгоритмы обхода:
- в глубину (depth-first search) – обход осуществляется по узлам.
- в ширину (breadth-first search) – поиск осуществляется по уровням;
Стиль дуг граф может быть не только в виде прямой линии, а вершин – выражен в цифрах. Существуют графы, именуемые взвешенными, где ребрам соответствует определенное значение (именуемое его весом). При совпадении концов ребра его называют петлей.
Графы довольно часто используются в транспортных и компьютерных сетях, веб-технологиях. По принципу граф построены социальные сети, где люди являются узлами, а дуги – их связями.
Множества
Хранение данных во множество организовано беспорядочно и без повторяющихся значений. В них можно добавлять и удалять объекты, а также есть еще ряд важнейших функций, позволяющих работать одновременно с двумя наборами функций.
Так, при двух заданных множествах функции выполнят:
- Union (объединение множеств) – объединятся все элементы, принадлежащие им обеим. Результат будет возвращен в качестве нового (не имеющего дубликатов);
- Intersection (пересечение множеств) – будет возвращено новое множество, которому будут принадлежать объекты, имевшиеся в обеих заданных множествах;
- Difference (разница множеств) – будет возвращено множество с элементами, содержавшимися в одном и не повторявшиеся в другом;
- Subset (подмножество) – возвращает булево значение, демонстрирующее содержатся ли в множестве все объекты иного.
Map
Map также именуют ассоциативный массив или словарь. Это структура данных, которая сохраняет данные в связке уникальный ключ/ значение. Чаще всего он используется, когда необходим быстрый поиск информации
С помощью Map можно:
- добавить пару;
- удалить пару;
- изменить пару;
- найти значения, которые связаны с определенными ключами.
Хэш-таблицы
Это структуры, реализующие интерфейс Map, позволяющий сохранять пару (ключ/ значение). Хеширование применяется для нахождения в массиве значения индекса, по которому будет найдено нужное значение.
При детальном рассмотрении можно увидеть, что хэш-таблица является массивом. В нем хэш-функция является индексом.
Коллизией называют хеширование двух вводов, имеющих одинаковый цифровой выход. Цель – уменьшение числа коллизий.
Когда в хэш-таблицу вводится пара ключ/ значение, с уникальным ключом проводится хеширование, после чего он становится числом. Оно в последствии используется в качестве фактического ключа, в котором это значение хранится. При повторной попытке получить доступ к этому же ключу, хеш-функция проведет его обработку и вернет то же числовое значение, которое в дальнейшем будет использовано для нахождения связанного значения. Это способствует быстрому поиску.
Производительность хеширования зависит от:
- функций хеширования;
- параметров хэш-таблиц;
- методов устранения коллизий.
Деревья
Деревом является иерархическая структура данных. Она составлена из узлов (вершин) и дуг (ребер). При близком рассмотрении можно понять, что деревьями являются связанные графы, не имеющие цикличности.
От деревьев, встречающихся в природе, классическое математическое дерево отличается тем, что корень последнего расположен вверху. А его ветви «растут» сверху вниз.
Дереву присущи характеристики:
- Каждое имеет единственную вершину (корневой узел), расположенную сверху и не имеющую предков. Никакая вершина не ссылается на корень, а из него можно достичь любой имеющейся вершины дерева (это следствие свойства связанности древовидной структуры).
- Вершины, которые не имеют потомков (не ссылаются на иные) называются терминальными узлами (листьями).
- Объекты, которые располагаются между вершиной и листьями, называются промежуточными узлами.
- Каждая вершина древовидной структуры имеет лишь единого предка, а если он является корневым – не имеет ни одного предка.
- У корневого узла может быть от нуля или более потомков.
- У каждого дочернего узла может быть от нуля или более дочерних вершин.
Поддеревом называется часть древовидной структуры, которая имеет вершину и имеющиеся потомки.
Существует несколько типов деревьев. Чаще других встречается бинарное дерево. Оно представляет собой структуру данных с иерархией, в которой каждый узел имеет определенное значение (которое является ключом) вместе со ссылками на потомков (слева и справа).
Для деревьев используются следующие методы обхода:
- прямой – осуществляется сверху вниз (начинается с посещения предков и постепенно переходит к потомкам);
- обратный – обход осуществляется снизу вверх (прежде посещаются потомки, потом – предки);
- симметричный – обход осуществляется слева направо (по очереди осуществляется обход поддеревьев главного дерева).
Выражение информации в виде древовидных структур оправдано в том случае, если у нее есть явная иерархия. Иерархически выраженная структура потребуется при работе с данными о географических объектах, служебных должностях и т.д. В таких случаях информацию лучше представлять в виде классических математических деревьев.
Дерево двоичного (бинарного) поиска
Кроме вышеуказанных характеристик деревьев, дереву двоичного поиска характерны еще ряд характеристик:
- Узел может иметь не больше двух детей (потомков).
- Левые потомки меньше текущего узла, что меньше, чем у правых детей.
Бинарные деревья помогают существенно ускорить работу объектами (находить, удалять, добавлять их).
Префиксные деревья (Trie), боры, лучи
Префиксные деревья, именуемые иногда борами и лучами, являются разновидностью древовидных структур. Они особенно эффективны для работы со строками, т.к. обеспечивают быстрый поиск информации. По сути бор является деревом поиска.
Чаще всего боры используют для:
- поиска слов в словарях;
- автозавершений в поисковиках;
- IP-маршрутизации.
Бор хранит данные в узлах. Такие деревья часто используются для хранения слов. Они хранятся в борах сверху вниз – в каждом узле по букве.
Для записи слова необходимо проследовать по ветвям дерева, вписывая за раз по одной букве. Если порядок букв не похож на другие слова в дереве либо слово заканчивается, шаги начинают расходиться. В каждой вершине находится буква (данные) вместе с логическим значением, которое указывает на то, является ли данный узел в слове последним или нет.
Двоичная куча
Так называют полное дерево, у которого в каждом узле до двух детей. У двоичной кучи все уровни до последнего заполнены полностью. В последнем уровне заполнение ведется слева направо.
Она может быть:
- максимальной – у родительских узлов ключи всегда больше либо равны тем ключам, которые у детей;
- минимальной – у родительских узлов ключи меньше либо равны ключам у дочерних элементов.
В двоичной куче прослеживается важность порядка между уровнями, но не между узлами одного уровня.
Это вся важная информация о структурах данных программы. Изучайте материал, находите новое и применяйте на практике. Если возникли вопросы – задавайте. Обязательно ответим на них.
