Двусвязный линейный список с указателем на хвост

Двусвязный список с заданными указателями на первый и последний узлы снимает проблему перемещения по списку в обе стороны и тем упрощает операции вставки и удаления в любом месте списка. Ценой за это является необходимость хранить в каждом узле дополнительный указатель на предыдущий элемент и корректировать эти указатели при изменениях списка. Для пустого списка оба указателя Head и Tail должны быть равны nil.

Двусвязный циклический список

Более популярный вариант двусвязного списка. Отсутствие указателя на хвост списка компенсируется возможностью легко перейти от первого узла к последнему по указателю Prev.

Пример реализации операции со списком

В качестве примера того, как реализуется одна и та же операция для разных вариантов представления линейного списка, рассмотрим операцию добавления нового узла в хвост списка.

Будем рассматривать список, размещенный в динамической памяти. Тогда для всех вариантов списка следует, прежде всего, создать новый узел и заполнить его поле данных:

var p: Link;

...

p := New(Link);

p^.Data := ...;

Дальнейшие действия будут различны для разных представлений списка.

Простой односвязный список:

p^.Next := nil;

if L = nil then

L := p;

else begin

q := L;

while q^.Next <> nil do

q := q^.Next; {Вперед, к хвосту!}

{Теперь q указывает на последний узел}

q^.Next := p;

p^.Next := nil;

end;

Простой односвязный список с указателем на хвост (LTail):

p^.Next := nil;

if L = nil then begin

L := p;

LTail := L;

end

else begin

LTail^.Next := p;

LTail := p;

end;

Циклический односвязный список с указателем на последний узел:

if L = nil then

p^.Next := p

else begin

{L указывает на последний, а не на первый узел!}

p^.Next := L^.Next;

L^.Next := p;

end;

L := p;

Циклический односвязный список с зацикливанием «через указатель»:

q := L;

while q^.Next <> Link(@L) do

q := q^.Next;

{Теперь q указывает на последний узел}

p^.Next := q^.Next;

q^.Next := p;

{Случай пустого списка не отличается от общего случая}

Двусвязный линейный список с указателем на хвост (LTail):

if L = nil then

L := p

else

LTail^.Next := p;

P^.Next := nil;

p^.Prev := LTail;

LTail := p;

Двусвязный циклический список:

if L = nil then begin

p^.Next := p;

p^.Prev := p;

L := p;

end

else begin

p^.Next := L;

p^.Prev := L^.Prev;

L^.Prev^.Next := p;

L^.Prev := p;

end;

Стеки

Стек – структура данных с односторонним доступом, хранящая последовательность значений, для которой определены следующие операции:

• очистить стек (сделать структуру пустой);
• проверить на пустоту;
• добавить элемент;
• взять элемент;
• прочитать элемент;
• записать элемент.

Особенностью стека является то, что в каждый момент времени мы имеем доступ лишь к одному элементу, который находится в конце стека – вершине стека.

При «добавлении элемента» новое значение добавляется в конец стека. При выполнении операции «взять элемент» – извлекается из него. Операции «прочитать элемент» и «записать элемент» работают с вершиной стека.

Говорят, что стек работает по принципу LIFO (Last in – first out; последним пришел – первым ушел).

Существуют два принципиально различных способа хранения стеков в памяти ЭВМ: хранение в виде массива последовательно расположенных элементов и хранение в виде односвязного списка.

Пусть элементами стека будут значения типа TItem.

Рассмотрим хранение стека в массиве. Для этого способа достаточно завести две переменные:

Var Top: Integer; {индекс вершины стека, число элементов в стеке} Stack: array[1..MaxSize] of TItem; {массив элементов стека}

Рассмотрим реализацию операций из функциональной спецификации стека.

Очистить стек. Для очистки стека достаточно обнулить индекс вершины стека Top. Нет никакой необходимости в физическом уничтожении данных:

procedure ClearStack;begin Top := 0;end;

Проверка на пустоту:

function IsEmpty: Boolean;begin IsEmpty := Top=0;end;

Чтение элемента:

function Get: TItem;begin if Top=0 then RunError else Get := Stack[Top];end;

Запись элемента:

procedure Put(Item: TItem);begin if Top=0 then RunError else Stack[Top] := Item;end;

Добавление элемента:

procedure Push(Item: TItem);begin if Top=MaxSize then RunError; Inc(Top); Stack[Top] := Item;end;

Взятие элемента:

function Pop: TItem;begin if Top=0 then RunError; Item := Stack[Top]; Dec(Top);end;

Второй способ хранения стека предполагает размещение стека в динамической памяти. Фактически стек хранится в однонаправленном списке. Указатель на начало списка является в то же время указателем на вершину стека (УВС).

Type PElement = ^TElement; TElement = record Item: TItem; Next: PElement; end;Var TopPointer: PElement;

