Списки Конструкторы и деструкторы Изменение списков Доступ к элементам списка Примеры списков В этом разделе для представления списков введен новый класс List При нашем подходе каждый элемент списка занимает одну позицию - первый элемент в первой позиции, второй элемент - во второй и т. д. Кроме того существует головная позиция, которая одновременно располагается перед первой и после последней позиции. Объект List обеспечивает доступ к его элементам через окно (window), которое в любой данный момент относится к некоторой позиции в списке. Большинство операций со списками выполняется либо с окном, либо с элементом в окне. Например, мы можем вызвать элемент, находящийся в окне, сдвинуть окно на следующую или предыдущую позицию или передвинуть его на первую или последнюю позицию. Мы также можем выполнить операцию удаления из списка элемента, находящегося в окне, или внести новый элемент в список сразу же после окна. На рис. 4 отражен наш подход к организации списка. Рис. 4: Структура списка длиной в семь элементов. Элементы в списке располагаются с 1 по 7 позицию. Головная позиция 0 располагается между первой и последней позициями. Окно, изображенное в виде квадрата, в данный момент находится в положении 2. Для реализации класса List будем использовать связанные списки. Каждый узел соответствует позиции в списке и содержит элемент, сохраняемый в этой позиции (узел, соответствующий головной позиции, называется головной узел). Узел представляется объектом класса ListNode, который получается из класса Node. Класс ListNode обладает компонентом данных _val, который указывает на фактический элемент. Список является коллекцией элементов некоторого заданного типа. Однако нет необходимости встраивать специфический тип элемента в описание класса ListNode или List, поскольку операции над списками действуют совершенно независимо от типа элемента. По этой причине мы определим эти классы как шаблоны класса. Тип элемента задается в виде параметра шаблона класса. Впоследствии, когда нам потребуется список элементов некоторого специфичного типа, мы обратимся к шаблону класса с заданным типом элемента, и тогда шаблон класса будет использован для создания фактического класса с этим типом элемента. Шаблон класса ListNode определяется следующим образом: template class ListNode : public Node { public : Т _val; ListNode (Т val); friend class List; }; Здесь через Т обозначен параметр типа. Для объявления конкретной реализации ListNode вместо параметра Т необходимо подставить название типа. Например, объявление ListNode а, b; Определяет а и b как объекты ListNode, каждый из них содержит указатель_на_целое (pointer_to_int). Конструктор ListNode может быть определен подобно template ListNode::ListNode (Т val) : _val(val) { } Конструктор ListNode неявно инициирует конструктор для базового класса Node, поскольку последний конструктор не имеет аргументов. Мы не определяем здесь деструктора класса ListNode. Как только удаляется объект ListNode, автоматически инициируется деструктор базового класса Node::~Node, объявленный как виртуальный. Заметим, что элемент, указанный элементом данных ListNode::_val не разрушается. Было бы безопасно разрушить элемент только в том случае, если бы было известно, что он создан как новый (new), но нет никакой гарантии такой ситуации. Вернемся к определению шаблона класса List. Класс List содержит три компонента данных: header указывает на головной узел, соответствующий головной позиции; win указывает на узел, который находится в позиции текущего окна; параметр _length содержит длину списка. Шаблон класса определяется следующим образом: template class List { private: ListNode *header; ListNode *win; int _length; public : List (void); ~List (void); Т insert (T); T append (Т); List *append(List *); Т prepend(T); Т remove (void); void val (T); Т val (void); T next (void); T prev(void); T first (void); T last (void); int length (void); bool isFirst (void); bool isLast (void); bool isHead(void); }; Для упрощения нашей реализации будем предполагать, что элементами списка являются указатели на объекты данного типа. Тогда объявление List р; определяет, что р будет списком указателей_на_полигоны (Polygons), тогда как объявление List q; будет ошибочным. Конструкторы и деструкторы Конструктор List создает и инициализирует пустой список, представленный одним головным узлом, со ссылками на самого себя: template List::List(void) : _length(0) { header = new ListNode (NULL); win = header; } Деструктор класса разрушает узлы связанного списка: template List::~List (void) { while (length() > 0) { first(); remove (); } delete header; } Заметим, что деструктор не разрушает сами элементы данных. <<<  Назад Вперед  >>>  1  2  3   8  Комментарии к статье  8 8  Обсудить в чате