Удаление текущего элемента из списка
begin
pnt:=current^.last;
pnt^.next:=current^next;
pnt2:=current^.next;
if not(pnt2=nil) then
pnt2^.last:=current^.last;
dispose(current);
end;
Список.Удаление элемента справа от текущего.
begin
pnt:=current^.next;
current^.next:=pnt^next;
pnt2:=pnt^.next;
if not(pnt2=nil) then
pnt2^.last:=current;
dispose(pnt);
end;
Список.Удаление элемента сслева от текущего.
begin
pnt:=current^.last;
current^.last:=pnt^.last;
pnt2:=pnt^.last;
if not(pnt2=nil) then
pnt2^.next:=current;
dispose(pnt);
end;
Стек. Операции над стеком.
– это структура данных, организованная по принципу LIFO (Last-In, First-Out) «первый вошел – последний вышел». Образно это можно представить как запаянную с одной стороны трубку, в которую закатываются шарики: Элементы в стек можно добавлять или извлекать только через его вершину
Здесь P – указатель на вершину стека. Самый первый элемент стека не имеет
впереди себя других элементов, поэтому в указатель Ps1 записывается пустой указатель – Nil.
Операции над стеками
начальное формирование стека (запись первой компоненты);
добавление компоненты в стек;
выборка компоненты (удаление).
Для работы со стеком используются 2 переменные: указатель на вершину и вспомогательный указатель
Var top, p: pnode;
Стек. Начальное формирование стека
New (top); {1}
Top^.d:=100; top^.s:=‘вася’; top^.p:=nil; {2}
{1} –выделение место в памяти и адрес его начала заносится в указатель на вершину стека,
{2}- заполняются все поля элемента стека
Стек.Добавление элемента в стек
New(p); //создаем элемент и заполняем его
P^.d:=10; p^.s:=‘петя’;// информационную часть
P^.p:=top;//связываем его с предыдущим элементом
Top:=p; //обновить указатель на вершину стека
Стек. Извлечение элемента из стека.
With top^ do writeln(d,s); {1}
P:=top; top:=top^.p; {2}
Dispose(p); {3}
{1}-получение информационной части элемента
{2}-перенос указателя на вершину стека на следующий элемент
{3}-освобождение памяти из-под элемента
Очереди. Операции над очередью.
– это структура данных, работающая по принципу: первый вошел, первый вышел. Образно такую структуру можно представить в виде открытой с двух сторон трубку – c одной стороны мы можем закатывать шарики, а из другого конца их извлекать:
Для работы с очередью используются указатели на ее начало и конец, а также вспомогательный указатель:
Var beg, fin, p: pnode;
Тип указателей должен соответствовать типу элементов, из которых состоит очередь.
Операции над очередями:
Начальное формирование очереди;
Добавление элемента в конец очереди;
Выборка элемента из начало очереди.
Очередь. Начальное формирование очереди
-это создание ее первого элемента и установка на него обоих указателей:
New (beg);
beg^.d:=100; beg^.s:=‘вася’; beg^.p:=nil;
fin:=beg;
Очередь. Извлечения элемента из очереди
D:=beg^.d; s:=beg^.s; {1}
P:=beg; beg:=beg^.p; {2}
Dispose (p); {3}
If beg=nil then fin:=nil; {4}
{1}-выборка элемента из начала очереди
{2}- указатель на начало очереди сдвигается на следующий элемент
{3} выбранный элемент удаляется
Очередь. Добавление элемента в очереди
New(p); {1}
P^.d:=10; p^.s:=‘петя’; p^.p:=nil; {2}
fin^.p:=p; {3}
fin:=p; {4}
{1,2}- создает новый элемент и заполняет его информацией
{3}-добавляет в последний элемент очереди ссылку на новый элемент
{4}- устанавливает новое значение указателя на конец очереди
Деревья. Степень и глубина деревьев.
Дерево – это иерархическая информационная структура, состоящая из
узлов, в каждом из которых может быть несколько указателей на дочерние узлы
следующего по иерархии уровня.
Прародитель всех узлов называется корнем дерева. Узлы, не имеющие
дочерних узлов, называются листьями. Промежуточные узлы называются
ветвями. Степень дерева – максимальный порядок его узлов. Глубина дерева –
это максимальная глубина его узлов.
Для работы, например, с двоичным деревом можно определить
следующие типы:
Type Tpz=^Tz; // Указатель на запись
Tz=Record // Запись узла дерева
Inf:string; // Информационная часть узла дерева
Kl:integer; // Уникальный ключ узла дерева
P1,P2:Tpz; // Указатели на дочерние узлы дерева
End;
Для работы с деревьями в основном используют рекурсивные процедуры
– процедуры, которые вызывают сами себя. Они позволяют проходить по всему
дереву только по одному вызову таких процедур.
Сложные структуры данных в Windows обычно представляются двумя способами: в виде только что рассмотренного списка и в виде дерева. Так, например, отображается структура каталогов в Проводнике: слева иерархическая структура диска в виде раскрывающихся значков с обозначениями «-» (развернут) и «+» (свернут), а справа — содержимое выбранного каталога в виде списка. Для создания подобных деревьев, отображающих иерархические структуры дан¬ных, в системе Delphi 7 реализован компонент TTreeView. Процесс создания дерева достаточно прост. Его начальную структуру можно сформи-ровать в редакторе, аналогичном редактору компонента TListView, только уровень вложенности элементов в таком списке не ограничен. У компонента TListView под-держивался только один уровень вложенности по схеме «объект — набор свойств». Каждому узлу дерева может соответствовать своя картинка. Ее номер указывается в поле редактора Image Index (Номер картинки), а сам список картинок задается в свойстве Images. Дополнительно, для каждого узла можно указать номер картинки, отражающей его выделенное состояние (свойство Selected Index), и номер картинки, отражающей его дополнительное состояние (свойство State Index). Имена узлов можно редактировать, как обычные названия объектов Windows. Многие свойства дерева совпадают со свойствами объекта TListView, но есть и небольшие отличия, вызванные необходимостью отображать неограниченные иерархии объектов и только одним режимом работы.
Полное дерево (complete tree) содержит максимально возможное число узлов на каждом уровне, за исключением того, что на нижнем уровне некоторые узлы могут не иметь потомков. Все узлы на нижнем уровне сдвигаются влево. Например, каждый уровень троичного дерева кроме листьев включает в себя три дочерних узла, и, возможно, один узел на уровень выше листьев.
Полные деревья обладают рядом важных свойств. Во-первых, это самые короткие деревья, которые могут содержать заданное количество узлов. Двоичное дерево - одно из самых коротких двоичных деревьев с шестью узлами. Существуют другие двоичные деревья глубины 3 с шестью узлами, но нет ни одного дерева глубиной, меньшей 3. Во-вторых, если полное дерево степени D содержит N узлов, оно будет иметь глубину O(logn(N)) и O(N) листов. Эти факты очень важны, потому что многие алгоритмы исследуют деревья с вершины до самого низа или наоборот. Алгоритм,который выполняет подобное действие один раз, имеет сложность O(log(N)). Особенно полезное свойство полных деревьев заключается в том, что их можно хранить в очень компактной форме в массивах. Если вы пронумеруете узлы в «естественном» порядке, сверху вниз и слева направо, то допускается разместить элементы дерева в массиве в этой же оередности.