单向链表的实现
原 作 者：querw
原 出 处：VC在线

代码：http://www.vczx.com/article/file/20040822213844_TestQueue.rar


　　独立于MFC的单项链表模板,多余的话我就不多说了.有附带功能演示用法.希望能给有同样需求的读者一点帮助.
　　以下是源代码.(不用cpp文件,使用时只要把文件Queue.h包含到工程中即可)
// Queue.h: interface for the CQueue class.
//
/********************************************************************
created: 2004/08/09
created: 9:8:2004 23:33
file base: queue
file ext: h
author: 阙荣文(北方工业大学计算机2000级)

purpose: 构建一个通用的,独立于MFC的单向链表
我想c++的标准库模板应该也有类似功能的类,但是我还是决定自己实现
这样可以使用我自己喜欢的参数调用方式.
希望对用同样需求的编程爱好者有用
*********************************************************************/

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_QUEUE_H__57C46373_D485_43F2_998C_D3EA4984E59A__INCLUDED_)
#define AFX_QUEUE_H__57C46373_D485_43F2_998C_D3EA4984E59A__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
template <class T>
class CQueue
{
public:
CQueue();
virtual ~CQueue();

int AddHead(T* pT);
int AddTail(T* pT);
int Insert(int nIndex,T* pElement); //在第nIndex个元素后插入

int GetSize();
BOOL GetAt(int nIndex,T& Element);

BOOL RemoveAt(int nIndex);
void RemoveAll();
BOOL RemoveHead();
BOOL RemoveTail();

int Find(T Element);
BOOL GetFirstNode(T &Element);
BOOL GetNextNode(T &Element);
protected:
struct Node{
Node* pNext;
T Data;
};
int m_nSize; //队列的大小
Node* m_pHead; //队列头指针
Node* m_pTail; //队列尾指针
Node* m_pCurrentNode; //当前节点的指针
};

//因为是模板类,所以所有函数的实现代码必须一起放在头文件中

template <class T>
CQueue<T>::CQueue()
{
m_nSize = 0;
m_pHead = NULL;
m_pTail = NULL;
m_pCurrentNode = NULL;
}

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

template <class T>
int CQueue<T>::AddHead(T* pT)
{
ASSERT(pT);
Node *pNewNode = new Node;
pNewNode->Data = *pT;
pNewNode->pNext = m_pHead;
m_pHead = pNewNode;
m_nSize++;
if(m_nSize == 1)
{
m_pTail = m_pHead;
}
return m_nSize;
}

template <class T>
int CQueue<T>::AddTail(T* pT)
{
ASSERT(pT);
Node *pNewNode = new Node;
pNewNode->Data = *pT;
if(m_pTail != NULL)
{
m_pTail->pNext = pNewNode;
}
m_pTail = pNewNode;
m_nSize++;
if(m_nSize == 1)
{
m_pHead = m_pTail;
}
m_pTail->pNext = NULL;
return m_nSize;
}

template <class T>
int CQueue<T>::Insert(int nIndex,T *pElement)
{
int nRet = 0;
if(nIndex < 0 || nIndex >= m_nSize || pElement == NULL)
{
nRet = -1;
}
else
{
T *pNode = m_pHead;
int i = 0;
while(pNode && i < nIndex)
{
pNode = pNode->pNext;
i++;
}
T *pNewNode = new T;
pNewNode->Data = pElement->pData;

pNewNode->pNext = pNode->pNext;
pNode->pNext = pNewNode;
if(pNewNode->pNext == NULL)
{
m_pTail = pNewNode;
}
m_nSize++;
nRet = m_nSize;
}
return nRet;
}

template <class T>
int CQueue<T>::GetSize()
{
return m_nSize;
}

template <class T>
BOOL CQueue<T>::GetAt(int nIndex,T& Element)
{
if(nIndex < 0 || nIndex >= m_nSize) return FALSE;
Node *pNode = m_pHead;
for(int i = 1; i <= nIndex; i++)
{
pNode = pNode->pNext;
}
Element = pNode->Data;
return TRUE;
}

template <class T>
BOOL CQueue<T>::RemoveAt(int nIndex)
{
if(nIndex < 0 || nIndex >= m_nSize) return FALSE;

Node *pNode = m_pHead,*pPreNode = NULL;
for(int i = 1; i <= nIndex; i++)
{
pPreNode = pNode;
pNode = pNode->pNext;
}
if(pPreNode != NULL)
{
pPreNode->pNext = pNode->pNext;
}
if(nIndex == 0)
{
m_pHead = pNode->pNext;
}
if(nIndex == m_nSize -1)
{
m_pTail = pPreNode;
}
if(pNode == m_pCurrentNode)
{
m_pCurrentNode = NULL;
}
delete pNode;
m_nSize--;

if(m_nSize ==0)
{
m_pHead = NULL;
m_pTail = NULL;
}
return TRUE;
}

template <class T>
BOOL CQueue<T>::RemoveHead()
{
return RemoveAt(0);
}

template <class T>
BOOL CQueue<T>::RemoveTail()
{
return RemoveAt(m_nSize - 1);
}

template <class T>
void CQueue<T>::RemoveAll()
{
Node *pNode = m_pHead;
while(pNode != NULL)
{
Node* pTempNode = pNode->pNext;
delete pNode;
pNode = pTempNode;
}
m_nSize = 0;
m_pTail = NULL;
m_pHead = NULL;
m_pCurrentNode = NULL;
}

template <class T>
int CQueue<T>::Find(T Element)
{
Node *pNode = m_pHead;
for(int i = 0; i < m_nSize; i++)
{
if(pNode->Data == Element)
{
return i;
}
pNode = pNode->pNext;
}
return -1;
}

template <class T>
BOOL CQueue<T>::GetFirstNode(T &Element)
{
BOOL bRet = FALSE;
if(m_pHead)
{
m_pCurrentNode = m_pHead;
Element = *m_pCurrentNode;
m_pCurrentNode = m_pCurrentNode->pNext;
bRet = TRUE;
}
else
{
}
return bRet;
}

template <class T>
BOOL CQueue<T>::GetNextNode(T &Element)
{
BOOL bRet = FALSE;
if(m_pCurrentNode)
{
Element = *m_pCurrentNode;
m_pCurrentNode = m_pCurrentNode->pNext;
bRet = TRUE;
}
else
{
}
return bRet;
}

#endif

评论