Остановимся на наиболее часто используемых структурах данных, называемых списками. Списки лежат в основе многих более сложных структур данных. В простейшем случае списки используются для представления кортежей.
Элемент кортежа характеризуется своим номером в последовательности (кортежным номером) и содержанием, то есть элементом множества $$E$$. Если длина кортежа равна $$n$$, $$n > 0$$, то кортеж $$S$$ удобно рассматривать как отображение $$s$$ множества $$N = \{1, 2\dts n\}$$ в множество $$E$$. Таким образом, $$s(i)$$ — это $$i$$ -й элемент кортежа $$S$$.
Термин "список" используется как обобщающее название различных структур данных, используемых для представления кортежей в памяти компьютера. При представлении кортежа в памяти появляется еще одна характеристика элемента кортежа — его позиция в памяти. В некоторых случаях номер элемента в кортеже и его позиция в памяти связаны друг с другом арифметическими соотношениями таким образом, что по номеру легко вычисляется позиция и, наоборот, по позиции вычисляется номер. В других случаях связь между номерами и позициями задается "таблично" или осуществляется с помощью алгоритмических процедур. Множество позиций обозначим через $$P$$. Иногда удобно считать, что в множестве $$P$$ имеется специальный элемент $${\rm nil}$$, указывающий на несуществующую область памяти. Таким образом, при рассмотрении того или иного списка мы имеем дело с тремя множествами $$E$$, $$N$$, $$P$$ и с отображениями на этих множествах.
Типичными при работе со списками являются следующие операции:
При описании этих и других операций со списками будем использовать следующие отображения и константы, заданные на множествах $$E$$, $$N$$, $$P$$:
Иногда для распознавания концевых элементов списка пользуются следующим соглашением: eсли pos является позицией последнего элемента списка, то полагают $$\Next\t{(pos)} = \pos$$, а если началом, то $$\Precede(\pos) = \pos$$. В случаях, когда позицией элемента, следующего за последним или предшествующего первому, является несуществующая позиция $$\rm nil$$, будем считать, что $$\rm nil$$ принадлежит множеству $$P$$. При изменении содержимого списка все введенные множества, отображения и константы могут изменяться.
Различные представления кортежей с помощью списковых структур характеризуются степенью эффективности выполнения тех или иных операций. Так, при одном представлении эффективно вычисляется порядковый номер элемента по его позиции, но менее эффективно осуществляется вставка нового элемента. При другом представлении легко осуществляется вставка, а определение порядкового номера элемента по его позиции требует довольно много времени, например пропорционально длине списка. К сожалению, не всегда удается найти способ представления кортежей, для которого все используемые в конкретном алгоритме операции одинаково эффективны. Поэтому выбор структуры для представления кортежа сопряжен с анализом алгоритма, а именно, с выяснением того, какие операции, в конечном счете, определяют его суммарную трудоемкость. В зависимости от набора операций, которые предполагается выполнять со списками, выделяют некоторые их разновидности.
Список, в который предполагается добавлять и удалять элементы лишь с одного его конца, называется стеком. Если добавление элементов должно происходить с одного конца, а удаление — с другого, то такой список называется очередью. Если удалять и добавлять элементы можно с любого конца списка, то такой список называется деком. Если добавлять можно с любого конца, а удалять только с одного, то список называется деком с ограниченным выходом. Списки более общего вида позволяют включать и удалять элементы из любой позиции. Списки классифицируются также по возможностям их сканирования (просмотра) в одном направлении (от начала к концу или от конца к началу) или в обоих направлениях. В первом случае список называется односторонним, во втором — двусторонним.
Списки, для которых не планируется выполнять операции вставки $$/$$ удаления из произвольной позиции, удобно представлять массивами. В этом случае кортежный номер элемента можно либо отождествить с номером элемента в массиве, либо сделать легко вычисляемым по этому номеру. Такие списки называют списками с прямым доступом к элементам. Другими словами, под прямым доступом мы понимаем возможность по номеру элемента в кортеже за единицу времени определять как сам элемент, так и его позицию в памяти.
При представлении кортежей, для которых планируется выполнение операций вставки $$/$$ удаления элемента из произвольной позиции, используется возможность нахождения программным путем свободного пространства в памяти для размещения вставляемого элемента. При использовании языков программирования высокого уровня эти обязанности обычно берет на себя система программирования (оператор new — в языках PASCAL и C). При вставлении нового элемента в список место, куда он вставляется, указывается с помощью косвенной адресации. Это может быть адрес элемента, перед которым либо после которого вставляется новый элемент, либо и тот, и другой. Такой способ дает возможность лишь последовательного доступа к элементам. Другими словами, при последовательном доступе гарантируется определение за единицу времени позиции очередного элемента лишь по позиции предыдущего или следующего за ним элемента, но не по его номеру в кортеже.
Отметим еще, что при конструировании списков иногда удобно элементами списка считать не сами элементы множества $$E$$, а их позиции в памяти. В этом случае списки, по терминологии Р.Тарьяна, называются экзогенными (внешними), в противном случае — эндогенными (внутренними). Экзогенный способ используют в тех случаях, когда элементы множества $$E$$ для своего представления требуют много пространства и переписывание элемента из одного участка памяти в другой сопряжено с большими затратами времени.
Преимущество использования экзогенных списков может ярко проявиться в такой задаче, как сортировка (упорядочение) элементов списка в порядке возрастания или убывания некоторой числовой характеристики, называемой ключом элемента. Основными операциями при сортировке, определяющими ее трудоемкость, являются операция сравнения ключей и операция перемещения элементов. Очевидно, что при эндогенном способе представления списка суммарные затраты времени на перемещение элементов могут оказаться намного больше, чем при экзогенном способе.
При описании операций над списками будем считать, что каждый из них описан с помощью дескриптора, имеющего форму записи, состоящей из нескольких полей. Дескриптор предназначен для того, чтобы явно указать составные части, из которых формируется список. Как правило, в дескриптор будет входить поле $$\first$$, содержащее позицию первого элемента. Если в конструкции списка используется некоторый массив, то в дескрипторе указывается имя этого массива.
Поля, относящиеся к конкретному списку $$L$$, будем записывать в форме$$\eq*{ L.<\!\t{имя\_поля}\!>. }$$
В полях дескриптора будем указывать также имена процедур и функций, которые реализуют примитивные операции над списками при рассматриваемой их реализации.
Так, например, дескриптор списка $$L$$ может иметь форму$$\eq*{ [\first, \length]. }$$
При таком дескрипторе
Прямой доступ, как правило, реализуется при представлении списка массивом.
Элементы кортежа размещаются в идущих подряд ячейках некоторого массива.
Для локализации списка в массиве введем целочисленную переменную $$\first$$ для
хранения номера позиции массива, в которой расположен его первый элемент,
и целочисленную переменную $$\length$$, означающую длину списка.
Равенство $$\length = 0$$ служит признаком того, что массив содержит пустой
список. Иногда для переменных, хранящих позицию элемента массива, удобно иметь
какое-либо условное значение, выходящее за рамки
Рассмотрим подробнее реализацию списка с прямым доступом, дающую возможность добавлять элементы к списку с любого его конца. Воспользуемся циклической "нумерацией" элементов массива, при которой следующим за последним элементом массива считается его первый элемент, а предыдущим для первого — последний (речь идет об элементах массива, а не об элементах списка). Если элементы массива пронумеровать числами от $$0$$ до $$n-1$$, то переход к следующему (предыдущему) элементу списка осуществляется с помощью прибавления (вычитания) единицы по модулю $$n$$, где $$n$$ — длина массива. Дескриптор такого списка будет иметь форму$$\eq*{ S = [n, \info, \first, \length]. }$$
Добавление элемента к началу списка осуществляется его записью в позицию $$\newfirst = (\newfirst - 1) \ {\rm mod} \ n,\ (0 \le \newfirst <
n)$$
с последующим присваиванием $$\first := \newfirst$$, а добавление в конец
(записью элемента в позицию ( $$\first + \length) \mod n$$
с последующим выполнением оператора $$\length := (\length + 1)$$. Заметим, что при таком способе
начальный фрагмент кортежа может оказаться в конце массива, а конечный фрагмент —
в начале. Заметим также, что добавление нового элемента возможно только при условии $$\length < n$$. Кроме того, нужно иметь в виду, что в системах
программирования со
Основные отображения для списка с прямым доступом, имеющего дескриптор $$S = [n, \info, \first, \length]$$, определяются следующим образом:
$$\Info(pos) = > S.\info [pos],$$ $$\Next(pos) = if (pos = S.\first +\, \t{S.}\length-1 ) then pos$$ $$else if (S.\length < S.n) then (\pos + 1)\ {\rm mod} S.n else \beyond,$$ $$\Precede (pos) = if (pos = S. \first) then pos$$ $$else if (S.>\length < S.n) then (pos - 1) {\rm mod} S.n else \beyond,$$ $$\Last = (S.\first + \t{S.}\length - 1)\ {\rm mod} S.n,$$ $$\Number(pos) = if (S.\first < pos) then (pos - S.\first + 1)$$ $$else (S.pos - S.\first + \,\t{S.n} - 1).$$Приведем несколько процедур для работы со списками с прямым доступом.
Создать пустой список
$$\formula{\t{procedure}\ {\rm SetEmpty}\t{(S);}\\ \ \t{begin} \\ \t{\rm S.}\first:=0;\\ \t{ S.}\length:=0\\ \t{end};}$$
Добавить элемент $$e$$ к концу списка $$S$$
$$\formula{ \t{procedure AddToEnd (e, S)};\\ \t{begin}\\ \mbox{}\q \t{if}\ {S.}\length < \t{S.n}\\ \mbox{}\q \t{then}\{\t{S.}\info[(\t{S.}\first + \t{S.}\length)\ {\rm mod}\ \t{S.n}]:= e;\ \t{S.}\length := \t{S.}\length + 1\}\\ \mbox{}\q \t{else 'массив переполнен'}\\ \t{end};}$$
Добавить элемент e к началу списка $$S$$
$$\formula{ \t{procedure AddToBegin (e, S);}\\ \mbox{}\q \t{begin}\\ \mbox{}\qq \t{if}\ \t{S.}\length < \t{S.n}\\ \mbox{}\qq \t{then}\ \t{\{S.}\first \!:=\! \t{S.}\first - 1;\ \t{S.}\info[\t{S.}\first] \!:=\! \t{e};\ \t{S.}\length \!:=\! \t{S.}\length + 1\}\\ \mbox{}\q \t{else 'массив переполнен'}\\ \t{end};}$$
Заменить элемент с кортежным номером $$k$$ на элемент $$e$$
$$\formula{ \t{procedure Set (k, e, S);}\\ \t{begin}\\ \mbox{}\q \t{S.}\info \t{[S.}\t{first} + \t{k} - 1] := \t{e}\\ \t{end};}$$Удалить последний элемент списка $$S$$
$$\formula{ \t{procedure DelLast (S);}\\ \t{begin} \\ \mbox{}\q \t{if}\ \t{S.}\length > 0\ \t{then}\ \t{S.}\length:= \t{S.}\length - 1\ \t{else 'список пуст'}\\ \t{end};}$$Удалить первый элемент списка $$S$$
$$\formula{ \t{procedure DelFirst (S);}\\ \t{begin}\\ \mbox{}\q \t{if}\ \t{S.}\length > 0\\ \mbox{}\q \t{then}\ \{\t{S.}\first := (\t{S.}\first + 1)\ {\rm mod}\ \t{S.n};\ \t{S.}\length := \t{S.}\length - 1\}\\ \mbox{}\q \t{else 'список пуст'}\\ \t end; }$$Последовательный доступ к элементам списка, как правило, реализуется с
использованием
Элементы связного списка, следующие друг за другом, не обязательно размещаются в последовательных ячейках памяти — доступ к следующему и предыдущему элементам осуществляется при помощи специальных ссылок (указателей). Чтобы обеспечить запоминание указателей на следующий и предыдущий элементы, каждый элемент списка "погружается" в узел, для которого в памяти компьютера формируется запись, состоящая из нескольких полей. В простейшем случае эта запись может состоять из двух полей. Одно из них — $$\Info$$ — предназначено для запоминания самого элемента, а другое — $$\Next$$ — для запоминания позиции следующего. Для обозначения такого узла будем использовать следующую форму:$$\eq*{ t: [\Info, \Next], }$$ где $$t$$ — позиция (адрес) узла в памяти. Поскольку у последнего элемента нет следующего, его поле $$\Next$$ заполняют значением $$\rm nil$$. Иногда вместо $$\rm nil$$ используют ссылку на сам этот элемент, что также может являться признаком конца списка. Мы часто будем пользоваться именно этим способом распознавания конца списка. Представление списка с помощью таких узлов обеспечивает сканирование списка от начала к его концу. Доступ к самому списку осуществляется через его голову с помощью переменной $$\first$$, содержащей позицию первого элемента. Такие списки называются односторонними.
При описании операций со списками через $$t\t{\^{}}$$ будем обозначать узел, расположенный в позиции $$t$$. Для доступа к полям узла $$t\t{\^{}}$$ используем форму $$t\t{\^{}}.\Info$$, $$t\t{\^{}}.\Next$$ и т.д. Оператор для создания нового узла будем записывать в виде$$\eq*{ \Create (t: [\Info, \Next]). }$$
Для обеспечения сканирования как от начала к концу, так и от конца к началу используют узлы следующего вида:$$\eq*{ t: [\Info, \Next, \Precede]. }$$
Поле $$t\t{\^{}}.\Precede$$ служит для запоминания позиции
элемента,
На рис. 2.1—2.6 представлено несколько разновидностей списков. Узлы списков изображены прямоугольниками, разделенными на части по числу полей. Стрелки проведены в соответствии со значениями полей $$\Next$$ и $$\Precede$$.
(рис 2.2) Односторонний список: вход через первый элемент, сканирование от начала к концу, признак конца — Next(pos) = nil(рис 2.1) Односторонний список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = pos
(рис 2.4) Односторонний циклический список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = first(рис 2.3) Односторонний циклический список: вход через последний элемент с помощью ссылки Last^.next; сканирование от начала к концу, признак конца — pos = last
(рис 2.6) Двусторонний список: вход через первый элемент, сканирование от начала к концу и от конца к началу; признак начала — Procede(pos) = nil; признак конца — Next(pos) = nil(рис 2.5) Двусторонний циклический список: вход через первый элемент; сканирование от начала к концу и от конца к началу, признак конца — Next(pos) = first Рассмотрим основные отображения и операции на примере двустороннего списка, сформированного из узлов вида $$t$$: $$[\Info, \Next, \Precede]$$.
Будем считать, что дескриптор списка $$S$$ имеет вид: $$[\first, \last]$$. Ниже условимся считать, что признак конца — $$\Next(\pos) = {\rm nil}$$, а признак начала — $$\Precede(\pos) = {\rm nil}$$. Основные отображения определяются следующим образом:
$$\Info(\pos) = \pos\t{\^{}}.\info$$,
$$\Next(\pos) = \pos\t{\^{}}.{\rm next}$$,
$$\Precede(\pos) = \pos\t{\^{}}.{\rm preced}$$,
Создать пустой список $$S$$
$$\formula{ \t{procedure SetEmpty (S)};\\ \t{begin} \first := {\rm nil}\\ \t end }$$
Удалить из списка $$S$$ элемент, находящийся в позиции pos памяти
$$\formula{ \t{procedure Del(S, pos)};\\ \t{begin}\\ \mbox{}\q \t{t} := {\rm pos}\t{\^{}}.{\rm precede};\ \t{u}:= {\rm pos}\t{\^{}}.{\rm next};\ \t{t\^{}}.{\rm next} := \t{u};\ \t{u}\t{\^{}}.{\rm precede} := \t{t}\\ \t end;}$$
Замечание В теле процедуры $$\rm Del$$ отсутствует параметр $$S$$. При ее использовании могут возникнуть проблемы, связанные с некорректным обращением, так как в процедуре не производится проверка, является ли позиция pos позицией какого-либо элемента списка $$S$$. Ответственность за некорректное обращение несет вызывающая программа. Проверка этого условия с помощью сканирования списка могла бы оказаться слишком дорогой и свела бы на нет преимущества использования связных списков. Еще одна проблема, связанная с выполнением этой операции, заключается в том, что узел $${\rm pos}\t{\^{}}$$ может оказаться недоступным при потере значения переменной pos, но память будет оставаться занятой. Если это нежелательно, следует, воспользовавшись системными средствами, освободить занимаемую узлом память. Замечания по поводу некорректного обращения будут справедливы и для некоторых следующих процедур, однако мы не будем каждый раз напоминать об этом.
Вставить в список $$S$$ элемент $$e$$ после элемента, находящегося в позиции $$\pos$$
$$\formula{ \t{procedure InsertAfter(S, pos, e)};\\ \t{begin}\\ \mbox{}\q {\rm create}(\t{t}: [\t{e},\ \t{pos}\t{\^{}}.{\rm next}, \t{pos}]);\ \t{pos}\t{\^{}}.{\rm next}\t{\^{}}.{\rm preced} := \t{t};\ \t{pos}\t{\^{}}.{\rm next} := \t{t}\\ \t{end}; }$$
Следующие две операции рассмотрим на примере одностороннего циклического списка (см. рис. 2.4).
Добавить элемент $$e$$ к концу списка $$S$$
$$\formula{ \t{procedure AddToEnd(e, S)};\\ \t{begin} {\rm create} (\t{t}:\,[\t{e},\,\t{S.}{\rm last}\t{\^{}}. {\rm next}]);\ \t{S}.{\rm last} := \t{t}\ \t{end}; }$$
Добавить элемент $$e$$ к началу списка $$S$$
$$\formula{ \t{procedure AddToBegin (e, S)};\\ \t{begin}\\ \mbox{}\q {\rm create}(\t{t}:\,[\t{e},\,\t{S}\t{\^{}}.{\rm last}\t{\^{}}.{\rm next}]);\ \t{S}.{\rm last}\t{\^{}}.{\rm next} := \t{t}\\ \t end; }$$
Следующие три процедуры рассмотрим на примере двустороннего циклического списка (см. рис. 2.6).
Удалить последний элемент списка $$S$$
$$\formula{ \t{procedure DelLast (S)};\\ \t{begin} \\ \mbox{} \q \t{t} := \t{S}.{\rm first}\t{\^{}}.{\rm precede}\t{\^{}}. {\rm precede};\ \t{t\^{}}.{\rm next} := \t{S}.{\rm first};\ \t{S}. {\rm first}\t{\^{}}.{\rm precede} := \t{t}\\ \t end; }$$
Удалить первый элемент списка $$S$$
$$\formula{ \t{procedure DelFirst(S)};\\ \t{begin}\\ \mbox{}\q \t{t} := \t{S}.{\rm first}\t{\^{}}.{\rm next};\, \t{S}. {\rm first}\t{\^{}}.{\rm precede}\t{\^{}}.{\rm next} := \t{t};\ \t{S}.{\rm first} := \t{t}\\ \t end; }$$
Удалить из списка $$S$$ элемент, находящийся в позиции $$\pos$$
$$\formula{ \t{procedure DelPosition (S, pos)};\\ \t{begin} \\ \mbox{}\q \t{if}\ {\rm pos} = \t{S}.{\rm first}\ \t{then} {\rm DelFirst}(\t{S})\ \t{else if} {\rm pos} = \t{S}.{\rm last}\ \t{then}\ {\rm DelLast}(\t{S})\\ \mbox{}\q \t{else} \{\t{t\^{}}.{\rm precede}\t{\^{}}.{\rm next} := \t{t\^{}}.{\rm next};\ \t{t\^{}}.{\rm next}\t{\^{}}.{\rm precede} := \t{t\^{}}.{\rm precede}\}\\ \t end; }$$
В рассмотренной ниже процедуре Concat, реализующей операцию "Соединить два списка", принято следующее решение. К списку $$S1$$ присоединяется список $$S2$$, список $$S2$$ сохраняется, а результирующим является список $$S1$$. Следует, однако, понимать, что если в список $$S2$$ будут внесены изменения, они автоматически произойдут в новом списке. Трудоемкость этой операции — $$O(1)$$.
$$\formula{ \t{begin} \t{S1}.{\rm last}\t{\^{}}.{\rm next} := \t{S2}.{\rm first}\ \t{end}; }$$
Из списка $$S$$ удалить элементы, удовлетворяющие некоторому условию. Предположим, что требуемое условие на элемент $$e$$ проверяется предикатом condition( $$e$$ ).
$$\formula{ \t{begin t} := \t{S}.{\rm first};\\ \mbox{}\q \t{while t} \ne {\rm nil}\ \t{do}\{\t{if condition} (\t{t\^{}}.{\rm info})\ \t{then DelPosition}(\t{S},{\rm pos});\ \t{t} := \\ \mbox{}\q \t{t\^{}}.{\rm next}\}\\ \t end; }$$
Построить список $$S1$$, состоящий из элементов данного списка $$S$$, удовлетворяющих некоторому условию. Предположим, что требуемое условие на элемент $$e$$ проверяется предикатом condition ( $$e$$ ).
$$\formula{ \t{begin} \t{t} := \t{S}.{\rm first};\ \t{SetEmpty}(\t{S1});\\ \mbox{}\q \t{while} \t{t} \ne {\rm nil} \t{do} \{\t{if} \t{condition}(\t{t\^{}}.{\rm info})\ \t{then}\ {\rm AddToEnd}(\t{e}, \t{S1});\ \t{t} := \t{t\^{}}.\t{next}\}\\ \t end; }$$
Получить список $$S1$$ реверсированием списка $$S$$
$$\formula{ \t begin\\ \mbox{}\q {\rm SetEmpty}(\t{S1});\, \t{t} := \t{S}.{\rm first};\\ \mbox{}\q \t{while}\ \t{t} \ne {\rm nil}\ \t{do} \{{\rm AddToBegin}(\t{t\^{}}.{\rm inf}, \t{S1});\ \t{t} := \t{t\^{}}.{\rm next}\}\\ \t end; }$$
Если использование динамических ссылок невозможно или нежелательно (тому могут быть свои причины), список со связями можно смоделировать при помощи массивов. В массиве $${\rm Inf}$$ хранятся элементы списка, то есть значения соответствующих полей узлов списка со связями. Позицией элемента является значение целочисленного индекса массива. Кроме того, вводится целочисленный массив $$\Next$$, в котором для каждого узла списка указана позиция, где расположен его преемник. В качестве индексного пространства используем отрезок $${[1\ldots n]}$$ целочисленного типа.
В одних и тех же массивах $${\rm Inf}$$ и $$\Next$$ могут размещаться сразу несколько списков, состоящих из узлов одного типа. С учетом такого возможного сосуществования различных списков их элементы могут размещаться в этих массивах хаотично, подобно тому, как узлы списков, представленных с помощью ссылок, могут произвольно располагаться в памяти компьютера.
На табл. 2.1 показано возможное заполнение массивов $${\rm Inf}$$ и $${\rm Next}$$ для одностороннего списка, представляющего кортеж $$(a, b, c, d, e)$$ (пустые клетки не имеют отношения к этому списку).
| Адрес | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Inf | e | b | c | d | a | |||||||
| Next | 0 | 6 | 9 | 1 | 3 |
Доступ к списку можно осуществить через его первый элемент, позиция которого в массиве задается значением переменной $${\rm first} = 11$$. Значение $$\Next[1] = 0$$ говорит о том, что в позиции $$1$$ расположен элемент, у которого нет преемника, то есть последний элемент кортежа.
На табл. 2.2 показано возможное заполнение массивов $${\rm Inf}$$, $$\rm Next$$ и $$\rm Precede$$ для представления кортежа ( $$a, b, c, d, e$$ ) двусторонним списком.
| Адрес | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Inf | e | b | c | d | a | |||||||
| Next | 0 | 6 | 9 | 1 | 3 | |||||||
| Precede | 9 | 11 | 3 | 6 | 0 |
Основные отображения $${\rm Info}({\rm pos})$$, $${\rm Next}({\rm pos})$$, $${\rm Precede}({\rm pos})$$, $${\rm First}$$, $${\rm Last}$$, $${\rm Length}$$ задаются очевидным образом. Если какие-либо из них не заданы явно, то их можно вычислять через другие сканированием списка.
Чтобы одни и те же массивы $${\rm Info}$$, $${\rm Next}$$, $${\rm Precede}$$ использовать для одновременного хранения нескольких однотипных списков, позиции этих массивов объединяют в один так называемый свободный список $${\rm Avail}$$. Это можно сделать, например, с помощью операторов
$$\formula{ \t begin\\ \mbox{} \q {\rm Avail}.{\rm first} :=1;\ {\rm Next}[\t{n}] := 0;\ \t{for}\ i:= 1\ \t{to}\ \t{n} - 1\ \t{do}\ {\rm Next}[\t{i}]:= \t{i} + 1;\\ \mbox{} \q {\rm Preced}[1]:= 0;\ \t{for}\ \t{i}:= 2\ \t{to}\ \t{n}\ \t{do}\ {\rm Preced}[i]:= \t{i} - 1;\\ \t{end}; }$$Массив $${\rm Info}$$ при этом не заполняется. При создании новых
списков используются элементы массивов $${\rm Info}$$, $${\rm
Next}$$, $${\rm Precede}$$,
предварительно удаляемые из списка $${\rm Avail}$$.
В момент создания нового узла из списка $${\rm Avail}$$
удаляется головной элемент, который и используется для добавления в новый
список. С другой стороны, при удалении элемента из какого-либо списка
освобождаемая позиция добавляется к свободному списку для последующего
использования. Такая техника применялась, когда системы программирования
не имели стандартных средств
Деревья находят широкое применение при проектировании алгоритмов и, в частности, структур данных. Отсылая читателя к литературе по теории графов, мы будем пользоваться такими понятиями, как узел, ребро, лист, потомок, сын, левый потомок, правый потомок, предок, отец, корень, ветвь и другие. Регулярным деревом назовем дерево, в котором фиксировано максимально возможное (как правило, небольшое) число потомков для каждого из его узлов. В частности, если число потомков для каждого узла не больше двух, то дерево называется бинарным, если не более трех — тернарным. Если это число может равняться только двум или трем, то дерево называется ( $$2$$ — $$3$$ )-деревом.
Достаточно универсальным является способ представления регулярных деревьев, при котором каждый узел представляется записью, содержащей, кроме прикладной информации, позиции смежных с ним элементов, например позиции потомков или наряду с потомками позицию предка или еще каких-либо узлов, в зависимости от потребностей. Регулярность дерева позволяет фиксировать число полей, достаточное для представления любого узла.
Так, узлы бинарного
Для представления нерегулярных деревьев (то есть деревьев, узлы которых могут иметь произвольное число потомков) применяют следующий способ: потомки каждого узла нумеруются и каждый узел представляется записью, включающей в себя позицию его первого (левого) потомка и позицию его "правого брата".
Для регулярных деревьев более экономным по памяти может оказаться представление с помощью массива. Рассмотрим этот прием на примере бинарного дерева. Значения индексов массива отождествляются с узлами дерева, пронумерованными так, что корень получает номер 1, а потомки узла c номером $$i$$ получают номера $$2i$$ и $$2i + 1$$. При таком представлении предок узла с номером $$i$$ будет иметь номер $$i \mathop{\rm div}\nolimits 2$$ (частное от деления $$i$$ на 2). Аналогично можно представить тернарное и другие регулярные деревья.
Остановимся вкратце на представлении графов общего вида.
Матричный способ представления может оказаться неэкономным с точки зрения
использования памяти, если граф разрежен. Так, например, известно, что
число ребер связного
Другой способ представления графа — это список или массив пар вершин, соответствующих ребрам. При таком способе, если граф не ориентирован, то из двух возможных пар ( $$i$$, $$j$$ ) и ( $$j$$, $$i$$ ) целесообразно хранить только одну, например ту, у которой первая компонента меньше второй.
Еще один способ, часто имеющий преимущества перед названными выше, — это представление графа массивом или списком списков (рис. 2.7).
(рис 2.7) Представление графа комбинацией списков: множество вершин представлено списком узлов, к каждому из которых справа подцеплен список смежных с ним вершинА именно, для каждой вершины организуется список смежных с ней вершин. В этом случае легко осуществляется доступ к окрестностям вершин. Примерно такого же эффекта можно достичь, представляя граф с помощью двух массивов: $${\rm inf} [1 \ldots m]$$ и $${\rm adr} [1\ldots n + 1)]$$, где $$m$$ — число ребер графа. Массив $${\rm adr}$$ назовем адресным, а $${\rm inf}$$ — информационным. В информационном массиве вначале перечисляются номера вершин, смежных с первой вершиной, затем — со второй и так далее. В адресном массиве указываются номера позиций информационного массива так, чтобы для каждой вершины $$i$$ по ним можно было находить фрагменты массива $${\rm inf}$$, в которых записаны номера вершин, смежных с этой вершиной. Например, $${\rm adr}[i]$$ может хранить позицию, с которой начинаются в массиве $${\rm inf}$$ вершины, смежные с $$i$$ -й, при этом $${\rm adr}[n + 1]$$ — первая позиция за пределами массива $${\rm inf}$$. В таком случае, если нам требуется с каждой вершиной $$j$$ из окрестности вершины $$i$$ выполнить оператор $$S(j)$$, то можно сделать это с помощью оператора цикла:$$\eq*{ for k := {\rm adr}[i]\ to\ {\rm adr} [i + 1] - 1\ \t{do} S({\rm inf}[k]). }$$
Заметим, что если граф не ориентирован, то каждое ребро ( $$i$$, $$j$$ ) будет представлено дважды: один раз в последовательности вершин, смежных с вершиной $$i$$, а второй раз — в последовательности вершин, смежных с вершиной $$j$$. Но эта избыточность часто бывает полезна с точки зрения времени выполнения операций над окрестностями вершин графа. Как недостаток такого представления графа, можно отметить неудобство при динамической модификации графа, например, добавление к графу ребра может потребовать большого количества пересылок в массиве $$\rm inf$$. Этого недостатка лишен способ представления графа, показанный на рис. 2.7.
Остановимся на наиболее часто используемых структурах данных, называемых списками. Списки лежат в основе многих более сложных структур данных. В простейшем случае списки используются для представления кортежей.
Элемент кортежа характеризуется своим номером в последовательности (кортежным номером) и содержанием, то есть элементом множества $$E$$. Если длина кортежа равна $$n$$, $$n > 0$$, то кортеж $$S$$ удобно рассматривать как отображение $$s$$ множества $$N = \{1, 2\dts n\}$$ в множество $$E$$. Таким образом, $$s(i)$$ — это $$i$$ -й элемент кортежа $$S$$.
Термин "список" используется как обобщающее название различных структур данных, используемых для представления кортежей в памяти компьютера. При представлении кортежа в памяти появляется еще одна характеристика элемента кортежа — его позиция в памяти. В некоторых случаях номер элемента в кортеже и его позиция в памяти связаны друг с другом арифметическими соотношениями таким образом, что по номеру легко вычисляется позиция и, наоборот, по позиции вычисляется номер. В других случаях связь между номерами и позициями задается "таблично" или осуществляется с помощью алгоритмических процедур. Множество позиций обозначим через $$P$$. Иногда удобно считать, что в множестве $$P$$ имеется специальный элемент $${\rm nil}$$, указывающий на несуществующую область памяти. Таким образом, при рассмотрении того или иного списка мы имеем дело с тремя множествами $$E$$, $$N$$, $$P$$ и с отображениями на этих множествах.
Типичными при работе со списками являются следующие операции:
При описании этих и других операций со списками будем использовать следующие отображения и константы, заданные на множествах $$E$$, $$N$$, $$P$$:
Иногда для распознавания концевых элементов списка пользуются следующим соглашением: eсли pos является позицией последнего элемента списка, то полагают $$\Next\t{(pos)} = \pos$$, а если началом, то $$\Precede(\pos) = \pos$$. В случаях, когда позицией элемента, следующего за последним или предшествующего первому, является несуществующая позиция $$\rm nil$$, будем считать, что $$\rm nil$$ принадлежит множеству $$P$$. При изменении содержимого списка все введенные множества, отображения и константы могут изменяться.
Различные представления кортежей с помощью списковых структур характеризуются степенью эффективности выполнения тех или иных операций. Так, при одном представлении эффективно вычисляется порядковый номер элемента по его позиции, но менее эффективно осуществляется вставка нового элемента. При другом представлении легко осуществляется вставка, а определение порядкового номера элемента по его позиции требует довольно много времени, например пропорционально длине списка. К сожалению, не всегда удается найти способ представления кортежей, для которого все используемые в конкретном алгоритме операции одинаково эффективны. Поэтому выбор структуры для представления кортежа сопряжен с анализом алгоритма, а именно, с выяснением того, какие операции, в конечном счете, определяют его суммарную трудоемкость. В зависимости от набора операций, которые предполагается выполнять со списками, выделяют некоторые их разновидности.
Список, в который предполагается добавлять и удалять элементы лишь с одного его конца, называется стеком. Если добавление элементов должно происходить с одного конца, а удаление — с другого, то такой список называется очередью. Если удалять и добавлять элементы можно с любого конца списка, то такой список называется деком. Если добавлять можно с любого конца, а удалять только с одного, то список называется деком с ограниченным выходом. Списки более общего вида позволяют включать и удалять элементы из любой позиции. Списки классифицируются также по возможностям их сканирования (просмотра) в одном направлении (от начала к концу или от конца к началу) или в обоих направлениях. В первом случае список называется односторонним, во втором — двусторонним.
Списки, для которых не планируется выполнять операции вставки $$/$$ удаления из произвольной позиции, удобно представлять массивами. В этом случае кортежный номер элемента можно либо отождествить с номером элемента в массиве, либо сделать легко вычисляемым по этому номеру. Такие списки называют списками с прямым доступом к элементам. Другими словами, под прямым доступом мы понимаем возможность по номеру элемента в кортеже за единицу времени определять как сам элемент, так и его позицию в памяти.
При представлении кортежей, для которых планируется выполнение операций вставки $$/$$ удаления элемента из произвольной позиции, используется возможность нахождения программным путем свободного пространства в памяти для размещения вставляемого элемента. При использовании языков программирования высокого уровня эти обязанности обычно берет на себя система программирования (оператор new — в языках PASCAL и C). При вставлении нового элемента в список место, куда он вставляется, указывается с помощью косвенной адресации. Это может быть адрес элемента, перед которым либо после которого вставляется новый элемент, либо и тот, и другой. Такой способ дает возможность лишь последовательного доступа к элементам. Другими словами, при последовательном доступе гарантируется определение за единицу времени позиции очередного элемента лишь по позиции предыдущего или следующего за ним элемента, но не по его номеру в кортеже.
Отметим еще, что при конструировании списков иногда удобно элементами списка считать не сами элементы множества $$E$$, а их позиции в памяти. В этом случае списки, по терминологии Р.Тарьяна, называются экзогенными (внешними), в противном случае — эндогенными (внутренними). Экзогенный способ используют в тех случаях, когда элементы множества $$E$$ для своего представления требуют много пространства и переписывание элемента из одного участка памяти в другой сопряжено с большими затратами времени.
Преимущество использования экзогенных списков может ярко проявиться в такой задаче, как сортировка (упорядочение) элементов списка в порядке возрастания или убывания некоторой числовой характеристики, называемой ключом элемента. Основными операциями при сортировке, определяющими ее трудоемкость, являются операция сравнения ключей и операция перемещения элементов. Очевидно, что при эндогенном способе представления списка суммарные затраты времени на перемещение элементов могут оказаться намного больше, чем при экзогенном способе.
При описании операций над списками будем считать, что каждый из них описан с помощью дескриптора, имеющего форму записи, состоящей из нескольких полей. Дескриптор предназначен для того, чтобы явно указать составные части, из которых формируется список. Как правило, в дескриптор будет входить поле $$\first$$, содержащее позицию первого элемента. Если в конструкции списка используется некоторый массив, то в дескрипторе указывается имя этого массива.
Поля, относящиеся к конкретному списку $$L$$, будем записывать в форме$$\eq*{ L.<\!\t{имя\_поля}\!>. }$$
В полях дескриптора будем указывать также имена процедур и функций, которые реализуют примитивные операции над списками при рассматриваемой их реализации.
Так, например, дескриптор списка $$L$$ может иметь форму$$\eq*{ [\first, \length]. }$$
При таком дескрипторе
Прямой доступ, как правило, реализуется при представлении списка массивом.
Элементы кортежа размещаются в идущих подряд ячейках некоторого массива.
Для локализации списка в массиве введем целочисленную переменную $$\first$$ для
хранения номера позиции массива, в которой расположен его первый элемент,
и целочисленную переменную $$\length$$, означающую длину списка.
Равенство $$\length = 0$$ служит признаком того, что массив содержит пустой
список. Иногда для переменных, хранящих позицию элемента массива, удобно иметь
какое-либо условное значение, выходящее за рамки
Рассмотрим подробнее реализацию списка с прямым доступом, дающую возможность добавлять элементы к списку с любого его конца. Воспользуемся циклической "нумерацией" элементов массива, при которой следующим за последним элементом массива считается его первый элемент, а предыдущим для первого — последний (речь идет об элементах массива, а не об элементах списка). Если элементы массива пронумеровать числами от $$0$$ до $$n-1$$, то переход к следующему (предыдущему) элементу списка осуществляется с помощью прибавления (вычитания) единицы по модулю $$n$$, где $$n$$ — длина массива. Дескриптор такого списка будет иметь форму$$\eq*{ S = [n, \info, \first, \length]. }$$
Добавление элемента к началу списка осуществляется его записью в позицию $$\newfirst = (\newfirst - 1) \ {\rm mod} \ n,\ (0 \le \newfirst <
n)$$
с последующим присваиванием $$\first := \newfirst$$, а добавление в конец
(записью элемента в позицию ( $$\first + \length) \mod n$$
с последующим выполнением оператора $$\length := (\length + 1)$$. Заметим, что при таком способе
начальный фрагмент кортежа может оказаться в конце массива, а конечный фрагмент —
в начале. Заметим также, что добавление нового элемента возможно только при условии $$\length < n$$. Кроме того, нужно иметь в виду, что в системах
программирования со
Основные отображения для списка с прямым доступом, имеющего дескриптор $$S = [n, \info, \first, \length]$$, определяются следующим образом:
$$\Info(pos) = > S.\info [pos],$$ $$\Next(pos) = if (pos = S.\first +\, \t{S.}\length-1 ) then pos$$ $$else if (S.\length < S.n) then (\pos + 1)\ {\rm mod} S.n else \beyond,$$ $$\Precede (pos) = if (pos = S. \first) then pos$$ $$else if (S.>\length < S.n) then (pos - 1) {\rm mod} S.n else \beyond,$$ $$\Last = (S.\first + \t{S.}\length - 1)\ {\rm mod} S.n,$$ $$\Number(pos) = if (S.\first < pos) then (pos - S.\first + 1)$$ $$else (S.pos - S.\first + \,\t{S.n} - 1).$$Приведем несколько процедур для работы со списками с прямым доступом.
Создать пустой список
$$\formula{\t{procedure}\ {\rm SetEmpty}\t{(S);}\\ \ \t{begin} \\ \t{\rm S.}\first:=0;\\ \t{ S.}\length:=0\\ \t{end};}$$
Добавить элемент $$e$$ к концу списка $$S$$
$$\formula{ \t{procedure AddToEnd (e, S)};\\ \t{begin}\\ \mbox{}\q \t{if}\ {S.}\length < \t{S.n}\\ \mbox{}\q \t{then}\{\t{S.}\info[(\t{S.}\first + \t{S.}\length)\ {\rm mod}\ \t{S.n}]:= e;\ \t{S.}\length := \t{S.}\length + 1\}\\ \mbox{}\q \t{else 'массив переполнен'}\\ \t{end};}$$
Добавить элемент e к началу списка $$S$$
$$\formula{ \t{procedure AddToBegin (e, S);}\\ \mbox{}\q \t{begin}\\ \mbox{}\qq \t{if}\ \t{S.}\length < \t{S.n}\\ \mbox{}\qq \t{then}\ \t{\{S.}\first \!:=\! \t{S.}\first - 1;\ \t{S.}\info[\t{S.}\first] \!:=\! \t{e};\ \t{S.}\length \!:=\! \t{S.}\length + 1\}\\ \mbox{}\q \t{else 'массив переполнен'}\\ \t{end};}$$
Заменить элемент с кортежным номером $$k$$ на элемент $$e$$
$$\formula{ \t{procedure Set (k, e, S);}\\ \t{begin}\\ \mbox{}\q \t{S.}\info \t{[S.}\t{first} + \t{k} - 1] := \t{e}\\ \t{end};}$$Удалить последний элемент списка $$S$$
$$\formula{ \t{procedure DelLast (S);}\\ \t{begin} \\ \mbox{}\q \t{if}\ \t{S.}\length > 0\ \t{then}\ \t{S.}\length:= \t{S.}\length - 1\ \t{else 'список пуст'}\\ \t{end};}$$Удалить первый элемент списка $$S$$
$$\formula{ \t{procedure DelFirst (S);}\\ \t{begin}\\ \mbox{}\q \t{if}\ \t{S.}\length > 0\\ \mbox{}\q \t{then}\ \{\t{S.}\first := (\t{S.}\first + 1)\ {\rm mod}\ \t{S.n};\ \t{S.}\length := \t{S.}\length - 1\}\\ \mbox{}\q \t{else 'список пуст'}\\ \t end; }$$Последовательный доступ к элементам списка, как правило, реализуется с
использованием
Элементы связного списка, следующие друг за другом, не обязательно размещаются в последовательных ячейках памяти — доступ к следующему и предыдущему элементам осуществляется при помощи специальных ссылок (указателей). Чтобы обеспечить запоминание указателей на следующий и предыдущий элементы, каждый элемент списка "погружается" в узел, для которого в памяти компьютера формируется запись, состоящая из нескольких полей. В простейшем случае эта запись может состоять из двух полей. Одно из них — $$\Info$$ — предназначено для запоминания самого элемента, а другое — $$\Next$$ — для запоминания позиции следующего. Для обозначения такого узла будем использовать следующую форму:$$\eq*{ t: [\Info, \Next], }$$ где $$t$$ — позиция (адрес) узла в памяти. Поскольку у последнего элемента нет следующего, его поле $$\Next$$ заполняют значением $$\rm nil$$. Иногда вместо $$\rm nil$$ используют ссылку на сам этот элемент, что также может являться признаком конца списка. Мы часто будем пользоваться именно этим способом распознавания конца списка. Представление списка с помощью таких узлов обеспечивает сканирование списка от начала к его концу. Доступ к самому списку осуществляется через его голову с помощью переменной $$\first$$, содержащей позицию первого элемента. Такие списки называются односторонними.
При описании операций со списками через $$t\t{\^{}}$$ будем обозначать узел, расположенный в позиции $$t$$. Для доступа к полям узла $$t\t{\^{}}$$ используем форму $$t\t{\^{}}.\Info$$, $$t\t{\^{}}.\Next$$ и т.д. Оператор для создания нового узла будем записывать в виде$$\eq*{ \Create (t: [\Info, \Next]). }$$
Для обеспечения сканирования как от начала к концу, так и от конца к началу используют узлы следующего вида:$$\eq*{ t: [\Info, \Next, \Precede]. }$$
Поле $$t\t{\^{}}.\Precede$$ служит для запоминания позиции
элемента,
На рис. 2.1—2.6 представлено несколько разновидностей списков. Узлы списков изображены прямоугольниками, разделенными на части по числу полей. Стрелки проведены в соответствии со значениями полей $$\Next$$ и $$\Precede$$.
(рис 2.2) Односторонний список: вход через первый элемент, сканирование от начала к концу, признак конца — Next(pos) = nil(рис 2.1) Односторонний список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = pos(рис 2.4) Односторонний циклический список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = first(рис 2.3) Односторонний циклический список: вход через последний элемент с помощью ссылки Last^.next; сканирование от начала к концу, признак конца — pos = last(рис 2.6) Двусторонний список: вход через первый элемент, сканирование от начала к концу и от конца к началу; признак начала — Procede(pos) = nil; признак конца — Next(pos) = nil(рис 2.5) Двусторонний циклический список: вход через первый элемент; сканирование от начала к концу и от конца к началу, признак конца — Next(pos) = firstРассмотрим основные отображения и операции на примере двустороннего списка, сформированного из узлов вида $$t$$: $$[\Info, \Next, \Precede]$$.
Будем считать, что дескриптор списка $$S$$ имеет вид: $$[\first, \last]$$. Ниже условимся считать, что признак конца — $$\Next(\pos) = {\rm nil}$$, а признак начала — $$\Precede(\pos) = {\rm nil}$$. Основные отображения определяются следующим образом:
$$\Info(\pos) = \pos\t{\^{}}.\info$$,
$$\Next(\pos) = \pos\t{\^{}}.{\rm next}$$,
$$\Precede(\pos) = \pos\t{\^{}}.{\rm preced}$$,
Создать пустой список $$S$$
$$\formula{ \t{procedure SetEmpty (S)};\\ \t{begin} \first := {\rm nil}\\ \t end }$$
Удалить из списка $$S$$ элемент, находящийся в позиции pos памяти
$$\formula{ \t{procedure Del(S, pos)};\\ \t{begin}\\ \mbox{}\q \t{t} := {\rm pos}\t{\^{}}.{\rm precede};\ \t{u}:= {\rm pos}\t{\^{}}.{\rm next};\ \t{t\^{}}.{\rm next} := \t{u};\ \t{u}\t{\^{}}.{\rm precede} := \t{t}\\ \t end;}$$
Замечание В теле процедуры $$\rm Del$$ отсутствует параметр $$S$$. При ее использовании могут возникнуть проблемы, связанные с некорректным обращением, так как в процедуре не производится проверка, является ли позиция pos позицией какого-либо элемента списка $$S$$. Ответственность за некорректное обращение несет вызывающая программа. Проверка этого условия с помощью сканирования списка могла бы оказаться слишком дорогой и свела бы на нет преимущества использования связных списков. Еще одна проблема, связанная с выполнением этой операции, заключается в том, что узел $${\rm pos}\t{\^{}}$$ может оказаться недоступным при потере значения переменной pos, но память будет оставаться занятой. Если это нежелательно, следует, воспользовавшись системными средствами, освободить занимаемую узлом память. Замечания по поводу некорректного обращения будут справедливы и для некоторых следующих процедур, однако мы не будем каждый раз напоминать об этом.
Вставить в список $$S$$ элемент $$e$$ после элемента, находящегося в позиции $$\pos$$
$$\formula{ \t{procedure InsertAfter(S, pos, e)};\\ \t{begin}\\ \mbox{}\q {\rm create}(\t{t}: [\t{e},\ \t{pos}\t{\^{}}.{\rm next}, \t{pos}]);\ \t{pos}\t{\^{}}.{\rm next}\t{\^{}}.{\rm preced} := \t{t};\ \t{pos}\t{\^{}}.{\rm next} := \t{t}\\ \t{end}; }$$
Следующие две операции рассмотрим на примере одностороннего циклического списка (см. рис. 2.4).
Добавить элемент $$e$$ к концу списка $$S$$
$$\formula{ \t{procedure AddToEnd(e, S)};\\ \t{begin} {\rm create} (\t{t}:\,[\t{e},\,\t{S.}{\rm last}\t{\^{}}. {\rm next}]);\ \t{S}.{\rm last} := \t{t}\ \t{end}; }$$
Добавить элемент $$e$$ к началу списка $$S$$
$$\formula{ \t{procedure AddToBegin (e, S)};\\ \t{begin}\\ \mbox{}\q {\rm create}(\t{t}:\,[\t{e},\,\t{S}\t{\^{}}.{\rm last}\t{\^{}}.{\rm next}]);\ \t{S}.{\rm last}\t{\^{}}.{\rm next} := \t{t}\\ \t end; }$$
Следующие три процедуры рассмотрим на примере двустороннего циклического списка (см. рис. 2.6).
Удалить последний элемент списка $$S$$
$$\formula{ \t{procedure DelLast (S)};\\ \t{begin} \\ \mbox{} \q \t{t} := \t{S}.{\rm first}\t{\^{}}.{\rm precede}\t{\^{}}. {\rm precede};\ \t{t\^{}}.{\rm next} := \t{S}.{\rm first};\ \t{S}. {\rm first}\t{\^{}}.{\rm precede} := \t{t}\\ \t end; }$$
Удалить первый элемент списка $$S$$
$$\formula{ \t{procedure DelFirst(S)};\\ \t{begin}\\ \mbox{}\q \t{t} := \t{S}.{\rm first}\t{\^{}}.{\rm next};\, \t{S}. {\rm first}\t{\^{}}.{\rm precede}\t{\^{}}.{\rm next} := \t{t};\ \t{S}.{\rm first} := \t{t}\\ \t end; }$$
Удалить из списка $$S$$ элемент, находящийся в позиции $$\pos$$
$$\formula{ \t{procedure DelPosition (S, pos)};\\ \t{begin} \\ \mbox{}\q \t{if}\ {\rm pos} = \t{S}.{\rm first}\ \t{then} {\rm DelFirst}(\t{S})\ \t{else if} {\rm pos} = \t{S}.{\rm last}\ \t{then}\ {\rm DelLast}(\t{S})\\ \mbox{}\q \t{else} \{\t{t\^{}}.{\rm precede}\t{\^{}}.{\rm next} := \t{t\^{}}.{\rm next};\ \t{t\^{}}.{\rm next}\t{\^{}}.{\rm precede} := \t{t\^{}}.{\rm precede}\}\\ \t end; }$$
В рассмотренной ниже процедуре Concat, реализующей операцию "Соединить два списка", принято следующее решение. К списку $$S1$$ присоединяется список $$S2$$, список $$S2$$ сохраняется, а результирующим является список $$S1$$. Следует, однако, понимать, что если в список $$S2$$ будут внесены изменения, они автоматически произойдут в новом списке. Трудоемкость этой операции — $$O(1)$$.
$$\formula{ \t{begin} \t{S1}.{\rm last}\t{\^{}}.{\rm next} := \t{S2}.{\rm first}\ \t{end}; }$$
Из списка $$S$$ удалить элементы, удовлетворяющие некоторому условию. Предположим, что требуемое условие на элемент $$e$$ проверяется предикатом condition( $$e$$ ).
$$\formula{ \t{begin t} := \t{S}.{\rm first};\\ \mbox{}\q \t{while t} \ne {\rm nil}\ \t{do}\{\t{if condition} (\t{t\^{}}.{\rm info})\ \t{then DelPosition}(\t{S},{\rm pos});\ \t{t} := \\ \mbox{}\q \t{t\^{}}.{\rm next}\}\\ \t end; }$$
Построить список $$S1$$, состоящий из элементов данного списка $$S$$, удовлетворяющих некоторому условию. Предположим, что требуемое условие на элемент $$e$$ проверяется предикатом condition ( $$e$$ ).
$$\formula{ \t{begin} \t{t} := \t{S}.{\rm first};\ \t{SetEmpty}(\t{S1});\\ \mbox{}\q \t{while} \t{t} \ne {\rm nil} \t{do} \{\t{if} \t{condition}(\t{t\^{}}.{\rm info})\ \t{then}\ {\rm AddToEnd}(\t{e}, \t{S1});\ \t{t} := \t{t\^{}}.\t{next}\}\\ \t end; }$$
Получить список $$S1$$ реверсированием списка $$S$$
$$\formula{ \t begin\\ \mbox{}\q {\rm SetEmpty}(\t{S1});\, \t{t} := \t{S}.{\rm first};\\ \mbox{}\q \t{while}\ \t{t} \ne {\rm nil}\ \t{do} \{{\rm AddToBegin}(\t{t\^{}}.{\rm inf}, \t{S1});\ \t{t} := \t{t\^{}}.{\rm next}\}\\ \t end; }$$
Если использование динамических ссылок невозможно или нежелательно (тому могут быть свои причины), список со связями можно смоделировать при помощи массивов. В массиве $${\rm Inf}$$ хранятся элементы списка, то есть значения соответствующих полей узлов списка со связями. Позицией элемента является значение целочисленного индекса массива. Кроме того, вводится целочисленный массив $$\Next$$, в котором для каждого узла списка указана позиция, где расположен его преемник. В качестве индексного пространства используем отрезок $${[1\ldots n]}$$ целочисленного типа.
В одних и тех же массивах $${\rm Inf}$$ и $$\Next$$ могут размещаться сразу несколько списков, состоящих из узлов одного типа. С учетом такого возможного сосуществования различных списков их элементы могут размещаться в этих массивах хаотично, подобно тому, как узлы списков, представленных с помощью ссылок, могут произвольно располагаться в памяти компьютера.
На табл. 2.1 показано возможное заполнение массивов $${\rm Inf}$$ и $${\rm Next}$$ для одностороннего списка, представляющего кортеж $$(a, b, c, d, e)$$ (пустые клетки не имеют отношения к этому списку).
| Адрес | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Inf | e | b | c | d | a | |||||||
| Next | 0 | 6 | 9 | 1 | 3 |
Доступ к списку можно осуществить через его первый элемент, позиция которого в массиве задается значением переменной $${\rm first} = 11$$. Значение $$\Next[1] = 0$$ говорит о том, что в позиции $$1$$ расположен элемент, у которого нет преемника, то есть последний элемент кортежа.
На табл. 2.2 показано возможное заполнение массивов $${\rm Inf}$$, $$\rm Next$$ и $$\rm Precede$$ для представления кортежа ( $$a, b, c, d, e$$ ) двусторонним списком.
| Адрес | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Inf | e | b | c | d | a | |||||||
| Next | 0 | 6 | 9 | 1 | 3 | |||||||
| Precede | 9 | 11 | 3 | 6 | 0 |
Основные отображения $${\rm Info}({\rm pos})$$, $${\rm Next}({\rm pos})$$, $${\rm Precede}({\rm pos})$$, $${\rm First}$$, $${\rm Last}$$, $${\rm Length}$$ задаются очевидным образом. Если какие-либо из них не заданы явно, то их можно вычислять через другие сканированием списка.
Чтобы одни и те же массивы $${\rm Info}$$, $${\rm Next}$$, $${\rm Precede}$$ использовать для одновременного хранения нескольких однотипных списков, позиции этих массивов объединяют в один так называемый свободный список $${\rm Avail}$$. Это можно сделать, например, с помощью операторов
$$\formula{ \t begin\\ \mbox{} \q {\rm Avail}.{\rm first} :=1;\ {\rm Next}[\t{n}] := 0;\ \t{for}\ i:= 1\ \t{to}\ \t{n} - 1\ \t{do}\ {\rm Next}[\t{i}]:= \t{i} + 1;\\ \mbox{} \q {\rm Preced}[1]:= 0;\ \t{for}\ \t{i}:= 2\ \t{to}\ \t{n}\ \t{do}\ {\rm Preced}[i]:= \t{i} - 1;\\ \t{end}; }$$Массив $${\rm Info}$$ при этом не заполняется. При создании новых
списков используются элементы массивов $${\rm Info}$$, $${\rm
Next}$$, $${\rm Precede}$$,
предварительно удаляемые из списка $${\rm Avail}$$.
В момент создания нового узла из списка $${\rm Avail}$$
удаляется головной элемент, который и используется для добавления в новый
список. С другой стороны, при удалении элемента из какого-либо списка
освобождаемая позиция добавляется к свободному списку для последующего
использования. Такая техника применялась, когда системы программирования
не имели стандартных средств
Деревья находят широкое применение при проектировании алгоритмов и, в частности, структур данных. Отсылая читателя к литературе по теории графов, мы будем пользоваться такими понятиями, как узел, ребро, лист, потомок, сын, левый потомок, правый потомок, предок, отец, корень, ветвь и другие. Регулярным деревом назовем дерево, в котором фиксировано максимально возможное (как правило, небольшое) число потомков для каждого из его узлов. В частности, если число потомков для каждого узла не больше двух, то дерево называется бинарным, если не более трех — тернарным. Если это число может равняться только двум или трем, то дерево называется ( $$2$$ — $$3$$ )-деревом.
Достаточно универсальным является способ представления регулярных деревьев, при котором каждый узел представляется записью, содержащей, кроме прикладной информации, позиции смежных с ним элементов, например позиции потомков или наряду с потомками позицию предка или еще каких-либо узлов, в зависимости от потребностей. Регулярность дерева позволяет фиксировать число полей, достаточное для представления любого узла.
Так, узлы бинарного
Для представления нерегулярных деревьев (то есть деревьев, узлы которых могут иметь произвольное число потомков) применяют следующий способ: потомки каждого узла нумеруются и каждый узел представляется записью, включающей в себя позицию его первого (левого) потомка и позицию его "правого брата".
Для регулярных деревьев более экономным по памяти может оказаться представление с помощью массива. Рассмотрим этот прием на примере бинарного дерева. Значения индексов массива отождествляются с узлами дерева, пронумерованными так, что корень получает номер 1, а потомки узла c номером $$i$$ получают номера $$2i$$ и $$2i + 1$$. При таком представлении предок узла с номером $$i$$ будет иметь номер $$i \mathop{\rm div}\nolimits 2$$ (частное от деления $$i$$ на 2). Аналогично можно представить тернарное и другие регулярные деревья.
Остановимся вкратце на представлении графов общего вида.
Матричный способ представления может оказаться неэкономным с точки зрения
использования памяти, если граф разрежен. Так, например, известно, что
число ребер связного
Другой способ представления графа — это список или массив пар вершин, соответствующих ребрам. При таком способе, если граф не ориентирован, то из двух возможных пар ( $$i$$, $$j$$ ) и ( $$j$$, $$i$$ ) целесообразно хранить только одну, например ту, у которой первая компонента меньше второй.
Еще один способ, часто имеющий преимущества перед названными выше, — это представление графа массивом или списком списков (рис. 2.7).
(рис 2.7) Представление графа комбинацией списков: множество вершин представлено списком узлов, к каждому из которых справа подцеплен список смежных с ним вершинА именно, для каждой вершины организуется список смежных с ней вершин. В этом случае легко осуществляется доступ к окрестностям вершин. Примерно такого же эффекта можно достичь, представляя граф с помощью двух массивов: $${\rm inf} [1 \ldots m]$$ и $${\rm adr} [1\ldots n + 1)]$$, где $$m$$ — число ребер графа. Массив $${\rm adr}$$ назовем адресным, а $${\rm inf}$$ — информационным. В информационном массиве вначале перечисляются номера вершин, смежных с первой вершиной, затем — со второй и так далее. В адресном массиве указываются номера позиций информационного массива так, чтобы для каждой вершины $$i$$ по ним можно было находить фрагменты массива $${\rm inf}$$, в которых записаны номера вершин, смежных с этой вершиной. Например, $${\rm adr}[i]$$ может хранить позицию, с которой начинаются в массиве $${\rm inf}$$ вершины, смежные с $$i$$ -й, при этом $${\rm adr}[n + 1]$$ — первая позиция за пределами массива $${\rm inf}$$. В таком случае, если нам требуется с каждой вершиной $$j$$ из окрестности вершины $$i$$ выполнить оператор $$S(j)$$, то можно сделать это с помощью оператора цикла:$$\eq*{ for k := {\rm adr}[i]\ to\ {\rm adr} [i + 1] - 1\ \t{do} S({\rm inf}[k]). }$$
Заметим, что если граф не ориентирован, то каждое ребро ( $$i$$, $$j$$ ) будет представлено дважды: один раз в последовательности вершин, смежных с вершиной $$i$$, а второй раз — в последовательности вершин, смежных с вершиной $$j$$. Но эта избыточность часто бывает полезна с точки зрения времени выполнения операций над окрестностями вершин графа. Как недостаток такого представления графа, можно отметить неудобство при динамической модификации графа, например, добавление к графу ребра может потребовать большого количества пересылок в массиве $$\rm inf$$. Этого недостатка лишен способ представления графа, показанный на рис. 2.7.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.