Структуры данных и модели вычислений

         

и других операций со списками


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

  • : , где (pos) — элемент списка, находящийся в позиции pos памяти.
  • , где (pos) — позиция элемента, следующего за элементом из позиции pos.
  • : , где (pos) — позиция элемента, находящегося перед элементом из позиции pos.
  • : , где (pos) — кортежный номер элемента, находящегося в позиции pos.
  • : , где () — позиция элемента, имеющего кортежный номер .
  • — длина списка.
  • — позиция первого элемента списка.
  • — позиция последнего элемента списка.


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

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

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

Содержание  Назад  Вперед