dlinktpl.h

《C++程序设计习题及解答》配套代码VC版

#ifndef _DLINKTPL_H_
#define _DLINKTPL_H_

// dlinktpl.h
#include <iostream.h>

// --------------------------------------------------------------------------
template< class T >
class Node 
{
public:
	Node( T& rt ) : data(rt), pNext(NULL), pPrev(NULL) {}
	Node* pNext;
	Node* pPrev;
	T& data;
};

// --------------------------------------------------------------------------
template< class T >
class DLink
{
public:
	DLink();
	~DLink();

public:
	void Add( T& );
	void Remove( T& );
	
public:
	void PrintFList();
	void PrintLList();

private:
	Node<T>* pFirst;
	Node<T>* pLast;
};

// --------------------------------------------------------------------------
template< class T >
DLink< T >::DLink()
{
	pFirst = pLast = NULL;
}

// --------------------------------------------------------------------------
template< class T >
void DLink< T >::Add( T& t )
{
	// 增加到尾部
	Node<T>* temp = new Node<T>(t);
	temp->pPrev = pLast;
	if ( pLast )
		pLast->pNext = temp;
	temp->pNext = 0;

	pLast = temp;
	if ( pFirst == NULL )
		pFirst = temp;
}

// --------------------------------------------------------------------------
template< class T >
void DLink< T >::Remove( T& t )
{
	Node<T>* n = NULL;
	for ( Node<T>* pF = pFirst; pF; pF = pF->pNext )
	{
		if ( pF->data == t )
		{
			n = pF;
			break;
		}
	}

	if ( n == NULL )
		return;

	Node<T>* pPrevS = n->pPrev;
	Node<T>* pNextS = n->pNext;

	if ( pPrevS )
		pPrevS->pNext = pNextS;
	else
		pFirst = pNextS; // 删除首元素

	if ( pNextS )
		pNextS->pPrev = pPrevS;
	else
		pLast = pPrevS; // 删除尾元素

	delete n;
}

// --------------------------------------------------------------------------
template< class T >
DLink< T >::~DLink()
{
	if ( pFirst == NULL )
		return;

	Node< T >* pN = pFirst;
	Node< T >* pF;
	
	do
	{
		pF = pN;
		pN = pF->pNext;
		delete pF;
	}while ( pN );
}

// --------------------------------------------------------------------------
template< class T >
void DLink< T >::PrintFList()
{
	for ( Node< T >* pF = pFirst; pF; pF = pF->pNext )
		cout << pF->data << "\t";
	cout << endl << endl;
}

// --------------------------------------------------------------------------
template< class T >
void DLink< T >::PrintLList()
{
	for ( Node< T >* pF = pLast; pF; pF = pF->pPrev )
		cout << pF->data << "\t";
	cout << endl << endl;
}

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

#endif // _DLINKTPL_H_