Разнородные связанные списки

Как и в разнородных массивах, каждый объект в разнородном списке образован от общего для всех базового класса. Каждая базовая составляющая объекта содержит указатель на следующий объект в списке. Благодаря полиморфизму указатель используется для выполнения методов производного объекта, невзирая на его тип.

Проиллюстрируем эти понятия на связанном списке геометрических объектов, образованных от варианта класса Shape.

Сертификация класса NodeShape

объявление

#include “graphlib.h”

class NodeShape

{

protected:

//координаты базовой точки, образец заполнения

//и указатель на следующий узел

float x, y;

int fillpat;

NodeShape *next;

public:

//конструктор

NodeShape (float h=0, float v=0, int fill=0);

//виртуальная функция рисования

virtual void Draw (void) const;

//методы обработки списков

void InsertAfter (NodeShape *p);

NodeShape *DeleteAfter (void);

NodeShape *Nexn (void);

};

описание

Координаты (x,y) задают базовую точку для производного объекта, который должен быть нарисован и заштрихован по образцу fillpat. Метод Draw инициализирует образец заполнения и графической системе и указатель next, указывающий на следующий объект типа NodeShape в связанном списке. Методы InsertAfter и DeleteAfter поддерживают кольцевой список посредством включения или удаления узла, следующего за текущим. Метод Next возвращает указатель на следующий узел.

Класс NodeShape находится в файле shapelst.h

Реализация класса NodeShape

Реализация класса NodeShape сделана по образцу класса CNode. Так как предполагается кольцевой список, конструктор должен создать начальный узел, который указывает на самого себя.

//конструктор. задаёт начальное значение базовой точки,

//образца заполнения и указателя next

NodeShape::NodeShape (float h, float v, int fill):

x (h), y (v), fillpat (fill)

{

next = this;

}

Образование связанных геометрических классов.Геометрические классы CircleFigure и RectangleFigure являются производными от класса NodeShape. В дополнение к методам базового класса они содержат метод Draw, перекрывающий виртуальный метод Draw базового класса. Методы Area и Perimeter не включаются. Мы используем класс CircleFigure для иллюстрации понятий.

//класс CircleFigure, образованный от класса NodeShape

class CircleFigure: public NodeShape

{

protected:

//радиус окружности

float radius;

public:

//конструктор

CircleFigure (float h, float v, float r, int fill);

//виртуальная функция рисования окружности

virtual void Draw (void) const;

};

//конструктор. инициализирует базовый класс и радиус

CircleFigure:: CircleFigure (float h, float v, float r, int fill):

NodeShape (h, v, fill), radius (r)

{}

//задать образец заполнения посредством вызова базового

//метода Draw и нарисовать окружность

void CircleFigure::Draw (void) const

{

NodeShape::Draw();

DrawCircle (x, y, radius);

}

Мы также включили в файл shapelst.h новый геометрический класс RightTriangle, который описывает прямоугольный треугольник с помощью координат самой левой точки его гипотенузы, базы и высоты.

y

(x, y) высота

x база

Чтобы сформировать связанный список, объявим заголовок, имеющий тип NodeShape и имя listHeader. Начиная с этого заголовка, будем динамически создавать узлы и с помощью InsertAfter включать их в список последовательно друг за другом. Например, следующая итерация создаёт четырёхэлементный список, в котором чередуются объекты-окружности и объекты-треугольники:

listHeader

//заголовок списка и указатель для создания нового списка

NodeShape listHeader, *p;

float x, y, radius, height;

//установить р на начала списка

p = &listHeader;

//включить 4 узла в список

for (int i=0; i<4; i++)

{

//координаты базовой точки

cout << “Введите x и y:”;

cin >> x >> y;

if (i % 2 == 0) //если 1 чётное, добавить окружность

{

cout << “Введите радиус окружности: ”;

cin >> radius;

//включить объект с заполнением в i список

p -> InsertAfter (new Circle (x, y, radius, i));

}

else //если i нечётное, добавить прямоугольный треугольник

{

cout << “Введите базу и высоту для прямоугольного

треугольника: ”;

cin >> base >> height;

p -> InsertAfter (new RightTriangle (x, y, radius, i));

}

//передвинуть р на только что созданный узел

p = p -> Next();

}

Динамическое связывание имеет принципиальное значение во время прохождения списка и визуального отображения содержащихся в нём объектов. В приведённом ниже фрагменте кода указатель р указывает либо на объект типа Circle, либо на объект типа RightTriangle. Поскольку Draw является виртуальной функцией, выполняется метод Draw того или иного производного класса.

p = listHeader.Next();

while (p != &listHeader)

{

p -> Draw();

p = p->Next();

}

Теперь мы готовы поставить задачу создания и управления разнородными списками целиком.