62226

Алгоритмы и структуры данных: развернутый видеокурс

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

В этой статье, делаем обзор видеокурса на тему “Алгоритмы и структуры данных”.

Массивы и базовые структуры данных

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

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

  • константный доступ по индексу;
  • непрерывный список памяти;
  • фиксированный размер.

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

https://www.youtube.com/watch?v=vRvSdWVst54

Очередь с приоритетом

Очередь с приоритетом

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

https://www.youtube.com/watch?v=jwlG7_7JVYs

Системы непересекающихся множеств

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

https://www.youtube.com/watch?v=bXBHYqNeBLo

Хеш-таблицы

Хэш-таблицы

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

https://www.youtube.com/watch?v=E6oY2EcMi9Y

Деревья поиска

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

https://www.youtube.com/watch?v=9cUwGI_F9jU

Дополнительные функции для деревьев поиска

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

https://www.youtube.com/watch?v=7jAJC8JvQUQ

Сплей-деревья

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

https://www.youtube.com/watch?v=AHWbu3B6UKA

Другие материалы по теме:

РУБРИКИ В СТАТЬЕ

Комментарии

BUG
LIVE