///////////////////////////////////////////////////////
//   模塊名： 雙向鏈表模板實(shí)現(xiàn)   
//   研究者： 長(zhǎng)壽夢(mèng)
//   最后更新：2010-05-05 
//////////////////////////////////////////////////////
#ifndef   DLIST_H   
#define   DLIST_H   

#include   <assert.h>   
#include   <iostream.h>   

template   <class   T>   class   CDList; 
  
//一：節(jié)點(diǎn)類
template   <class   T>   
class   CDListNode   
{   
  public:   
      friend   CDList<T>;//節(jié)點(diǎn)的友元是鏈表
  private:   
      T   data;   //數(shù)據(jù)域 
      CDListNode<T>   *   previous; //前一個(gè)  
      CDListNode<T>   *   next;  //下一個(gè) 
}; 
  
//二：鏈表類
template   <class   T>   
class   CDList   
{   
  private:   
      CDListNode<T>   *   m_phead;  //頭
      CDListNode<T>   *   m_ptail;   //尾
      int m_count; //節(jié)點(diǎn)個(gè)數(shù)  
      
  public:   
      void   show(void);   
      CDList();   
      ~CDList();   
      
      //   Head/Tail   Access   Methods   
      T   &   GetHead(void)   const;     
      T   &   GetTail(void)   const;   
      
      //   Operations   Methods   
      void   RemoveHead(void);     
      void   RemoveTail(void); 
      void   RemoveAll(void);  
      int   AddHead(const   T   &   NewNode);     
      int   AddTail(const   T   &   NewNode);   
          
      
      //   Iteration   Methods   
      int   GetHeadPosition(void)   const;   
      int   GetTailPosition(void)   const;   
      T   &   GetNext(int   position)   const;     
      T   &   GetPrev(int   position)   const;     
      
      //   Retrieval/Modification   Methods   
      T   &   GetAt(int   position)   const;     
      void   SetAt(int   pos,   const   T   &   newElement);   
      void   RemoveAt(int   position);   
      
      //   Insertion   Methods   
      int   InsertBefore(int   position,const   T   &   newElement);   
      int   InsertAfter(int   position,   const   T   &   newElement);   
      
      //   Searching   Methods   
      int   Find(const   T   &   searchValue,   int   startAfter   =   1)   const;   
      
      //   Status   Methods   
      int   GetCount(void)   const;   
      int   GetSize(void)   const;   
      bool   IsEmpty(void)   const;   
};   

//////////////////////////////////////////////////////////////////////   
//實(shí)現(xiàn)部分代碼
//////////////////

//1.構(gòu)造：初始化列表
template   <class   T>   
CDList<T>::CDList():m_phead(NULL),   m_ptail(NULL),   m_count(0)   
{   
}   
//2.析構(gòu)
template   <class   T>   
CDList<T>::~CDList()   
{   
    RemoveAll();   
}   

//3.   獲取頭結(jié)點(diǎn)的值   
template   <class   T>   
T   &   CDList<T>::GetHead(void)   const   
{   
    assert(m_phead   !=   NULL);   
    return   m_phead->data;   
}   

//4.   獲取尾結(jié)點(diǎn)的值   
template   <class   T>   
T   &   CDList<T>::GetTail(void)   const   
{   
    assert(m_ptail   !=   NULL);   
    return   m_ptail->data;   
}   

// 5.  刪除頭結(jié)點(diǎn)   
template   <class   T>   
void   CDList<T>::RemoveHead(void)   
{   
    if(m_phead   !=   NULL)   //   鏈表不為空   
    {   
        CDListNode<T>   *pRemove;   
        pRemove=m_phead;
        if(pRemove->next   ==   NULL)   // 只有一個(gè)結(jié)點(diǎn)   
            m_phead   =   m_ptail   =   NULL;   
        else   
        {   
            m_phead   =   m_phead->next;   
            m_phead->previous   =   NULL;   
        }   
        
        delete   pRemove;//回收資源   
        m_count--;   
    }   
}   

// 6.  刪除尾結(jié)點(diǎn)   
template   <class   T>   
void   CDList<T>::RemoveTail(void)   
{   
    if(m_ptail   !=   NULL)   //   鏈表不為空   
    {   
        CDListNode<T>   *pRemove;   
        pRemove   =   m_ptail;   
        
        if(pRemove->previous   ==   NULL)   //   只有一個(gè)結(jié)點(diǎn)   
            m_phead   =   m_ptail   =   NULL;   
        else   
        {   
            m_ptail   =   m_ptail->previous;   
            m_ptail->next   =   NULL;   
        }   
        
        delete   pRemove;   
        m_count--;   
    }   
}   

