///////////////////////////////////////////////////////
//   模块名: 双向链表模板实现   
//   研究者: 长寿梦
//   最后更新:2010-05-05 
//////////////////////////////////////////////////////
#ifndef   DLIST_H   
#define   DLIST_H   

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

template   
<class   T>   class   CDList; 
  
//一:节点类
template   <class   T>   
class   CDListNode   
{   
  
public:   
      friend   CDList
<T>;//节点的友元是链表
  private:   
      T   data;   
//数据域 
      CDListNode<T>   *   previous; //前一个  
      CDListNode<T>   *   next;  //下一个 
}

  
//二:链表类
template   <class   T>   
class   CDList   
{   
  
private:   
      CDListNode
<T>   *   m_phead;  //
      CDListNode<T>   *   m_ptail;   //
      int m_count; //节点个数  
      
  
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;   
}
;   

//////////////////////////////////////////////////////////////////////   
//实现部分代码
//////////////////

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

//3.   获取头结点的值   
template   <class   T>   
T   
&   CDList<T>::GetHead(void)   const   
{   
    assert(m_phead   
!=   NULL);   
    
return   m_phead->data;   
}
   

//4.   获取尾结点的值   
template   <class   T>   
T   
&   CDList<T>::GetTail(void)   const   
{   
    assert(m_ptail   
!=   NULL);   
    
return   m_ptail->data;   
}
   

// 5.  删除头结点   
template   <class   T>   
void   CDList<T>::RemoveHead(void)   
{   
    
if(m_phead   !=   NULL)   //   链表不为空   
    {   
        CDListNode
<T>   *pRemove;   
        pRemove
=m_phead;
        
if(pRemove->next   ==   NULL)   // 只有一个结点   
            m_phead   =   m_ptail   =   NULL;   
        
else   
        
{   
            m_phead   
=   m_phead->next;   
            m_phead
->previous   =   NULL;   
        }
   
        
        delete   pRemove;
//回收资源   
        m_count--;   
    }
   
}
   

// 6.  删除尾结点   
template   <class   T>   
void   CDList<T>::RemoveTail(void)   
{   
    
if(m_ptail   !=   NULL)   //   链表不为空   
    {   
        CDListNode
<T>   *pRemove;   
        pRemove   
=   m_ptail;   
        
        
if(pRemove->previous   ==   NULL)   //   只有一个结点   
            m_phead   =   m_ptail   =   NULL;   
        
else   
        
{   
            m_ptail   
=   m_ptail->previous;   
            m_ptail
->next   =   NULL;   
        }
   
        
        delete   pRemove;   
        m_count
--;   
    }
   
}
   

//7.  从链表头部插入结点   
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.  从链表尾部插入结点   
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.   删除所有结点   
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.  获取头结点位置   
template   <class   T>   
int   CDList<T>::GetHeadPosition(void)   const   
{   
    
    
return   (m_count!=0)   ?   1   :   0;   
}
   

//  11. 获取尾结点位置   
template   <class   T>   
int   CDList<T>::GetTailPosition(void)   const   
{   
    
return   m_count;   
}
   

// 12. 获取某结点的后一个结点值   
template   <class   T>   
T   
&   CDList<T>::GetNext(int   position)   const   
{   
    
return   GetAt(position+1);   
}
     

// 13.  获取某结点的前一个结点值   
template   <class   T>   
T   
&   CDList<T>::GetPrev(int   position)   const   
{   
    
return   GetAt(position-1);   
}
   

//14.  获取结点值   
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++)   //   定位结点   
    {   
        p   
=   p->next;   
    }
   
    
return   p->data;   
}
   

//15.  修改结点值   
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.  删除结点   
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++)   //   定位结点   
    {   
        pRemove   
=   pRemove->next;   
    }
   
    
    
if   (pRemove->previous   ==   NULL)   //   如果是头结点   
    {   
        RemoveHead();   
        
return;   
    }
   
    
    
if   (pRemove->next   ==   NULL)   //   如果是尾结点   
    {   
        RemoveTail();   
        
return;   
    }
   
    
    CDListNode
<T>   *p;   
    p   
=   pRemove->previous;   
    p
->next   =   pRemove->next;   
    pRemove
->next->previous   =   p;   
    
    delete   pRemove;   
    m_count
--;   
}
   

//17.  在某个结点之前插入新结点   
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++)   //   定位结点   
    {   
        p   
=   p->next;   
    }
   
    
    
//   在头结点前插入新结点   
    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.  在某个结点之后插入新结点   
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++)   //   定位结点   
    {   
        p   
=   p->next;   
    }
   
    
    
//   在尾结点后插入新结点   
    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.  在链表中查找结点   
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所指的结点向后查找   
    for(i=1;   i<startAfter;   i++)   p=p->next;   
    
    
while   (p   !=   NULL)   
    
{   
        
//   返回结点在链表中的位置,第一个结点为1   
        if   (p->data   ==   searchValue)   return   i+1;     
        p   
=   p->next;   
        i
++;   
    }
   
    
    
return   0;   //   没有找到   
}
   

//20.   获取链表结点个数   
template   <class   T>   
int   CDList<T>::GetCount(void)   const   
{   
    
return   m_count;   
}
   

//21.   获取链表结点个数   
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. 显示链表结点元素    优点之一
template   <class   T>   
void   CDList<T>::show(void)   
{   
    CDListNode
<T>   *p;   
    
    cout
<<"当前链表共有结点:"<<GetCount()<<"";   
    cout
<<endl<<"结点顺序列表如下:";   
    p   
=   m_phead;   
    
while(p   !=   NULL)   
    
{   
        cout
<<"     "<<   p->data;   
        p   
=   p->next;   
    }
   
    
    cout
<<endl<<"结点逆序列表如下:";   
    p   
=   m_ptail;   
    
while   (p   !=   NULL)   
    
{   
        cout
<<"     "<<   p->data;   
        p   
=   p->previous;   
    }
   
    cout
<<endl<<endl;   
}
   

#endif