ЛЕКЦИЯ 4. ОПЕРАЦИИ НАД СВЯЗНЫМИ СПИСКАМИ

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

Основные вопросы: операции для работы со списками

Основные операции: Создание, вставка, удаление, просмотр.

Просмотр (перебор) элементов списка

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

Алгоритм перебора для односвязного списка

{ Перебор 1-связного списка }

Procedure LookSll(head : sllptr);

{ head - указатель на начало списка }

var cur : sllptr; { адрес текущего элемента }

begin

cur:=head; { 1-й элемент списка назначается текущим }

while cur <> nil do begin

< обработка c^.inf >

cur:=cur^.next;

end; end;

В двухсвязном списке возможен перебор как в прямом направлении, так и в обратном.

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

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

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

Рис.5. Вставка элемента в середину 2-связного списка

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

Рис. 6. Вставка элемента в начало 1-связного списка