Чем стек отличается от структуры данных линейный список

7

Стек Занятие 1. Стек. Отличия стека от списка. Основные операции со стеком.

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

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

Стек часто называют структурой LIFO [сокращение LIFO означает Last In – First Out (последний пришел, первый вышел)]. Это сокращение представляет удобный способ запомнить механизм работы стека

Изобразим стек графически:

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

Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.

Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.

Итак, если стек – это список, то добавление или извлечение элементов происходит с начала и только с начала (или возможно с конца и только с конца) списка.

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

Таким образом, описать стек можно следующим образом:

Если стек пуст, то значение указателя равно Nil.

Рассмотрим возможные операции со стеком.

Занесение элемента в стек

Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.

Структуры данных, которые необходимо знать каждому программисту

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

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

Что такое структура данных?

Независимо от профессии, ежедневная работа связана с данными. Шеф-повар, инженер-программист или даже рыбак — все они работают с теми или иными формами данных.

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

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

Массивы

Массивы — одна из самых простых и часто применяемых структур данных. Такие структуры данных, как очереди и стеки, основаны на массивах и связанных списках (которые мы рассмотрим чуть позже).

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

Существует два типа массивов: одномерные и многомерные. Первые представляют собой простейшие линейные структуры, а вторые — вложенные и включают другие массивы.

Основные операции с массивами

• Get — получить элемент массива по заданному индексу.
• Insert — вставить элемент массива по заданному индексу.
• Length — получить количество элементов в заданном массиве.
• Delete — удалить элемент массива по заданному индексу. Может быть выполнено либо путем установки значения undefined , либо путем копирования элементов массива, за исключением удаляемого, в новый массив.
• Update — обновление значения элемента массива по заданному индексу.
• Traverse — проход цикла через массив для выполнения функций над элементами массива.
• Search — поиск определенного элемента в заданном массиве с помощью выбранного алгоритма.

Применение массивов

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

Связанный список (Linked List)

Связанный список — это набор элементов, называемых узлами, в линейной последовательной структуре. Узел — простой объект с двумя свойствами. Это переменные для хранения данных и адреса памяти следующего узла в списке. Поэтому узел знает только о том, какие данные он содержит и кто его сосед. Это позволяет создавать связанные списки, в которых каждый узел связан с другим.

Существует несколько типов связанных списков.

• Односвязный. Обход элементов может выполняться только в прямом направлении.
• Двусвязный. Обход элементов может выполняться как в прямом, так и в обратном направлениях. Узлы включают дополнительный указатель, известный как prev , указывающий на предыдущий узел.
• Круговые связанные. Это связанные списки, в которых предыдущий ( prev ) указатель “головы” указывает на “хвост”, а следующий указатель “хвоста” указывает на “голову”.

Основные операции со связанными списками

• Insertion — добавление узла в список. Это может быть сделано на основе требуемого местоположения, такого как голова, хвост или где-то посередине.
• Delete — удаление узла в начале списка или на основе заданного ключа.
• Display — отображение полного списка.
• Search — поиск узла в данном связанном списке.
• Update — обновление значения узла в заданном ключе.

Применение связанных списков

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

Стек — линейная структура данных, которая создается на основе массивов или связанных списков. Стек следует принципу Last-In-First-Out (LIFO, “первым на вход — последним на выход”), т.е. последний элемент, вошедший в стек, будет первым, кто покинет его. Причина, по которой эта структура называется стеком, в том, что ее можно визуализировать как стопку книг на столе (по-английски stack).

Основные операции со стеком

• Push — вставка элемента в верхнюю часть стека.
• Pop — удаление элемента из верхней части стека с возвращением элемента.
• Peek — просмотр элемента в верхней части стека.
• isEmpty — проверка пустоты стека.

Применение стеков

• В истории навигации браузера.
• Для реализации рекурсии.
• При выделении памяти на основе стека.

Очередь

Как и стек, очередь — это еще один тип линейной структуры данных, основанной либо на массивах, либо на связанных списках. Очереди отличаются от стеков тем, что они основаны на принципе First-In-First-Out (FIFO, “первым на вход — первым на выход”), где элемент, который входит в очередь первым, и покинет ее первым.

Реальная аналогия структуры данных “очереди” — это очередь людей, ожидающих покупки билета в кино.

Основные операции с очередями

• Enqueue — вставка элемента в конец очереди.
• Dequeue — удаление элемента из передней части очереди.
• Top/Peek — возвращает элемент из передней части очереди без удаления.
• isEmpty — проверка содержимого очереди.

Применение очередей

• Обслуживание нескольких запросов на одном общем ресурсе.
• Управление потоками в многопоточных средах.
• Балансировка нагрузки.

