Понятие структуры.

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

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

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

Списки

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

Кортеж – это конечная последовательность, возможно с повторениями, элементов некоторого множества . Элементами кортежа могут быть числа, символы и т.д. В более сложных случаях элементами кортежа могут быть также кортежи. Кортеж характеризуется своей длиной. Удобно рассматривать кортежи, не содержащие ни одного элемента. Такие кортежи называются пустыми. Длина пустого кортежа считается равной 0.

Элемент кортежа характеризуется своим номером в последовательности (кортежным номером) и своим содержанием, то есть элементом множества . Если длина кортежа равна , , то кортеж удобно рассматривать как отображение множества в множество . Таким образом, , это -ый элемент кортежа.

Термин список используется как обобщающее название различных структур данных, используемых для представления кортежей в памяти компьютера. При представлении кортежа в памяти появляется еще одна характеристика элемента кортежа – его позиция в памяти. Множество позиций обозначим через . Иногда удобно считать, что в множестве имеется специальный элемент nil, указывающий на несуществующую область памяти. Таким образом, при рассмотрении того или иного списка имеем дело с тремя множествами и с отображениями на этих множествах.

Типичными при работе со списками являются следующие операции.

¨ Нахождение позиции элемента в памяти по его номеру в кортеже.

¨ Нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции

¨ Нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции.

¨ Удаление элемента, находящегося в заданной позиции.

¨ Вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции.

¨ Определение длины кортежа.

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

· Info: , где Info(pos) – элемент списка находящийся, в позиции pos памяти.

· Next: , где Next(pos) – позиция элемента, следующего за элементом из позиции pos.

· Precede: , где Precede(pos) – позиция элемента, находящегося перед элементом из позиции pos.

· First – позиция первого элемента списка.

· Last – позиция последнего элемента списка.

Различные представления кортежей с помощью списковых структур характеризуются степенью эффективности выполнения тех или иных операций. Так, при одном представлении эффективно вычисляется порядковый номер элемента по его позиции, но менее эффективно осуществляется вставка нового элемента. При другом представлении легко осуществляется вставка, а определение порядкового номера элемента по его позиции требует заметного объема вычислений, например, пропорционального длине списка. К сожалению, не всегда удается найти способ представления кортежей, для которого все используемые в конкретном алгоритме операции одинаково эффективны. Поэтому выбор структуры для представления кортежа сопряжен с анализом алгоритма (а зачастую и области его применения). В зависимости от набора операций, которые предполагается выполнять со списками, выделяют некоторые их разновидности.

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

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

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

При представлении кортежей, для которых планируется выполнение операций вставки/удаления элемента из произвольной позиции, используется возможность нахождения программным путем свободного пространства в памяти для размещения вставляемого элемента. При использовании языков высокого уровня эти обязанности берет на себя обычно система программирования ( оператор new – в языках PASCAL и C). При вставлении нового элемента в список место, кода он вставляется, указывается с помощью косвенной адресации. Это может быть адрес элемента, перед которым вставляется новый элемент, либо после которого, либо и тот и другой. Такой способ дает возможность лишь последовательного доступа к элементам.