ОДНОСВЯЗНАЯ РЕАЛИЗАЦИЯ ЦИКЛИЧЕСКОГО СПИСКА

Реализация циклического списка с помощью динамических переменных приведена на рис. 2.5.

Head

Реализация циклического списка с помощью динамических

Рис. 2.5. Реализация циклического списка с помощью динамических

переменных

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

Класс tCircleList может быть описан следующим образом:

type

tValue= Real; pltem= Atltem; tltem= record Value: tValue; Next: pltem; end; //record tltem tCircleList=class protected fHead: pltem; fSize: Word; public

// тип значения элемента списка - вещественный // тип указателя на элемент списка // тип элемента списка // содержательная часть элемента списка //указатель на следующий элемент списка

// класс - циклический список

// поле - указатель на текущий элемент списка // поле - число элементов списка

// Свойство - число элементов списка // (доступ по чтению и записи) property Size: Word read fSize write fSize;

// Свойство - указатель на начало списка // (доступ по чтению и записи)

property Head: pltem read fHead write fHead;

// Включение эл-та со значением v после элемента с адресом Addr procedure lnsertAfter(Addr: pltem; v: tValue);

// Включение эл-та со значением v перед эл-том с адресом Addr procedure lnsertBefore(Addr: pltem; v: tValue);

// Исключение элемента, следующего за эл-том с адресом Addr function DeleteAfter(Addr: pltem): tValue;

// Исключение элемента с указателем Addr function Delete(Addr: pltem): tValue;

// Включение элемента со значением v в начало списка procedure lnsertHead(v: tValue);

// Включение элемента со значением v в конец списка procedure lnsertRear(v: tValue);

// Исключение элемента из начала списка function DeleteHead:tValue;

// Исключение элемента из конца списка function DeleteRear:tValue;

// Сцепление со списком CList2 procedure Concat(var CList2: tCircleList);

// Поиск элемента со значением v и возвращение его адреса function Search(v: tValue): pltem;

function Empty: Boolean; //возвращение true, если список пуст procedure Clear; //очистка списка

constructor Create; //конструктор - создание списка

destructor Destroy; override; //деструктор - удаление списка end; //class tCircleList

Класс tCircleList не объявлен наследником класса tList поскольку реализация практически всех его методов отличается от реализации одноименных методов для нециклического списка. Отличия, в основном, заключаются в следующем:

  • • для операций Insert After и Insert Before по-другому осуществляются включение элемента в пустой список, в начало и конец циклического списка;
  • • применение операции DeleteAfter для циклического списка, состоящего из одного элемента, не должно приводить к исключению самого этого элемента;
  • • методы DeleteAfter и Delete должны восстанавливать указатель на последний элемент циклического списка, если он исключается при выполнении этих операций;
  • • в методах Search и Clear признаком завершения просмотра циклического списка является достижение вспомогательным указателем того элемента, с которого начался просмотр.

И только конструктор Create и деструктор Destroy реализуются так же как и одноименные методы класса tList.

Операции включения и исключения справа и слева от текущего элемента (InsertHead, InsertRear, DeleteHead, DeleteRear) выполняют те же действия, что и одноименные операции для нециклического списка. Отличие заключается в том, что новые операции изменяют значение указателя на последний элемент циклического списка, если список расширился влево или вправо либо сузился слева или справа.

 
< Пред   СОДЕРЖАНИЕ     След >