Практикум по реализации структур данных и алгоритмов
Практикум по реализации структур данных и алгоритмов
Практикум представляет собой серию интерактивных заданий, направленных на глубокое понимание устройства фундаментальных структур данных и алгоритмов через их непосредственную реализацию в коде. Этот подход позволяет перейти от абстрактного описания теории к созданию рабочих программ, где каждый элемент имеет конкретное место в памяти и выполняет четкую функцию. Задания строятся по принципу постепенного усложнения: от простых линейных структур до сложных графовых моделей и многопоточных систем. Каждый этап требует написания кода, его тестирования и анализа производительности. Такой метод обучения формирует прочную базу для решения реальных инженерных задач, так как разработчик видит не только "как это работает", но и "почему это работает именно так".
Линейные структуры данных
Односвязный список (Singly Linked List)
Односвязный список — это динамическая структура данных, состоящая из узлов, где каждый узел содержит значение и ссылку на следующий узел в последовательности. Структура не требует выделения непрерывного блока памяти, что обеспечивает гибкость при изменении размера коллекции.
Задание 1: Базовая реализация
Создайте класс Node, содержащий поле для хранения значения и ссылку на следующий узел. Реализуйте класс LinkedList с методами добавления элемента в конец (append), удаления первого элемента (pop) и перебора всех элементов (traverse).
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def traverse(self):
current = self.head
while current:
print(current.value)
current = current.next
В этом примере каждый вызов метода append создает новый объект в памяти и обновляет ссылку последнего узла. Метод traverse проходит по цепочке ссылок, пока не достигнет конца списка (значения None).
Задание 2: Вставка и удаление
Добавьте возможность вставки элемента после заданного узла и удаление элемента по значению. Обратите внимание на обработку граничных случаев: удаление первого узла, удаление несуществующего значения или удаление единственного узла.
def insert_after(self, target_value, new_value):
current = self.head
while current and current.value != target_value:
current = current.next
if not current:
return False
new_node = Node(new_value)
new_node.next = current.next
current.next = new_node
return True
def remove(self, value):
if not self.head:
return False
if self.head.value == value:
self.head = self.head.next
return True
current = self.head
while current.next and current.next.value != value:
current = current.next
if current.next:
current.next = current.next.next
return True
return False
Логика удаления требует сохранения ссылки на предыдущий узел, чтобы перенаправить её на следующий узел, исключая удаляемый элемент из цепи. Это предотвращает утечки памяти и сохраняет целостность структуры.
Двусвязный список (Doubly Linked List)
Двусвязный список расширяет функциональность односвязного, добавляя каждому узлу ссылку на предыдущий элемент. Это позволяет двигаться по списку в обоих направлениях, но увеличивает накладные расходы на память из-за хранения дополнительной ссылки.
Задание 3: Реализация двунаправленного движения
Реализуйте структуру, где каждый узел имеет поля prev и next. Добавьте методы prepend (добавление в начало) и reverse_traverse (проход с конца).
class DoublyNode {
int value;
DoublyNode prev;
DoublyNode next;
public DoublyNode(int value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
private DoublyNode head;
private DoublyNode tail;
public void prepend(int value) {
DoublyNode newNode = new DoublyNode(value);
if (head == null) {
head = tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
public void reverseTraverse() {
DoublyNode current = tail;
while (current != null) {
System.out.print(current.value + " ");
current = current.prev;
}
}
}
При добавлении элемента в начало необходимо обновить ссылку prev у старого хедера, чтобы он указывал на новый узел, а затем сделать новый узел новым хедером. При удалении элементов важно корректно обновлять обе ссылки (prev и next) соседних узлов.
Стек (Stack)
Стек — это структура данных, работающая по принципу LIFO (Last In, First Out). Последний добавленный элемент является первым доступным для извлечения. Основные операции включают push (добавление) и pop (удаление).
Задание 4: Реализация стека на основе массива
Создайте фиксированный стек с возможностью динамического расширения при переполнении. Реализуйте метод peek для просмотра верхнего элемента без его удаления.
public class Stack<T>
{
private T[] _items;
private int _count;
private const int InitialCapacity = 4;
public Stack()
{
_items = new T[InitialCapacity];
_count = 0;
}
public void Push(T item)
{
if (_count == _items.Length)
{
Resize();
}
_items[_count] = item;
_count++;
}
public T Pop()
{
if (_count == 0)
{
throw new InvalidOperationException("Stack is empty");
}
_count--;
T item = _items[_count];
_items[_count] = default; // Освобождение ссылки
return item;
}
public T Peek()
{
if (_count == 0)
{
throw new InvalidOperationException("Stack is empty");
}
return _items[_count - 1];
}
private void Resize()
{
int newSize = _items.Length * 2;
var newArray = new T[newSize];
Array.Copy(_items, newArray, _items.Length);
_items = newArray;
}
}
Динамическое расширение массива происходит путем создания нового массива вдвое большей емкости и копирования существующих элементов. Это обеспечивает амортизированную сложность операций добавления O(1).
Очередь (Queue)
Очередь работает по принципу FIFO (First In, First Out). Элементы добавляются в конец (enqueue) и удаляются из начала (dequeue). Для эффективной реализации часто используется связный список или кольцевой буфер.
Задание 5: Циклический буфер (Circular Buffer)
Реализуйте очередь с использованием массива фиксированного размера, где указатели головы и хвоста циклически перемещаются. Это позволяет избежать смещения элементов при каждом удалении.
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.head = 0
self.tail = 0
self.size = 0
def enqueue(self, item):
if self.size == self.capacity:
raise Exception("Queue is full")
self.queue[self.tail] = item
self.tail = (self.tail + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.size == 0:
raise Exception("Queue is empty")
item = self.queue[self.head]
self.queue[self.head] = None
self.head = (self.head + 1) % self.capacity
self.size -= 1
return item
Использование оператора остатка от деления % обеспечивает циклическое движение индексов. Когда индекс достигает конца массива, он сбрасывается на ноль, позволяя использовать освободившееся место.
Деревья и древовидные структуры
Бинарное дерево поиска (Binary Search Tree - BST)
Бинарное дерево поиска — это древовидная структура, где каждый узел имеет не более двух потомков. Левый поддерево всегда содержит значения меньше текущего узла, а правое — больше. Это свойство позволяет выполнять поиск, вставку и удаление за время O(log n) в среднем случае.
Задание 6: Реализация BST
Создайте класс TreeNode и методы для вставки (insert) и поиска (search) значений. Реализуйте обход дерева в порядке возрастания (in-order traversal).
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (!this.root) {
this.root = newNode;
return;
}
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) {
current.left = newNode;
break;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
break;
}
current = current.right;
}
}
}
search(value) {
let current = this.root;
while (current) {
if (value === current.value) return true;
if (value < current.value) current = current.left;
else current = current.right;
}
return false;
}
inOrderTraversal(node = this.root, result = []) {
if (node) {
this.inOrderTraversal(node.left, result);
result.push(node.value);
this.inOrderTraversal(node.right, result);
}
return result;
}
}
Алгоритм вставки сравнивает новое значение с текущим узлом и спускается влево или вправо до нахождения свободного места. Обход in-order гарантирует получение отсортированного списка значений.
AVL-дерево (Balanced BST)
AVL-дерево — это самобалансирующееся бинарное дерево поиска, где разность высот левого и правого поддеревьев любого узла не превышает единицы. Это гарантирует логарифмическую высоту дерева даже в худшем случае.
Задание 7: Балансировка вращениями
Реализуйте проверку баланса и вращения (rotation) для восстановления свойства AVL после вставки. Вращения бывают правым (right rotation) и левым (left rotation).
class AVLNode {
int value;
AVLNode left, right;
int height;
AVLNode(int value) {
this.value = value;
this.height = 1;
}
}
class AVLTree {
private AVLNode root;
private int getHeight(AVLNode node) {
return node == null ? 0 : node.height;
}
private int getBalance(AVLNode node) {
return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
}
private AVLNode rotateRight(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
private AVLNode rotateLeft(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
return y;
}
public void insert(int value) {
root = insertRec(root, value);
}
private AVLNode insertRec(AVLNode node, int value) {
if (node == null) return new AVLNode(value);
if (value < node.value) node.left = insertRec(node.left, value);
else if (value > node.value) node.right = insertRec(node.right, value);
else return node;
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
int balance = getBalance(node);
if (balance > 1 && value < node.left.value) return rotateRight(node);
if (balance < -1 && value > node.right.value) return rotateLeft(node);
if (balance > 1 && value > node.left.value) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (balance < -1 && value < node.right.value) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
}
Вращение меняет локальную структуру дерева, сохраняя свойство порядка ключей, но уменьшая высоту дерева. Алгоритм проверяет баланс после каждой вставки и применяет соответствующее вращение при нарушении условий.
Хэш-таблица (Hash Table)
Хэш-таблица — это структура данных, обеспечивающая быстрое хранение и извлечение данных с помощью хэш-функции. Ключ преобразуется в индекс массива, куда помещается значение. Коллизии (совпадение хэшей) решаются методом цепочек или открытой адресации.
Задание 8: Реализация с обработкой коллизий
Создайте таблицу с использованием метода цепочек (linked list) для разрешения коллизий. Реализуйте методы put, get и remove.
class HashTable:
def __init__(self, size=16):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
index = self._hash(key)
bucket = self.table[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
index = self._hash(key)
bucket = self.table[index]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)
def remove(self, key):
index = self._hash(key)
bucket = self.table[index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
return
raise KeyError(key)
Хэш-функция распределяет ключи равномерно по ячейкам массива. При коллизии элементы добавляются в список внутри ячейки. Поиск и удаление проходят по этому списку.
Графы и сетевые структуры
Представление графа
Граф состоит из вершин и ребер. Существуют два основных способа представления: матрица смежности и список смежности. Матрица удобна для плотных графов, список — для разреженных.
Задание 9: Список смежности
Реализуйте структуру графа с использованием словаря, где ключ — вершина, а значение — список соседей.
#include <vector>
#include <unordered_map>
#include <string>
class Graph {
private:
std::unordered_map<std::string, std::vector<std::string>> adjList;
public:
void addEdge(const std::string& u, const std::string& v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // Для неориентированного графа
}
std::vector<std::string>& getNeighbors(const std::string& vertex) {
return adjList[vertex];
}
void addVertex(const std::string& vertex) {
if (adjList.find(vertex) == adjList.end()) {
adjList[vertex] = {};
}
}
};
Каждая вершина хранит список своих соседей, что позволяет быстро перебирать связи. Добавление новой вершины инициализирует пустой список.
Поиск в ширину (BFS) и глубину (DFS)
Поиск в ширину посещает все соседи узла перед переходом к следующему уровню. Поиск в глубину исследует ветвь до конца перед возвратом.
Задание 10: Алгоритмы обхода
Напишите функции BFS и DFS для обхода графа, найденного в задании 9.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
for neighbor in graph.get_neighbors(vertex):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
def dfs(graph, start, visited=None, result=None):
if visited is None:
visited = set()
if result is None:
result = []
visited.add(start)
result.append(start)
for neighbor in graph.get_neighbors(start):
if neighbor not in visited:
dfs(graph, neighbor, visited, result)
return result
BFS использует очередь для обеспечения уровня обхода. DFS использует рекурсию (или стек) для глубокого погружения в структуру.
Алгоритм Дейкстры
Алгоритм Дейкстры находит кратчайший путь от начальной вершины до всех остальных в взвешенном графе с неотрицательными весами.
Задание 11: Кратчайший путь
Реализуйте алгоритм с использованием приоритетной очереди.
import java.util.*;
class Edge {
String to;
int weight;
Edge(String to, int weight) {
this.to = to;
this.weight = weight;
}
}
class DijkstraSolver {
public Map<String, Integer> dijkstra(Map<String, List<Edge>> graph, String start) {
Map<String, Integer> distances = new HashMap<>();
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
for (String node : graph.keySet()) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(start, 0);
pq.offer(new Node(start, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
String u = current.node;
if (current.distance > distances.get(u)) continue;
for (Edge edge : graph.getOrDefault(u, Collections.emptyList())) {
int alt = distances.get(u) + edge.weight;
if (alt < distances.get(edge.to)) {
distances.put(edge.to, alt);
pq.offer(new Node(edge.to, alt));
}
}
}
return distances;
}
static class Node {
String node;
int distance;
Node(String node, int distance) {
this.node = node;
this.distance = distance;
}
}
}
Алгоритм выбирает вершину с минимальным расстоянием, обновляет расстояния до соседей и добавляет их в очередь. Процесс повторяется до исчерпания очереди.
Сортировка и поиск
Быстрая сортировка (Quick Sort)
Быстрая сортировка использует стратегию "разделяй и властвуй". Выбирается опорный элемент, массив разделяется на части с меньшими и большими элементами, затем рекурсивно сортируются подмассивы.
Задание 12: Реализация Quick Sort
Напишите функцию сортировки с выбором опорного элемента по середине.
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_index = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[(low + high) // 2]
i = low
j = high
while i <= j:
while arr[i] < pivot:
i += 1
while arr[j] > pivot:
j -= 1
if i <= j:
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
return i
Разбиение переставляет элементы так, чтобы слева были меньше опорного, а справа — больше. Рекурсия завершается, когда подмассивы становятся пустыми или одноэлементными.
Бинарный поиск (Binary Search)
Бинарный поиск работает только на отсортированных массивах. Он сравнивает целевое значение со средним элементом и отбрасывает половину массива, где может находиться искомое значение.
Задание 13: Реализация Binary Search
Напишите рекурсивную и итеративную версии поиска.
public class BinarySearch
{
public int Iterative(int[] arr, int target)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
public int Recursive(int[] arr, int target, int left, int right)
{
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return Recursive(arr, target, mid + 1, right);
return Recursive(arr, target, left, mid - 1);
}
}
Вычисление среднего индекса как left + (right - left) / 2 предотвращает переполнение целочисленного типа при больших значениях.
Анализ сложности и оптимизация
Оценка временной сложности
Понимание асимптотической сложности помогает выбирать оптимальные алгоритмы для конкретных задач. O(1) означает постоянное время, O(n) — линейное, O(n^2) — квадратичное.
Задание 14: Анализ кода
Проанализируйте предоставленные выше реализации и определите их временную сложность в лучшем, среднем и худшем случаях.
| Алгоритм | Лучший случай | Средний случай | Худший случай |
|---|---|---|---|
| Односвязный список (поиск) | O(1) | O(n) | O(n) |
| BST (поиск) | O(1) | O(log n) | O(n) |
| AVL (поиск) | O(log n) | O(log n) | O(log n) |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) |
| Бинарный поиск | O(1) | O(log n) | O(log n) |
Для односвязного списка поиск всегда требует прохода по всем элементам в худшем случае. BST в вырожденном случае превращается в список, теряя преимущества деревьев. AVL гарантирует логарифмическую высоту благодаря балансу.
Оптимизация памяти
Эффективное управление памятью критично для производительности. Использование сборщика мусора, избегание утечек и выбор правильных структур данных снижает потребление ресурсов.
Задание 15: Утечки памяти
Изучите код реализации стека и очереди. Найдите места, где могут возникать утечки памяти (например, отсутствие очистки ссылок после удаления). Исправьте их.
В C# очистка default в методе Pop стека освобождает ссылку, позволяя сборщику мусора удалить объект. В Python аналогичная операция не требуется из-за автоматической сборки мусора, но явное обнуление полезно для понимания процесса.
См. также
Другие статьи этого же раздела в боковом меню (как на странице «О разделе»). Также вы можете найти SQL, bash, git, docker тренажёры в соответствующих главах. Тренажёры представляют собой интерактивные платформы, где обучение происходит через непосредственное выполнение практических задач в контролируемой среде. Смуляция представляет собой процесс создания и использования модели реальной системы или явления для изучения её поведения, анализа сценариев и прогнозирования результатов без необходимости…Тренажёр
Тренажёры
Смуляции