Алгоритмы и структуры данных

1.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
CONTACT US
АЛГОРИТМЫ И
СТРУКТУРЫ
ДАННЫХ
АВТОР: ХАЛЫҚБАЙ АҚАРЫС

2.

STUDIO
SHODWE
ВОПРОСЫ
- Что такое алгоритмы и структуры данных
- Зачем изучать алгоритмы и структуры данных
- Что такое абстрактные типы данных
- Линейные структуры данных
- Односвязные и двусвязные списки, стеки, деки, очереди
HOME
SERVICE
ABOUT US
CONTACT US

3.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Определение кратчайшего пути, выбор необходимого подмножества объектов, поиск
наилучшего совпадения строк — каждую из этих задач можно решить несколькими разными
способами. Все они дадут одинаковый результат, но один вариант окажется самым простым в
реализации; другой — более эффективным; а третий — максимально быстрым, но при этом
будет использовать много оперативной памяти.
Так происходит потому, что в каждом из этих решений будут применяться разные алгоритмы.
Алгоритм — это инструкция, которая описывает порядок выполнения действий.
Алгоритмы описывают то, как мы преобразуем данные, чтобы получить требуемый результат. С
ними тесно связаны структуры данных, в которых эти данные хранятся. Разные структуры
хранят данные по-разному и из-за этого у них возникают интересные свойства.
CONTACT US

4.

STUDIO
SHODWE
Допустим, вы хотите взять книгу в библиотеке. Среди нескольких
тысяч изданий библиотекарь быстро найдёт нужный вам
экземпляр, потому что книги на полках расставлены в алфавитном
порядке. А теперь представьте, что вам нужно отыскать какуюнибудь книгу у себя дома, в книжном шкафу. Если книги в нём
расположены не по порядку, то, вероятно, вы потратите на поиски
много времени.
Но вот в библиотеку поступило собрание сочинений А. П. Чехова в
восемнадцати томах. Свободного пространства в нужном месте
может не оказаться, и библиотекарю придётся переставлять другие
книги, переносить их с полки на полку. Этот процесс может занять
какое-то время, зато после добавления новых книг алфавитный
порядок в библиотеке сохранится. А в домашний книжный шкаф, в
котором нет определённой системы, положить новые книги можно
быстро и легко — на любое свободное место.
HOME
SERVICE
ABOUT US
CONTACT US

5.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
CONTACT US
Итак, вот что мы можем сказать про эти «структуры данных»:
• Библиотека, в которой книги расставлены в алфавитном порядке: быстрый поиск, но добавление новых книг в некоторых
случаях может быть медленным.
• Шкаф, в котором книги стоят без определённого порядка: медленный поиск, зато добавлять новые книги можно быстро.
Как видите, даже в таком простом примере нет однозначно лучшего решения. Для разных задач мы будем использовать разные
способы хранения данных.

6.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
CONTACT US
ЗАЧЕМ ИЗУЧАТЬ АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
• Вы узнаете, как оценивать эффективность кода и сможете применять этот навык в работе, в том числе при
проведении код-ревью.
• Знание специфики разных структур данных позволит вам правильно их использовать и писать более эффективный
код.
• Помимо эффективности, мы будем много говорить о корректности алгоритмов. Например, задача, в которой нужно
добраться городским наземным транспортом из точки А в точку Б, может иметь много решений. Только одно из них
будет оптимальным с точки зрения времени, часть — корректными, а какие-то в некоторых случаях вообще могут
давать неверный результат. Вы научитесь видеть и понимать такие моменты.
• На задачах на алгоритмы удобно тренировать навык написания чистого кода. В них не будет противоречивых
требований продуктовой логики, некорректных входных данных, «магии», скрытой за фреймворками, и вызовами
внешних API. Поэтому почти для любой задачи на алгоритмы можно написать аккуратное, понятное, лаконичное и
при этом эффективное решение. Но для того, чтобы его найти, нужно будет попрактиковаться.
• Алгоритмы не устаревают. Они не привязаны к конкретным технологиям или техническому стеку, поэтому
полученные знания и навыки будут актуальны до тех пор, пока люди не перестанут писать код.
• Мы изучим не все существующие алгоритмы, это и не нужно. Столкнувшись с новой задачей, вы уже будете знать, что
и где нужно искать, и сможете разобраться с решением.

7.

STUDIO
SHODWE
АБСТРАКТНЫЕ ТИПЫ ДАННЫХ
Абстрактные типы данных (АТД) — это математические модели,
которые описывают данные и операции над ними независимо от
их реализации. Основная идея АТД заключается в том, чтобы
скрыть внутреннее устройство данных и представить их
пользователю только в виде доступных операций.
Примеры АТД:
• Список (List)
• Стек (Stack)
• Множество (Set)
• Ассоциативный массив (Map)
HOME
SERVICE
ABOUT US
CONTACT US

