Лабораторная работа 7

ДВУНАПРАВЛЕННЫЙ НЕОДНОРОДНЫЙ СПИСОК

С ОДНОРОДНЫМИ ПОДСПИСКАМИ

Введение

Список является структурой хранения данных. Если список – динамическая структура данных, то в простейшем случае – это линейный связный список, состоящий из элементов (узлов), каждый из которых содержит как собственные данные, так и одну (или две) ссылки на следующий (и предыдущий) узел. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, количество элементов не нужно задавать заранее, порядок обхода списка всегда явно задается его внутренними связями.

Существует несколько разновидностей связного списка. Однонаправленный список – каждый элемент содержит данные и указатель на следующий элемент. В кольцевом списке последний элемент содержит указатель на первый элемент. Двунаправленный связный список – в этом списке каждый элемент содержит указатели как на следующий, так и на предыдущий элементы. В таком списке, в отличие от однонаправленного списка, можно перемещаться в двух направлениях. В однородном списке все элементы имеют один и тот же тип. Неоднородный (гетерогенный) список имеет разнотипные элементы, причем однотипные элементы в нем объединяют в однородные подсписки.

Целью данной лабораторной работе является изучение приложения для работы с двунаправленным неоднородным списком с однородными подсписками, представленным на рис.7.1. Из структуры списка видно, что основной список состоит из взаимосвязанных первых элементов подсписков. Ссылка на начало списка находится в указателе first, а ссылка на конец списка – в указателеlast.

Классы

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

class link

{

public:

link* prev; // указатель на предыдущий элемент основного списка

link* next; // указатель на следующий элемент основного списка

link* down; // указатель на следующий элемент подсписка

types type;

link(){prev=next=down=0;}//конструктор с умолчанием

};

Рис.7.1 – структура двунаправленного неоднородного списка

с n однородными подсписками

Примем также, что список предназначен для контроля товаров в спортивном магазине, группируемых в подсписки по наименованию и фирме-производителю. Пусть товарами будут «велосипеды» и «роликовые коньки». Тогда в списке они должны быть представлены элементами подсписков - объектами соответствующих классов. Эти классы будут производными классами от базового класса. Для определения объекта производного класса в базовый класс введен элементtype типа-перечисление: enum types{Roll, Bike}.

//---------------------------------------------------------------------------

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

class TRoll:public link

{

public:

char* date; //дата поступления

char* comp; //производитель

int diam; //диаметр колес (в мм)

int count; //количество (штук)

TRoll(); //конструктор

~TRoll(); //деструктор

};

//--------------------------------------------------------------------------

//производный класс для элемента подсписка - велосипед

class TBike:public link

{

public:

char* date; //дата поступления

char* comp; //производитель

int diam; //диаметр колес (в мм)

int count; //количество (штук)

float weight; //вес (в кг)

int speeds; //количество скоростей

TBike(); //конструктор

~TBike(); //деструктор

};

//--------------------------------------------------------------------------

При создании объектов классов TRoll иTBike – элементов подсписков – в конструкторах этих классов в данное-элемент базового классаtypeподставляется значение (Roll, Bike), позволяющее идентифицировать создаваемые объекты. Доступ кtype– через указатель на базовый классlink.

Теперь создадим класс, объединяющий созданные выше классы для элементов подсписков и предназначенный для создания объекта «список».

//--------------------------------------------------------------------------

//класс для списка

class list

{

public:

link* first; //указатель на начало списка

link* last; //указатель на конец списка

int count_dsp; //количество подсписков

int count_elem_sp; //количество элементов в списке

bool is_empty; //флаг "список пуст"

list(); //конструктор

~list(); //деструктор

void append_bike(TBike*);//добавление элемента-велосипеда в список

void append_roll(TRoll*);//добавление элемента-роликовые коньки

// в список

void del(int); //удаление элемента из списка

void out_list(); //вывод списка в таблицу

void clear_down(int); //удаление подсписка из списка

void clear(); //уничтожение списка

};

//--------------------------------------------------------------------------

Комментарии в объявлении последнего класса содержат перечень большинства операций при работе со списком. Следует отметить, что все элементы списка имеют по три указателя (prev,next,down), но только в элементах основной части списка, т.е. в первых элементах подсписков, используются все три указателя, а в остальных элементах подсписков – один указатель (down). При удалении первого элемента подсписка на его место ставится второй, что потребует в нем инициализации указателейprevиnextадресами предыдущего и последующего элементов соответственно в основной части списка.