Этапы решения алгоритмической задачи. Базовые структуры данных

Ранее отмечалось, что выбор структур данных существенно влияет на процесс проектирования алгоритма.

Структурой данных будем называть способ организации взаимосвязанных элементов данных.

Среди линейных структур данных можно выделить две самых важных — одномерный массив и связный список.

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

Индекс массива, состоящего из п элементов, является целым числом и принимает значения от 0 до `n-1` или от 1 до `n`. В некоторых языках можно указать явно нижнюю и верхнюю границы изменения индекса.

Время обращения к любому элементу массива одинаково и не зависит от его положения в массиве.

На основе одномерных массивов создаются различные структуры данных, например, многомерные массивы (матрицы), строки (массивы из символов).

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

В однонаправленном связном списке (односвязном списке) каждый узел содержит только один указатель, в который помещается ссылка на следующий элемент списка, либо null, если текущий элемент является последним.

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

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

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

В двунаправленном связном списке (двусвязном списке) каждый узел содержит указатели на предыдущий и последующий узлы:

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

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

Стеком называют такой список, в котором можно удалить только последний элемент, а новый элемент добавить только в его конец. Последний элемент называют вершиной стека, поскольку стек обычно изображают на рисунках как стопку книг. Принципом работы стека является "последним вошел, первым вышел" ("last-in-first-out", или LIFO), поскольку первым из стека всегда удаляется элемент, добавленный в него последним. Нельзя выдернуть книгу из середины стопки, или добавить в середину новую.

Очередью называют такой список, в котором добавление элемента возможно лишь в конец очереди, удаление — только из начала очереди. Принципом работы является "первым вошел, первым вышел" ("first-in-first-out", или FIFO). Здесь есть полная аналогия с очередью в магазине.

Двухсторонняя очередь или дек (deque — double ended queue) - это список, в котором элементы можно добавлять и удалять как в начало, так и в конец.

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