8.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
CONTACT US
ВАЖНОСТЬ АБСТРАКТНЫХ ТИПОВ ДАННЫХ
1. Упрощение разработки
• Абстракция позволяет сосредоточиться на функциональности, не отвлекаясь на реализацию. Это упрощает
понимание и разработку программ.
2. Модульность
• Реализацию одного и того же АТД можно менять, не затрагивая остальной код. Например, реализацию
очереди можно заменить с массива на связный список.
3. Повторное использование
• Однажды разработанные структуры данных (например, стек или очередь) можно применять в разных
проектах.
4. Эффективность
• Понимание свойств АТД помогает выбирать оптимальные структуры данных для решения задач (например,
хэш-таблицы для быстрого поиска или деревья для сортировки).
5. Обеспечение надёжности
• За счёт скрытия деталей реализации уменьшается риск ошибок.
6. Пример из реальной жизни
• Интернет-магазины используют ассоциативные массивы для хранения информации о продуктах (ключ — это
ID товара, значение — его описание и цена).

9.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
CONTACT US
ЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ
Линейные структуры данных — это тип структур данных, в которых элементы организованы последовательно один за другим. Каждый
элемент связан с предыдущим и/или следующим элементом, создавая логический порядок.
Характеристики линейных структур данных:
1. Последовательность: Элементы расположены в строго линейном порядке (например, 1-й, 2-й, 3-й элемент и так далее).
2.Один путь доступа: Доступ к элементам происходит по порядку, один за другим.
3.Простота: Линейные структуры данных проще в понимании и реализации по сравнению с нелинейными структурами, такими как
деревья или графы.
Примеры использования линейных структур данных:
1. Массивы:
⚬ Хранение данных фиксированного размера (например, массив температур за неделю).
2.Стек:
⚬ Управление вызовами функций (стек вызовов в программировании).
⚬ Отмена действий (Ctrl+Z в текстовых редакторах).
3.Очередь:
⚬ Планировщик задач в операционной системе.
⚬ Система обработки очередей в банке.
4.Связный список:
⚬ Реализация динамических данных (например, текстовые редакторы с "неограниченной" длиной текста).

10.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
CONTACT US
ОДНОСВЯЗНЫЕ И ДВУСВЯЗНЫЕ СПИСКИ
Связные списки — это динамические структуры данных, состоящие из узлов (элементов), где каждый узел содержит
данные и ссылки (указатели) на другие узлы.
Односвязный список (Singly Linked List)
Описание:
• Каждый узел содержит два поля:
a. Данные (хранят значение элемента).
b. Указатель (ссылка на следующий узел).
• Последний узел содержит указатель None (обозначает конец списка).
Пример структуры:
10 -> 20 -> 30 -> None
Преимущества:
• Экономит память, так как хранит только один указатель.
• Лёгкость добавления новых элементов в начало или конец.
Недостатки:
• Односторонняя навигация (нет возможности двигаться назад).
• Более сложный доступ к элементам (поиск требует обхода списка).

11.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
CONTACT US
ОДНОСВЯЗНЫЕ И ДВУСВЯЗНЫЕ СПИСКИ
Двусвязный список (Doubly Linked List)
Описание:
• Каждый узел содержит три поля:
a. Данные (хранят значение элемента).
b. Указатель на следующий узел.
c. Указатель на предыдущий узел.
• Первый узел содержит указатель None в поле предыдущего узла, а последний узел — в поле следующего узла.
Пример структуры:
None <- 10 <-> 20 <-> 30 -> None
Преимущества:
• Двусторонняя навигация: можно двигаться вперёд и назад.
• Упрощённое удаление элементов, так как есть доступ к предыдущему узлу.
Недостатки:
• Увеличенные затраты памяти, так как хранятся два указателя на узел.
• Сложность реализации и управления.

12.

STUDIO
SHODWE
СТЕКИ
HOME
SERVICE
ABOUT US
CONTACT US
Стек — это линейная структура данных, работающая по принципу LIFO (Last In, First Out), что означает: элемент, добавленный последним, будет извлечён
первым. Представьте стопку тарелок: тарелка, которую положили последней, будет убрана первой.
Ключевые операции стека:
1. push(x): Добавление элемента в стек (наверх).
2.pop(): Удаление верхнего элемента из стека.
3.peek() / top(): Просмотр верхнего элемента без удаления.
4.isEmpty(): Проверка, пуст ли стек.
Реализация стека
Стек может быть реализован:
• С помощью массива: Фиксированный размер.
• С помощью связного списка: Гибкость, но дополнительные затраты памяти.
Примеры использования стека:
1. Управление вызовами функций:
⚬ В процессе выполнения программы стек используется для хранения вызовов функций.
⚬ Когда функция завершается, её вызов удаляется из стека.
2.Обратный обход (Backtracking):
⚬ В задачах, где нужно вернуться к предыдущему состоянию (например, решение лабиринта).
3.Алгоритмы обработки строк:
⚬ Проверка сбалансированности скобок (например, ((a+b)*c)):
⚬ Используется стек для хранения открывающихся скобок.
4.Отмена действий (Undo/Redo):
⚬ В текстовых редакторах, например, при нажатии Ctrl+Z действия помещаются в стек отмен.
5.Реализация калькулятора:
⚬ Обратная польская нотация (Reverse Polish Notation, RPN) использует стек для вычислений.

