Структуры Данных и Алгоритмы: Комплексное Руководство для Программистов

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

Этот реферат призван стать всеобъемлющим руководством, раскрывающим ключевые концепции, теоретические основы и практические алгоритмические подходы, необходимые для глубокого понимания мира «Языков и систем программирования». Мы погрузимся в суть различных структур данных, исследуем логику работы алгоритмов и научимся оценивать их эффективность, предоставляя студентам и учащимся технических вузов мощный инструментарий для дальнейшего профессионального роста.

Что такое структура данных?

В сердце любой вычислительной задачи лежит информация, и то, как эта информация организована, напрямую влияет на эффективность её обработки. Структура данных — это специализированный формат для организации, хранения и управления данными в компьютере, предназначенный для обеспечения эффективного доступа и модификации. Иными словами, это способ упорядочивания информации таким образом, чтобы к ней можно было быстро обращаться, добавлять новые элементы, удалять существующие или модифицировать их. Представьте библиотеку: книги можно просто свалить в кучу, а можно расставить по алфавиту, по жанрам, по авторам. Каждый из этих способов — это структура данных, и от её выбора зависит, насколько быстро вы найдёте нужную книгу, что напрямую влияет на производительность программы.

Что такое алгоритм?

Если структура данных — это план хранения, то алгоритм — это рецепт, последовательность чётко определённых инструкций для решения конкретной вычислительной задачи. Алгоритм берёт входные данные, обрабатывает их согласно определённым правилам и выдаёт результат. Это своего рода пошаговый процесс, гарантирующий получение желаемого исхода. Возьмём, к примеру, сортировку списка чисел: существует множество алгоритмов для этой задачи (пузырьковая сортировка, быстрая сортировка, сортировка слиянием), и каждый из них по-своему достигает цели, но с разной эффективностью. От качества выбора и реализации алгоритма напрямую зависит скорость и ресурсоёмкость программы, делая его центральным элементом оптимизации.

Важность изучения и анализа сложности

Знание структур данных и алгоритмов само по себе ценно, но без понимания их сложности оно остаётся неполным. Анализ сложности — это процесс оценки ресурсов (времени и памяти), которые алгоритм потребует для выполнения задачи. Для этого в информатике используется так называемая O-нотация (или «большое О»), которая описывает верхнюю границу роста времени выполнения или используемой памяти алгоритма в зависимости от размера входных данных.

Например, алгоритм с временной сложностью O(n) означает, что время его выполнения растёт линейно с увеличением количества входных элементов (n). Если же сложность O(n²), то время растёт квадратично, что делает его непригодным для больших объёмов данных. Алгоритмы со сложностью O(logN) или O(1) считаются очень эффективными. Понимание этих метрик позволяет разработчику выбрать наиболее оптимальное решение для конкретной задачи, предсказать поведение программы при масштабировании данных и, в конечном итоге, создавать высокопроизводительное и ресурсоэффективное программное обеспечение. Игнорирование анализа сложности часто приводит к созданию медленных и неэффективных систем, которые не способны справиться с реальными нагрузками, а значит, и удовлетворить потребности пользователей.

Линейные Структуры Данных: От Базиса к Динамике

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

Массивы: Статический Основатель

Когда речь заходит о хранении упорядоченных коллекций элементов, первое, что приходит на ум — это массив. Массив представляет собой статический, упорядоченный набор элементов одного типа, хранящихся в непрерывной области памяти. Это его главное преимущество: благодаря такому физическому расположению, доступ к любому элементу по его индексу осуществляется за постоянное время, то есть за O(1), независимо от размера массива. Это делает массивы идеальным выбором для задач, требующих быстрого случайного доступа к данным.

Однако у этой жёсткой структуры есть и обратная сторона — фиксированный размер. После создания массива изменить его размер крайне затруднительно. Если требуется добавить больше элементов, чем было изначально предусмотрено, придётся создать новый, больший массив и скопировать в него все старые элементы, что является дорогостоящей операцией со сложностью O(n), где n — количество элементов. Аналогично, удаление элемента из середины массива или вставка нового требует сдвига всех последующих элементов, что также влечёт за собой временную сложность O(n). Эти ограничения делают массивы менее гибкими для динамически изменяющихся коллекций, где часто происходят вставки и удаления, что вынуждает разработчиков искать более адаптивные решения.

Связные Списки: Гибкость и Динамика

В отличие от статических массивов, связный список — это динамическая структура данных, чья гибкость позволяет эффективно управлять изменяющимся объёмом информации. Его уникальность заключается в том, что порядок элементов в списке не привязан к их физическому расположению в памяти. Каждый элемент, или узел, связного списка содержит не только сами данные, но и указатель (или ссылку) на следующий узел в последовательности. Это позволяет «разбросать» элементы по всей доступной памяти, связывая их логически, а не физически. Доступ к списку всегда осуществляется через указатель, который указывает на его корень — первый элемент.

Односвязный список

Односвязный список (однонаправленный) является самой простой формой связного списка. В нём каждый узел состоит из двух полей:

• Данные (Value): Хранит полезную информацию.
• Указатель на следующий узел (Next): Содержит адрес следующего элемента в списке. Последний элемент списка имеет указатель на NULL, сигнализирующий о его конце.

Графически узел односвязного списка можно представить как блок, разделённый на две части: левая для данных, правая — для указателя, из которого выходит стрелка, направленная к следующему блоку (узлу).


[ Данные | Next ] --> [ Данные | Next ] --> ... --> [ Данные | NULL ]


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

Операции:

• Вставка в начало: Элементарна и быстра, имеет временную сложность O(1). Новый узел создаётся, его указатель Next направляется на текущий первый элемент, а затем корень списка обновляется, указывая на новый узел.
• Удаление из начала: Также O(1). Указатель корня просто перенаправляется на следующий элемент.
• Вставка/удаление в середине: Эти операции требуют предварительного поиска нужной позиции, что влечёт за собой обход части списка. В худшем случае, когда нужно найти элемент в конце или вставить его после него, это приводит к временной сложности O(n), так как приходится последовательно перебирать элементы.

Двусвязный список