Рассмотрим реализацию основных операций над стеком для такого способа хранения.

Очистить стек. В данном случае надо обязательно физически освободить всю память, выделенную под элементы стека:

procedure ClearStack;Var Temp: PElement;begin while TopPointer<>nil do begin Temp := TopPointer; TopPointer := TopPointer^.Next; Dispose(Temp); end;end;

Проверка на пустоту:

function IsEmpty: Boolean;begin IsEmpty := TopPointer=nil;end;

Чтение элемента:

function Get: TItem;begin if TopPointer=nil then RunError else Get := TopPointer^.Item;end;

Запись элемента:

procedure Put(Item: TItem);begin if TopPointer=nil then RunError else TopPointer^.Item := Item;end;

Добавление элемента. При добавлении надо выделить память под новый элемент стека:

procedure Push(Item: TItem);Var Temp: PElement;begin Temp := New(PElement); Temp^.Item := Item; Temp^.Next := TopPointer; TopPointer := Temp;end;

Взятие элемента должно сопровождаться освобождением памяти, которую он занимал в куче:

function Pop: TItem;Var Temp: PElement;begin if TopPointer=nil then RunError; Item := TopPointer^.Item; Temp := TopPointer^.Next; Dispose(TopPointer); TopPointer := Temp;end;

Например, последовательность операторов

ClearStack;Push(3); Push(7); Push(2); Push(1);

Преимуществом спискового хранения является то, что нет необходимости резервировать память для максимально возможного числа элементов стека, что требуется при хранении в массиве. На практике же удобным оказывается хранение в массиве, так как при операции «очистить стек» не нужно пробегать весь стек – очистка производится в одно действие.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Лабораторная работа выполняется на ПЭВМ.

1. Для всехвариантов нужно реализовать следующий минимальный набор операций со структурой:

- инициализация;

- уничтожение структуры с освобождением памяти;

- добавление узла в структуру;

- удаление узла из структуры

- выдача текущего состояния структуры на экран.

Тип данных, хранящихся в узлах, выбирается по желанию студента

2. Разработать и отладить программу, проверить ее работу путем введения абстрактных исходных данных.

3. Создать отчет

Контрольные вопросы

· Динамическая память. Методы работы с динамической памятью. Указатели.

· Линейный список – как структура данных.

· Виды линейных списков.

· Стек – как структура данных.

Лабораторная работа №4

СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ

Цель работы:

Ознакомление студента со способом хранения данных в форме деревьев.

Время выполнения 4 часа.

ЗАДАНИЕ

§ Разработать программу, реализующую работу с динамической структурой.

§ Произвести отладку программы путем ввода исходных данных и проверки корректности полученного результата;

§ Сделать отчет.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Рассмотрим еще один способ хранения множества значений – представление множеств с помощью деревьев.

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

У всякой вершины, кроме корня, должен быть единственный отец. Корень отца не имеет.

Двоичным назовем такое дерево, у которого каждая вершина может иметь не более двух сыновей.

Поддеревом назовем вершину со всеми ее потомками.

На первом уровне двоичного дерева может быть только одна вершина – корень, на втором – две (сыновья корня), на третьем – четыре (сыновья сыновей корня). В общем случае на i-м уровне может быть до 2^i-1 вершин. Дерево, содержащее n полностью заполненных уровней, будем называть полным. Полное двоичное дерево содержит =2ⁱ-1 вершин.

Всякое непустое двоичное T-дерево разбивается на 3 части: корень, левое и правое поддеревья. Отсюда можно дать следующее рекурсивное определение двоичного дерева:

1. пустое дерево – двоичное дерево;

2. вершина с левым и правым двоичными поддеревьями – двоичное дерево.

Левое и правое поддеревья могут быть пустыми.

Прямо из рекурсивного определения дерева можно вывести следующее ссылочное представление дерева в программе:

PTree = ^TTree;TTree = record Item: T; {элемент дерева} Left, Right: PTree; {указатели на поддеревья}end;

Где Left, Right равны nil, если соответствующие поддеревья пусты.

Есть еще нессылочный способ хранения деревьев. Пусть мы имеем дело с полным двоичным деревом, состоящим из n уровней. Можно организовать такое хранение дерева в массиве Value: array[1..N] of T, что:

Value[1] – корень дерева;

Value[2*i] – левый сын вершины Value[i];

Value[2*i+1] – правый сын вершины Value[i].

Недостаток такого хранения дерева – большие накладные расходы при изменении структуры дерева (например, если мы меняем местами два поддерева). Этот способ также неэкономен, если мы имеем дело с неполным двоичным деревом (в этом случае мы все равно вынуждены выделять память под все (даже отсутствующие) вершины полного двоичного дерева).

Высотой поддерева будем считать максимальную длину цепи y[1]..y[n] его вершин такую, что y[i+1] – сын y[i] для всех i. Высота пустого дерева равна 0. Высота дерева из одного корня – единице. Высота дерева на рисунке на предыдущей странице равна 3-м.

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