Граф — это структура данных, представляющая собой взаимосвязь узлов, которые также называются вершинами. Пара (x,y) называется ребром. Это указывает на то, что вершина x соединена с вершиной y . Ребро может указывать на вес/стоимость, то есть стоимость прохождения по пути между двумя вершинами.

Ключевые термины

• Размер — количество ребер в графике.
• Порядок — количество вершин в графе.
• Смежность — случай, когда два узла соединены одним и тем же ребром.
• Петля — вершина, соединенная ребром сама с собой.
• Изолированная вершина — вершина, которая не связана с другими вершинами.

Графы делятся на два типа. Они различаются главным образом по направлениям пути между двумя вершинами.

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

Распространенные алгоритмы обхода графов

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

Основные операции с графами

• Add vertex : добавить вершину в граф.
• Add edge : добавить ребро между двумя вершинами.
• Display : отобразить вершину.
• Total cost of traversal : найти общую стоимость пути обхода.

Применение графов

• Для представления потоковых вычислений.
• При распределении ресурсов операционной системой.
• Реализация алгоритмов поиска друзей в Facebook.
• Расчет кратчайшего пути между двумя локациями (Google Maps).

Дерево

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

Существует несколько типов деревьев.

• N-арное дерево.
• Сбалансированное дерево.
• Бинарное дерево.
• Бинарное дерево поиска (BST).
• Дерево AVL.
• Красно-черное дерево.
• 2-3-дерево.

BST — самые распространенные типы деревьев.

Основные операции с BST

• Insert — вставка элемента в дерево.
• Search — поиск элемента в дереве.
• PreorderTraversal — обход дерева прямым способом.
• InorderTraversal — обход дерева центрированным способом.
• PostorderTraversal — обход дерева обратным способом.

Применение деревьев

• Представление организации.
• Представление компьютерной файловой системы.
• Представление химической формулы.
• В деревьях принятия решений.
• Внутри JVM (Java Virtual Machine) для хранения объектов Java.

Хэш-таблица

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

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

Хеширование (хэш-функция)

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

• h — хэш-функция.
• k — ключ, из которого должно быть определено хэш-значение.
• m — размер хэш-таблицы.

Например, рассмотрим использование хэш-функции k%17 . Если исходный ключ равен 20 , то хэшированный будет 20%17=3 . Значение будет храниться в хэш-таблице под индексом 3 .

Зачем нужен хэш?

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

Коллизии

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

• Когда k = 18, h(18) = 18%17 = 1.
• При k = 20, h(20) = 20%17 = 3.
• При k = 35, h(35) = 35%17 = 1.

Когда ключи равняются 18 и 35, происходит коллизия, поскольку они направляются к индексу 1.

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

Основные операции с хэш-таблицами

• Search — поиск элемента в хэш-таблице.
• Insert — вставка элемента в хэш-таблицу.
• Delete — удаление элемента из хэш-таблицы.

Применение хэш -таблиц

• В индексации баз данных.
• При проверке орфографии.
• При реализации заданной структуры данных.
• В кэше.

Заключение

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

Основные понятия структуры данных программы

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

Основополагающие сведения о структурах данных

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

Структуры данных делятся на:

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

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

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

Базовые термины

Перед изучением структуры данных кратко коснемся их основы – терминов, а затем перейдем к применению. К ним относятся:

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

Характеристики

Важными характеристиками структур данных являются:

• Корректность – она должна грамотно реализовывать свой интерфейс.
• Сложность времени – должно использоваться минимальное количество времени на выполнение операций.
• Сложность пространства – при проведении операций память должна использоваться минимально.

Какие проблемы можно решить с помощью структуры данных

В связи с тем, что приложения становятся все более сложными, а количество составляющей информации в них постоянно растет, то возникают три проблемы:

• замедление процесса поиска в связи с ростом данных;
• ограниченная скорость процессоров. Несмотря на то, что она достаточно высокая, с ростом объема информации и она ограничивается;
• многократные запросы через поиск на веб-серверах вызывают сбои в их работе.

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

Случаи выполнения

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

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

Основные виды структур

К основным видам структуры данных относятся:

Массивы

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

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

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

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

Язык программирования определяет, с какого значения в массиве начинается нумерация. Во многих языках начальным индексом массива определен 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, позволяющий сохранять пару (ключ/ значение). Хеширование применяется для нахождения в массиве значения индекса, по которому будет найдено нужное значение.

При детальном рассмотрении можно увидеть, что хэш-таблица является массивом. В нем хэш-функция является индексом.

Коллизией называют хеширование двух вводов, имеющих одинаковый цифровой выход. Цель – уменьшение числа коллизий.

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