Двусвязный список (двунаправленный) — это усовершенствованная версия односвязного списка, предлагающая значительно большую гибкость. В отличие от своего однонаправленного собрата, каждый узел двусвязного списка содержит не один, а два указателя:

• Данные (Value): Как и прежде, полезная информация.
• Указатель на следующий узел (Next): Адрес следующего элемента.
• Указатель на предыдущий узел (Previous): Адрес предшествующего элемента.

Графически узел двусвязного списка выглядит как блок с тремя полями: Previous слева, Данные в центре и Next справа. Стрелки от Previous и Next указывают на соответствующие узлы.


[ Prev | Данные | Next ] <--> [ Prev | Данные | Next ] <--> ... <--> [ Prev | Данные | NULL ]
NULL <-- [ Prev | Данные | Next ]

В двусвязном списке указатель Next последнего элемента равен NULL, а указатель Previous первого элемента также равен NULL. Это позволяет двигаться по списку в обоих направлениях: от начала к концу и от конца к началу, что упрощает и ускоряет многие операции. Например, после нахождения нужного элемента, вставка или удаление рядом с ним может быть выполнена за O(1), поскольку есть прямой доступ к предшествующему и последующему узлам.

Однако эта гибкость имеет свою цену — накладные расходы по памяти. Каждый узел двусвязного списка требует хранения двух указателей вместо одного, что означает примерно в два раза больше памяти для хранения указателей на каждый узел по сравнению с односвязным списком. Этот компромисс между удобством и потреблением памяти является ключевым при выборе типа связного списка, заставляя разработчика взвешивать приоритеты.

Циклический список

Циклический список (кольцевой, замкнутый) представляет собой особую разновидность связных списков, которая может быть как односвязной, так и двусвязной. Главная отличительная черта циклического списка заключается в том, что его последний элемент содержит указатель не на NULL, а на первый элемент списка. Таким образом, список образует замкнутое кольцо, и в нём отсутствуют NULL-указатели, которые обычно сигнализируют о конце или начале.

Если это односвязный циклический список, то указатель Next последнего элемента указывает на первый. В случае двусвязного циклического списка, помимо этого, указатель Previous первого элемента указывает на последний.

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

Стеки (LIFO): Принцип "Последним пришел – Первым вышел"

Представьте себе стопку тарелок: чтобы взять нижнюю, вам сначала придётся убрать все верхние. Именно этот принцип лежит в основе стека (от англ. stack — стопка) — одной из самых фундаментальных линейных структур данных, работающей по правилу LIFO (Last In — First Out), что означает "последним пришёл — первым вышел". Элементы добавляются и удаляются только с одного конца, который называется вершиной стека.

Стеки обладают строгим набором базовых операций:

• push (проталкивание): Добавляет элемент на вершину стека. Эта операция всегда выполняется за постоянное время, то есть имеет временную сложность O(1).
• pop (выталкивание): Удаляет элемент с вершины стека. Как и push, эта операция также имеет сложность O(1).
• peek (или back): Позволяет просмотреть значение верхнего элемента стека, не удаляя его. Сложность также O(1).
• size: Возвращает текущее количество элементов в стеке. Сложность O(1).
• clear: Очищает стек, удаляя все элементы.

Стеки играют критически важную роль в вычислительной технике. Один из наиболее распространённых примеров — стек вызовов функций в операционных системах и языках программирования. Когда одна функция вызывает другую, контекст текущей функции (локальные переменные, адрес возврата) помещается в стек. Когда вызванная функция завершается, её контекст извлекается из стека, и выполнение программы возвращается к предыдущей функции. Кроме того, стеки используются для синтаксического анализа выражений, реализации рекурсивных алгоритмов и управления памятью, демонстрируя свою универсальность.

Очереди (FIFO): Принцип "Первым пришел – Первым обслужен"

В отличие от стека, очередь функционирует по принципу FIFO (First In — First Out), что означает "первый пришёл — первый обслужен". Это аналогично очереди в магазине или на автобусной остановке: кто первым встал, того первым и обслужат. Элементы добавляются в один конец очереди (называемый хвостом или концом), а удаляются из другого (называемого головой или началом).

Основные операции с очередью также определены чётко:

• enqueue (поставить в очередь): Добавляет элемент в конец очереди. Временная сложность O(1).
• dequeue (убрать из очереди): Извлекает элемент из начала очереди, удаляя его. Временная сложность O(1).
• peek (или front): Позволяет просмотреть первый элемент очереди без его удаления. Сложность O(1).
• back: Обращение к последнему элементу очереди без его удаления. Сложность O(1).
• empty: Проверяет, пуста ли очередь. Сложность O(1).

Очереди незаменимы в задачах, где важен порядок обработки элементов, например, в системах управления буферами, планировщиках задач операционных систем, при обработке сетевых пакетов или в алгоритмах поиска в ширину (BFS) для обхода графов.

Сравнение реализаций очередей: Массив против Связного Списка

Очереди могут быть реализованы различными способами, но две наиболее распространённые реализации — это использование массива и связного списка. Каждая из них имеет свои уникальные преимущества и недостатки, которые необходимо учитывать при выборе оптимального решения.

Реализация на массиве:

• Преимущества:
  • Хорошая локальность данных: Элементы очереди хранятся в смежных ячейках памяти. Это повышает эффективность кэша процессора, так как при доступе к одному элементу соседние, скорее всего, уже будут загружены в кэш. Это может обеспечить более высокую производительность на практике, особенно при больших объёмах данных.
  • Минимальные накладные расходы на память: Для каждого элемента хранится только само значение, без дополнительных указателей, что делает реализацию более компактной с точки зрения памяти на единицу данных.
• Недостатки:
  • Фиксированный размер: Массив имеет ограниченный размер. При попытке добавить элемент в полную очередь возникает переполнение, что требует создания нового, большего массива и копирования всех элементов. Эта операция является дорогостоящей и имеет временную сложность O(n).
  • Неэффективная операция dequeue без кольцевого буфера: Если элементы просто удаляются из начала массива, то для поддержания "начала" очереди в первой ячейке необходимо сдвигать все последующие элементы влево. Это приводит к временной сложности O(n) для операции dequeue, что значительно ухудшает производительность. Для решения этой проблемы часто используется кольцевой буфер (циклический массив), где голова и хвост очереди перемещаются по кругу, а при достижении конца массива происходит "переворот" к его началу. В такой реализации dequeue также становится O(1).