//7.  從鏈表頭部插入結(jié)點(diǎn)   
template   <class   T>   
int   CDList<T>::AddHead(const   T   &   NewNode)   
{   
    CDListNode<T>   *p;   
    p   =   new   CDListNode<T>;   
    p->data   =   NewNode;   
    p->previous   =   NULL;   
    
    if(m_phead   ==   NULL)   //   鏈表為空   
    {   
        p->next   =   NULL;   
        m_ptail   =   p;   
    }   
    else   
    {   
        p->next   =   m_phead;   
        m_phead->previous   =   p;   
    }   
    m_phead   =   p;   
    m_count++;   
    
    return   1;   
}   

// 8.  從鏈表尾部插入結(jié)點(diǎn)   
template   <class   T>   
int   CDList<T>::AddTail(const   T   &   NewNode)   
{   
    CDListNode<T>   *p;   
    p   =   new   CDListNode<T>;   
    p->data   =   NewNode;   
    
    p->next   =   NULL;   
    if(m_ptail   ==   NULL) //   鏈表為空   
    {   
        p->previous   =   NULL;   
        m_phead   =   p;   
    }   
    else   
    {   
        p->previous   =   m_ptail;   
        m_ptail->next   =   p;   
    }   
    m_ptail   =   p;   
    m_count++;   
    
    return   m_count;   
}   

//9.   刪除所有結(jié)點(diǎn)   
template   <class   T>   
void   CDList<T>::RemoveAll(void)   
{   
    CDListNode<T>   *p   =   m_phead;   
    while   (m_phead   !=   NULL)   
    {   
        m_phead   =   m_phead->next;   
        delete   p;   
        p   =   m_phead;   
        m_count--;   
    }   
    m_ptail   =   NULL;   
}     

// 10.  獲取頭結(jié)點(diǎn)位置   
template   <class   T>   
int   CDList<T>::GetHeadPosition(void)   const   
{   
    
    return   (m_count!=0)   ?   1   :   0;   
}   

//  11. 獲取尾結(jié)點(diǎn)位置   
template   <class   T>   
int   CDList<T>::GetTailPosition(void)   const   
{   
    return   m_count;   
}   

// 12. 獲取某結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)值   
template   <class   T>   
T   &   CDList<T>::GetNext(int   position)   const   
{   
    return   GetAt(position+1);   
}     

// 13.  獲取某結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)值   
template   <class   T>   
T   &   CDList<T>::GetPrev(int   position)   const   
{   
    return   GetAt(position-1);   
}   

