9.4. Структуры данных
Раздел 9. Алгоритмы и программирование (продолжение)
📋 Содержание темы:
Стек
Стек (stack) — структура данных, работающая по принципу LIFO (Last In, First Out) — «последним пришёл, первым вышел».
Основные операции:
push(x)— добавление элемента в вершинуpop()— удаление и возврат элемента из вершиныpeek()— просмотр элемента без удаленияis_empty()— проверка на пустоту
Реализация на списках:
stack = [] # Добавление (push) stack.append(1) stack.append(2) stack.append(3) print(stack) # [1, 2, 3] # Извлечение (pop) top = stack.pop() print(top) # 3 print(stack) # [1, 2] # Просмотр вершины print(stack[-1]) # 2 # Проверка на пустоту print(len(stack) == 0) # False
Применение стека:
# Проверка баланса скобок
def is_balanced(expr):
"""Проверяет правильность расстановки скобок."""
stack = []
matching = {')': '(', ']': '[', '}': '{'}
for char in expr:
if char in '([{':
stack.append(char)
elif char in ')]}':
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
return len(stack) == 0
print(is_balanced("({[]})")) # True
print(is_balanced("({[})")) # False
Очередь
Очередь (queue) — структура данных, работающая по принципу FIFO (First In, First Out) — «первым пришёл, первым вышел».
Основные операции:
enqueue(x)— добавление в конецdequeue()— удаление из началаfront()— просмотр первого элементаis_empty()— проверка на пустоту
Реализация с помощью deque:
from collections import deque
queue = deque()
# Добавление (enqueue)
queue.append("Анна")
queue.append("Борис")
queue.append("Вера")
print(queue) # deque(['Анна', 'Борис', 'Вера'])
# Извлечение (dequeue)
person = queue.popleft()
print(person) # Анна
print(queue) # deque(['Борис', 'Вера'])
# Просмотр первого элемента
print(queue[0]) # Борис
Очередь на списке (медленно для больших объёмов):
queue = []
queue.append("Анна")
queue.append("Борис")
# Извлечение из начала (O(n) — медленно!)
person = queue.pop(0)
# Проверка на пустоту
print(len(queue) == 0)
Совет: Используйте
collections.deque вместо списка для реализации очереди — это работает быстрее.Связный список
Связный список — структура данных, состоящая из узлов, каждый из которых хранит данные и ссылку на следующий узел.
Реализация узла:
class Node:
"""Узел связного списка."""
def __init__(self, data):
self.data = data
self.next = None
Реализация списка:
class LinkedList:
"""Односвязный список."""
def __init__(self):
self.head = None
def push_front(self, data):
"""Добавить в начало."""
node = Node(data)
node.next = self.head
self.head = node
def push_back(self, data):
"""Добавить в конец."""
node = Node(data)
if self.head is None:
self.head = node
return
current = self.head
while current.next:
current = current.next
current.next = node
def remove(self, data):
"""Удалить первый элемент с указанными данными."""
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
def to_list(self):
"""Преобразовать в обычный список."""
result = []
current = self.head
while current:
result.append(current.data)
current = current.next
return result
Использование:
lst = LinkedList() lst.push_back(1) lst.push_back(2) lst.push_front(0) print(lst.to_list()) # [0, 1, 2] lst.remove(1) print(lst.to_list()) # [0, 2]
Деревья
Дерево — структура данных с иерархической организацией элементов.
Основные понятия:
- Корень — вершина без родителя
- Лист — вершина без потомков
- Высота дерева — длина пути от корня до самого глубокого листа
Бинарное дерево:
class TreeNode:
"""Узел бинарного дерева."""
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Пример: дерево поиска
# 5
# / \
# 3 7
# / \ / \
# 1 4 6 8
Обходы дерева:
# Обход в глубину (Depth-First Search)
def preorder(node):
"""Корень → Лево → Право."""
if node is None:
return []
return [node.value] + preorder(node.left) + preorder(node.right)
def inorder(node):
"""Лево → Корень → Право."""
if node is None:
return []
return inorder(node.left) + [node.value] + inorder(node.right)
def postorder(node):
"""Лево → Право → Корень."""
if node is None:
return []
return postorder(node.left) + postorder(node.right) + [node.value]
# Обход в ширину (Breadth-First Search)
from collections import deque
def bfs(root):
"""Обход по уровням."""
if root is None:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Построение бинарного дерева поиска:
def insert(root, value):
"""Вставка значения в дерево поиска."""
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def search(root, value):
"""Поиск значения в дереве поиска."""
if root is None or root.value == value:
return root
if value < root.value:
return search(root.left, value)
return search(root.right, value)
# Построение дерева
root = None
for x in [5, 3, 7, 1, 4, 6, 8]:
root = insert(root, x)
print(inorder(root)) # [1, 3, 4, 5, 6, 7, 8]
Словари и множества
Словари (dict):
# Создание словаря
person = {
"имя": "Анна",
"возраст": 15,
"класс": "9А"
}
# Доступ по ключу
print(person["имя"]) # Анна
# Добавление / изменение
person["оценка"] = 5
person["возраст"] = 16
# Проверка ключа
print("имя" in person) # True
# Перебор
for key, value in person.items():
print(f"{key}: {value}")
# Методы
keys = person.keys()
values = person.values()
Множества (set):
# Создание множества
numbers = {1, 2, 3, 4, 5}
# Добавление
numbers.add(6)
# Удаление
numbers.remove(3)
# Операции над множествами
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
print(a | b) # Объединение: {1, 2, 3, 4, 5, 6}
print(a & b) # Пересечение: {3, 4}
print(a - b) # Разность: {1, 2}
print(a ^ b) # Симметрическая разность: {1, 2, 5, 6}
# Проверка принадлежности
print(3 in a) # True
Практические задачи
Задача 1: Инвертировать связный список
def reverse_list(head):
"""Инвертирует связный список."""
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
Задача 2: Проверка палиндрома через стек
def is_palindrome(s):
"""Проверяет, является ли строка палиндромом."""
s = s.lower().replace(" ", "")
stack = []
for char in s:
stack.append(char)
for char in s:
if char != stack.pop():
return False
return True
print(is_palindrome("А роза упала на лапу Азора")) # True
Задача 3: Поиск в ширину в графе
from collections import deque
def bfs(graph, start):
"""Обход графа в ширину."""
visited = set()
queue = deque([start])
visited.add(start)
order = []
while queue:
vertex = queue.popleft()
order.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']
Задача 4: Частотный анализ текста
def frequency_analysis(text):
"""Подсчитывает частоту каждого символа."""
freq = {}
for char in text:
freq[char] = freq.get(char, 0) + 1
# Сортировка по убыванию частоты
sorted_freq = sorted(freq.items(), key=lambda x: -x[1])
return sorted_freq
text = "привет мир"
for char, count in frequency_analysis(text):
print(f"'{char}': {count}")
Задача 5: Найти путь в графе (DFS)
def dfs_path(graph, start, end, path=None):
"""Находит путь между двумя вершинами графа."""
if path is None:
path = []
path = path + [start]
if start == end:
return path
for neighbor in graph[start]:
if neighbor not in path:
result = dfs_path(graph, neighbor, end, path)
if result:
return result
return None
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(dfs_path(graph, 'A', 'F')) # ['A', 'C', 'F']
Совет: Выбор структуры данных зависит от задачи: стек — для обратного порядка, очередь — для обхода в ширину, дерево — для иерархических данных.