Базовые структуры данных. Деки, списки и хеш-таблицы

Лекция 3: Базовые структуры данных. Деки, списки и хеш-таблицы

0  Начала

Структура данных – одна из основ программирования. Если алгоритм, это то, как делать, то структура – это то, над чем делать.

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

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

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

1  Деки

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

Над деком можно производить четыре операции:

§  pushFront(D, x) – добавить элемент x в начало дека D.

§  pushBack(D, x) – добавить элемент x в конец дека D.

§  popFront(D) – удалить элемент с начала дека D.

§  popBack(D) – удалить элемент с конца дека D.

При этом операции удаления элемента могут возвращать удалённый элемент. Все эти операции выполняются за время Θ(1).

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

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

У дека также есть свойства, такие как размер, начало, конец и прочие. Начало и конец дека (указатели на крайние элементы или их индексы в массиве, содержащем дек) необходимо знать для выполнения тех самых основных операций над ним.

Реализовывать дек можно как с помощью двусвязных списков, так и на основе массивов. Реализовать дек очень просто (см. домашнее задание).

1.1  Очередь

Возьмите дек и скажите, что в этот дек элементы можно добавлять только с начала, а удалять только с конца. Вы получите очередь. Таким образом, очередь – это дек без операций pushBack() и popFront() (или pushFront() и popBack() – не суть важно). Так что всё вышесказанное относительно дека относится также и к очереди.

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

Применяется очередь очень широко. В тех же мультизадачных системах каждая задача ждёт своего времени в очереди.

1.2  Стек

Проведём над деком примерно те же пассы, что и в главе 1.1. Если ограничить работу с деком только одним краем (т. е. или началом или концом), мы получим стек. Итак, стек – это дек, операции над которым проводятся только с одним из его концов. Соответственно, почти всё сказанное относительно дека справедливо и для стека.

Стек также очень просто реализовать на массиве.

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

1.3  Послесловие

Как вы увидели, дек – очень полезная структура. Ещё полезней (в том числе и из-за более простой реализации) стек и очередь. Вообще говоря, дек редко применяется в чистом виде (может, даже реже чем его уточнение – стек).

2  Списки

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

2.1  Определения

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