Производительность хеширования зависит от:

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

Деревья

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

От деревьев, встречающихся в природе, классическое математическое дерево отличается тем, что корень последнего расположен вверху. А его ветви «растут» сверху вниз.

Дереву присущи характеристики:

1. Каждое имеет единственную вершину (корневой узел), расположенную сверху и не имеющую предков. Никакая вершина не ссылается на корень, а из него можно достичь любой имеющейся вершины дерева (это следствие свойства связанности древовидной структуры).
2. Вершины, которые не имеют потомков (не ссылаются на иные) называются терминальными узлами (листьями).
3. Объекты, которые располагаются между вершиной и листьями, называются промежуточными узлами.
4. Каждая вершина древовидной структуры имеет лишь единого предка, а если он является корневым – не имеет ни одного предка.
5. У корневого узла может быть от нуля или более потомков.
6. У каждого дочернего узла может быть от нуля или более дочерних вершин.

Поддеревом называется часть древовидной структуры, которая имеет вершину и имеющиеся потомки.

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

Для деревьев используются следующие методы обхода:

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

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

Дерево двоичного (бинарного) поиска

Кроме вышеуказанных характеристик деревьев, дереву двоичного поиска характерны еще ряд характеристик:

1. Узел может иметь не больше двух детей (потомков).
2. Левые потомки меньше текущего узла, что меньше, чем у правых детей.

Бинарные деревья помогают существенно ускорить работу объектами (находить, удалять, добавлять их).

Префиксные деревья (Trie), боры, лучи

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

Чаще всего боры используют для:

• поиска слов в словарях;
• автозавершений в поисковиках;
• IP-маршрутизации.

Бор хранит данные в узлах. Такие деревья часто используются для хранения слов. Они хранятся в борах сверху вниз – в каждом узле по букве.

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

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

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

• максимальной – у родительских узлов ключи всегда больше либо равны тем ключам, которые у детей;
• минимальной – у родительских узлов ключи меньше либо равны ключам у дочерних элементов.

В двоичной куче прослеживается важность порядка между уровнями, но не между узлами одного уровня.

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

Структуры данных, которые необходимо знать каждому программисту

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

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

Что такое структура данных?

Независимо от профессии, ежедневная работа связана с данными. Шеф-повар, инженер-программист или даже рыбак — все они работают с теми или иными формами данных.

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

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

Массивы

Массивы — одна из самых простых и часто применяемых структур данных. Такие структуры данных, как очереди и стеки, основаны на массивах и связанных списках (которые мы рассмотрим чуть позже).

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

Существует два типа массивов: одномерные и многомерные. Первые представляют собой простейшие линейные структуры, а вторые — вложенные и включают другие массивы.

Основные операции с массивами

• Get — получить элемент массива по заданному индексу.
• Insert — вставить элемент массива по заданному индексу.
• Length — получить количество элементов в заданном массиве.
• Delete — удалить элемент массива по заданному индексу. Может быть выполнено либо путем установки значения undefined , либо путем копирования элементов массива, за исключением удаляемого, в новый массив.
• Update — обновление значения элемента массива по заданному индексу.
• Traverse — проход цикла через массив для выполнения функций над элементами массива.
• Search — поиск определенного элемента в заданном массиве с помощью выбранного алгоритма.

Применение массивов

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

Одномерный массив
Многомерный массив

Связанный список (Linked List)

Связанный список — это набор элементов, называемых узлами, в линейной последовательной структуре. Узел — простой объект с двумя свойствами. Это переменные для хранения данных и адреса памяти следующего узла в списке. Поэтому узел знает только о том, какие данные он содержит и кто его сосед. Это позволяет создавать связанные списки, в которых каждый узел связан с другим.

Существует несколько типов связанных списков.

• Односвязный. Обход элементов может выполняться только в прямом направлении.
• Двусвязный. Обход элементов может выполняться как в прямом, так и в обратном направлениях. Узлы включают дополнительный указатель, известный как prev , указывающий на предыдущий узел.
• Круговые связанные. Это связанные списки, в которых предыдущий ( prev ) указатель “головы” указывает на “хвост”, а следующий указатель “хвоста” указывает на “голову”.

Основные операции со связанными списками

• Insertion — добавление узла в список. Это может быть сделано на основе требуемого местоположения, такого как голова, хвост или где-то посередине.
• Delete — удаление узла в начале списка или на основе заданного ключа.
• Display — отображение полного списка.
• Search — поиск узла в данном связанном списке.
• Update — обновление значения узла в заданном ключе.

Применение связанных списков

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

