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

5
51994
Добавить в избранное

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

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

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

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

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

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

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

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

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

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

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

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

Хеш-таблицы

Хэш-таблицы

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

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

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

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

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

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

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

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

Интересуетесь алгоритмами?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




Добавить комментарий