Организация и функционирование компьютеров

begin

next := po; {Первый элемент списка}

prev := @p0; {Сcылка на указатель первого элемента}

while (nextNil) and (order (r, next^.d) >= 0) do begin

prev := @(next.p); {Сcылка на указатель в предыдущем элементе}

next := next.p {Переход к следующему элементу}

end; {Cписок кончился или последняя запись предшествует текущей}

new (curr); {Создание копии элемента списка}

curr^.d := r; {Заполнение элемента}

curr^.p := prev^; {Ссылка последующий элемент списка}

prev^ := curr; {Ссылка в прдыдущем элементе на новый}

end;

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

function exclude_from_list (r: rec): boolean;

var next: plist; prev: ^plist;

begin

exclude_from_list := false;

next := po; {Первый элемент списка}

prev := @p0; {Сcылка на указатель первого элемента}

while (nextNil) and (order (r, next^.d)

if order (r, next^.d) = 0 {Уничтожить элемент списка}

then begin prev^ := next.p; {Ссылка в прдыдущем элементе на последующий}

dispose (next); {Освободить ненужную память}

exclude_from_list := true; {Элемент удален}

break

end

else begin prev := @(next.p); {Сcылка на указатель в предыдущем элементе}

next := next.p {Переход к следующему элементу}

end

end;

Кольцевой список отличается от линейного тем, что в нем указатель в последнем элементе не равен Nil, а указывает на первый элемент, то есть ссылки замыкают список в кольцо. Кольцевой список позволяет производить поиск не только с первого, но и с любого элемента. Процедуры поиска, добавления и уничтожения в кольцевом списке несколько отличаются за счет проверки условия окончания поиска (next p0 вместо next Nil).

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

4.13.4. Использование указателей для обработки деревьев.

Графом называется совокупность объектов, называемых вершинами графа, и связей между ними, которые принято называть дугами графа. Граф, в котором каждая связь имеет направление, называется направленным графом. Принято изображать вершины графа точками на плоскости, а связи между ними – отрезками (направленные связи – стрелками). Путем на графе называется последовательность вершин, соединенных дугами. Для направленного графа направление пути должно совпадать с направлением каждой дуги пути.

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