datastructs.h

斯坦福Energy211/CME211课《c++编程——地球科学科学家和工程师》的课件

#ifndef INCLUDE_DATASTRUCTS
#define INCLUDE_DATASTRUCTS

#include <iostream>
#include <stdexcept>

// Declare these classes in advance so that they
// can be declared as friends by node classes
template<typename T> class Queue;
template<typename T> class DQueue;

// Node for singly-linked list
template<typename T> class SingleNode {
	friend class Queue<T>;
	friend class Queue<T>::Iterator;
	
	// Make everything private so that only friend
	// classes can use this class
private:
	SingleNode( const T& data )
	{
		m_Data = data;
		m_pNext = NULL;
	}
	~SingleNode()
	{
		// This makes it possible to delete all
		// nodes in a list by deleting the head
		delete m_pNext;
	}
	
	SingleNode<T> *GetNext() { return m_pNext; }
	void SetNext( SingleNode<T> *pNode ) { m_pNext = pNode; }
	
	T& GetData() { return m_Data; }
	void SetData( const T& data ) { m_Data = data; }
	
	T m_Data;
	SingleNode<T> *m_pNext;
} ;

// Node for doubly-linked list
template<typename T> class DoubleNode {
	friend class DQueue<T>;
	friend class DQueue<T>::Iterator;
	friend class DQueue<T>::ReverseIterator;
	
private:
	DoubleNode( const T& data )
	{
		m_Data = data;
		m_pNext = NULL;
		m_pPrev = NULL;
	}
	~DoubleNode()
	{
		delete m_pNext;
	}
	
	DoubleNode<T> *GetNext() { return m_pNext; }
	DoubleNode<T> *GetPrev() { return m_pPrev; }
	void SetNext( DoubleNode<T> *pNode ) { m_pNext = pNode; }
	void SetPrev( DoubleNode<T> *pNode ) { m_pPrev = pNode; }
	
	T& GetData() { return m_Data; }
	void SetData( const T& data ) { m_Data = data; }

	T m_Data;
	DoubleNode<T> *m_pNext;
	DoubleNode<T> *m_pPrev;
} ;

// Class for implementing a singly-linked list
template<typename T> class Queue {
public:
	Queue()
	{
		m_pHead = NULL;
		m_pTail = NULL;
	}
	~Queue()
	{
		delete m_pHead;
	}	
	
	// Add element to the back of the list
	void EnQueue( const T& item )
	{
		SingleNode<T> *pNewTail = new SingleNode<T>( item );
		if ( m_pTail != NULL )
			m_pTail->SetNext( pNewTail );
		else
			m_pHead = pNewTail;
		m_pTail = pNewTail;
	}
	// Remove element from the front of the list
	T DeQueue()
	{
		if ( m_pHead == NULL )
			throw std::runtime_error( "queue empty" );
		SingleNode<T> *pOldHead = m_pHead;
		m_pHead = m_pHead->GetNext();
		T data = pOldHead->GetData();
		pOldHead->SetNext( NULL );
		delete pOldHead;
		return data;
	}

	// Class for iterating through the list
	class Iterator {
	public:
		Iterator( SingleNode<T> *pData = NULL )
		{
			m_pData = pData;
		}
		Iterator( const Iterator& i )
		{
			m_pData = i.m_pData;
		}
		~Iterator()
		{
		}
		
		Iterator& operator=( const Iterator& i )
		{
			m_pData = i.m_pData;
			return *this;
		}
		// Overload ++ for moving through the list
		// from front to back
		// Prefix form: for implementing ++i
		Iterator& operator++() 
		{ 
			m_pData = m_pData->GetNext();
			return *this; 
		}
		// Postfix form: for implementing i++
		Iterator operator++( int ) 
		{ 
			Iterator result( *this );
			++*this;
			return result;
		}
		// Dereferencing extracts underlying data
		// Non-const reference
		T& operator*()
		{
			return m_pData->GetData();
		}
		// const reference
		const T& operator*() const
		{
			return m_pData->GetData();
		}

		// Comparison operators for use in checking
		// whether iteration should end
		bool operator!=( const Iterator& i ) const
		{
			return m_pData != i.m_pData;
		}
		bool operator==( const Iterator& i ) const
		{
			return m_pData == i.m_pData;
		}
		
	private:
		SingleNode<T> *m_pData;
	} ;

	// These iterators are used to help iterate
	// through the entire list
	Iterator Begin() const 
	{
		Iterator i( m_pHead );
		return i;
	}
	Iterator End() const
	{
		Iterator i( NULL );
		return i;
	}
	
private:
	SingleNode<T> *m_pHead;
	SingleNode<T> *m_pTail;
} ;