Реализация на связном списке:

• Преимущества:
  • Динамический размер: Связный список легко расширяется и сжимается, адаптируясь к изменяющемуся количеству элементов без необходимости дорогостоящих перераспределений памяти и копирования.
  • Операции enqueue и dequeue имеют сложность O(1): Добавление в конец и удаление из начала очереди сводится к изменению указателей, что является очень быстрой операцией. Это достигается за счёт хранения указателей на голову и хвост списка.
• Недостатки:
  • Более высокие накладные расходы на память: Каждый элемент связного списка, помимо данных, хранит один или два указателя (для односвязного или двусвязного списка соответственно). Это увеличивает потребление памяти на каждый элемент.
  • Низкая локальность данных: Элементы связного списка могут быть расположены в произвольных областях памяти, что снижает эффективность кэша процессора. При обходе очереди процессор может чаще сталкиваться с промахами кэша, что потенциально замедляет работу.
  • Доступ к элементам по индексу имеет сложность O(n): Для доступа к k-му элементу необходимо последовательно пройти k узлов, что является медленной операцией.

Вывод: Выбор между массивной и списковой реализацией очереди ��ависит от конкретных требований задачи. Если количество элементов заранее известно и редко меняется, а также критична кэш-эффективность, массив (особенно в виде кольцевого буфера) может быть предпочтительнее. Если же размер очереди сильно варьируется, и частые вставки/удаления являются ключевыми операциями, то связный список обеспечит большую гибкость и стабильную O(1) производительность для этих операций.

Преобразование Арифметических Выражений и Его Значение

Мир программирования часто сталкивается с необходимостью обработки математических выражений. Однако привычная для человека инфиксная запись (например, A + B * C) с её приоритетами операций и скобками представляет определённые сложности для компьютерной обработки. Именно здесь на помощь приходит элегантное и мощное решение — обратная польская запись.

Обратная Польская Запись (ОПЗ): Постфиксная Нотация

Обратная польская запись (ОПЗ), также известная как постфиксная нотация, представляет собой уникальный способ записи математических и логических выражений, где знаки операций следуют за операндами, к которым они применяются. Главное преимущество ОПЗ заключается в её однозначности: она полностью исключает необходимость использования скобок для указания порядка выполнения операций. Это значительно упрощает её синтаксический анализ и вычисление компьютерными системами.

Рассмотрим пример:

• Инфиксное выражение: (a + b) * (c + d) - e
• Эквивалентное выражение в ОПЗ: ab + cd + * e -

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

Алгоритм преобразования в ОПЗ (Алгоритм сортировочной станции Дейкстры)

Алгоритм преобразования выражения из инфиксной формы в форму ОПЗ был предложен знаменитым учёным-компьютерщиком Эдсгером Дейкстрой и часто известен как алгоритм сортировочной станции. В его основе лежит использование стека для временного хранения операторов и скобок.

Приведём пошаговое описание алгоритма:

