mylist.h

一个采用链表编写的列表类

// MyList.h: interface for the CMyList class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_MYLIST_H__AA31DDA1_20D5_4B97_8D52_1A0730BE2CA9__INCLUDED_)
#define AFX_MYLIST_H__AA31DDA1_20D5_4B97_8D52_1A0730BE2CA9__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

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

	POSITION AddTail(T t);
	POSITION AddHead(T t);

	POSITION Find(T t);
	T GetAt(POSITION position);
	void SetAt(POSITION position, T t);
	
	POSITION GetHeadPosition() const;
	POSITION GetTailPosition() const;
	T GetNext(POSITION& rPosition);
	T GetPrev(POSITION& rPosition);
	
	POSITION InsertBefore(POSITION position, T t);
	POSITION InsertAfter(POSITION position, T t);

	void RemoveAt(POSITION position);
	void RemoveAll();

	int GetCount() const;

protected:
	struct CNode
	{
		CNode* pNext;
		CNode* pPrev;
		T data;
	};

	CNode* m_pNodeHead;
	CNode* m_pNodeTail;

	int m_nCount;

};

//////////////////////////////////////////////////////////////////////
// CList<T> inline functions

template<class T>
CMyList<T>::CMyList()
{
	m_pNodeHead = NULL;
	m_pNodeTail = NULL;

	m_nCount = 0;
}

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

template<class T>
POSITION CMyList<T>::AddTail(T t)
{
	CNode* p = new CNode;
	p->pNext = NULL;
	p->pPrev = m_pNodeTail;
	p->data = t;

	if (m_pNodeTail)
		m_pNodeTail->pNext = p;
	else
		m_pNodeHead = p;

	m_pNodeTail = p;
	m_nCount++;
	return (POSITION)p;
}

template<class T>
POSITION CMyList<T>::AddHead(T t)
{
	CNode* p = new CNode;
	p->pNext = m_pNodeHead;
	p->pPrev = NULL;
	p->data = t;

	if (m_pNodeHead)
		m_pNodeHead->pPrev = p;
	else
		m_pNodeTail = p;

	m_pNodeHead = p;
	m_nCount++;
	return (POSITION)p;
}

template<class T>
POSITION CMyList<T>::Find(T t)
{
	CNode* p = m_pNodeHead;
	while (p)
	{
		if (p->data == t)
			break;
		p = p->pNext;
	}
	
	return (POSITION)p;
}

template<class T>
T CMyList<T>::GetAt(POSITION position)
{
	CNode* p = (CNode*)position;

	return p->data;
}

template<class T>
void CMyList<T>::SetAt(POSITION position, T t)
{
	CNode* p = (CNode*)position;
	p->data = t;
}

template<class T>
POSITION CMyList<T>::GetHeadPosition() const
{
	return (POSITION)m_pNodeHead;
}

template<class T>
POSITION CMyList<T>::GetTailPosition() const
{
	return (POSITION)m_pNodeTail;
}

template<class T>
T CMyList<T>::GetNext(POSITION& rPosition)
{
	CNode* p = (CNode*)rPosition;
	rPosition = (POSITION)p->pNext;

	return p->data;
}

template<class T>
T CMyList<T>::GetPrev(POSITION& rPosition)
{
	CNode* p = (CNode*)rPosition;
	rPosition = (POSITION)p->pPrev;

	return p->data;
}

template<class T>
void CMyList<T>::RemoveAt(POSITION position)
{
	CNode* p = (CNode*)position;
//	ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
	CNode* pNext = p->pNext;
	CNode* pPrev = p->pPrev;
	delete p;
	m_nCount--;

	if (pNext)
		pNext->pPrev = pPrev;
	else
		m_pNodeTail = pPrev;

	if (pPrev)
		pPrev->pNext = pNext;
	else
		m_pNodeHead = pNext;
}

template<class T>
void CMyList<T>::RemoveAll()
{
	CNode* p = m_pNodeHead;
	while (p)
	{
		p = p->pNext;
		delete m_pNodeHead;
		m_pNodeHead = p;
	}
	m_pNodeTail = NULL;
	m_nCount = 0;
}

template<class T>
POSITION CMyList<T>::InsertBefore(POSITION position, T t)
{
	if (position == NULL)
		return AddHead(t);

	CNode* p = (CNode*)position;
	CNode* pPrev = p->pPrev;
	if (pPrev == NULL)
		return AddHead(t);

	CNode* pNew = new CNode;
	pNew->pPrev = pPrev;
	pNew->pNext = p;
	pNew->data = t;
	p->pPrev = pNew;
	pPrev->pNext = pNew;

	return (POSITION)pNew;
}

template<class T>
POSITION CMyList<T>::InsertAfter(POSITION position, T t)
{
	if (position == NULL)
		return AddTail(t);

	CNode* p = (CNode*)position;
	CNode* pNext = p->pNext;
	if (pNext == NULL)
		return AddTail(t);

	CNode* pNew = new CNode;
	pNew->pPrev = p;
	pNew->pNext = pNext;
	pNew->data = t;
	p->pNext = pNew;
	pNext->pPrev = pNew;

	return (POSITION)pNew;
}

template<class T>
int CMyList<T>::GetCount() const
{
	return m_nCount;
}

#endif // !defined(AFX_MYLIST_H__AA31DDA1_20D5_4B97_8D52_1A0730BE2CA9__INCLUDED_)