13.

STUDIO
SHODWE
stack = []
# Добавление элементов
stack.append(10)
stack.append(20)
stack.append(30)
print("Стек:", stack) # [10, 20, 30]
# Удаление верхнего элемента
top = stack.pop()
print("Удалённый элемент:", top) # 30
print("После удаления:", stack) # [10, 20]
# Просмотр верхнего элемента
print("Верхний элемент:", stack[-1]) # 20
# Проверка на пустоту
print("Пустой ли стек?", len(stack) == 0) # False
СТЕКИ
HOME
SERVICE
ABOUT US
CONTACT US

14.

STUDIO
SHODWE
ОЧЕРЕДИ
HOME
SERVICE
ABOUT US
CONTACT US
Очередь — это линейная структура данных, работающая по принципу FIFO (First In, First Out), что означает: элемент, добавленный первым, будет извлечён
первым.
Представьте очередь в магазине — первый пришёл, первый обслуживается.
Ключевые характеристики очереди:
1. FIFO: Первый вошёл — первый вышел.
2.Ограниченный доступ: Элементы добавляются только в конец очереди и удаляются только из начала.
3.Простота реализации: Может быть реализована с использованием массивов, списков или связных списков.
Операции очереди:
1. enqueue(x): Добавление элемента в конец очереди.
2.dequeue(): Удаление элемента из начала очереди.
3.front(): Просмотр элемента в начале очереди без удаления.
4.isEmpty(): Проверка, пуста ли очередь.
Типы очередей:
1. Обычная очередь (Simple Queue)
⚬ Стандартная очередь с принципом FIFO.
⚬ Пример: enqueue(10) -> enqueue(20) -> dequeue() -> 10.
2.Кольцевая очередь (Circular Queue)
⚬ Конечная структура, где последний элемент связан с первым.
⚬ Используется для эффективного использования памяти.
3.Двусторонняя очередь (Deque)
⚬ Элементы могут добавляться и удаляться с обеих сторон (рассматривали ранее).
4.Приоритетная очередь (Priority Queue)
⚬ Элементы имеют приоритет, и извлечение выполняется на основе их приоритета, а не порядка поступления.
⚬ Пример: Задачи с высоким приоритетом обрабатываются первыми.

15.

STUDIO
SHODWE
from collections import deque
# Создание очереди
queue = deque()
# Добавление элементов (enqueue)
queue.append(10)
queue.append(20)
queue.append(30)
print("Очередь:", queue) # deque([10, 20, 30])
# Удаление элемента (dequeue)
front = queue.popleft()
print("Удалённый элемент:", front) # 10
print("После удаления:", queue) # deque([20, 30])
# Проверка первого элемента
print("Первый элемент:", queue[0]) # 20
# Проверка на пустоту
print("Очередь пуста?", not queue) # False
ОЧЕРЕДИ
HOME
SERVICE
ABOUT US
CONTACT US

16.

STUDIO
SHODWE
ДЕКИ
HOME
SERVICE
ABOUT US
CONTACT US
Дека (от англ. double-ended queue) — это линейная структура данных, которая позволяет добавлять и удалять элементы как с
начала, так и с конца. Она сочетает свойства очереди и стека, обеспечивая гибкость в работе с данными.
Ключевые характеристики деки:
1. Двусторонний доступ:
⚬ Элементы могут быть добавлены или удалены как с начала, так и с конца.
2.Гибкость:
⚬ Можно использовать как стек (LIFO), так и очередь (FIFO).
Операции деки:
1. Добавление элементов:
⚬ append(x) — добавить элемент в конец.
⚬ appendleft(x) — добавить элемент в начало.
2.Удаление элементов:
⚬ pop() — удалить элемент с конца.
⚬ popleft() — удалить элемент с начала.
3.Дополнительные операции:
⚬ extend(iterable) — добавить несколько элементов в конец.
⚬ extendleft(iterable) — добавить несколько элементов в начало.
⚬ rotate(n) — сдвиг элементов вправо на n позиций.

17.

ДЕКИ
STUDIO
SHODWE
from collections import deque
# Создание деки
dq = deque()
# Добавление элементов
dq.append(10)
# В конец
dq.appendleft(20)
# В начало
dq.append(30)
print("Дека:", dq)
# deque([20, 10, 30])
# Удаление элементов
dq.pop()
# Удалить с конца
dq.popleft()
# Удалить с начала
print("После удаления:", dq) # deque([10])
# Дополнительные операции
dq.extend([40, 50]) # Добавить элементы в конец
dq.rotate(1)
# Сдвиг вправо на 1
print("После операций:", dq) # deque([50, 10, 40])
HOME
SERVICE
ABOUT US
CONTACT US

18.

STUDIO
SHODWE
HOME
SERVICE
ABOUT US
СПАСИБО ЗА ВНИМАНИЕ
CONTACT US