数据结构的线性结构-双向链表

如果需要在单个链接列表中搜索元素，则必须从第一个元素开始搜索，双向链接列表在每个节点（起始节点和最后一个节点除外）中存储两个指针. 指针指向前一个节点的地址和下一个节点的地址，因此无论哪个节点都可以用来查找其他节点.

删除双向链表中的元素时，应注意，他有一个指向前驱的指针和一个指向下一个节点的指针. 删除元素后，前一个节点的指针将指向已删除节点的下一个节点，而已删除节点的下一个节点指针将指向已删除的节点的上一个节点.

双向链表的操作要求前一个节点的指针指向插入节点，然后，指向插入节点的两个指针指向之前和之后的两个节点线性双链表线性双链表，而指向后一个节点的指针指向插入节点.

双向链表的C ++代码实现:

AL_Node.h文件

template<typename T> class AL_ListDouble;
template<typename T>
class AL_Node
{
    //声明一个朋友类，使这个朋友类可以访问这个类的私有元素
    friend class AL_ListDouble<T>;
public :
    ~AL_Node();
private :
    AL_Node();
    AL_Node(const T &tTemplate);
    AL_Node(const AL_Node<T>& cAL_Node);
    T m_data;//存储数据
    AL_Node *m_pPre;//记录链表的头结点地址
    AL_Node *m_pNext; //指向下一个节点地址
};
template<typename T>
AL_Node<T>::AL_Node():m_pPre(NULL),m_pNext(NULL)
{
}
template<typename T>
AL_Node<T>::AL_Node(const T &tTemplate):m_pPre(NULL),m_pNext(NULL),m_data(tTemplate)
{
}
template<typename T>
AL_Node<T>::~AL_Node()
{
    m_pPre=NULL;
    m_pNext=NULL;
}
#endif // AL_NODE

AL_ListDouble.h文件

