Файл: 6. Разработка контейнера на основе адресного списка.pdf

6. Разработка контейнера на основе адресного списка 

В разделе 4 в качестве примера описания и использования классов был 

представлен  контейнер  на  основе  массива.  Как  известно,  существует  и 

альтернативная  реализация  контейнера,  которая  использует  адресные  связи 

между  элементами  и  механизм  динамического  распределения  памяти. 

Сравнение  и  алгоритмическая  реализация  этих  вариантов  представлена  в 

классических  учебниках  по  Структурам  Данных.  Краткое  введение  в  этот 

материал можно найти в учебном пособии [ 8 ]. 

Динамический  адресный  список  представляет  из  себя  набор  элементов, 

занимающих  свои  отдельные  области  памяти.  Элементы  связываются  в 

логическую последовательность с помощью адресных полей.  

Можно  предложить  два  варианта  объектной  реализации  адресного 

списка.  Более  общий  вариант  предполагает  использование  для  связи 

собираемых в контейнер объектов вспомогательных объектов-посредников. 

Более  простой  вариант  основан  на  включении  служебных  адресных  полей 

непосредственно  в  сами  объекты,  поэтому  он  возможен  только  если 

доступно исходное описание класса хранимых объектов. 

Рассмотрим  первый  вариант,  причем  в  качестве  примера  возьмем 

объектную  реализацию  контейнера  для  хранения  и  обработки  графических 

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

полиморфизма, 

этот 

простейший 

вариант 

контейнера 

будет 

модифицирован  и  получит  способность  хранить  любые  графические 

объекты. 

Схематично  списковый  контейнер  для  объектов-окружностей  можно 

представить следующим образом. 

Каждый  отдельный  элемент  списка  будем  рассматривать  как 

самостоятельный  объект,  отвечающий  за  хранение  адреса  следующего 

элемента  и  адреса  связанной  с  ним  окружности.  Сам  контейнер  как  набор 

элементов-объектов  тоже  является  объектом,  реализующим  основную 

функциональность динамического списка. 

Для  программной  реализации  прежде  всего  необходимо  ввести  два 

класса:  класс  «ЭлементСписка»  и  класс  «СписковыйКонтейнер». 

Неформально структуру этих классов можно описать следующим образом.  

Класс «ЭлементСписка» должен содержать: 

  адрес  следующего  элемента-объекта  (поле  данных  объектного 

типа) 

  адрес окружности (поле данных классового типа  Circle) 

  одно или несколько информационных полей (при необходимости) 

  конструктор(ы)  для  создания  нового  элемента-объекта  с 

необходимыми значениями свойств 

  методы доступа к закрытым адресным данным 

Класс «СписковыйКонтейнер» должен содержать: 

элемент 1 

адрес второго 

элемента 

адрес  

окружности 

адрес первого 

элемента

элемент 2 

адрес третьего 

элемента 

адрес  

окружности 

элемент 3 

адрес следующего 

элемента 

адрес  

окружности 

окружность 1

окружность 2

окружность 3

  адрес первого элемента списка (поле объектного типа) 

  адрес последнего элемента списка (при необходимости) 

  одно или несколько информационных полей (при необходимости) 

  конструктор(ы)  для  создания  контейнера  в  начальном  состоянии 

(чаще всего пустом) 

  методы доступа к информационным полям (при необходимости) 

  методы добавления, удаления, поиска и итеративной обработки 

Формализованное описание класса «ЭлементСписка» : 

TPosrednik  =  class  

private  

   ItemInf : string;   //  или другой необходимый тип 

   Next : TPosrednik;   // свойство-указатель на следующий элемент 

   Circ : TCircle;  // свойство-указатель адресуемой окружности  

public   

   сonstructor  Create (aInf : string;  aNext : TPosrednik;   aCirc : TCircle );  

   function   GetNext : TPosrednik;    // получение адреса след. элемента 

   function  GetCirc : TCircle;    // важно: метод для доступа к окружности! 

   function   GetInf : string;  

   procedure   SetNext (aNext : TPosrednik);   // изменение адреса след. эл-та 

   procedure   SetCirc (aCirc : TCircle);  // для присоединения другой окр-ти 

   procedure   SetInf (aInf : string);  // для изменения информационного поля 

end; 

class   Posrednik  { 

   private   int   ItemInf;   //  или другой необходимый тип 

   private   Posrednik   Next;   // свойство-указатель на следующий элемент 

   private   Circle   Circ;  // свойство-указатель адресуемой окружности  

   public  Posrednik (int  aInf,  Posrednik   aNext,  Circle  aCirc) {…;}  

   public  Posrednik   GetNext( ) {…;}    // получение адреса след. элемента 

   public  Circle   GetCirc( ) {…;}  // важно: метод для доступа к окр-ти! 

   public  int   GetInf ( ) {…;}  

   public  void  SetNext (Posrednik   aNext) {…;}  // изменить адрес след. эл-та 

   public void  SetCirc (Circle  aCirc) {…};  // для присоединения другой окр. 

   public  void   SetInf (int   aInf) {…};  // для изменения информац. поля 

};

Описание  основного  класса  «СписковыйКонтейнер»  (для  упрощения 

изложения добавление нового элемента будем производить в начало списка): 

CircleListContainer = class 

private 

   ContInf : string; 

   First : TPosrednik;  // указатель на первый элемент списка 

public   

   сonstructor   Create (ainf : string);  // создание пустого списка 

   function  GetFirst : TPosrednik;   

  //  здесь должны быть методы доступа к информационному свойству 

   procedure  Add (ainf : string;  aCirc : TCircle);  // добавление объекта 

   function  Delete (ainf : string) : boolean;  // удаление эл-та по его инф. части  

   function  Search (aRad : integer) : TPosrednik;  // поиск эл-та по радиусу окр. 

   procedure  ShowAll;   // итератор для отображения всех окружностей 

   procedure  MoveAll (dx, dy : integer);  // итератор-перемещатель 

 end; 

Программная реализация некоторых методов (обратить внимание на 

использование Get-методов для доступа к закрытым данным объектов-

элементов списка и объектов-окружностей!): 

constructor   CircleListContainer.Create (ainf : string);   

    begin   First := nil;   ContInf := ainf;   

    end; 

procedure   CircleListContainer.Add ( ainf : string;  aCirc : TCircle);  

    begin   // напомним, что добавление — в начало списка! 

          First := TPosrednik.Create (ainf, First, aCirc);  //  красиво и компактно! 

    end;     

procedure  CircleListContainer.ShowAll;  

    var   Temp : TPosrednik;   // вспом. объектная перем. для прохода по списку 

    begin  

Temp := First;     

while (Temp <> nil)  do    

begin 

   Temp.GetCirc.Show;    // доступ к методу объекта-окружности 

   Temp := Temp.GetNext;   //  получение адреса след. элемента 

end; 

    end; 

function  CircleListContainer.Search (aRad : integer) : TPosrednik; 

   var   Temp : TPosrednik; 

   begin 

      result := nil; 

      Temp := First; 

      while (Temp <> nil)  do    

if  (Temp.GetCirc.GetR = aRad)   then 

begin 

   result := Temp; 

   break; 

end    

else  Temp := Temp.GetNext 

   end;