单向链表的实现原 作 者：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

评论