Глава 2. Представление абстрактных объектов

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

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

2.1. Представление последовательностей

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

2.1.1. Смежное представление

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

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

Алгоритм 2.1. Включение и исключение элементов при последовательном размещении

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

2.1.2. Характеристические векторы

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

Например, для последовательности (1,2,3,4,5,6,7,8,9) характеристический вектор подпоследовательности чисел, кратных 3, имеет вид (0,0,1,0,0,1,0,0,1).

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

2.1.3. Связанное размещение

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

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

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

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

С помощью связанных распределений мы добились большей гибкости, но потеряли возможность работать с элементами последовательности как с массивами, когда по номеру можно непосредственно обратиться к элементу . В связанном размещении такой возможности не существует, и доступ к элементам последовательности не является прямым и эффективным. Например, при поиске среднего элемента последовательности, даже при известной ее длине, требуется просмотреть по связанному списку половину последовательности. В алгоритмах 2.2 и 2.3 приводятся программы, реализованные на языках Pascal и С, связанного формирования списка элементов последовательности. В программы включены операции работы со списком: печать элементов списка, включение новых элементов в список и удаление элементов из списка.

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

Циклическая форма представления позволяет эффективно возвращаться с последнего элемента списка к первому.

Рис. 2.1. Циклический список

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

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

Рис. 2.2 Дважды связанный список

Алгоритм 2.2. Программа на Pascalе включения и исключения элементов из списка

(см. скан)

(см. скан)

Алгоритм 2.3. Программа на Си включения и исключения элементов из списка

(см. скан)

(см. скан)

Связанное представление предпочтительнее лишь в том случае, если в значительной степени используются операции включения и исключения элементов.