Структуры и алгоритмы обработки данных. Ключарев А.А - 30 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

30
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;
Использование двух указателей в линейном двунаправленном спис-
ке позволяет ускорить операции, связанные с передвижением по спис-
ку за счет двунаправленности этого движения. Однако элементы спис-
ка за счет дополнительного поля занимают больший объем памяти. Кроме
того, усложнились операции вставки и удаления элементов за счет не-
обходимости манипулирования большим числом указателей.
1.2.7. Циклические списки
Линейные списки характерны тем, что в них можно выделить пер-
вый и последний элементы (имеющие пустые указатели), причем для
однонаправленного линейного списка обязательно нужно иметь указа-
тель на первый элемент. Это приводило к тому, что алгоритмы вставки
и удаления крайних и средних элементов списка отличались друг от
друга, что, естественно, усложняло соответствующие операции.
Основное отличие циклического списка состоит в том, что в этом
списке нет элементов, содержащих пустые указатели, и, следователь-
но, нельзя выделить крайние элементы. Таким образом, все элементы
являются «средними».
Циклические списки, так же как и линейные, бывают однонаправ-
ленными и двунаправленными.
1.2.7.1. Циклический однонаправленный список
Циклический однонаправленный список похож на линейный одно-
направленный список, но его последний элемент содержит указатель,
связывающий его с первым элементом (рис. 4).
Для полного обхода такого списка достаточно иметь указатель на
произвольный элемент, а не на первый, как в линейном однонаправ-

Страницы