//14.  獲取結(jié)點(diǎn)值   
template   <class   T>   
T   &   CDList<T>::GetAt(int   position)   const   
{   
    assert((position>0)   &&   (position<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    for(int   i=1;i<position;i++)   //   定位結(jié)點(diǎn)   
    {   
        p   =   p->next;   
    }   
    return   p->data;   
}   

//15.  修改結(jié)點(diǎn)值   
template   <class   T>   
void   CDList<T>::SetAt(int   pos,   const   T   &   newElement)   
{   
    assert((pos>0)   &&   (pos<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    for(int   i=1;   i<pos;   i++)   
    {   
        p   =   p->next;   
    }   
    p->data   =   newElement;   
}   

// 16.  刪除結(jié)點(diǎn)   
template   <class   T>   
void   CDList<T>::RemoveAt(int   position)   
{   
    assert((position>0)   &&   (position<=m_count));   
    
    CDListNode<T>   *pRemove   =   m_phead;   
    for   (int   i=1;   i<position;   i++)   //   定位結(jié)點(diǎn)   
    {   
        pRemove   =   pRemove->next;   
    }   
    
    if   (pRemove->previous   ==   NULL)   //   如果是頭結(jié)點(diǎn)   
    {   
        RemoveHead();   
        return;   
    }   
    
    if   (pRemove->next   ==   NULL)   //   如果是尾結(jié)點(diǎn)   
    {   
        RemoveTail();   
        return;   
    }   
    
    CDListNode<T>   *p;   
    p   =   pRemove->previous;   
    p->next   =   pRemove->next;   
    pRemove->next->previous   =   p;   
    
    delete   pRemove;   
    m_count--;   
}   

//17.  在某個(gè)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)   
template   <class   T>   
int   CDList<T>::InsertBefore(int   position,   const   T   &   newElement)   
{   
    assert((position>0)   &&   (position<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    for   (int   i=1;   i<position;   i++)   //   定位結(jié)點(diǎn)   
    {   
        p   =   p->next;   
    }   
    
    //   在頭結(jié)點(diǎn)前插入新結(jié)點(diǎn)   
    if   (p->previous   ==   NULL)   return   AddHead(newElement);   
    
    CDListNode<T>   *pNewNode;   
    pNewNode   =   new   CDListNode<T>;   
    pNewNode->data   =   newElement;   
    
    pNewNode->previous   =   p->previous;   
    pNewNode->next   =   p;   
    p->previous->next   =   pNewNode;   
    p->previous   =   pNewNode;   
    
    m_count++;   
    return   i;   
}   

// 18.  在某個(gè)結(jié)點(diǎn)之后插入新結(jié)點(diǎn)   
template   <class   T>   
int   CDList<T>::InsertAfter(int   position,   const   T   &   newElement   )   
{   
    assert((position>0)   &&   (position<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    for(int   i=1;   i<position;   i++)   //   定位結(jié)點(diǎn)   
    {   
        p   =   p->next;   
    }   
    
    //   在尾結(jié)點(diǎn)后插入新結(jié)點(diǎn)   
    if   (p->next   ==   NULL)   return   AddTail(newElement);   
    
    CDListNode<T>   *pNewNode;   
    pNewNode   =   new   CDListNode<T>;   
    pNewNode->data   =   newElement;   
    
    pNewNode->previous   =   p;   
    pNewNode->next   =   p->next;   
    p->next->previous   =   pNewNode;   
    p->next   =   pNewNode;   
    
    m_count++;   
    return   i+1;   
}   

// 19.  在鏈表中查找結(jié)點(diǎn)   
template   <class   T>   
int   CDList<T>::Find(const   T   &   searchValue,   int   startAfter)   const   
{   
    assert((startAfter>0)   &&   (startAfter<=m_count));   
    
    CDListNode<T>   *p   =   m_phead;   
    int   i;   
    
    //   從startAfter所指的結(jié)點(diǎn)向后查找   
    for(i=1;   i<startAfter;   i++)   p=p->next;   
    
    while   (p   !=   NULL)   
    {   
        //   返回結(jié)點(diǎn)在鏈表中的位置，第一個(gè)結(jié)點(diǎn)為1   
        if   (p->data   ==   searchValue)   return   i+1;     
        p   =   p->next;   
        i++;   
    }   
    
    return   0;   //   沒有找到   
}   

//20.   獲取鏈表結(jié)點(diǎn)個(gè)數(shù)   
template   <class   T>   
int   CDList<T>::GetCount(void)   const   
{   
    return   m_count;   
}   

//21.   獲取鏈表結(jié)點(diǎn)個(gè)數(shù)   
template   <class   T>   
int   CDList<T>::GetSize(void)   const   
{   
    return   m_count;   
}   

// 22. 判斷鏈表是否為空   
template   <class   T>   
bool   CDList<T>::IsEmpty(void)   const   
{   
    return   (m_count   ==   0)   ?   true   :   false;   
}   

 //23. 顯示鏈表結(jié)點(diǎn)元素    優(yōu)點(diǎn)之一
template   <class   T>   
void   CDList<T>::show(void)   
{   
    CDListNode<T>   *p;   
    
    cout<<"當(dāng)前鏈表共有結(jié)點(diǎn)："<<GetCount()<<"個(gè)";   
    cout<<endl<<"結(jié)點(diǎn)順序列表如下：";   
    p   =   m_phead;   
    while(p   !=   NULL)   
    {   
        cout<<"     "<<   p->data;   
        p   =   p->next;   
    }   
    
    cout<<endl<<"結(jié)點(diǎn)逆序列表如下：";   
    p   =   m_ptail;   
    while   (p   !=   NULL)   
    {   
        cout<<"     "<<   p->data;   
        p   =   p->previous;   
    }   
    cout<<endl<<endl;   
}   

#endif