Начало
Учебные материалы
Этапы решения алгоритмической задачи. Базовые структуры данных
Этапы решения алгоритмической задачи Важные типы задач Линейные структуры данных Графы Деревья Множества и словари
Линейные структуры данных
*Структурой данных* будем называть способ организации взаимосвязанных элементов данных.
Среди линейных структур данных можно выделить две самых важных —
одномерный массив и связный список.
*Одномерный массив* — это последовательность из `n` однотипных элементов, расположенных подряд в оперативной
памяти компьютера, доступ к которым выполняется по значению так называемого *индекса* массива.
--
Индекс массива, состоящего из п элементов, является
целым числом и принимает значения от 0 до `n-1` или от 1 до `n`.
В некоторых языках можно указать явно нижнюю и верхнюю границы изменения индекса.
Время обращения к любому элементу массива одинаково и не зависит от его положения в массиве.
На основе одномерных массивов создаются различные структуры данных, например, многомерные массивы (матрицы), строки (массивы из символов).
--
*Связный список* — это последовательность (которая может быть пустой)
нескольких элементов данных, называемых *узлами*. В каждом узле
хранится информация двух видов: собственно данные узла и одна или несколько
ссылок на другие узлы связного списка, называемых указателями.
Специальное значение указателя null говорит о том, что
указатель ни на что не указывает.
В *однонаправленном связном списке* (односвязном списке) каждый узел содержит только один указатель, в который
помещается ссылка на следующий элемент списка, либо null, если текущий элемент
является последним.
--
Для обращения к заданному элементу связного списка необходимо выбрать
первый узел списка, а затем перемещаться по цепочке элементов до достижения
нужного узла. Поэтому, в отличие от одномерных массивов, время,
затрачиваемое на доступ к произвольному элементу однонаправленного списка зависит
от его положения в списке. Это является существенным недостатком
связного списка.
Однако у него есть и преимущества. Во-первых, что для
элементов связного списка не требуется предварительное резервирование
оперативной памяти компьютера. Во-вторых, вставка и удаление элементов списка
не представляют особого труда и выполняются достаточно быстро изменением
значений нескольких указателей.
--
Часто в начале связного списка добавляют специальный узел,
называемый *головой*, в который помещают текущее количество элементов в списке и указатели на первый и последний
элементы списка.
В двунаправленном связном списке (двусвязном списке) каждый узел содержит указатели на предыдущий и последующий узлы:
Массив и связный список являются представлениями абстрактной структуры данных, которую называют список (в математике конечная последовательность),
т.е. набор элементов данных, организованных в заданном линейном порядке. Базовыми операциями для списка являются
поиск, добавление и удаление элемента.
--
Выделяют специальные ограниченные по допустимым операциям разновидности списка, которые часто используются в алгоритмах.
*Стеком* называют такой список, в котором можно удалить только последний элемент, а новый элемент добавить только в его конец.
Последний элемент называют *вершиной* стека, поскольку стек обычно изображают на рисунках
как стопку книг. Принципом работы стека является
"последним вошел, первым вышел" ("last-in-first-out", или LIFO), поскольку первым
из стека всегда удаляется элемент, добавленный в него последним. Нельзя выдернуть книгу из середины стопки, или добавить в середину новую.
--
*Очередью* называют такой список, в котором
добавление элемента возможно лишь в конец очереди, удаление — только из начала очереди.
Принципом работы является "первым
вошел, первым вышел" ("first-in-first-out", или FIFO). Здесь есть
полная аналогия с очередью в магазине.
*Двухсторонняя очередь* или дек (deque — double ended queue) - это список,
в котором элементы можно добавлять и удалять как в начало, так и в конец.
Во многих алгоритмах требуется искать в списке элемент с наивысшим приоритетом.
Для решения подобной задачи применяют специальную структуру данных,
которая называется *очередью с приоритетами*.
К основным операциям над очередью с приоритетами относятся: поиск наибольшего
элемента, удаление наибольшего элемента и добавление нового элемента.
