2.1. СТРУКТУРЫ ДАННЫХ: СПИСКИ, ОЧЕРЕДИ И СТЕКИ

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

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

Рассмотрим список

Простейшей его реализацией будет структура последовательно связанных компонент, изображенная на рис. 2.1. Каждая компонента в этой структуре состоит из двух ячеек памяти. Первая ячейка содержит сам элемент 4), вторая — указатель следующего элемента. Это можно реализовать в виде двух массивов, которые на рис. 2.2 названы ИМЯ и СЛЕДУЮЩАЯ 2). Если КОМПОНЕНТА - индекс в рассматриваемом массиве, то ИМЯ [КОМПОНЕНТА] - сам элемент, хранящийся там, а СЛЕДУЮЩАЯ [КОМПОНЕНТА] - индекс следующего элемента в списке (если такой элемент существует). Если КОМПОНЕНТА - индекс последнего элемента в этом списке, то СЛЕДУЮЩАЯ[КОМПОНЕНТА]=0.

На рис. 2.2 СЛЕДУЮЩАЯ означает постоянный указатель на первую компоненту в списке. Заметим, что порядок элементов в

Рис. 2.1. Список со связями.

Рис. 2.2. Представление списка из четырех элементов.

массиве ИМЯ не совпадает с их порядком в списке. Тем не менее рис. 2.2 дает верное представление списка, изображенного на рис. 2.1, так как массив располагает элементы в том же порядке, в каком они расположены в списке (2.1).

Опишем процедуру, вставляющую новую компоненту в список. В ней предполагается, что номер незанятой ячейки в массивах ИМЯ и а индекс той компоненты в списке, после которой надлежит вставить ЭЛЕМЕНТ:

Любой разумный перевод в команды РАМ приведет к тому, что время выполнения процедуры ВСТАВИТЬ не будет зависеть от размера списка.

Пример 2.1. Допустим, что мы хотим вставить в список (2.1) элемент Новэлем после Элем 2 и получить список

Если пятая ячейка в каждом массиве на рис. 2.2 пуста, можно вставить Новэлем после Элем 2 (позиция 3), вызвав . В результате выполнения трех операторов в процедуре ВСТАВИТЬ получим: Новэлем,

Рис. 2.3. Список со вставленным элементом Новэлем.

и тем самым создадутся массивы, показанные на рис. 2,3.

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

Часто в один и тот же массив вкладываются несколько списков Обычно один из этих списков состоит из незанятых ячеек; мы будем называть его свободным списком. Для добавления элемента к списку А можно так изменить процедуру ВСТАВИТЬ, чтобы незанятая ячейка получалась путем удаления первой ячейки в свободном списке. При удалении элемента из списка А соответствующая ячейка возвращается в свободный список для будущего употребления.

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

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

Рис. 2.4. Реализация стека.

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

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

Со списком часто работают очень ограниченными приемами. Например, элементы добавляются или удаляются только на конце списка. Иными словами, элементы вставляются и удаляются по принципу "последний вошел — первый вышел". В этом случае список называют стеком или магазином.

Часто стек реализуется в виде одного массива. Например, список

можно было бы хранить в массиве ИМЯ, как показано на рис. 2.4. Переменная ВЕРШИНА является указателем последнего элемента, добавленного к стеку. Чтобы добавить новый элемент в стек, значение ВЕРШИНА увеличивают на 1, а затем помещают новый элемент в (Поскольку массив ИМЯ имеет конечную длину I, перед попыткой вставить новый элемент следует проверить, что Чтобы удалить элемент из вершины стека, надо просто уменьшить значение ВЕРШИНА на 1. Заметим, что не обязательно физически стирать элемент, удаляемый из стека. Чтобы узнать, пуст ли стек, достаточно проверить, не имеет ли ВЕРШИНА значение, меньшее нуля. Понятно, что время выполнения операций ЗАТОЛКНУТЬ и

Рис. 2.5. Реализация очереди в виде одного массива.

ВЫТОЛКНУТЬ и проверка пустоты не зависят от числа элементов в стеке.

Другой специальный вид списка — очередь, т. е. список, в который элементы всегда добавляются с одного (переднего) конца, а удаляются с другого. Как и стек, очередь можно реализовать одним массивом, как показано на рис. 2.5, где приведена очередь, содержащая список из элементов Два указателя обозначают ячейки текущего переднего и заднего концов очереди. Чтобы добавить новый элемент к очереди, как и в случае стека, полагают и помещают новый элемент в Чтобы удалить элемент из очереди, заменяют ЗАДНИЙ на Заметьте, что эта техника с точки зрения доступа к элементам основана на принципе "первый вошел — первый вышел".

Поскольку массив ИМЯ имеет конечную длину, скажем указатели ПЕРЕДНИЙ и ЗАДНИЙ рано или поздно доберутся до его конца. Если длина списка, представленного этой очередью, никогда не превосходит I, то можно трактовать как элемент, следующий за элементом

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

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