Очередь
Стек
Список
Линейный однонаправленный список
Список – это структура данных, представляющая собой логически связанную последовательность элементов списка. В связанном списке (или просто списке; по-английски linked list) элементы линейно упорядочены, но порядок определяется не номерами, как в массиве, а указателями, входящими в состав элементов списка. Списки являются удобным способом хранения динамических множеств, позволяющим реализовать все операции, перечисленные во введении к этой части (хотя и не всегда эффективно).
Если каждый, стоящий в очереди, запомнит, кто за ним стоит, получится односторонне связанный список – при такой организации элементы некоторого типа образуют цепочку. В этом списке любой элемент имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем у последнего элемента. Если он запомнит ещё и стоящего впереди, будет двусторонне связанный список. Для связывания элементов в списке используют систему указателей, и в зависимости от их количества в элементах различают односвязные и двусвязные линейные списки.
Рисунок 3.1 – Линейный односвязный список
Основные операции, осуществляемые с линейным однонаправленным списком:
– вставка элемента;
– просмотр;
– поиск;
– удаление элемента.
Следует обратить особое внимание на то, что при выполнении любых операций с линейным однонаправленным списком необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен.
Для описания алгоритмов этих основных операций используем следующие объявления:
type
PElement = ^TypeElement; {указатель на тип элемента}
TypeElement = record {тип элемента списка}
Data: TypeData; {поле данных элемента}
Next: PElement; {поле указателя на следующий элемент}
end;
var
ptrHead: PElement; {указатель на первый элемент списка}
ptrCurrent: PElement; {указатель на текущий элемент}
Вставка первого и последующих элементов списка отличаются друг от друга. Поэтому приводится два алгоритма вставки, оформленных в виде процедур языка Pascal: InsFirst_LineSingleList и Ins_LineSingleList. В качестве входных параметров передаются данное для заполнения создаваемого элемента, указатель на начало списка и указатель на текущий элемент в списке (при необходимости). Выходными параметрами процедур является указатель на начало списка (который возможно изменится) и указатель текущего элемента, который показывает на вновь созданный элемент (при вставке первого элемента указателем на него будет указатель на заголовок списка).
Для добавления элемента в конец списка используется процедура вставки последующего элемента для случая, когда текущий элемент является последним в списке.
procedure Ins_LineSingleList(DataElem: TypeData;
var ptrHead, ptrCurrent: PElement);
{Вставка непервого элемента в линейный однонаправленный список}
{справа от элемента, на который указывает ptrCurrent}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
New(ptrAddition);
ptrAddition^.Data := DataElem;
if ptrHead = nil then begin {список пуст}
{создаем первый элемент списка}
ptrAddition^.Next := nil;
ptrHead := ptrAddition;
end else begin {список не пуст}
{вставляем элемент списка справа от элемента,}
{на который указывает ptrCurrent}
ptrAddition^.Next := ptrCurrent^.Next;
ptrCurrent^.Next := ptrAddition;
end;
ptrCurrent := ptrAddition;
end;
procedure InsFirst_LineSingleList(DataElem: TypeData;
var ptrHead: PElement);
{Вставка первого элемента в линейный однонаправленный список}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
New(ptrAddition);
ptrAddition^.Data := DataElem;
if ptrHead = nil then begin {список пуст}
{создаем первый элемент списка}
ptrAddition^.Next := nil;
end else begin {список не пуст}
{вставляем новый элемент слева (перед) первым элементом}
ptrAddition^.Next := ptrHead;
end;
ptrHead := ptrAddition;
end;
Листинг 3.1 – Процедуры добавления элемента в односвязный список (в хвост и голову)
Порядок следования операторов присваивания обеих процедур очень важен. При неправильном переопределении указателей возможен разрыв списка или потери указателя на первый элемент, что приводит к потере доступа к части или всему списку.
Операция просмотра списка заключается в последовательном просмотре всех элементов списка.
procedure Scan_LineSingleList(ptrHead: PElement);
{Просмотр линейного однонаправленного списка}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
ptrAddition := ptrHead;
while ptrAddition <> nil do begin {пока не конец списка}
writeln(ptrAddition^.Data); {Вывод значения элемента}
ptrAddition := ptrAddition^.Next;
end;
end;
Листинг 3.2 – Процедура просмотра односвязного списка
Операция поиска элемента в списке заключается в последовательном просмотре всех элементов списка до тех пор, пока текущий элемент не будет содержать заданное значение или пока не будет достигнут конец списка. В последнем случае фиксируется отсутствие искомого элемента в списке (функция принимает значение false). Входными параметрами являются значение, которое должен содержать искомый элемент и указатель на список. В качестве выходного параметра передается указатель, который устанавливается на найденный элемент или остается без изменений, если элемента в списке нет.
function Find_LineSingleList(DataElem: TypeData;
var ptrHead, ptrCurrent: PElement): boolean;
{Поиск элемента в линейном однонаправленном списке}
var
ptrAddition:PElement; {Дополнительный указатель}
begin
if (ptrHead <> nil)then begin {Если существует список}
ptrAddition := ptrHead;
while (ptrAddition <> nil) and
(ptrAddition^.Data <> DataElem) do
{пока не конец списка и не найден элемент}
ptrAddition := ptrAddition^.Next;
{Если элемент найден,
то результатом работы функции является - true}
if ptrAddition <> nil then begin
Find_LineSingleList := true;
ptrCurrent := ptrAddition;
end else begin
Find_LineSingleList := false;
end;
end else begin
Find_LineSingleList:=false;
end;
end;
Листинг 3.2 – Процедуры добавления элемента в односвязный список (в хвост и голову)
Ниже представлен псевдокод процедуры List-Search(L, k), котораянаходит в списке L (с помощью простого линейного поиска) первый элемент, имеющий ключ k. Точнее говоря, она возвращает указатель на этот элемент или NIL, если элемента с таким ключом в списке нет.
Листинг 3.3 – Линейный поиск элемента в списке
Поиск в списке из n элементов требует в худшем случае (когда приходится просматривать весь список) Θ(n) операций.
Можно отметить, что алгоритмы просмотра и поиска будут корректно работать без дополнительных проверок и в случае, когда список пуст.
Операция удаления элемента линейного однонаправленного списка осуществляет удаление элемента, на который установлен указатель текущего элемента. После удаления указатель текущего элемента устанавливается на предшествующий элемент списка, или на новое начало списка, если удаляется первый.
Алгоритмы удаления первого и не первого элементов списка отличаются друг от друга. Поэтому в процедуре, реализующую данную операцию, осуществляется проверка, какой элемент удаляется, и далее реализуется соответствующий алгоритм удаления.
procedure Del_LineSingleList(var ptrHead,
ptrCurrent: PElement);
{Удаление элемента из линейного однонаправленного списка}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
if ptrCurrent <> nil then begin {вх.параметр корректен}
if ptrCurrent = ptrHead then begin {удаляем первый}
ptrHead := ptrHead^.Next;
dispose(ptrCurrent);
ptrCurrent := ptrHead;
end else begin {удаляем не первый}
{устанавливаем вспомогательный указатель на элемент,
предшествующий удаляемому}
ptrAddition := ptrHead;
while ptrAddition^.Next <> ptrCurrent do
ptrAddition := ptrAddition^.Next;
{непосредственное удаление элемента}
ptrAddition^.Next := ptrCurrent^.Next;
dispose(ptrCurrent);
ptrCurrent := ptrAddition;
end;
end;
end;
Листинг 3.4 – Линейный поиск элемента в списке
Линейный однонаправленный список имеет только один указатель в элементах. Это позволяет минимизировать расход памяти на организацию такого списка. Одновременно, это позволяет осуществлять переходы между элементами только в одном направлении, что зачастую увеличивает время, затрачиваемое на обработку списка. Например, для перехода к предыдущему элементу необходимо осуществить просмотр списка с начала до элемента, указатель которого установлен на текущий элемент.
Для ускорения подобных операций целесообразно применять переходы между элементами списка в обоих направлениях. Это реализуется с помощью линейных двунаправленных списков.
Линейный двунаправленный список
В этом линейном списке любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке или является пустым указателем у последнего элемента, а второй указывает на предыдущий элемент в списке или является пустым указателем у первого элемента.
Рисунок 3.2 – Линейный двусвязный список
Основные операции, осуществляемые с линейным двунаправленным списком те же, что и с однонаправленным линейным списком:
– вставка элемента;
– просмотр;
– поиск;
– удаление элемента.
Следует обратить внимание на то, что в отличии от однонаправленного списка здесь нет необходимости обеспечивать позиционирование какого-либо указателя именно на первый элемент списка, так как благодаря двум указателям в элементах можно получить доступ к любому элементу списка из любого другого элемента осуществляя переходы в прямом или обратном направлении. Однако часто бывает полезно иметь указатель на заголовок списка.
Для описания алгоритмов этих основных операций используем следующие объявления:
type
PElement = ^TypeElement;{указатель на тип элемента}
TypeElement = record {тип элемента списка}
Data: TypeData; {поле данных элемента}
Next, {поле указателя на следующий элемент}
Last: PElement; {поле указателя на предыдующий элемент}
end;
var
ptrHead: PElement; {указатель на первый элемент списка}
ptrCurrent: PElement; {указатель на текущий элемент}
Операция вставки реализовывается с помощью двух процедур, аналогичных процедурам вставки для линейного однонаправленного списка: InsFirst_LineDubleList и Ins_LineDubleList. Однако, при вставке последующего элемента придется учитывать особенности добавления элемента в конец списка.
procedure Ins_LineDubleList(DataElem: TypeData;
var ptrHead, ptrCurrent: PElement);
{Вставка непервого элемента в линейный двунаправленный список}
{справа от элемента, на который указывает ptrCurrent}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
New(ptrAddition);
ptrAddition^.Data := DataElem;
if ptrHead = nil then begin {список пуст}
{создаем первый элемент списка}
ptrAddition^.Next := nil;
ptrAddition^.Last := nil;
ptrHead := ptrAddition;
end else begin {список не пуст}
{вставляем элемент списка справа от элемента,}
{на который указывает ptrCurrent}
if ptrCurrent^.Next <> nil then {вставляем не последний}
ptrCurrent^.Next^.Last := ptrAddition;
ptrAddition^.Next := ptrCurrent^.Next;
ptrCurrent^.Next := ptrAddition;
ptrAddition^.Last := ptrCurrent;
end;
ptrCurrent := ptrAddition;
end;
procedure InsFirst_LineDubleList(DataElem: TypeData;
var ptrHead: PElement);
{Вставка первого элемента в линейный двунаправленный список}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
New(ptrAddition);
ptrAddition^.Data := DataElem;
ptrAddition^.Last := nil;
if ptrHead = nil then begin {список пуст}
{создаем первый элемент списка}
ptrAddition^.Next := nil;
end else begin {список не пуст}
{вставляем новый элемент слева (перед) первым элементом}
ptrAddition^.Next := ptrHead;
ptrHead^.Last := ptrAddition;
end;
ptrHead := ptrAddition;
end;
Листинг 3.4 – Процедуры добавления элемента в двусвязный список (в хвост и голову)
Порядок следования операторов присваивания обеих процедур здесь также очень важен. При неправильном переопределении указателей возможен разрыв списка или потери указателя на первый элемент, что приводит к потере доступа к части или всему списку.
Ниже представлен псевдокод процедуры List-Insert, которая добавляет элемент х к списку L, помещая его в голову списка.
Листинг 3.5 – Добавление элемента в голову списка
Процедура List-Insert выполняется за время O(1) (не зависящее от длины списка).
Операция просмотра и операция поиска для линейного двунаправленного списка реализуются абсолютно аналогично соответствующим процедурам для линейного однонаправленного списка, и приводить их не будем. Отметим только, что просматривать и искать здесь можно в обоих направлениях.
Операция удаления элемента также осуществляется во многом аналогично удалению из линейного однонаправленного списка.
procedure Del_LineDubleList(var ptrHead,
ptrCurrent: PElement);
{Удаление элемента из линейного двунаправленного списка}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
if ptrCurrent <> nil then begin {вх.параметр корректен}
if ptrCurrent = ptrHead then begin {удаляем первый}
ptrHead := ptrHead^.Next;
dispose(ptrCurrent);
ptrHead^.Last := nil;
ptrCurrent := ptrHead;
end else begin { удаляем не первый }
if ptrCurrent^.Next = nil then begin {удаляем последний}
ptrCurrent^.Last^.Next := nil;
dispose(ptrCurrent);
ptrCurrent := ptrHead;
end else begin {удаляем не последний и не первый}
ptrAddition := ptrCurrent^.Next;
ptrCurrent^.Last^.Next := ptrCurrent^.Next;
ptrCurrent^.Next^.Last := ptrCurrent^.Last;
dispose(ptrCurrent);
ptrCurrent := ptrAddition;
end;
end;
end;
end;
Листинг 3.6 – Процедура удаления элемента из двусвязного списка
Ниже представлена процедура List-Delete на псевдокоде, которая удаляет элемент х из списка L, направляя указатели «в обход» этого элемента. При этом в качестве аргумента ей передаётся указатель на х. Если задан ключ элемента х, то перед удалением надо найти его указатель с помощью процедуры List-Search.
Листинг 3.7 – Удаление элемента из двусвязного списка
Процедура List-Delete работает за время O(1); однако для удаления элемента с заданные ключом его надо сначала найти, что потребует времени Q(n).
Использование двух указателей в линейном двунаправленном списке позволяет ускорить операции, связанные с передвижением по списку за счет двунаправленности этого движения. Однако, элементы списка за счет дополнительного поля занимают больший объем памяти. Кроме того, усложнились операции вставки и удаления элементов за счет необходимости манипулирования большим числом указателей.
Двунаправленный список с фиктивными элементами
Рисунок 3.3 – Двусвязный список c фиктивным элементом
На рисунке 3.2 показан список L, использующий фиктивный элемент nil[L](темно – серый прямоугольник). Вместо head[L]используем next[nil[L]]. (a) Пустой список. (б) Список, у которого элемент с ключом 9 – голова, 1 - хвост). (в) Тот же список после процедуры List-Insert'(L,x), если key[x] = 25. (г) После удаления элемента с ключом 1. Новый хвост имеет ключ 4.
Если забыть об особых ситуациях на концах списка, процедуру List-Delete можно записать совсем просто:
Листинг 3.8 – Упрощенная процедура удаления элемента из списка
Такие упрощения станут «законными», если добавить к списку L фиктивный элемент nil[L], который будет иметь поля next и prev наравне с прочими элементами списка. Этот элемент (называемый по-английски sentinel, что означает «часовой») не позволит выйти за пределы списка. Указатель на него играет роль значения NIL. Замкнём список в кольцо: в поля next[nil[L]]и prev[nil[L]]запишем указатели на голову и хвост списка соответственно, а в поля prev у головы списка и next у хвоста списка занесём указатели на nil[L](рис. 3.2). При этом next[nil[L]] – указатель на голову списка, так что атрибут head[L]становится лишним. Пустой список L теперь будет кольцом, в котором nil[L] – единственный элемент.
В процедуре List-Search нужно лишь заменить NIL на nil[L]и head[L]на next[nil[L]]:
Листинг 3.9 – Процедура поиска в списке с фиктивным элементом
Для удаления элемента применяется процедура List-Delete, приведенная выше. Наконец, добавлять элемент к списку можно так:
Листинг 3.10 – Процедура добавления в список с фиктивным элементом
Пример работы процедур List-Insert и List-Delete показан на рис.3.2. Использование фиктивных элементов едва ли может улучшить асимптотику времени работы алгоритма, но упрощает программу. Иногда (если использование фиктивных элементов позволяет сократить фрагмент кода, находящийся глубоко внутри цикла), можно ускорить исполнение программы в несколько раз;
Не следует применять фиктивные элементы без нужды. Если алгоритм использует много коротких списков, использование фиктивных элементов может обернуться серьезной дополнительной тратой памяти. Обычно фиктивные элементы используются только тогда, когда это существенно упрощает программу.
Циклические списки
Линейные списки характерны тем, что в них можно выделить первый и последний элементы (имеющие пустые указатели), причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Это приводило к тому, что алгоритмы вставки и удаления крайних и средних элементов списка отличались друг от друга, что, естественно, усложняло соответствующие операции.
Основное отличие циклического списка состоит в том, что в этом списке нет элементов, содержащих пустые указатели, и, следовательно, нельзя выделить крайние элементы. Таким образом, все элементы являются «средними».
Циклические списки также как и линейные бывают однонаправленными и двунаправленными.
Циклический однонаправленный список
Циклический однонаправленный список похож на линейный однонаправленный список, но его последний элемент содержит указатель, связывающий его с первым элементом.
Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие «первого» элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как «первый» путем установки на него специального указателя. Это требуется, например, для предотвращения «зацикливания» при просмотре списка.
Рисунок 3.4 – Циклический односвязный список
Основные операции, осуществляемые с циклическим однонаправленным списком:
– вставка элемента;
– просмотр;
– поиск;
– удаление элемента.
Для описания алгоритмов этих основных операций используем те же объявления данных, что и для линейного однонаправленного списка.
Вставка элемента в список, как уже говорилось, проще, чем для линейного однонаправленного списка и реализуется с помощью одной единственной процедуры: Ins_CicleSingleList. В качестве входных параметров передаются данное для заполнения создаваемого элемента, указатель на начало списка и указатель на текущий элемент в списке, после которого осуществляется вставка. Выходными параметрами процедур является указатель на начало списка (который возможно изменится) и указатель текущего элемента, который показывает на вновь созданный элемент.
procedure Ins_CicleSingleList(DataElem: TypeData;
var ptrHead, ptrCurrent: PElement);
{Вставка элемента в циклический однонаправленный список}
{справа от элемента, на который указывает ptrCurrent}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
New(ptrAddition);
ptrAddition^.Data := DataElem;
if ptrHead = nil then begin {список пуст}
{создаем первый элемент списка}
ptrAddition^.Next := ptrAddition; {цикл из 1 элемента}
ptrHead := ptrAddition;
end else begin {список не пуст}
{вставляем элемент списка справа от элемента,}
{на который указывает ptrCurrent}
ptrAddition^.Next := ptrCurrent^.Next;
ptrCurrent^.Next := ptrAddition;
end;
ptrCurrent := ptrAddition;
end;
Листинг 3.11 – Процедура добавления элемента в циклический двусвязный список
Порядок следования операторов присваивания процедуры очень важен. При неправильном переопределении указателей возможен разрыв списка или потери указателя на первый элемент, что приводит к потере доступа к части или всему списку.
Операция просмотра списка заключается в последовательном просмотре всех элементов списка. В отличие от линейного однонаправленного списка здесь признаком окончания просмотра списка будет возврат к элементу, выделенным как «первый».
procedure Scan_CicleSingleList(ptrHead: PElement);
{Просмотр циклического однонаправленного списка}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
if ptrHead <> nil do begin {список не пуст}
ptrAddition := ptrHead;
repeat
writeln(ptrAddition^.Data); {Вывод значения элемента}
ptrAddition := ptrAddition^.Next;
until ptrAddition = ptrHead;
end;
end;
Листинг 3.12 – Процедура просмотра циклического односвязного списка
Операция поиска элемента в списке заключается в последовательном просмотре всех элементов списка до тех пор, пока текущий элемент не будет содержать заданное значение или пока не достигнут «первый» элемент списка. В последнем случае фиксируется отсутствие искомого элемента в списке (функция принимает значение false). Входными параметрами являются значение, которое должен содержать искомый элемент и указатель на список. В качестве выходного параметра передается указатель, который устанавливается на найденный элемент или остается без изменений, если элемента в списке нет.
function Find_CicleSingleList(DataElem: TypeData;
var ptrHead,
ptrCurrent: PElement): boolean;
{Поиск в циклическом однонаправленном списке}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
if ptrHead <> nil do begin {список не пуст}
ptrAddition := ptrHead;
repeat
ptrAddition := ptrAddition^.Next;
until (ptrAddition = ptrHead) or {прошли весь список}
(ptrAddition^.Data = DataElem) {элемент найден}
if ptrAddition^.Data = DataElem then begin
Find_CicleSingleList := true;
ptrCurrent := ptrAddition;
end else begin
Find_CicleSingleList := false;
end;
end else begin
Find_CicleSingleList := false;
end;
end;
Листинг 3.13 – Процедура поиска элемента в циклическом односвязном списке
Операция удаления элемента циклического однонаправленного списка осуществляет удаление элемента, на который установлен указатель текущего элемента. После удаления указатель текущего элемента устанавливается на следующий за удаляемым элемент списка. Здесь не требуется отдельных алгоритмов удаления для крайних элементов списка, как это было в линейных списках, но в случае удаления «первого» элемента, необходимо соответствующий указатель переместить на следующий элемент.
procedure Del_CicleSingleList(var ptrHead, ptrCurrent: PElement);
{Удаление элемента из циклического однонаправленного списка}
var
ptrAddition: PElement; {дополнительный указатель}
begin
if ptrCurrent <> nil then begin {вх.параметр корректен}
if ptrHead^.Next <> ptrHead then begin
{Если удаляемый элемент не единственный в списке}
{Устанавливаем вспомогательный указатель на элемент,
предшествующий удаляемому}
ptrAddition := ptrHead;
while ptrAddition^.Next <> ptrCurrent do
ptrAddition := ptrAddition^.Next;
{непосредственное удаление элемента}
ptrAddition^.Next := ptrCurrent^.Next;
if ptrHead = ptrCurrent then {удаляем первый}
ptrHead := ptrCurrent^.Next;
dispose(ptrCurrent);
ptrCurrent := ptrAddition^.Next;
end else begin
ptrHead:=nil;
dispose(ptrCurrent);
ptrCurrent:=nil;
end;
end;
end;
Листинг 3.13 – Процедура удаления элемента из циклического односвязного списка
Циклический однонаправленный список, так же как и линейный однонаправленный список имеет только один указатель в элементах, что позволяет минимизировать расход памяти на организацию списка, но обеспечивает переходы между элементами только в одном направлении. Одновременно, здесь упрощены операции вставки и удаления элементов.
Для ускорения доступа к элементам списка путем применения переходов между элементами в обоих направлениях в циклических списках применяют тот же подход, что и в линейных списках: циклический двунаправленный список.
Циклический двунаправленный список
В этом циклическом списке любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент.
Рисунок 3.5 – Циклический двусвязный список
Основные операции, осуществляемые с циклическим двунаправленным списком:
– вставка элемента;
– просмотр;
– поиск;
– удаление элемента.
Для описания алгоритмов этих основных операций используем те же объявления данных, что и для линейного двунаправленного списка.
Вставка элемента в список, как уже говорилось, проще, чем для линейного двунаправленного списка и реализуется с помощью одной единственной процедуры: Ins_CicleDubleList. В качестве входных параметров передаются: данное для заполнения создаваемого элемента, указатель на начало списка и указатель на текущий элемент в списке, после которого осуществляется вставка. Выходными параметрами процедур является указатель на начало списка (который возможно изменится) и указатель текущего элемента, который показывает на вновь созданный элемент.
procedure Ins_CicleDubleList(DataElem: TypeData;
var ptrHead, ptrCurrent: PElement);
{Вставка элемента в циклический двунаправленный список
справа от элемента, на который указывает ptrCurrent}
var
ptrAddition: PElement; {вспомогательный указатель}
begin
New(ptrAddition);
ptrAddition^.Data := DataElem;
if ptrHead = nil then begin {список пуст}
{создаем первый элемент списка}
ptrAddition^.Next := ptrAddition; {петля из 1 элемента}
ptrAddition^.Last := ptrAddition;
ptrHead := ptrAddition;
end else begin {список не пуст}
{вставляем элемент списка справа от элемента,}
{на который указывает ptrCurrent}
ptrAddition^.Next := ptrCurrent^.Next;
ptrCurrent^.Next := ptrAddition;
ptrAddition^.Last := ptrCurrent;
ptrAddition^.Next^.Last := ptrAddition;
end;
ptrCurrent := ptrAddition;
end;
Листинг 3.14 – Процедура добавления элемента в циклический двусвязный список
Порядок следования операторов присваивания процедуры очень важен. При неправильном переопределении указателей возможен разрыв списка или потери указателя на первый элемент, что приводит к потере доступа к части или всему списку.
Операция просмотра и операция поиска для циклического двунаправленного списка реализуются абсолютно аналогично соответствующим процедурам для циклического однонаправленного списка, и приводить их не будем. Отметим только, что просматривать и искать здесь можно в обоих направлениях.
Операция удаления элемента также осуществляется во многом аналогично удалению из циклического однонаправленного списка.
procedure Del_CicleDubleList(var ptrHead, ptrCurrent: PElement);
{Удаление элемента из циклического двунаправленного списка}
var
ptrAddition: PElement; {дополнительный указатель}
begin
if ptrCurrent <> nil then begin {вх.параметр корректен}
if ptrHead^.Next <> ptrHead then begin
{Если удаляемый элемент не единственный в списке}
ptrAddition := ptrCurrent^.Next;
ptrCurrent^.Last^.Next := ptrCurrent^.Next;
ptrCurrent^.Next^.Last := ptrCurrent^.Last;
if ptrHead = ptrCurrent then {удаляем первый}
ptrHead := ptrCurrent^.Next;
dispose(ptrCurrent);
ptrCurrent := ptrAddition;
end else begin
ptrHead:=nil;
dispose(ptrCurrent);
ptrCurrent:=nil;
end;
end;
end;
Листинг 3.15 – Процедура удаления элемента из циклического двусвязного списка
Использование двух указателей в циклическом двунаправленном списке позволяет ускорить операции, связанные с передвижением по списку за счет двунаправленности этого движения. Однако, элементы списка за счет дополнительного поля занимают больший объем памяти. Операции вставки и удаления элементов здесь осуществляются проще, чем в линейном двунаправленном списке, но сложнее, чем в циклическом однонаправленном списке (за счет необходимости манипулирования большим числом указателей).
Стек можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка.
При реализации стека в виде статического массива необходимо резервировать массив, длина которого равна максимально возможной глубине стека, что приводит к неэффективному использованию памяти. Одновременно, работать с такой реализацией проще и быстрее.
При такой реализации дно стека будет располагаться в первом элементе массива, а рост стека будет осуществляться в сторону увеличения индексов. Одновременно, необходимо отдельно хранить значение индекса элемента массива, являющегося вершиной стека.
Можно обойтись без отдельного хранения индекса, если в качестве вершины стека всегда использовать первый элемент массива, но в этом случае, при записи или чтении из стека, необходимо будет осуществлять сдвиг всех остальных элементов, что приводит к дополнительным затратам вычислительных ресурсов.
Стек как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа всегда идет с заголовком стека, то есть не требуется осуществлять просмотр элементов, удалению и вставку элементов в середину или конец списка, то достаточно использовать экономичный по памяти линейный однонаправленный список. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует и указатель принимает значение nil.
Рисунок 3.6 – Стек и его организация
Поскольку стек, по своей сути, является структурой с изменяемым количеством элементов, то основное внимание уделим динамической реализации стека. Как уже говорилось выше, для такой реализации целесообразно использовать линейный однонаправленный список.
Описание элементов стека аналогично описанию элементов линейного однонаправленного списка, где DataType является типом элементов стека.
Основные операции, производимые со стеком:
- записать (положить в стек);
- прочитать (снять со стека);
- очистить стек;
- проверка пустоты стека.
Реализация этих операций приведена в виде соответствующих процедур, которые, в свою очередь, используют процедуры операций с линейным однонаправленным списком.
procedure PushStack(NewElem: TypeData;
var ptrStack: PElement);
{Запись элемента в стек (положить в стек)}
begin
InsFirst_LineSingleList(NewElem, ptrStack);
end;
procedure PopStack(var NewElem: TypeData,
ptrStack: PElement);
{Чтение элемента из стека (снять со стека)}
begin
if ptrStack <> nil then begin
NewElem := ptrStack^.Data;
Del_LineSingleList(ptrStack, ptrStack); {удаляем вершину}
end;
end;
procedure ClearStack(var ptrStack: PElement);
{Очистка стека}
begin
while ptrStack <> nil do
Del_LineSingleList(ptrStack, ptrStack); {удаляем вершину}
end;
function EmptyStack(var ptrStack: PElement): boolean;
{Проверка пустоты стека}
begin
if ptrStack = nil then EmptyStack := true
else EmptyStack := false;
end;
Листинг 3.16 – Реализация стека на базе линейного однонаправленного списка
Листинг 3.17 – Операции со стеком
Очередь – это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. Здесь используется принцип «первым пришел – первым вышел» (FIFO: First Input – First Output).
Очередь можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка.
При реализации очереди в виде статического массива необходимо резервировать массив, длина которого равна максимально возможной длине очереди, что приводит к неэффективному использованию памяти.
При такой реализации начало очереди будет располагаться в первом элементе массива, а рост очереди будет осуществляться в сторону увеличения индексов. Однако, поскольку добавление элементов происходит в один конец, а выборка – из другого конца очереди, то с течением времени будет происходить миграция элементов очереди из начала массива в сторону его конца. Это может привести к быстрому исчерпанию массива и невозможности добавлении новых элементов в очередь при наличии свободных мест в начале массива. Предотвратить это можно двумя способами:
- после извлечения очередного элемента из начала очереди осуществлять сдвиг всей очереди на один элемент к началу массива. При этом необходимо отдельно хранить значение индекса элемента массива, являющимся концом очереди (начало очереди всегда в первом элементе массива);
- представить массив в виде циклической структуры, где первый элемент массива следует за последним. Элементы очереди располагаются в «круге» элементов массива в последовательных позициях, конец очереди находится по часовой стрелке на некотором расстоянии от начала. При этом необходимо отдельно хранить значение индекса элемента массива, являющимся началом очереди, и значение индекса элемента массива, являющимся концом очереди. Когда происходит добавление в конец или извлечение из начала очереди, осуществляется смещение значений этих двух индексов по часовой стрелке.
С точки зрения экономии вычислительных ресурсов более предпочтителен второй способ. Однако здесь усложняется проверка на пустоту очереди и контроль переполнения очереди – индекс конца очереди не должен «набегать» на индекс начала.
Очередь как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа идет с обоими концами очереди, то предпочтительно будет использовать линейный двунаправленный список. Хотя, как уже говорилось при описании этого списка, для работы с ним достаточно иметь один указатель на любой элемент списка, здесь целесообразно хранить два указателя – один на начало списка (откуда извлекаем элементы) и один на конец списка (куда добавляем элементы). Если очередь пуста, то списка не существует, и указатели принимают значение nil.
Поскольку очередь, по своей сути, является структурой с изменяемым количеством элементов, то основное внимание уделим динамической реализации очереди. Как уже говорилось выше, для такой реализации целесообразно использовать линейный двунаправленный список.
Рисунок 3.7 – Очередь и ее организация
Описание элементов очереди аналогично описанию элементов линейного двунаправленного списка, где DataType является типом элементов очереди. Дополнительно введем два указателя на начало и конец очереди:
var
ptrBeginQueue,
ptrEndQueue: PElement;
Основные операции, производимые с очередью:
- добавить элемент;
- извлечь элемент;
- очистить очередь;
- проверка пустоты очереди.
Реализация этих операций приводится в виде соответствующих процедур, которые, в свою очередь, используют процедуры операций с линейным двунаправленным списком.
procedure Enqueue(NewElem: TypeData;
var ptrBeginQueue, ptrEndQueue: PElement);
{Добавление элемента в очередь}
begin
Ins_LineDoubleList(NewElem, ptrBeginQueue, ptrEndQueue);
end;
procedure Dequeue(var NewElem: TypeData;
var ptrBeginQueue: PElement);
{Извлечение элемента из очереди}
begin
if ptrBeginQueue <> nil then begin
NewElem := ptrEndQueue^.Data;
Del_LineDoubleList(ptrBeginQueue, ptrBeginQueue);
end;
end;
procedure ClearQueue(var ptrBeginQueue,
ptrEndQueue: PElement);
{Очистка очереди}
begin
while ptrBeginQueue <> nil do
Del_LineDoubleList(ptrBeginQueue, ptrBeginQueue);
ptrEndQueue := nil;
end;
function EmptyQueue(var ptrBeginQueue: PElement): boolean;
{Проверка пустоты очереди}
begin
if ptrBeginQueue = nil then EmptyQueue := true
else EmptyQueue := false;
end;
Листинг 3.18 – Реализация очереди на базе линейного двунаправленного списка
Листинг 3.19 – Операции с очередью