Структуры и алгоритмы обработки данных


Циклические списки


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

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

pic1_3.jpg (9176 bytes)

Рис.1.3. Однонаправленный циклический список

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

В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка.

pic1_4.jpg (10926 bytes)

Рис.1.4. Двунаправленный циклический список

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

 

добавление (справа и слева от текущего);

удаление (справа и слева от текущего);

поиск;

вывод списка.

 

program;

type element = record

               data:string;

               last, next: pointer;

     end;

var

      i,n: integer;

      point: pointer;

      current, pnt, pnt2: ^element;

      s:string;

begin

new(current);

current^.data:=-first-;

current^.next:=current

current^.last:=current;

repeat

        writeln(-1 v сделать текущим-);




Начало  Назад  Вперед



Книжный магазин