Стек — линейная структура данных, которая создается на основе массивов или связанных списков. Стек следует принципу Last-In-First-Out (LIFO, “первым на вход — последним на выход”), т.е. последний элемент, вошедший в стек, будет первым, кто покинет его. Причина, по которой эта структура называется стеком, в том, что ее можно визуализировать как стопку книг на столе (по-английски stack).

Основные операции со стеком

• Push — вставка элемента в верхнюю часть стека.
• Pop — удаление элемента из верхней части стека с возвращением элемента.
• Peek — просмотр элемента в верхней части стека.
• isEmpty — проверка пустоты стека.

Применение стеков

• В истории навигации браузера.
• Для реализации рекурсии.
• При выделении памяти на основе стека.

Очередь

Как и стек, очередь — это еще один тип линейной структуры данных, основанной либо на массивах, либо на связанных списках. Очереди отличаются от стеков тем, что они основаны на принципе First-In-First-Out (FIFO, “первым на вход — первым на выход”), где элемент, который входит в очередь первым, и покинет ее первым.

Реальная аналогия структуры данных “очереди” — это очередь людей, ожидающих покупки билета в кино.

Основные операции с очередями

• Enqueue — вставка элемента в конец очереди.
• Dequeue — удаление элемента из передней части очереди.
• Top/Peek — возвращает элемент из передней части очереди без удаления.
• isEmpty — проверка содержимого очереди.

Применение очередей

• Обслуживание нескольких запросов на одном общем ресурсе.
• Управление потоками в многопоточных средах.
• Балансировка нагрузки.

Граф — это структура данных, представляющая собой взаимосвязь узлов, которые также называются вершинами. Пара (x,y) называется ребром. Это указывает на то, что вершина x соединена с вершиной y . Ребро может указывать на вес/стоимость, то есть стоимость прохождения по пути между двумя вершинами.

Ключевые термины

• Размер — количество ребер в графике.
• Порядок — количество вершин в графе.
• Смежность — случай, когда два узла соединены одним и тем же ребром.
• Петля — вершина, соединенная ребром сама с собой.
• Изолированная вершина — вершина, которая не связана с другими вершинами.

Графы делятся на два типа. Они различаются главным образом по направлениям пути между двумя вершинами.

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

Распространенные алгоритмы обхода графов

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

Основные операции с графами

• Add vertex : добавить вершину в граф.
• Add edge : добавить ребро между двумя вершинами.
• Display : отобразить вершину.
• Total cost of traversal : найти общую стоимость пути обхода.

Применение графов

• Для представления потоковых вычислений.
• При распределении ресурсов операционной системой.
• Реализация алгоритмов поиска друзей в Facebook.
• Расчет кратчайшего пути между двумя локациями (Google Maps).

Ориентированный граф со стоимостью

Дерево

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

Существует несколько типов деревьев.

• N-арное дерево.
• Сбалансированное дерево.
• Бинарное дерево.
• Бинарное дерево поиска (BST).
• Дерево AVL.
• Красно-черное дерево.
• 2-3-дерево.

BST — самые распространенные типы деревьев.

Простое дерево

Основные операции с BST

• Insert — вставка элемента в дерево.
• Search — поиск элемента в дереве.
• PreorderTraversal — обход дерева прямым способом.
• InorderTraversal — обход дерева центрированным способом.
• PostorderTraversal — обход дерева обратным способом.

Применение деревьев

• Представление организации.
• Представление компьютерной файловой системы.
• Представление химической формулы.
• В деревьях принятия решений.
• Внутри JVM (Java Virtual Machine) для хранения объектов Java.

Хэш-таблица

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

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

Хеширование (хэш-функция)

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

• h — хэш-функция.
• k — ключ, из которого должно быть определено хэш-значение.
• m — размер хэш-таблицы.

Например, рассмотрим использование хэш-функции k%17 . Если исходный ключ равен 20 , то хэшированный будет 20%17=3 . Значение будет храниться в хэш-таблице под индексом 3 .

Хэш-функция для ключей

Зачем нужен хэш?

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

Коллизии

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

• Когда k = 18, h(18) = 18%17 = 1.
• При k = 20, h(20) = 20%17 = 3.
• При k = 35, h(35) = 35%17 = 1.

Когда ключи равняются 18 и 35, происходит коллизия, поскольку они направляются к индексу 1.

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

Основные операции с хэш-таблицами

• Search — поиск элемента в хэш-таблице.
• Insert — вставка элемента в хэш-таблицу.
• Delete — удаление элемента из хэш-таблицы.

Применение хэш -таблиц

• В индексации баз данных.
• При проверке орфографии.
• При реализации заданной структуры данных.
• В кэше.

Заключение

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