单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指列表中的下一个结点;
列表是由结点构成,由head指针指向第一个成为表头的结点而终止于最后一个指向nuLL的指针;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的笔记潇汀会尽量详细讲解一些相关知识的,希望大家继续关注我的博客。
本节笔记到这里就结束了。
潇汀一有时间就会把自己的学习心得,觉得比较好的知识点写出来和大家一起分享。
编程开发的路很长很长,非常希望能和大家一起交流,共同学习,共同进步。
如果文章中有什么疏漏的地方,也请大家指正。也希望大家可以多留言来和我探讨编程相关的问题。
最后,谢谢你们一直的支持~~~
C++完整个代码示例(代码在VS2005下测试可运行)
AL_Node.h
/** @(#)$Id: AL_Node.h 25 2013-08-30 03:08:31Z xiaoting $ @brief store data, and be used to AL_ListSingle, AL_ListDouble, AL_ListCircular and so on @Author $Author: xiaoting $ @Date $Date: 2013-08-30 11:08:31 +0800 (周五, 30 八月 2013) $ @Revision $Revision: 25 $ @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_Node.h $ @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_Node.h 25 2013-08-30 03:08:31Z xiaoting $ */ #ifndef CXX_AL_NODE_H #define CXX_AL_NODE_H /////////////////////////////////////////////////////////////////////////// // AL_Node /////////////////////////////////////////////////////////////////////////// template<typename T> class AL_ListSingle; template<typename T> class AL_ListDouble; template<typename T> class AL_ListCircular; template<typename T> class AL_Node { public: /** * Destruction * * @param * @return * @note * @attention */ ~AL_Node(); protected: private: friend class AL_ListSingle<T>; friend class AL_ListDouble<T>; friend class AL_ListCircular<T>; /** * Construction * * @param * @return * @note private the Construction, avoid the others use it * @attention */ AL_Node(); /** * Construction * * @param const T& tTemplate * @return * @note * @attention private the Construction, avoid the others use it */ AL_Node(const T& tTemplate); public: protected: private: T m_data; //the friend class can use it directly AL_Node *m_pPre; //previous data AL_ListDouble will use it AL_Node *m_pNext; //next data }; /////////////////////////////////////////////////////////////////////////// // AL_Node /////////////////////////////////////////////////////////////////////////// /** * Construction * * @param * @return * @note private the Construction, avoid the others use it * @attention */ template<typename T> AL_Node<T>::AL_Node(): m_pPre(NULL), m_pNext(NULL) { memset(&m_data, 0x00, sizeof(T)); } /** * Construction * * @param const T& tTemplate * @return * @note * @attention private the Construction, avoid the others use it */ template<typename T> AL_Node<T>::AL_Node(const T& tTemplate): m_data(tTemplate), m_pPre(NULL), m_pNext(NULL) { } /** * Destruction * * @param * @return * @note * @attention */ template<typename T> AL_Node<T>::~AL_Node() { //it doesn't matter to clear the pointer or not. m_pPre = NULL; m_pNext = NULL; } #endif // CXX_AL_NODE_H /* EOF */
AL_ListSingle.h
/** @(#)$Id: AL_ListSingle.h 25 2013-08-30 03:08:31Z xiaoting $ @brief Singly linked list (single list) is a list, which is characterized by the direction of the chain links are unidirectional, Chain accessed through sequential reads starting from the head; linked list is constructed using pointers list; known the list of nodes, as a linked list nodes is assembled; wherein each node has a pointer member variable refers to the next list node; @Author $Author: xiaoting $ @Date $Date: 2013-08-30 11:08:31 +0800 (周五, 30 八月 2013) $ @Revision $Revision: 25 $ @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListSingle.h $ @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListSingle.h 25 2013-08-30 03:08:31Z xiaoting $ */ #ifndef CXX_AL_LISTSINGLE_H #define CXX_AL_LISTSINGLE_H #ifndef CXX_AL_NODE_H #include "AL_Node.h" #endif /////////////////////////////////////////////////////////////////////////// // AL_ListSingle /////////////////////////////////////////////////////////////////////////// template<typename T> class AL_ListSingle { public: static const DWORD LISTSINGLE_POSITION_INVALID = 0xffffffff; /** * Construction * * @param * @return * @note * @attention */ AL_ListSingle(); /** * Destruction * * @param * @return * @note * @attention */ ~AL_ListSingle(); /** * Length * * @param VOID * @return DWORD * @note get the length of the list * @attention */ DWORD Length() const; /** * Find * * @param const T& tTemplate * @return DWORD * @note find the position of tTemplate * @attention if not find, will be return 0xffffffff */ DWORD Find(const T& tTemplate ) const; /** * IsElement * * @param const T& tTemplate * @return BOOL * @note the tTemplate is in the list? * @attention */ BOOL IsElement(const T& tTemplate ) const; /** * Insert * * @param DWORD dwIndex * @param const T& tTemplate * @return BOOL * @note inset the tTemplate into the list at the position * @attention */ BOOL Insert(DWORD dwIndex,const T& tTemplate ); /** * InsertBegin * * @param const T& tTemplate * @return BOOL * @note inset the tTemplate into the list at the position * @attention */ BOOL InsertBegin(const T& tTemplate ); /** * InsertEnd * * @param const T& tTemplate * @return BOOL * @note inset the tTemplate into the list at the position * @attention */ BOOL InsertEnd(const T& tTemplate ); /** * Remove * * @param const T& tTemplate * @return BOOL * @note remove the tTemplate into the list * @attention */ BOOL Remove(const T& tTemplate ); /** * IsEmpty * * @param VOID * @return BOOL * @note the list has data? * @attention */ BOOL IsEmpty() const; /** * Get * * @param * @return BOOL * @note get the const T& at the position * @attention the dwIndex must is little than the list length */ T Get(DWORD dwIndex) const; /** * Set * * @param DWORD dwIndex * @param const T& tTemplate * @return BOOL * @note Replaced with the element element element on position index, and returns the old element... * @attention Index must in the list */ T Set(DWORD dwIndex, const T& tTemplate ); /** * Clear * * @param VOID * @return VOID * @note clear the data in the list * @attention all data will be clear */ VOID Clear(); protected: private: /** * GetNodeByIndex * * @param * @return BOOL * @note get the const T& at the position * @attention the dwIndex must is little than the list length */ AL_Node<T>* GetNodeByIndex(DWORD dwIndex) const; public: protected: private: AL_Node<T>* m_pHeader; }; /////////////////////////////////////////////////////////////////////////// // AL_ListSingle /////////////////////////////////////////////////////////////////////////// /** * Construction * * @param * @return * @note * @attention */ template<typename T> AL_ListSingle<T>::AL_ListSingle(): m_pHeader(NULL) { } /** * Destruction * * @param * @return * @note * @attention */ template<typename T> AL_ListSingle<T>::~AL_ListSingle() { Clear(); } /** * Length * * @param * @return * @note get the length of the list * @attention */ template<typename T> DWORD AL_ListSingle<T>::Length() const { if (TRUE == IsEmpty()) { return 0; } AL_Node<T>* pMove = NULL; DWORD dwCount = 1; pMove = m_pHeader; while (NULL != pMove->m_pNext) { dwCount ++; pMove = pMove->m_pNext; } return dwCount; } /** * Find * * @param const T& tTemplate * @return DWORD * @note find the position of tTemplate * @attention if not find, will be return 0xffffffff */ template<typename T> DWORD AL_ListSingle<T>::Find(const T& tTemplate ) const { if (TRUE == IsEmpty()) { return LISTSINGLE_POSITION_INVALID; } AL_Node<T>* pMove = NULL; DWORD dwCount = 1; //loop the next data; pMove = m_pHeader; while (NULL != pMove->m_pNext) { if (tTemplate == pMove->m_data) { //find the data return dwCount-1; } dwCount ++; pMove = pMove->m_pNext; } //the end if (tTemplate == pMove->m_data) { //find the data return dwCount-1; } return LISTSINGLE_POSITION_INVALID; } /** * IsElement * * @param const T& tTemplate * @return BOOL * @note the tTemplate is in the list? * @attention */ template<typename T> BOOL AL_ListSingle<T>::IsElement(const T& tTemplate ) const { if (LISTSINGLE_POSITION_INVALID == Find(tTemplate )) { return FALSE; } return TRUE; } /** * Insert * * @param const T& tTemplate * @param DWORD dwIndex * @return BOOL * @note inset the tTemplate into the list at the position * @attention */ template<typename T> BOOL AL_ListSingle<T>::Insert(DWORD dwIndex, const T& tTemplate ) { if (dwIndex > Length()) { //can not insert to this position return FALSE; } AL_Node<T>* pInsert = new AL_Node<T>; pInsert->m_data = tTemplate; if (0x00 == dwIndex) { //header pInsert->m_pNext = m_pHeader; m_pHeader = pInsert; return TRUE; } AL_Node<T>* pPre = GetNodeByIndex(dwIndex - 1); if ((NULL == pPre)) { //error return FALSE; } if (Length() == dwIndex){ //end pPre->m_pNext = pInsert; return TRUE; } //among of the list AL_Node<T>* pIndexNode = GetNodeByIndex(dwIndex); if ((NULL == pIndexNode)) { //error return FALSE; } pInsert->m_pNext = pIndexNode; pPre->m_pNext = pInsert; return TRUE; /* AL_Node<T>* pMove = NULL; DWORD dwCount = 1; //loop the next data; pMove = m_pHeader; while (NULL != pMove->m_pNext) { if (dwCount-1 == dwIndex) { //insert this place pInsert->m_pNext = pMove->m_pNext pMove->m_pNext = pInsert; return TRUE; } dwCount++ pMove = pMove->m_pNext; } // the end pMove->m_pNext = pInsert; */ return TRUE; } /** * InsertBegin * * @param const T& tTemplate * @return BOOL * @note inset the tTemplate into the list at the position * @attention */ template<typename T> BOOL AL_ListSingle<T>::InsertBegin(const T& tTemplate ) { return Insert(0, tTemplate); } /** * InsertEnd * * @param const T& tTemplate * @return BOOL * @note inset the tTemplate into the list at the position * @attention */ template<typename T> BOOL AL_ListSingle<T>::InsertEnd(const T& tTemplate ) { return Insert(Length(), tTemplate); } /** * Remove * * @param const T& tTemplate * @return BOOL * @note remove the tTemplate into the list * @attention */ template<typename T> BOOL AL_ListSingle<T>::Remove(const T& tTemplate ) { if (TRUE == IsEmpty()) { return FALSE; } DWORD dwPosition = Find(tTemplate); if (LISTSINGLE_POSITION_INVALID == dwPosition) { //can not find the data return FALSE; } AL_Node<T>* pDelete = GetNodeByIndex(dwPosition); if (NULL == pDelete) { //error return FALSE; } if (0x00 == dwPosition) { //header m_pHeader = pDelete->m_pNext; } else { AL_Node<T>* pPre = GetNodeByIndex(dwPosition - 1); if (NULL == pPre) { //error return FALSE; } pPre->m_pNext = pDelete->m_pNext; } delete pDelete; pDelete = NULL; return TRUE; /* AL_Node<T>* pMove = NULL; AL_Node<T>* pPreMove = NULL; //loop the next data; pMove = m_pHeader; do { if (tTemplate == pMove->m_data) { //remove the data if (1 == Length()) { //do not exist the pre move, only one data exist in the list, delete m_pHeader; m_pHeader = NULL; } else { pPreMove->m_pNext = pMove->m_pNext; delete pMove; pMove = NULL; } return TRUE; } pMove = pMove->m_pNext; pPreMove = pMove; } while (NULL != pMove->m_pNext); */ return FALSE; } /** * IsEmpty * * @param * @return BOOL * @note the list has data? * @attention */ template<typename T> BOOL AL_ListSingle<T>::IsEmpty() const { return (NULL == m_pHeader) ? TRUE:FALSE; } /** * Get * * @param * @return T * @note get the T at the position * @attention the dwIndex must is little than the list length */ template<typename T> T AL_ListSingle<T>::Get(DWORD dwIndex) const { if (TRUE == IsEmpty()) { //error } if (Length()-1 < dwIndex) { //error } AL_Node<T>* pMove = NULL; DWORD dwCount = 0; //loop the next data; pMove = m_pHeader; do { if (dwCount == dwIndex) { //insert this place return pMove->m_data; } dwCount++; pMove = pMove->m_pNext; } while (NULL != pMove->m_pNext); //the end return pMove->m_data; } /** * Set * * @param DWORD dwIndex * @param const T& tTemplate * @return T * @note Replaced with the element element element on position index, and returns the old element... * @attention Index must in the list */ template<typename T> T AL_ListSingle<T>::Set(DWORD dwIndex, const T& tTemplate ) { if (Length()-1 < dwIndex) { //error } T tTypeTemp = m_pElements[dwIndex]; m_pElements[dwIndex] = tTemplate ; return tTypeTemp; } /** * Clear * * @param VOID * @return VOID * @note clear the data in the list * @attention all data will be clear */ template<typename T> VOID AL_ListSingle<T>::Clear() { if (NULL == m_pHeader) { //No data, return; } AL_Node<T>* pDelete = NULL; while(NULL != m_pHeader->m_pNext){ //get the node pDelete = m_pHeader->m_pNext; m_pHeader->m_pNext = pDelete->m_pNext; delete pDelete; pDelete = NULL; } // at last delete the header delete m_pHeader; m_pHeader = NULL; } /** * GetNodeByIndex * * @param * @return BOOL * @note get the const T& at the position * @attention the dwIndex must is little than the list length */ template<typename T> AL_Node<T>* AL_ListSingle<T>::GetNodeByIndex(DWORD dwIndex) const { if (Length()-1 < dwIndex) { //error return NULL; } AL_Node<T>* pMove = NULL; DWORD dwCount = 1; //loop the next data; pMove = m_pHeader; while (NULL != pMove->m_pNext) { if (dwCount-1 == dwIndex) { //get this place return pMove; } dwCount ++; pMove = pMove->m_pNext; } //the end return pMove; } #endif // CXX_AL_LISTSINGLE_H /* EOF */
测试代码
#ifdef TEST_AL_LISTSINGLE AL_ListSingle<DWORD> cListSingle; BOOL bEmpty = cListSingle.IsEmpty(); std::cout<<bEmpty<<std::endl; int array[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; for(int i=0;i<15;i++) cListSingle.Insert(cListSingle.Length(), array[i]); bEmpty = cListSingle.IsEmpty(); std::cout<<bEmpty<<std::endl; //test the interface DWORD dwListSeqLen = cListSingle.Length(); std::cout<<dwListSeqLen<<std::endl; DWORD dwFind = cListSingle.Find(16); std::cout<<dwFind<<std::endl; dwFind = cListSingle.Find(12); std::cout<<dwFind<<std::endl; BOOL bElement = cListSingle.IsElement(16); std::cout<<bElement<<std::endl; bElement = cListSingle.IsElement(14); std::cout<<bElement<<std::endl; BOOL bInsert = cListSingle.Insert(0, 0); std::cout<<bInsert<<std::endl; bInsert = cListSingle.Insert(16, 16); std::cout<<bInsert<<std::endl; bInsert = cListSingle.Insert(16, 999); std::cout<<bInsert<<std::endl; BOOL bRemove = cListSingle.Remove(9846354); std::cout<<bRemove<<std::endl; bRemove = cListSingle.Remove(999); std::cout<<bRemove<<std::endl; INT it = 0x00; for (DWORD i=0; i<cListSingle.Length(); i++) { it = cListSingle.Get(i); std::cout<<it<<std::endl; } cListSingle.Clear(); bEmpty = cListSingle.IsEmpty(); std::cout<<bEmpty<<std::endl; dwListSeqLen = cListSingle.Length(); std::cout<<dwListSeqLen<<std::endl; bInsert = cListSingle.Insert(1, 999); std::cout<<bInsert<<std::endl; bInsert = cListSingle.Insert(0, 666); std::cout<<bInsert<<std::endl; bRemove = cListSingle.Remove(666); std::cout<<bRemove<<std::endl; bEmpty = cListSingle.IsEmpty(); std::cout<<bEmpty<<std::endl; dwListSeqLen = cListSingle.Length(); std::cout<<dwListSeqLen<<std::endl; #endif
© 著作权归作者所有
相关热门文章
发表评论