sinlist.hpp

该源码实现二叉树的模拟

//////////////////////////////////////////////////////////////////////////
// CSinList.h
// Author : sc
// Date : 2008/10/20

#ifndef _SinList_H_
#define _SinList_H_

#include "ListNode.hpp"

template <class T>
class CSinList
{
	public:
		CSinList();
		~CSinList();

		int GetCount(void) const;							//


		T GetTail(void) const;								//
		T GetAt(int nIndex) const;							//
		T GetHead(void) const;								//

		T PopHead(void);									//
		T PopTail(void);									//

		T PushHead(T& srcData);								//
		T PushTail(T& srcData);								//

		T InsertAt(T& srcData, int nIndex);					//
		int Find(T& srcData, int nStartPos = 0, int nIncSize = 1) const;

		void RemoveAll(void);

	protected:
		CListNode<T>* MovePtrTo(int nIndex) const;			//


	private:
		CListNode<T>*	m_Head;
		CListNode<T>*	m_Tail;
		int				m_NodeCount;
		
};

template <class T>
CSinList<T>::CSinList()
{
	m_Tail = NULL;
	m_Head = NULL;

	m_NodeCount = 0;
}

template <class T>
CSinList<T>::~CSinList()
{
	RemoveAll();
}

template <class T>
int CSinList<T>::GetCount(void) const
{
	return m_NodeCount;
}


template <class T>
T CSinList<T>::PushHead(T& srcData)
{
	if(m_NodeCount == 0)
	{
		m_Head = new CListNode<T>(srcData);
		m_Tail = m_Head;
		m_NodeCount++;
	}
	else
	{
		CListNode<T>* pTmpNode = new CListNode<T>(srcData);
		pTmpNode->m_Next = m_Head;
		m_Head = pTmpNode;
		m_NodeCount ++;
	}
	return m_Head->m_Data;
}

template <class T>
T CSinList<T>::PushTail(T& srcData)
{
	if(m_NodeCount == 0)
	{
		m_Head = new CListNode<T>(srcData);
		m_Tail = m_Head;
		m_NodeCount++;

		return m_Tail->m_Data;
	}

	else
	{
		m_Tail->m_Next = new CListNode<T>(srcData);
		m_Tail = m_Tail->m_Next;

		m_NodeCount ++;
		return m_Tail->m_Data;
	}
}


template <class T>
T CSinList<T>::GetHead() const
{
	if(m_NodeCount == 0)
		throw "Invalide argument";
	return m_Head->m_Data;
}

template <class T>
T CSinList<T>::GetTail() const
{
	if(m_NodeCount == 0)
		throw "Invalide argument";
	return m_Tail->m_Data;
}

//////////////////////////////////////////////////////////////////////////
// GetAt(int nIndex)
template <class T>
T CSinList<T>::GetAt(int nIndex) const
{
	if(nIndex < 0 || nIndex > m_NodeCount)
		throw "Invalide argument";
	CListNode<T>* pTmpNode;
	pTmpNode = m_Head;

	for(int i = 0; i < nIndex; i++)
	{
		pTmpNode = pTmpNode->m_Next;		
	}
	return pTmpNode->m_Data;
}

//////////////////////////////////////////////////////////////////////////
// RemoveAll(void)

template <class T>
void CSinList<T>::RemoveAll(void)
{
	CListNode<T>* pTmpNode = m_Head;
	CListNode<T>* pIterative = NULL;

	
	for(int nCirTmp = 0; nCirTmp < m_NodeCount; nCirTmp++)
	{
		pIterative = pTmpNode;
		pTmpNode = pTmpNode->m_Next;		
		
		delete pIterative;
	}
	m_Head = NULL;
	m_Tail = NULL;
	m_NodeCount = 0;
}

//////////////////////////////////////////////////////////////////////////
// popHead(void)
template <class T>
T CSinList<T>::PopHead(void)
{
	T tmpData = m_Head->m_Data;
	CListNode<T>* pTmp = m_Head;

	if(m_NodeCount == 0)
		throw "Invalide argument";
	m_Head = m_Head->m_Next;

	delete pTmp;

	m_NodeCount--;
	return tmpData;
}

//////////////////////////////////////////////////////////////////////////
// popTail(void)
template <class T>
T CSinList<T>::PopTail(void)
{
	T retData = m_Tail->m_Data;

	if(m_NodeCount == 0)
		throw "Invalide argument";

	if(m_NodeCount == 1)
	{
		delete m_Head;

		m_Head = m_Tail = NULL;
		m_NodeCount --;

		return retData;
	}

	CListNode<T>* pTmpNode = m_Head;
	for(int nCirTmp = 0; nCirTmp < m_NodeCount - 2; nCirTmp++)
	{
		pTmpNode = pTmpNode->m_Next;
	}
	m_Tail = pTmpNode;
	pTmpNode = pTmpNode->m_Next;
	m_NodeCount --;
	delete pTmpNode;

	return retData;
}

//////////////////////////////////////////////////////////////////////////
// InsertAt(T& srcData, int nIndex)
// All the element seems to move once to the next positon, this means you should
// not insert at the tail of the list
// remark : if you want to insert at the tail of the list
// you should not call this function , you should call
// pushTail() instead
template <class T>
T CSinList<T>::InsertAt(T& srcData, int nIndex)
{
	if(nIndex < 0 || nIndex > m_NodeCount)
		throw "Invalide argument";

	if(nIndex == 0)
	{
		PushHead(srcData);
	}
	else if(nIndex == m_NodeCount)
	{
		PushTail(srcData);
	}

	else
	{
		CListNode<T>* pInsertBefor = MovePtrTo(nIndex - 1);
		CListNode<T>* pInsertAfter = pInsertBefor->m_Next;

		CListNode<T>* pTmpNewNode = new CListNode<T>(srcData);
		pInsertBefor->m_Next = pTmpNewNode;
		pTmpNewNode->m_Next= pInsertAfter; 

		m_NodeCount++;
	}

	return srcData;
}

//////////////////////////////////////////////////////////////////////////
// MovePtrTo(int nIndex)   nIndex should be treated as the sub label
//

template <class T>
CListNode<T>* CSinList<T>::MovePtrTo(int nIndex) const
{
	if(nIndex < 0 || nIndex >= m_NodeCount)
		throw "Invalide argument";

	CListNode<T>* pTmpNodePtr = m_Head;
	for(int nCirTmp = 0; nCirTmp < nIndex; nCirTmp++)
	{
		pTmpNodePtr = pTmpNodePtr->m_Next;
	}
	
	return pTmpNodePtr;
}

template <class T>
int CSinList<T>::Find(T& srcData, int nStartPos /* = 0 */, int nIncSize /* = 1 */) const
{
	for(int nCirTmp = nStartPos; nCirTmp < m_NodeCount; nCirTmp += nIncSize)
	{
		if(GetAt(nCirTmp) == srcData)
			return nCirTmp;
	}
	return -1;
}

#endif