1. Инициализация: Создайте пустой стек для операторов и пустую выходную строку (или список) для ОПЗ.
2. Посимвольное чтение: Последовательно читайте символы из входной инфиксной строки слева направо.
   • Операнды: Если прочитанный символ является операндом (число, переменная), он немедленно переписывается в выходную строку.
   • Открывающая скобка (: Помещается в стек.
   • Закрывающая скобка ): Все операции из стека, начиная с вершины, выталкиваются в выходную строку до тех пор, пока не встретится ближайшая открывающая скобка (. Открывающая скобка удаляется из стека (но не записывается в выходную строку), а сама закрывающая скобка игнорируется. Если до открывающей скобки стек опустел, значит, в выражении ошибка (несбалансированные скобки).
   • Оператор ( +, -, *, /, ^ и т.д.):
     • Если стек пуст, или на вершине стека находится открывающая скобка (, текущий оператор помещается в стек.
     • В противном случае, пока на вершине стека находится оператор с большим или равным приоритетом (и, возможно, левоассоциативный оператор с равным приоритетом), этот оператор выталкивается в выходную строку.
     • После этого текущий оператор помещается в стек.
     • Пример приоритетов: ^ (возведение в степень) обычно имеет самый высокий приоритет, затем * и /, затем + и -.
3. Завершение: После того как все символы из входной инфиксной строки были обработаны:
   • Если в стеке остались какие-либо операторы, они поочерёдно выталкиваются в выходную строку.
   • Если при этом в стеке обнаруживается открывающая скобка, это указывает на ошибку (несбалансированные скобки).

Пример (из (A + B) * C в A B + C *):

Символ	Стек	Выходная строка (ОПЗ)	Комментарий
(	(		Открывающая скобка помещена в стек
A	(	A	Операнд сразу в ОПЗ
+	(, +	A	Оператор + помещен в стек (т.к. на вершине ()
B	(, +	A B	Операнд сразу в ОПЗ
)	(	A B +	+ вытолкнут в ОПЗ, ( удалена из стека
*	*	A B +	Оператор * помещен в стек
C	*	A B + C	Операнд сразу в ОПЗ
(конец)		A B + C *	* вытолкнут из стека в ОПЗ

Практическое применение ОПЗ

Обратная польская запись находит широкое применение в различных областях программирования благодаря своей простоте и однозначности:

• Компиляторы и интерпретаторы: Одним из основных применений является этап синтаксического анализа (парсинга) и генерации кода для математических выражений. Преобразование в ОПЗ значительно упрощает построение дерева синтаксического анализа и последующее вычисление выражений.
• Калькуляторы: Большинство инженерных и научных калькуляторов используют ОПЗ внутренне для выполнения вычислений. Это позволяет им обрабатывать сложные выражения без необходимости сложной логики для работы со скобками и приоритетами операторов.
• Базы данных: В некоторых системах управления базами данных (СУБД) запросы, содержащие математические операции, могут быть внутренне преобразованы в ОПЗ для более эффективного выполнения.
• Встроенные системы: В средах с ограниченными ресурсами памяти ОПЗ может быть очень ценной. Отсутствие скобок позволяет сократить объём программы за счёт уменьшения количества токенов (символов) в выражении. Например, (A + B) * (C - D) в инфиксной форме содержит 4 оператора и 4 скобки. В ОПЗ это A B + C D - *, что означает 4 оператора и 0 скобок. Это уменьшение количества символов может быть критичным для компактности кода, обеспечивая его эффективность в условиях ограниченных ресурсов.
• Обработка командной строки: Некоторые командные оболочки и утилиты могут использовать принципы ОПЗ для интерпретации сложных цепочек команд.

Таким образом, ОПЗ является не просто теоретической концепцией, а мощным инструментом, значительно упрощающим обработку арифметических выражений в самых разных программных системах.

Графы: Представление и Алгоритмические Основы

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

Матрица Смежности

Одним из наиболее интуитивно понятных способов представления графа является матрица смежности. Это квадратная матрица размером V×V, где V — количество вершин в графе. Каждая ячейка A_ij этой матрицы хранит информацию о наличии ребра между вершинами i и j.

• Если между вершинами i и j существует ребро, элемент A_ij равен 1.
• Если ребра нет, элемент A_ij равен 0.
• Для взвешенных графов (где ребра имеют "вес" или "стоимость") A_ij может хранить этот вес вместо 1.

Для неориентированного графа (где ребра не имеют направления, то есть связь i-j эквивалентна j-i), матрица смежности является симметричной относительно главной диагонали (A_ij = A_ji). В ориентированном графе (где ребра имеют направление, например, от i к j), A_ij ≠ A_ji, и матрица несимметрична.


Пример матрицы смежности для неориентированного графа с 4 вершинами:
1 2 3 4
1 |0 1 1 0|
2 |1 0 1 0|
3 |1 1 0 1|
4 |0 0 1 0|


Здесь A₁₂ = 1 означает, что между вершинами 1 и 2 есть ребро.

Недостатки и оптимальное применение

Главный недостаток матрицы смежности кроется в её потреблении памяти. Для графа с V вершинами требуется O(V²) памяти, поскольку матрица всегда квадратная. Это может быть крайне неэффективно для разреженных графов — графов, в которых количество рёбер (E) значительно меньше максимально возможного (V²). В таких случаях большая часть матрицы будет заполнена нулями, что является пустой тратой памяти.

Несмотря на это, матрица смежности удобна для представления плотных графов, где число ребер близко к максимально возможному. Она также позволяет быстро (за O(1)) проверить наличие ребра между любыми двумя вершинами, что является преимуществом для некоторых алгоритмов, часто выполняющих такие проверки, и в этих сценариях она демонстрирует свою эффективность.

Матрица Инцидентности

Матрица инцидентности — это ещё один способ представления графа, который связывает вершины с рёбрами. В этой матрице строки соответствуют вершинам, а столбцы — рёбрам.

• Для неориентированного графа, элемент B_ij равен 1, если вершина i является одним из концов ребра j. В противном случае, B_ij равен 0. Каждая колонка (ребро) будет содержать ровно две единицы.
• Для ориентированного графа (орграфа), элемент B_ij равен 1, если дуга j входит в вершину i, и -1, если дуга j выходит из вершины i. Если вершина i не связана с дугой j, B_ij равен 0. Каждая колонка (дуга) будет содержать одну 1 и одну -1.

Матрица инцидентности занимает O(V⋅E) памяти, что для большинства практических графов может быть больше, чем у матрицы смежности или списка смежности. Поэтому она используется реже, когда требуется явное связывание вершин и рёбер, а не только вершин друг с другом.

Список Смежности

Наиболее гибким и часто используемым способом представления графов, особенно разреженных, является список смежности. Он представляет собой массив (или вектор) списков, где каждый элемент массива соответствует вершине графа. С каждым элементом массива связан список, который содержит все вершины, непосредственно смежные с данной.


Пример списка смежности для неориентированного графа:
Вершина 1: [2, 3]
Вершина 2: [1, 3]
Вершина 3: [1, 2, 4]
Вершина 4: [3]


Здесь "Вершина 1: [2, 3]" означает, что из вершины 1 есть ребра к вершинам 2 и 3.

Представление графа в виде списка смежности значительно компактнее по сравнению с матрицей смежности, особенно для разреженных графов. Его потребление памяти составляет O(V + E), где V — количество вершин, а E — количество рёбер. Это делает его крайне эффективным для графов с большим количеством вершин, но относительно малым числом связей.

Сравнительный анализ потребления памяти

Чтобы наглядно продемонстрировать различия в потреблении памяти, рассмотрим граф с V = 100 вершинами.

Матрица смежности:
Потребляет V² единиц памяти. Для 100 вершин это будет 100² = 10 000 единиц памяти. (Единица памяти может быть булевым значением для невзвешенного графа или небольшим целым числом для взвешенного).

Список смежности:
Потребляет O(V + E) единиц памяти (плюс небольшие накладные расходы на узлы списка, которые здесь упростим до одной "единицы").

• Для плотного графа: Представим, что у нас почти полный неориентированный граф, где E ≈ V² / 2. Для 100 вершин это будет примерно 100² / 2 = 5000 ребер.
  В этом случае потребление памяти составит V + 2E (поскольку каждое ребро хранится дважды — для обеих вершин, к которым оно примыкает) = 100 + 2 * 5000 = 10 100 единиц памяти. В этом сценарии матрица смежности и список смежности сопоставимы по объёму занимаемой памяти.
• Для разреженного графа: Пусть E ≈ 2V, то есть каждое ребро имеет в среднем две связи. Для 100 вершин это будет примерно 2 * 100 = 200 ребер.
  Потребление памяти составит V + 2E = 100 + 2 * 200 = 500 единиц памяти. В этом случае список смежности значительно экономичнее по памяти (500 против 10 000).

Вывод: Очевидно, что для разреженных графов список смежности является гораздо более предпочтительным вариантом с точки зрения использования памяти. Более того, многие важные алгоритмы на графах, такие как поиск в глубину (DFS) и поиск в ширину (BFS), а также алгоритмы поиска кратчайших путей (например, алгоритм Дейкстры), часто более эффективно работают со списком смежности, поскольку они естественным образом обходят соседей каждой вершины. Это позволяет избегать избыточных и медленных итераций по всей строке или столбцу матрицы смежности, где большая часть значений может быть нулевой.

Эффективные Алгоритмы Сравнения Строк

Поиск подстроки в тексте — одна из наиболее распространённых задач в информатике, будь то поиск слова в документе, антивирусное сканирование или анализ ДНК. Разработано множество алгоритмов для решения этой задачи, каждый со своими особенностями и эффективностью.

Алгоритм Прямого Перебора (Наивный)

Алгоритм прямого перебора (наивный) является самым простым и очевидным подходом к поиску подстроки. Его принцип работы заключается в следующем:

1. Шаблон (подстрока) последовательно сравнивается с каждой возможной подстрокой текста той же длины.
2. Начинается сравнение с первой позиции текста. Первые m символов шаблона сравниваются с первыми m символами текста (где m — длина шаблона).
3. Если все символы совпадают, подстрока найдена.
4. Если найдено несовпадение, шаблон сдвигается на одну позицию вправо, и сравнение повторяется.


Текст: A B C D A B C E
Шаблон: A B C E

Попытка 1:
Текст: A B C D A B C E
Шаблон: A B C E
^ ^ ^ ^
Совпадение до D, но E не совпадает с D. Сдвиг на 1.

Попытка 2:
Текст: A B C D A B C E
Шаблон: A B C E
^
B не совпадает с A. Сдвиг на 1.
... и так далее.


Временная сложность: В худшем случае, например, когда шаблон AAAA ищется в тексте AAAAAAAAAB, алгоритм прямого перебора будет выполнять сравнения почти для каждой позиции, а затем для каждой позиции шаблона. Это приводит к временной сложности O(n⋅m), где n — длина текста, а m — длина шаблона. Для больших текстов и шаблонов такой подход становится крайне неэффективным, требуя значительных вычислительных ресурсов.

Алгоритм Рабина-Карпа

Алгоритм Рабина-Карпа предлагает более продвинутый подход, используя технику хеширования для ускорения сравнений. Вместо посимвольного сравнения каждой подстроки текста с шаблоном, алгоритм вычисляет хеш-значение для шаблона и хеш-значения для всех подстрок текста такой же длины.

Принцип работы:

1. Вычисляется хеш-значение для шаблона.
2. Для каждой подстроки текста, имеющей ту же длину, что и шаблон, вычисляется её хеш-значение.
3. Если хеш-значения шаблона и подстроки текста совпадают, тогда (и только тогда) производится посимвольная проверка, чтобы исключить коллизии хеш-функции (когда разные строки имеют одинаковый хеш).
4. Ключевой особенностью является использование "скользящего хеша" (rolling hash), который позволяет эффективно пересчитывать хеш для следующей подстроки текста за O(1) время, не пересчитывая его с нуля.

Временная сложность:

• Среднее время исполнения: При правильном выборе хеш-функции, которая минимизирует коллизии, средняя временная сложность алгоритма Рабина-Карпа составляет O(n). Это достигается благодаря быстрому пересчёту хешей и редким посимвольным проверкам.
• Худший случай: В худшем случае, если хеш-функция даёт много коллизий (например, все подстроки имеют одинаковый хеш), алгоритм может деградировать до O(nm), поскольку придётся выполнять посимвольную проверку для каждой позиции.

Практическое применение: Алгоритм Рабина-Карпа особенно эффективен для:

• Определения плагиата: Сравнение больших объёмов текста на предмет совпадений.
• Поиска множественных шаблонов: Если нужно найти несколько шаблонов одинаковой длины в одном тексте, можно вычислить хеш каждого шаблона и затем искать их все за один проход по тексту.

Алгоритм Бойера-Мура

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

1. Сравнение справа налево: Шаблон выравнивается по началу текста, но сравнение символов начинается с последнего символа шаблона и движется к первому.
2. Эвристика "плохого символа" (Bad Character Rule): Если при сравнении справа налево обнаружено несовпадение символа в шаблоне с символом в тексте (называемым "плохим символом"), алгоритм смотрит, есть ли этот "плохой символ" в шаблоне.
   • Если "плохого символа" нет в шаблоне, шаблон сдвигается за этот "плохой символ".
   • Если "плохой символ" есть в шаблоне, шаблон сдвигается таким образом, чтобы ближайшее вхождение этого символа в шаблоне (справа налево) совпало с "плохим символом" в тексте. Это позволяет избежать ненужных сравнений.
3. Эвристика "хорошего суффикса" (Good Suffix Rule): Если часть шаблона (суффикс) уже совпала с текстом, но затем п��оизошло несовпадение, алгоритм ищет в шаблоне другое вхождение этого "хорошего суффикса". Шаблон сдвигается таким образом, чтобы это следующее вхождение суффикса в шаблоне совпало с уже совпавшим суффиксом в тексте.

Благодаря этим эвристикам, алгоритм Бойера-Мура часто делает "прыжки" на несколько символов, значительно сокращая количество сравнений.

Анализ временной сложности

• Лучший случай: Ω(n/m) сравнений. Это происходит, когда шаблон находится в начале текста, и обе эвристики позволяют эффективно пропускать символы. Например, при поиске шаблона ABC в тексте AAAAAAAAAAAAAAAAAABC, алгоритм может сделать очень большие сдвиги. Предварительная обработка шаблона занимает O(m) времени.
• Худший случай: O(n⋅m). Такой случай может возникнуть на специально подобранных "неудачных" текстах, например, при поиске AAAAA в AAAAAAAAB. Однако, для непериодических шаблонов, в худшем случае требуется не более 3n сравнений символов текста, что является весьма эффективным результатом.
• Средний случай: На практике, средняя временная сложность алгоритма Бойера-Мура часто приближается к O(n + m) или даже лучше — O(n/m), особенно когда размер алфавита (множества возможных символов) велик по сравнению с длиной шаблона. В большинстве реальных сценариев он считается одним из самых быстрых алгоритмов поиска подстрок.

Алгоритм Кнута-Морриса-Пратта (КМП)

Алгоритм Кнута-Морриса-Пратта (КМП) является ещё одним высокоэффективным алгоритмом, который гарантирует линейную временную сложность O(n) в худшем случае. Его уникальность заключается в том, что он никогда не возвращается назад по тексту, а движется только вперёд.

Основой алгоритма КМП является использование префикс-функции (также известной как "failure function" или "next array"), которая предварительно вычисляется для шаблона. Префикс-функция для каждого символа шаблона указывает на длину наибольшего собственного префикса, который также является суффиксом текущей части шаблона.

Принцип работы:

1. Предварительная обработка шаблона: Вычисляется префикс-функция для всего шаблона. Эта фаза занимает O(m) времени.
2. Поиск: При сравнении шаблона с текстом, если происходит несовпадение, алгоритм использует значения префикс-функции, чтобы определить, на сколько символов нужно сдвинуть шаблон. Это позволяет избегать избыточных сравнений, которые характерны для наивного алгоритма, и никогда не просматривать уже сравненные символы текста повторно.

КМП алгоритм очень ценен в ситуациях, когда текст может быть очень длинным или даже бесконечным (например, в потоковой передаче данных), поскольку он обрабатывает каждый символ текста только один раз, обеспечивая оптимальную производительность.

Деревья Сортировки: Бинарные Деревья Поиска

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

Бинарное Дерево Поиска (БДП): Определение и Свойства

Бинарное дерево поиска (БДП) — это особый тип бинарного дерева (где каждый узел имеет не более двух дочерних узлов), которое удовлетворяет строго определённым условиям, обеспечивающим эффективность поиска:

1. Бинарная структура: Каждый узел (кроме листьев) имеет максимум два дочерних узла, называемых левым и правым потомками.
2. Иерархия: Все узлы левого поддерева произвольного узла X должны иметь значения ключей данных меньше, чем значение ключа данных самого узла X.
3. Иерархия (продолжение): Все узлы правого поддерева произвольного узла X должны иметь значения ключей данных не меньше (то есть больше или равны), чем значение ключа данных узла X.
4. Рекурсивное свойство: Оба поддерева (левое и правое) сами по себе также являются бинарными деревьями поиска.
5. Ключи данных: Данные в каждом узле должны обладать ключами, для которых определена операция сравнения (например, числа, строки).

Эти свойства гарантируют, что при поиске элемента достаточно сравнивать его значение с текущим узлом и принимать решение, двигаться ли в левое или правое поддерево, что существенно сокращает область поиска и ускоряет доступ к данным.

Построение Дерева Сортировки

Процесс построения дерева сортировки (то есть бинарного дерева поиска) из неупорядоченной последовательности элементов достаточно прост и основывается на рекурсивном применении правил БДП:

1. Инициализация: Первый элемент сортируемой последовательности становится корнем дерева.
2. Вставка последующих элементов: Для каждого последующего элемента из последовательности:
   • Сравните его значение с ключом текущего узла.
   • Если новый элемент меньше ключа текущего узла, перейдите в его левое поддерево.
   • Если новый элемент больше или равен ключу текущего узла, перейдите в его правое поддерево.
   • Продолжайте этот процесс рекурсивно, пока не будет найдено пустое место (NULL-указатель), куда и вставляется новый узел.

Таким образом, дерево постепенно формируется, а его структура отражает относительный порядок элементов.

Использование для Сортировки

Одним из элегантных применений бинарного дерева поиска является сортировка. После того как все элементы исходной последовательности были вставлены в структуру БДП, для получения отсортированной последовательности необходимо выполнить специфический обход дерева, который называется инфиксным (или симметричным) обходом.

Инфиксный обход предполагает следующие шаги для каждого узла:

1. Рекурсивно обойти левое поддерево.
2. Обработать (посетить) сам узел (например, вывести его значение).
3. Рекурсивно обойти правое поддерево.

Поскольку в БДП все элементы левого поддерева меньше корня, а все элементы правого поддерева больше или равны корню, инфиксный обход гарантированно выдаст элементы в строго возрастающем порядке.

Характеристики и Операции в БДП

Эффективность бинарного дерева поиска проявляется в скорости выполнения основных операций:

• Поиск элемента: В сбалансированном бинарном дереве поиска операция поиска элемента занимает O(logN) времени, где N — количество узлов. Это объясняется тем, что на каждом шаге поиска область потенциальных узлов сокращается примерно вдвое.
• Вставка элемента: Аналогично поиску, вставка нового узла в сбалансированное БДП также выполняется за O(logN) времени.
• Удаление элемента: Удаление элемента из сбалансированного БДП также занимает O(logN) времени, хотя эта операция является одной из самых сложных из-за необходимости поддержания свойств БДП.

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

Сбалансированные и Несбалансированные Деревья Поиска

Критически важным аспектом для производительности БДП является его сбалансированность.

Определение сбалансированного состояния: Бинарное дерево считается сбалансированным, если для любого его узла высоты его левого и правого поддеревьев отличаются не более чем на 1. Это свойство гарантирует, что дерево не выродится в линейный список, и его высота останется логарифмической (O(logN)).

Проблема несбалансированных деревьев: Если элементы вставляются в БДП в уже отсортированном или почти отсортированном порядке, дерево может выродиться в линейный список (или "палку"). В таком случае, операции поиска, вставки и удаления будут иметь временную сложность O(n), что ничем не лучше, чем поиск в обычном связном списке или массиве в худшем случае, и может привести к критическому падению производительности.

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

• АВЛ-деревья: Первые самобалансирующиеся БДП, названные в честь своих изобретателей Адельсона-Вельского и Ландиса. Они строго поддерживают условие баланса (разница высот поддеревьев не более 1).
• Красно-чёрные деревья: Более сложный, но также очень эффективный тип самобалансирующихся деревьев, широко используемый, например, в стандартных библиотеках многих языков программирования (например, std::map в C++ или TreeMap в Java).

Эти деревья гарантируют, что независимо от порядка вставки элементов, высота дерева всегда будет логарифмической, что обеспечивает стабильную и высокую производительность для всех основных операций (поиска, вставки, удаления) на уровне O(logN).

Хеш-Таблицы: Эффективный Доступ по Ключу

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

Введение в Хеш-Таблицы

Суть хеш-таблицы заключается в использовании хеш-функции. Это функция, которая принимает на вход ключ (например, строку или число) и преобразует его в целое число — хеш-значение. Это хеш-значение затем используется как индекс в базовом массиве (или векторе), где фактически хранятся данные. Идеальная хеш-функция должна быть:

• Простой с вычислительной точки зрения: Быстро вычислять хеш.
• Равномерно распределять ключи: Генерировать индексы таким образом, чтобы элементы равномерно распределялись по всей хеш-таблице.
• Минимизировать количество коллизий: Желательно, чтобы разные ключи давали разные хеш-значения.

Цель такого преобразования — обеспечить доступ к данным за время, близкое к O(1) в среднем случае, то есть независимо от количества элементов в таблице.

Понятие Коллизии

Однако на практике идеальных хеш-функций не существует, особенно когда диапазон возможных ключей намного больше размера самой хеш-таблицы. В таких случаях неизбежно возникает коллизия: ситуация, когда два или более разных ключа, будучи обработанными одной и той же хеш-функцией, генерируют один и тот же хеш-значение (то есть указывают на один и тот же индекс в базовом массиве).

Коллизии — это не ошибка, а естественное следствие работы хеш-функций. Главная задача при проектировании хеш-таблиц — не избежать коллизий (что часто невозможно), а разработать эффективные стратегии для их разрешения, чтобы найти новое место для хранения "конфликтующих" ключей, не жертвуя при этом производительностью.

Методы Разрешения Коллизий

Существуют два основных класса методов для разрешения коллизий: метод цепочек (внешнее хеширование) и метод открытой адресации (закрытое хеширование).

Метод цепочек (Внешнее хеширование)

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

• Принцип работы:
  1. При вставке элемента (ключ, значение) вычисляется хеш-функция h(ключ).
  2. Элемент добавляется в связанный список, который находится по индексу h(ключ) в базовом массиве.
  3. Если ячейка пуста, она содержит NIL (или nullptr), и новый элемент становится первым в списке.
• Операции: Вставка, удаление и поиск элемента сводятся к выполнению соответствующих операций (вставки, удаления, поиска) над связанным списком, находящимся по вычисленному хеш-индексу.
• Временная сложность:
  • В среднем: При равномерном распределении ключей хеш-функцией, длина каждого связанного списка будет небольшой. Поэтому операции вставки, удаления и поиска имеют среднюю временную сложность O(1).
  • В худшем случае: Если хеш-функция работает плохо, и все ключи хешируются в одну и ту же ячейку, то все элементы окажутся в одном длинном связанном списке. В этом сценарии операции деградируют до O(n), так как потребуется обход всего списка.
• Преимущества: Относительно прост в реализации, хорошо работает при высоких коэффициентах загрузки (отношение количества элементов к размеру таблицы).

Метод Открытой Адресации (Закрытое хеширование)

В отличие от метода цепочек, при открытой адресации все записи хранятся непосредственно в самой хеш-таблице, без использования внешних связанных списков. Каждая ячейка таблицы содержит либо сам элемент, либо специальное значение NULL (или EMPTY), указывающее на её пустоту.

• Принцип работы: При возникновении коллизии (когда вычисленный хеш-индекс h(ключ) уже занят), для поиска свободного места используется специальная последовательность зондирования (probe sequence). Это алгоритм, который генерирует последовательность альтернативных индексов, пока не будет найдена свободная ячейка.
• Временная сложность:
  • В среднем: При хорошей хеш-функции и низком коэффициенте загрузки, операции вставки, удаления и поиска также имеют среднюю временную сложность O(1).
  • В худшем случае: При плохом распределении ключей или сильной кластеризации (скоплении элементов в соседних ячейках), эти операции могут деградировать до O(n), поскольку придётся просматривать значительную часть таблицы.
• Преимущества: Отсутствие накладных расходов на указатели, что может экономить память.
• Разновидности открытой адресации:
  • Линейное зондирование (линейное пробирование):
    • Принцип: При коллизии проверяется следующая ячейка по порядку. Если индекс i занят, проверяется i+1, затем i+2 и так далее по модулю размера таблицы m. Формула для генерации последовательности зондирования: h(k, i) = (h'(k) + i) mod m, где h'(k) — начальный хеш-индекс, i — шаг (0, 1, 2, ...).
    • Проблема первичной кластеризации: Основным недостатком линейного зондирования является образование кластеров — больших непрерывных блоков занятых ячеек. Когда новый элемент хешируется в такой кластер или рядом с ним, ему приходится просматривать весь кластер для нахождения свободного места. По мере заполнения таблицы (увеличения коэффициента загрузки), эти кластеры растут, что значительно увеличивает среднее время выполнения операций, потенциально приближая его к O(n), что ставит под угрозу производительность системы.
  • Квадратичное зондирование:
    • Принцип: Чтобы уменьшить проблему кластеризации, шаг при поиске свободного места изменяется не линейно, а квадратично. Формула: h(k, i) = (h'(k) + c₁i + c₂i²) mod m, где c₁ и c₂ — константы. Это помогает более широко "разбросать" элементы по таблице.
  • Двойное хеширование:
    • Принцип: При коллизии, вместо фиксированного или квадратичного шага, для определения следующей ячейки вычисляется вторая хеш-функция h₂(k). Формула: h(k, i) = (h₁(k) + i ⋅ h₂(k)) mod m. Это обеспечивает наиболее равномерное распределение зондирующих последовательностей и значительно снижает вероятность кластеризации.

Свойства Хорошей Хеш-Функции

Эффективность хеш-таблицы в значительной степени зависит от качества используемой хеш-функции. Идеальная хеш-функция должна обладать следующими свойствами:

• Простота с вычислительной точки зрения: Функция должна быть быстрой, чтобы не замедлять операции вставки, удаления и поиска.
• Равномерное распределение ключей: Функция должна максимально равномерно распределять хеш-значения по всему диапазону индексов базового массива. Это минимизирует вероятность коллизий и обеспечивает сбалансированное использование памяти.
• Минимизация количества коллизий: Хотя полное исключение коллизий часто невозможно, хорошая хеш-функция должна стараться генерировать как можно меньше одинаковых хеш-значений для разных ключей.

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

Заключение

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

Мы углубились в механизмы работы стеков (LIFO) и очередей (FIFO), проанализировали алгоритм преобразования арифметических выражений в обратную польскую запись, что является краеугольным камнем для компиляторов и интерпретаторов. Исследовали различные способы представления графов в памяти, сравнив матрицу смежности, матрицу инцидентности и список смежности, демонстрируя их применимость в зависимости от плотности графа. Рассмотрели эффективность алгоритмов сравнения строк, таких как наивный подход, алгоритм Рабина-Карпа, Бойера-Мура и КМП, подчеркнув их производительность в различных сценариях. Наконец, мы разобрались в устройстве бинарных деревьев поиска, их роли в сортировке и важности балансировки, а также в методах адресации и разрешения коллизий в хеш-таблицах, которые обеспечивают молниеносный доступ к данным по ключу.

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

Надеемся, что этот реферат станет ценным ресурсом для студентов и будущих специалистов в области информатики и программирования. Дальнейшее углубленное изучение этих тем, их практическое применение и экспериментирование с различными реализациями позволят вам не только успешно справляться с типовыми задачами, но и самостоятельно разрабатывать инновационные алгоритмические решения. Мир программирования постоянно развивается, но фундамент, заложенный структурами данных и алгоритмами, остаётся неизменным ориентиром в этом стремительном прогрессе. Продолжайте учиться, экспериментировать и строить!

Список использованной литературы

1. Красиков, И. В. Алгоритмы. Просто как 2х2 / И. В. Красиков, И. Е. Красикова. – М. : Эксмо, 2007. – 256 с.
2. Колдаев, В. Д. Основы алгоритмизации и программирования: Учебное пособие / В. Д. Колдаев; под ред. Л. Г. Гагариной. – М. : ИД «ФОРУМ»: ИНФРА-М, 2006. – 416 с.
3. Ахо, А. Структуры данных и алгоритмы / А. Ахо, В. Хопкрофт, Д. Ульман, Д. Джеффри. – М. : ИД «Вильямс», 2003. – 384 с.
4. Вирт, Н. Алгоритмы + Структуры данных = Программы / Н. Вирт.
5. Графы: основы теории, алгоритмы поиска / А. Шагин // NOP::Nuances of Programming : [сайт]. – URL: https://medium.com/nuances-of-programming/графы-основы-теории-алгоритмы-поиска-9a7f34c67c7e (дата обращения: 03.11.2025).
6. Почему работает алгоритм преобразования инфиксной записи в постфиксную // Habr : [сайт]. – URL: https://habr.com/ru/articles/707996/ (дата обращения: 03.11.2025).
7. Сортировка с помощью дерева // prog-cpp.ru : [сайт]. – URL: https://prog-cpp.ru/sort-tree/ (дата обращения: 03.11.2025).
8. Алгоритмы и структуры данных для начинающих: стеки и очереди // Tproger : [сайт]. – URL: https://tproger.ru/articles/algoritmy-i-struktury-dannyh-dlya-nachinayushhih-steki-i-ocheredi/ (дата обращения: 03.11.2025).
9. Многообразие связных списков // Habr : [сайт]. – URL: https://habr.com/ru/articles/484920/ (дата обращения: 03.11.2025).
10. Связные списки: классификация, основные понятия // prog-cpp.ru : [сайт]. – URL: https://prog-cpp.ru/linked-list/ (дата обращения: 03.11.2025).
11. Бинарные деревья | Алгоритмы на деревьях // Хекслет : [сайт]. – URL: https://ru.hexlet.io/courses/introduction_to_programming/lessons/trees/theory_unit (дата обращения: 03.11.2025).
12. Бинарное дерево: что это такое и как оно работает // Skyeng : [сайт]. – URL: https://skyeng.ru/articles/binarnoe-derevo-chto-eto-takoe-i-kak-ono-rabotaet/ (дата обращения: 03.11.2025).
13. Обратная польская нотация // YouTube : [видео]. – URL: https://www.youtube.com/watch?v=F_S9gL_s7fE (дата обращения: 03.11.2025).
14. Односвязный список // Яндекс Образование : [сайт]. – URL: https://education.yandex.ru/ege/materials/informatics/odnosvyaznyy-spisok/ (дата обращения: 03.11.2025).
15. Дерево поиска, наивная реализация // Викиконспекты : [сайт]. – URL: https://neerc.ifmo.ru/wiki/index.php?title=Дерево_поиска,_наивная_реализация (дата обращения: 03.11.2025).
16. Поиск подстроки (образца) в строке (string-matching). Алгоритмы: Рабина-Карпа Кнута-Морриса-Пратта, Бойера-Мура // ВУнивере.ру : [сайт]. – URL: https://vunivere.ru/works/31206 (дата обращения: 03.11.2025).
17. Строковые алгоритмы на практике. Часть 3 — Алгоритм Рабина — Карпа // Habr : [сайт]. – URL: https://habr.com/ru/companies/mailru/articles/321852/ (дата обращения: 03.11.2025).
18. Строковые алгоритмы на практике. Часть 2 — Алгоритм Бойера — Мура // Habr : [сайт]. – URL: https://habr.com/ru/companies/mailru/articles/321850/ (дата обращения: 03.11.2025).
19. Какие алгоритмы существуют для поиска подстрок в текстовых данных? // Яндекс : [сайт]. – URL: https://yandex.ru/turbo/yandex.ru/s/support/search/algorithm.html (дата обращения: 03.11.2025).