Файл: Связные списки,стеки, очереди.doc

Связные списки, стеки, очереди.

Оглавление

Связные списки, стеки и очереди

Как и массивы, связные списки представляют собой универсальную структуру данных, широко используемую многими программистами. Однако, в отличие от массивов, связные списки не входят в состав стандартного языка Object Pascal. Тем не менее, в Object Pascal создать связный список достаточно просто. Все что для этого нужно - наличие в составе языка указателя, хотя фактически могут использоваться и классы или объекты.

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

Односвязные списки

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

Рис.1 Односвязаный список.

А каким образом помечается конец списка? Самый простой способ - установить указатель ссылки в последнем элементе списка равным nil. Это будет означать, что следующий элемент отсутствует. Второй способ - ввести специальный узел, называемый конечным узлом, и установить так, чтобы ссылка последнего узла указывала на этот узел. И третий способ - установить так, чтобы ссылка последнего узла указывала на первый элемент. В этом случае мы получим круговой связный список.

Рассмотрим, чем же связный список отличается от массива. Первое, что нужно отметить, - размер связного списка можно не устанавливать. Для массива нам всегда было нужно заранее знать, сколько элементов будет в нем храниться (чтобы можно было статически распределить непрерывный участок памяти) или разработать некоторую схему расширения массива (или его сокращения), чтобы массив мог разместить большее (или меньшее) количество элементов. В связном списке каждый узел является отдельным элементом. И в простых случаях распределение памяти под каждый узел выполняется отдельно. При необходимости добавления в список нового элемента под него распределяется память, а затем на него устанавливается ссылка из списка. При удалении узла нужно всего лишь удалить ссылки на него и освободить занимаемую им память.

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

Хуже то, что память под каждый узел распределяется отдельно. Сравним эту ситуацию с аналогичной ситуацией для массива. Распределение памяти под п элементов массива, фактически, представляет собой операцию класса О(1) (одна операция): все элементы должны находится в одном непрерывном блоке памяти, поэтому одновременно распределяется целый блок. Для связного списка память под узлы распределяется отдельно, следовательно, это операция класса О(п) (n- операций). Даже если не учитывать быстродействие, подобное поведение может привести к фрагментации памяти.

Самым большим недостатком связного списка является получение доступа к некоторому элементу п. В массиве доступ к n-ному элементу требует проведения простых арифметических вычислений, поскольку все элементы содержатся в одном непрерывном блоке памяти. С другой стороны, в списке получение доступа к элементу п требует прохождения по ссылкам от первого элемента до n-ного. Другого метода доступа не существует, мы всегда должны следовать по ссылкам.

Узлы связного списка

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

type

PElem = ^Elem; {Указатель на элемент списка}

Elem = record {Элемент списка - запись}

Data : TdataType; {Данные, хранящиеся в узле списка (тип - любой) }

Next : PElem; {Указатель на следующий элемент списка}

end;

Тип PElem представляет собой указатель на запись Elem, поле Next которой содержит ссылку на точно такой же узел, а поле Data - сами дан­ные. В приведенном примере тип данных узла задан как TdataType, и должен быть описан пользователем заранее (например, для хранения в списке целых чисел можно записать Type TdataType=Integer). Для перехода по ссылке на следующий элемент нужно написать примерно следующий код:

var

NextNode, CurrentNode : PElem; {где CurrentNode – указатель на текущий элемент,

NextNode – указатель на следующий элемент}

begin

…..

NextNode : = CurrentNode^.Next;

Обращения к данным, находящимся в узле списка с адресом CurrentNode, будет записано так: CurrentNode^.Data:=5; или writeln(CurrentNode^.Data);

Создание односвязного списка

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

Var HeadList : PElem;

Если HeadList содержит nil, списка еще нет. Таким образом, это начальное значение связного списка. Для определенности, в начале программы указателю на начало списка необходимо присвоить значение nil.

HeadList:=nil {инициализация связного списка}

Вставка и удаление элементов в односвязном списке

Каким образом можно вставить новый элемент в связный список? Или удалить? Оказывается, что для выполнения этих операций требуется выполнить небольшую работу с указателями. Для односвязного списка существует только один вариант вставки - после заданного элемента списка. Нужно установить ссылки так, чтобы указатель Next нашего нового узла указывал на узел после заданного, а указатель Next заданного узла - на наш новый узел. В коде это выглядит следующим образом:

var

GivenNode, NewNode : PElem; { GivenNode – указатель на заданный узел}

begin

New(NewNode);

Newnode^.Data:=15 ; {задаем значение поля Data}

NewNode ^. Next := GivenNode ^. Next ;