// Class for implementing a doubly-linked list
template<typename T> class DQueue {
public:
	DQueue()
	{
		m_pHead = NULL;
		m_pTail = NULL;
	}
	~DQueue()
	{
		delete m_pHead;
	}
	
	// For adding to the back of the list
	void PushBack( const T& item )
	{
		DoubleNode<T> *pNewTail = new DoubleNode<T>( item );
		if ( m_pTail != NULL )
			m_pTail->SetNext( pNewTail );
		else
			m_pHead = pNewTail;
		pNewTail->SetPrev( m_pTail );
		m_pTail = pNewTail;
	}
	// For adding to the front
	void PushFront( const T& item )
	{
		DoubleNode<T> *pNewHead = new DoubleNode<T>( item );
		if ( m_pHead != NULL )
			m_pHead->SetPrev( pNewHead );
		else
			m_pTail = pNewHead;
		pNewHead->SetNext( m_pHead );
		m_pHead = pNewHead;
	}
	// For removing from the back
	T PopBack()
	{
		if ( m_pTail == NULL )
			throw std::runtime_error( "queue empty" );
		DoubleNode<T> *pOldTail = m_pTail;
		m_pTail = m_pTail->GetPrev();
		if ( m_pTail != NULL )
			m_pTail->SetNext( NULL );
		T data = pOldTail->GetData();
		pOldTail->SetNext( NULL );
		delete pOldTail;
		return data;
	}
	// For removing from the front
	T PopFront()
	{
		if ( m_pHead == NULL )
			throw std::runtime_error( "queue empty" );
		DoubleNode<T> *pOldHead = m_pHead;
		m_pHead = m_pHead->GetNext();
		if ( m_pHead != NULL )
			m_pHead->SetPrev( NULL );
		T data = pOldHead->GetData();
		pOldHead->SetNext( NULL );
		delete pOldHead;
		return data;
	}
	
	// For iterating through the list from front to back
	class Iterator {
	public:
		Iterator( DoubleNode<T> *pData = NULL )
		{
			m_pData = pData;
		}
		Iterator( const Iterator& i )
		{
			m_pData = i.m_pData;
		}
		~Iterator()
		{
		}
		
		Iterator& operator=( const Iterator& i )
		{
			m_pData = i.m_pData;
			return *this;
		}
		Iterator& operator++() 
		{ 
			m_pData = m_pData->GetNext();
			return *this; 
		}
		Iterator operator++( int ) 
		{ 
			Iterator result( *this );
			++*this;
			return result;
		}
		Iterator& operator--() 
		{ 
			m_pData = m_pData->GetPrev();
			return *this; 
		}
		Iterator operator--( int ) 
		{ 
			Iterator result( *this );
			--*this;
			return result;
		}
		T& operator*()
		{
			return m_pData->GetData();
		}
		const T& operator*() const
		{
			return m_pData->GetData();
		}
		
		bool operator!=( const Iterator& i ) const
		{
			return m_pData != i.m_pData;
		}
		bool operator==( const Iterator& i ) const
		{
			return m_pData == i.m_pData;
		}

	private:
		DoubleNode<T> *m_pData;
	} ;
	
	// For iterating through the class from back to front
	class ReverseIterator {
	public:
		ReverseIterator( DoubleNode<T> *pData = NULL )
		{
			m_pData = pData;
		}
		ReverseIterator( const ReverseIterator& i )
		{
			m_pData = i.m_pData;
		}
		~ReverseIterator()
		{
		}
		
		ReverseIterator& operator=( const ReverseIterator& i )
		{
			m_pData = i.m_pData;
			return *this;
		}
		// Note that ++ goes from back to front!
		ReverseIterator& operator++() 
		{ 
			m_pData = m_pData->GetPrev();
			return *this; 
		}
		ReverseIterator operator++( int ) 
		{ 
			ReverseIterator result( *this );
			++*this;
			return result;
		}
		ReverseIterator& operator--() 
		{ 
			m_pData = m_pData->GetNext();
			return *this; 
		}
		ReverseIterator operator--( int ) 
		{ 
			ReverseIterator result( *this );
			--*this;
			return result;
		}
		T& operator*()
		{
			return m_pData->GetData();
		}
		const T& operator*() const
		{
			return m_pData->GetData();
		}
		
		bool operator!=( const ReverseIterator& i ) const
		{
			return m_pData != i.m_pData;
		}
		bool operator==( const ReverseIterator& i ) const
		{
			return m_pData == i.m_pData;
		}
		
	private:
		DoubleNode<T> *m_pData;
	} ;
	
	Iterator Begin() const 
	{
		Iterator i( m_pHead );
		return i;
	}
	Iterator End() const
	{
		Iterator i( NULL );
		return i;
	}

	// Need these to support iterating from back to front
	ReverseIterator RBegin() const 
	{
		ReverseIterator i( m_pTail );
		return i;
	}
	ReverseIterator REnd() const
	{
		ReverseIterator i( NULL );
		return i;
	}
	
private:
	DoubleNode<T> *m_pHead;
	DoubleNode<T> *m_pTail;
} ;

#endif // INCLUDE_DATASTRUCTS