Реализация связанного списка в виде шаблона класса...366
Приведённый далее шаблон класса LinkedList выглядит практически идентично классу AccountLinkedList из программы BUDGET3, если заменить класс Node обобщённым классом Т.
/* LinkedList — связанный список произвольных объектов */
#ifndef _ACCOUNTLINKEDLIST_
#define _ACCOUNTLINKEDLIST_
/* Предварительное объявление класса LinkedList */
template < class T > class LinkedList;
/* Node — узел связанного списка; каждый */
/* узел указывает на объект Т */
template < class T > class Node
{
public:
Node(LinkedList< T >* pL, T* pT)
{
pList = pL;
pNext = 0;
pObject = pT;
}
Node< T >* next( ) { return pNext; }
Node<T >* next(Node< T >* pN) { pNext = pN;
return pNext; }
T* current( ) { return pObject; }
_________________
366 стр. Часть 6. Великолепная десятка
protected:
LinkedList< T >* pList;
Node< T >* pNext;
T* pObject;
};
/* LinkedList — связанный список объектов Node */
template < class T > class LinkedList
{
public :
LinkedList< T >( ) { pFirst = 0 ; }
Node< T >* firstNode( ) { return pFirst ; }
Node< T >* lastNode( )
{
/* Если список пуст, возвращает 0 */
if ( pFirst == 0 )
{
return 0 ;
}
/* В противном случае ищем последний элемент списка */
Node< T >* pN = pFirst ;
while ( true )
{
Node< T >* pNext = pN -> next( ) ;
if ( pNext == 0 )
{
break ;
}
pN = pNext ;
}
return pN ;
}
void addNode( Node< T >* pNode )
{
Node< T >* pN = lastNode( ) ;
if ( pN == 0 )
{
pFirst = pNode ;
}
else
{
pN -> next( pNode ) ;
}
}
protected :
Node< T >* pFirst ;
} ;
#endif
_________________
367 стр. Глава 31. Программа BUDGET
«Дальнейшее рассмотрение может оказаться проще, если вы мысленно замените обобщённый класс Т действительным классом Account. При этом вы увидите, насколько программа становится похожей на свою предшественницу — программу BUDGET3.»
[Советы]
Выражение template < class Т > class LinkedList представляет собой предварительное объявление шаблона, необходимое для класса Node.
«Не забывайте о том, что шаблоны классов LinkedList и Node не являются реальными классами до тех пор, пока параметр Т не будет заменён действительным классом.»
[Помни!]
Шаблон класса Node сконструирован для работы в качестве узла связанного списка. Каждый узел указывает на объект класса Т, который будет определён позже. Конструктор инициализирует члены-указатели: pList указывает на LinkedList, членом которого является данный объект Node, pObject указывает на объект типа Т, a pNext инициализируется значением 0 , указывающим, что пока узел не является членом списка.
"Активный метод" next ( Node< T >* ) добавляет текущий узел в список путём инициализации указателя pNext. "Пассивный метод" next( ) просто возвращает следующий объект Node< T > в списке. Это обычная практика кодирования, когда функция fn( ) возвращает текущее значение объекта, a fn( Т ) устанавливает его значение на основе аргумента.
Эта версия addNode( ) более усовершенствована по сравнению с представленной в программе BUDGET3, поскольку добавляет узел в конец списка. Преимущество такого подхода в том, что объекты считываются из списка в том же порядке, в котором были в него внесены, а недостаток в том, что метод lastNode( ) должен выполнять проход по всему списку всякий раз, когда требуется внести в список новый объект. Это может существенно замедлить работу программы при большом количестве элементов в списке.