Общие сведения о списках
Остановимся на наиболее часто используемых структурах данных, называемых списками. Списки лежат в основе многих более сложных структур данных. В простейшем случае списки используются для представления кортежей.
Кортеж — это конечная последовательность, возможно с повторениями, элементов некоторого множества . Элементами кортежа могут быть числа, символы некоторого алфавита, точки плоскости и т.д. В более сложных случаях элементами кортежа, в свою очередь, могут быть также кортежи. Элементы, не являющиеся кортежами, называются атомами. Количество элементов в кортеже называется его длиной. Удобно рассматривать кортежи, не содержащие ни одного элемента. Такие кортежи называются пустыми. Длина пустого кортежа считается равной .
Элемент кортежа характеризуется своим номером в последовательности (кортежным номером) и содержанием, то есть элементом множества . Если длина кортежа равна , , то кортеж
удобно рассматривать как отображение множества в множество . Таким образом, — это -й элемент кортежа .
Термин "список" используется как обобщающее название различных структур данных, используемых для представления кортежей в памяти компьютера. При представлении кортежа в памяти появляется еще одна характеристика элемента кортежа — его позиция в памяти. В некоторых случаях номер элемента в кортеже и его позиция в памяти связаны друг с другом арифметическими соотношениями таким образом, что по номеру легко вычисляется позиция и, наоборот, по позиции вычисляется номер. В других случаях связь между номерами и позициями задается "таблично" или осуществляется с помощью алгоритмических процедур. Множество позиций обозначим через . Иногда удобно считать, что в множестве имеется специальный элемент , указывающий на несуществующую область памяти. Таким образом, при рассмотрении того или иного списка мы имеем дело с тремя множествами , , и с отображениями на этих множествах.
Типичными при работе со списками являются следующие операции:
- Нахождение позиции элемента в памяти по его номеру в кортеже.
- Нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции.
- Нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции.
- Удаление элемента, находящегося в заданной позиции.
- Вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции.
- Определение длины кортежа.
При описании этих и других операций со списками будем использовать следующие отображения и константы, заданные на множествах , , :
- : , где (pos) — элемент списка, находящийся в позиции pos памяти.
- , где (pos) — позиция элемента, следующего за элементом из позиции pos.
- : , где (pos) — позиция элемента, находящегося перед элементом из позиции pos.
- : , где (pos) — кортежный номер элемента, находящегося в позиции pos.
- : , где () — позиция элемента, имеющего кортежный номер .
- — длина списка.
- — позиция первого элемента списка.
- — позиция последнего элемента списка.
Иногда для распознавания концевых элементов списка пользуются следующим соглашением: eсли pos является позицией последнего элемента списка, то полагают , а если началом, то . В случаях, когда позицией элемента, следующего за последним или предшествующего первому, является несуществующая позиция , будем считать, что принадлежит множеству . При изменении содержимого списка все введенные множества, отображения и константы могут изменяться.
Различные представления кортежей с помощью списковых структур характеризуются степенью эффективности выполнения тех или иных операций. Так, при одном представлении эффективно вычисляется порядковый номер элемента по его позиции, но менее эффективно осуществляется вставка нового элемента. При другом представлении легко осуществляется вставка, а определение порядкового номера элемента по его позиции требует довольно много времени, например пропорционально длине списка. К сожалению, не всегда удается найти способ представления кортежей, для которого все используемые в конкретном алгоритме операции одинаково эффективны. Поэтому выбор структуры для представления кортежа сопряжен с анализом алгоритма, а именно, с выяснением того, какие операции, в конечном счете, определяют его суммарную трудоемкость. В зависимости от набора операций, которые предполагается выполнять со списками, выделяют некоторые их разновидности.
Список, в который предполагается добавлять и удалять элементы лишь с одного его конца, называется стеком.
Если добавление элементов должно происходить с одного конца, а удаление — с другого, то такой список называется очередью. Если удалять и добавлять элементы можно с любого конца списка, то такой список называется деком. Если добавлять можно с любого конца, а удалять только с одного, то список называется деком с ограниченным выходом. Списки более общего вида позволяют включать и удалять элементы из любой позиции. Списки классифицируются также по возможностям их сканирования (просмотра) в одном направлении (от начала к концу или от конца к началу) или в обоих направлениях. В первом случае список называется односторонним, во втором — двусторонним.
Списки, для которых не планируется выполнять операции вставки
удаления из произвольной позиции, удобно представлять массивами. В этом случае кортежный номер элемента можно либо отождествить с номером элемента в массиве, либо сделать легко вычисляемым по этому номеру. Такие списки называют списками с прямым доступом к элементам. Другими словами, под прямым доступом мы понимаем возможность по номеру элемента в кортеже за единицу времени определять как сам элемент, так и его позицию в памяти.
При представлении кортежей, для которых планируется выполнение операций вставкиудаления элемента из произвольной позиции, используется возможность нахождения программным путем свободного пространства в памяти для размещения вставляемого элемента. При использовании языков программирования высокого уровня эти обязанности обычно берет на себя система программирования (оператор new — в языках PASCAL и C). При вставлении нового элемента в список место, куда он вставляется, указывается с помощью косвенной адресации. Это может быть адрес элемента, перед которым либо после которого вставляется новый элемент, либо и тот, и другой. Такой способ дает возможность лишь последовательного доступа к элементам. Другими словами, при последовательном доступе гарантируется определение за единицу времени позиции очередного элемента лишь по позиции предыдущего или следующего за ним элемента, но не по его номеру в кортеже.
Отметим еще, что при конструировании списков иногда удобно элементами списка считать не сами элементы множества , а их позиции в памяти. В этом случае списки, по терминологии Р.Тарьяна, называются экзогенными (внешними), в противном случае — эндогенными (внутренними). Экзогенный способ используют в тех случаях, когда элементы множества для своего представления требуют много пространства и переписывание элемента из одного участка памяти в другой сопряжено с большими затратами времени.
Преимущество использования экзогенных списков может ярко проявиться в такой задаче, как сортировка (упорядочение) элементов списка в порядке возрастания или убывания некоторой числовой характеристики, называемой ключом элемента. Основными операциями при сортировке, определяющими ее трудоемкость, являются операция сравнения ключей и операция перемещения элементов. Очевидно, что при эндогенном способе представления списка суммарные затраты времени на перемещение элементов могут оказаться намного больше, чем при экзогенном способе.
При описании операций над списками будем считать, что каждый из них описан с помощью дескриптора, имеющего форму записи, состоящей из нескольких полей. Дескриптор предназначен для того, чтобы явно указать составные части, из которых формируется список. Как правило, в дескриптор будет входить поле , содержащее позицию первого элемента. Если в конструкции списка используется некоторый массив, то в дескрипторе указывается имя этого массива.
Поля, относящиеся к конкретному списку , будем записывать в форме
В полях дескриптора будем указывать также имена процедур и функций, которые реализуют примитивные операции над списками при рассматриваемой их реализации.
Так, например, дескриптор списка может иметь форму
При таком дескрипторе
- означает позицию первого элемента списка ,
- — его длину.