#ifndef AL_LISTDOUBLE_INCLUDE
#define AL_LISTDOUBLE_INCLUDE
#include <windows.h>
#include "AL_Node.h"
template<typename T>
class AL_ListDouble
{
public:
    static const  DWORD LISTDOUBLE_POSITION_INVALID = 0xffffffff;
    AL_ListDouble();
    ~AL_ListDouble();
    DWORD Length() const;
    DWORD Find(const T &tTemplate)const;
    bool IsElement(const T & tTemplate)const;
    bool Insert(DWORD dwIndex, const T & tTemplate);
    bool InsertBegin(const T &tTemplate);
    bool InsertEnd(const T &tTemplate);
    bool Remove(const T &tTemplate);
    bool IsEmpty()const;
    bool Get(T & tTypeOut, DWORD dwIndex)const;
    bool Set(const DWORD &tTemplate, DWORD dwIndex, T &tTypeOut);
    void Clear();
private:
    AL_Node<T> * GetNodeByIndex(DWORD dwIndex) const;
    AL_Node<T> * m_Header;
    DWORD        m_dwSize;
};
template<typename T>
inline AL_ListDouble<T>::AL_ListDouble():m_Header(NULL),m_dwSize(0x00)
{
    //创建指向头结点的指针
    m_Header = new AL_Node<T>();
}
template<typename T>
inline AL_ListDouble<T>::~AL_ListDouble()
{
    Clear();
    if (m_Header!=NULL)
    {
        delete m_Header;
        m_Header = NULL;
    }
}
template<typename T>
inline DWORD AL_ListDouble<T>::Length() const
{
    return m_dwSize;
}
template<typename T>
inline DWORD AL_ListDouble<T>::Find(const T & tTemplate) const
{
   if (IsEmpty()==true)
   {
       return LISTDOUBLE_POSITION_INVALID;
   }
   AL_Node<T> * pMove = NULL;
   DWORD dwCount = 1;
   pMove = m_Header->m_pNext;
   while (pMove->m_pNext!=NULL)
   {
       if (pMove->m_data==tTemplate)
       {
           return dwCount-1;
       }
       dwCount++;
       pMove = pMove->m_pNext;
   }
   if (pMove->m_data==tTemplate)
   {
       return dwCount - 1;
   }
   return LISTDOUBLE_POSITION_INVALID;
}
template<typename T>
inline bool AL_ListDouble<T>::IsElement(const T & tTemplate) const
{
    if (Find(tTemplate) == LISTDOUBLE_POSITION_INVALID)
    {
        return false;
    }
    return true;
}
template<typename T>
inline bool AL_ListDouble<T>::Insert(DWORD dwIndex, const T & tTemplate)
{
    if (dwIndex>Length())
    {
        return false;
    }
    AL_Node<T>* pInsert = new AL_Node<T>;
    pInsert->m_data = tTemplate;
    AL_Node<T> * pPer = NULL;
    if (dwIndex==0x00)
    {
        pPer = m_Header;
    }
    else
    {
        pPer = GetNodeByIndex(dwIndex - 1);
    }
    if (pPer==NULL)
    {
        return false;
    }
    if (dwIndex == Length())
    {
        //将节点指向插入的节点
        pPer->m_pNext = pInsert;
        //将插入节点的指针指向他的前驱节点
        pInsert->m_pPre = pPer;
    }
    else
    {
        AL_Node<T>* pIndexNode = pPer->m_pNext;
        if (pIndexNode==NULL)
        {
            return false;
        }
        pPer->m_pNext = pInsert;
        pInsert->m_pPre = pPer;
        pInsert->m_pNext = pIndexNode;
        pIndexNode->m_pPre = pInsert;
    }
    m_dwSize++;
    return true;
}
template<typename T>
inline bool AL_ListDouble<T>::InsertBegin(const T & tTemplate)
{
    return Insert(0x00,tTemplate);
}
template<typename T>
inline bool AL_ListDouble<T>::InsertEnd(const T & tTemplate)
{
    return Insert(Length(),tTemplate);
}
template<typename T>
inline bool AL_ListDouble<T>::Remove(const T & tTemplate)
{
    if (IsEmpty()==true)
    {
        return false;
    }
    DWORD dwPosition = Find(tTemplate);
    if (dwPosition == LISTDOUBLE_POSITION_INVALID)
    {
        return false;
    }
    AL_Node<T> *  p_Deltet =GetNodeByIndex(dwPosition);
  if (p_Deltet==NULL)
  {
      return false;
  }
  AL_Node<T> * pPer = NULL;
  if (dwPosition==0x00)
  {
      pPer = m_Header;
  }
  else
  {
      //指向要删除的节点的前驱节点
      pPer = p_Deltet->m_pPre;
  }
  if (pPer==NULL)
  {
      return false;
  }
  pPer->m_pNext = p_Deltet->m_pNext;
  //获取要删除节点的后一个节点
  AL_Node<T>*p_Next = p_Deltet->m_pNext;
  //设置它的前驱节点
  if (p_Next!=NULL)
  {
      p_Next->m_pPre = pPer;
  }
  delete p_Deltet;
  p_Deltet = NULL;
  m_dwSize--;
    return true;
}
template<typename T>
inline bool AL_ListDouble<T>::IsEmpty() const
{
    return (m_Header->m_pNext == NULL) ? true : false;
}
template<typename T>
inline bool AL_ListDouble<T>::Get(T & tTypeOut, DWORD dwIndex) const
{
     if (IsEmpty()==true)
     {
         return false;
     }
     if (Length()-1<dwIndex)
     {
         return false;
     }
     AL_Node<T> *pGet = GetNodeByIndex(dwIndex);
     if (pGet==NULL)
     {
         return false;
     }
     tTypeOut = pGet->m_data;
     return true;
}
template<typename T>
inline bool AL_ListDouble<T>::Set(const DWORD & tTemplate, DWORD dwIndex, T & tTypeOut)
{
    if (Length()-1<dwIndex)
    {
        return false;
    }
    AL_Node<T>*pSet = GetNodeByIndex(dwIndex);
    if (pSet==NULL)
    {
        return false;
    }
    tTypeOut = pSet->m_data;
    pSet->m_data = tTemplate;
    return true;
}
template<typename T>
inline void AL_ListDouble<T>::Clear()
{
    if (IsEmpty()==true)
    {
        return;
    }
    AL_Node<T>*pDelete = NULL;
    while (m_Header->m_pNext != NULL)
    {
        pDelete = m_Header->m_pNext;
        m_Header->m_pNext = pDelete->m_pNext;
        delete pDelete;
        pDelete = NULL;
    }
    m_dwSize = 0x00;
}
template<typename T>
inline AL_Node<T>* AL_ListDouble<T>::GetNodeByIndex(DWORD dwIndex) const
{
    if (Length()-1<dwIndex)
    {
        return NULL;
    }
    AL_Node<T>*pMove = NULL;
    DWORD dwCount = 1;
    pMove = m_Header->m_pNext;
    while (pMove->m_pNext!=NULL)
    {
        if (dwIndex==dwCount-1)
        {
            return pMove;
        }
        dwCount++;
        pMove = pMove->m_pNext;
    }
    return pMove;
}
#endif

测试代码:

void DoubleTest()
{
    //创建一个双链表
    AL_ListDouble<DWORD> cListDouble;
    bool bEmpty = cListDouble.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++)
   {
       cListDouble.Insert(cListDouble.Length(), array[i]);
   }
   bEmpty = cListDouble.IsEmpty();
   DWORD cLength = cListDouble.Length();
   std::cout << bEmpty << "  " << cLength << std::endl;
   //寻找元素的位置
   DWORD dwFind = cListDouble.Find(11);
   std::cout << dwFind << std::endl;
   //判断元素是否存在
   bool dwemdw = cListDouble.IsElement(47);
   bool dwendw2 = cListDouble.IsElement(14);
   std::cout << dwemdw << "  " << dwendw2 << std::endl;
   //测试删除元素
   dwemdw = cListDouble.Remove(456);
   dwendw2 = cListDouble.Remove(13);
   cLength = cListDouble.Length();
   std::cout << dwemdw << "  " << dwendw2 << "  " << cLength << std::endl;
   //获取元素修改元素
      DWORD SU,w;
       bool byGet = cListDouble.Get(SU, cListDouble.Length()-1);
       bool bySet = cListDouble.Set(25, cListDouble.Length()-1,w);
       std::cout << byGet << " " << SU << std::endl;
       std::cout << bySet << "  " << w << std::endl;
       byGet = cListDouble.Get(SU, cListDouble.Length() - 1);
       std::cout << byGet<<" "<<SU << std::endl;
}
int main(int argc, char *argv[])
{
    DoubleTest();
    getchar();
    return 0;
}

运行结果:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-244279-1.html