GivenNode ^. Next : = NewNode;

Рис.2 Вставка нового узла в односвязный список.

Аналогично, для удаления простейшим вариантом является удаление элемента, находящегося после заданного узла (GivenNode). В этом случае мы устанавливаем, чтобы указатель Next заданного узла указывал на узел, расположенный после удаляемого. После этого удаляемый узел уже выделен из списка и может быть освобожден. В коде это выглядит следующим образом:

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

var

HeadList , NewNode : PElem;

begin

………….

New(NewNode); {выделяем память под новый узел, указатель - NewNode}

NewNode^.Data:=X {заполняем поле Data для нового узла значением Х}

NewNode^.Next : = HeadList; {связываем новый узел с первым элементом – головой списка}

HeadList: = NewNode ; {список начинается с нового элемента}

………….

а удаление будет выглядеть так:

var

HeadList, TempNode : PElem;

begin

…….

TempNode:=HeadList; {запоминаем адрес первого элемента}

HeadList:= HeadList^.Next; {начало списка переставляем на следующий элемент}

Dispose(TempNode); {освобождаем память, занимаемую бывшим первым элементом }

……………………

Обратите внимание, что код вставки элемента будет работать даже в случае, когда исходный список пуст, т.е. содержит nil (HeadList = nil, после вставки будет создан первый и единственный элемент списка), а код удаления элемента правильно установит указатель на начало связного списка HeadList в nil, если происходит удаление последнего узла.

Прохождение связного списка

Прохождение связного списка также не представляет никаких трудностей. Фактически мы переходим от узла к узлу по указателям Next до достижения указателя nil, который свидетельствует об окончании списка. Вывод на экран содержимого списка, заданного указателем на начало HeadList, будет выглядеть следующим образом

var

HeadList, TempNode : PElem;

begin

…….

TempNode:=HeadList; {Для прохождения по списку нельзя использовать адрес первого элемента HeadList, т.к. потеряем весь список}

While TempNode <> nil do { пока список не пустой}

begin

Writeln(TempNode^.Data); {печатаем значение в текущем узле}

TempNode:= TempNode^.Next; {переставляем указатель на следующий элемент}

end;

…….

Очистка связного списка тре­бует небольшого изменения алгоритма, чтобы гарантировать, что мы не ссылаемся на поле Next после освобождения узла (типичная ошибка).

var

HeadList, TempNode : PElem;

begin

…….

While HeadList <> nil do { Пока список не пустой}

begin

TempNode:=HeadList {запоминаем адрес первого элемента }

HeadList:= HeadList ^.Next; {переставляем указатель начала списка на следующий элемент}

Dispose(TempNode); {удаляем предыдущий элемент }

end;

…….

Обратите внимание, что по окончании цикла While указатель на начало списка HeadList будет иметь значение nil. При работе со связными списками по завершении программы или по окончании работы со списком необходимо провести очистку, и освободить динамическую память, занимаемую такой структурой.

Теперь, когда мы научились проходить по узлам связного списка, давайте вер­немся к вопросу, который, наверное, появился у вас пару абзацев назад. А что если нам нужно вставить узел перед заданным узлом? Как это сделать? Единствен­ным решением такой задачи для односвязного списка является прохождение спис­ка и поиск узла, перед которым мы должны вставить новый узел. При прохожде­нии будут использоваться две переменных: одна будет указывать на текущий (This), а вторая на предыдущий узел (Pre). Когда будет найден заданный узел, у нас будет указатель на предыдущий узел, что позволит использовать алгоритм вставки после заданного узла. Вставка нового узла будет происходить между узлами Pre и This. В коде это выглядит следующим образом:

var

HeadList , NewNode, Pre,This : PElem;

Found:Boolean; X, Xnew:integer;

begin

………….

Pre:=nil;

This:=HeadList;

Found:=False; {Место вставки еще не найдено}

While (This<>nil) and not Found do {Второе условие – признак окончания поиска при обнаружении позиции вставки, например, This^.data=X. В этом случае вставка нового элемента будет сделана перед элементом со значением, равным Х.}

Begin

Pre:=This;

Found:= This^.data=X;

This:=This^.next;

End;

If Found then

Begin

{Если позиция вставки найдена, то добавляем новый узел между Pre и This}

New(NewNode); {выделяем память под новый узел, указатель - NewNode}

NewNode^.Data:=Xnew {заполняем поле Data для нового узла значением Хnew}

Pre^.next:=NewNode; {связываем предыдущий элемент Pre с новым NewNode}

NewNode^.next:=This; {связываем новый элемент NewNode с текущим This }

End;

……

Рис.4 Вставка нового элемента перед заданным узлом.