Двоичное T-дерево упорядочено, если для любой вершины X справедливо такое свойство: все элементы, хранимые в левом поддереве, меньше элемента, хранимого в X, а все элементы, хранимые в правом поддереве, больше элемента, хранимого в X.

Важное свойство упорядоченного дерева: все элементы его различны.

В дальнейшем будет идти речь только о двоичных упорядоченных деревьях, опуская слова «двоичный» и «упорядоченный».

Поиск/добавление/удаление в T-деревьях

Алгоритм поиска можно записать, пользуясь рекурсивным определением двоичного дерева в рекурсивном виде. Если искомый элемент Item меньше Tree^.Item, то поиск продолжается в левом поддереве, если равен – то поиск считается успешным, если больше – поиск продолжается в правом поддереве; поиск считается неудачным, если мы дошли до пустого поддерева, а элемент найден не был:

function Exist(Item: T; Tree: PTree): Boolean;begin if Tree=nil then begin Exist := False; Exit end; if Tree^.Item=Item then Exist := True else if Tree^.Item>Item then Exist := Exist(Item, Tree^.Left) else Exist := Exist(Item, Tree^.Right);end;

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

Как писать нерекурсивную программу обработки дерева, мы рассмотрим на примере алгоритма добавления элемента в дерево. Сначала надо найти вершину, к которой в качестве сына мы добавим новую вершину (фактически произвести поиск), а затем присоединить к найденной новую вершину, содержащую добавляемый элемент Item (процедура написана в предположении, что добавляемого элемента в дереве нет):

procedure Add(Item: T; Tree: PTree);Var NewNode: PTree;begin {поиск вершины} while ((Item>Tree^.Item)and(Tree^.Right<>nil))or ((Item<Tree^.Item)and(Tree^.Left<>nil)) do if Item>Tree^.Item then Tree := Tree^.Right else Tree := Tree^.Left; {создание и добавление новой вершины} NewNode := New(PTree); NewNode^.Item := Item; NewNode^.Left := nil; NewNode^.Right := nil; If Item>Tree^.Item then Tree^.Right := NewNode else Tree^.Left := NewNode;end;

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

Надо не забыть, что при замене вершина, на которую мы будем производить замену, может иметь правое поддерево. Это поддерево надо поставить вместо перемещаемой вершины.

procedure Del(Item: T; Tree: PTree);Var Tree2, Father: PTree; Dir: (L, R); {направление движения (влево/вправо)}begin {поиск удаляемого элемента} Father := nil; {отец элемента} while ((Item>Tree^.Item)and(Tree^.Right<>nil))or ((Item<Tree^.Item)and(Tree^.Left<>nil)) do begin Father := Tree; if Item>Tree^.Item then begin Tree := Tree^.Right; Direction := R; end else begin Tree := Tree^.Left; Direction := L; end; end; if (Tree^.Left<>nil)and(Tree^.Right<>nil then begin{требуется замена} Father := Tree; Tree2 := Tree^.Right; While (Tree2^.Left<>nil) do begin Father := Tree2; Tree2 := Tree2^.Left; end; Tree^.Item := Tree2^.Item; Father^.Left := Tree2^.Right; Dispose(Tree2); end else {удаление} if (Tree^.Left=nil) then begin if Father<>nil then if Direction=L then Father^.Left := Tree^.Right; else Father^.Right := Tree^.Right; Dispose(Tree); end else begin if Father<>nil then if Direction=L then Father^.Left := Tree^.Left; else Father^.Right := Tree^.Left; Dispose(Tree); end;end;

Каковы же теоретические сложности этих алгоритмов (то, что они одинаковы, понятно, так как в основе везде поиск)? В лучшем случае – случае полного двоичного дерева – мы получим сложность T_max(log(n)). В худшем случае наше дерево может выродиться в список. Такое может произойти, например, при добавлении элементов в порядке возрастания. При работе со списком в среднем нам придется просмотреть половину списка. Это даст сложность T(n).

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

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Лабораторная работа выполняется на ПЭВМ.

Для получения результата необходимо сделать следующее:

1. Проанализировать исходные данные.

2. Выработать алгоритм решения задачи поиска, добавления или удаления в F-деревьях

3. Разработать и отладить программу.

4. Создать отчет

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что такое дерево, двоичное дерево, поддерево?

2. Чем алгоритм удаления из упорядоченного дерева сложнее алгоритма добавления?

3. Приведите определение идеально сбалансированного дерева и дерева сбалансированного по АВЛ.

4. Что такое вращения и для чего они применяются? Перечислите используемые в этой работе вращения.

5. Что такое коэффициент сбалансированности и почему его следует хранить для каждой вершины дерева?

Лабораторная работа №5