lianbiao2.cpp

链表的例程 一种模版 用指针c++实现的一种源程序

 //   List.h:   interface   for   the   CList   class.   
  //   
  //////////////////////////////////////////////////////////////////////   
    
  #include   "Trace.h"   
    
  #if   !defined(AFX_LIST_H__9BAE9A88_3C1E_4BE5_A347_293DB317A031__INCLUDED_)   
  #define   AFX_LIST_H__9BAE9A88_3C1E_4BE5_A347_293DB317A031__INCLUDED_   
    
  #if   _MSC_VER   >   1000   
  #pragma   once   
  #endif   //   _MSC_VER   >   1000   
    
  ////////////////////////////////////////////////////////////////////////   
  //   
  // CNode存储链表中的一个接点   
    
  template   <class   T>   
  class   CNode   
  {   
  public:   
  CNode();   
  CNode(T   _t);   
  ~CNode()   ;   
  CNode<T>   *   next;   
  CNode<T>   *   prev;   
  T   val;   
  };   
    
    
  ////////////////////////////////////////////////////////////////////////   
  //   
  // 链表类申明   
    
  template   <class   T,class   H   =   CNode<T>   > //T为LIST存储元素的类型   
  class   CList //H为LIST中头接点类型   
  {   
  public:   
  friend   class   iterator;   
    
  CList();   
    
  ~CList()   ;   
    
  inline   bool   PushFront(T   n);   
  inline   T   PopFront();   
  inline   bool   PushBack(T   n);   
  inline   T   PopBack();   
  bool   RemoveAll();   
    
  class   iterator   {   
  public:   
  iterator():pNode(NULL)   {};   
  iterator(H   *   p):pNode(p)   {};   
  ~iterator()   {};   
  iterator   (const   iterator   &   it):pNode(it.pNode)   {};   
  inline   const   iterator   &   operator   ++   ()   {   
  pNode   =   pNode->next;   
  return   *this;   
  };   
  inline   const   iterator   operator   ++   (int)   {   
  const   iterator   temp   =   *this;   
  pNode   =   pNode->next;   
  return   temp;   
  };   
  inline   bool   operator   ==   (iterator   &   p)   {   
  return   (pNode   ==   p.pNode);   
  };   
  inline   bool   operator   !=   (iterator   &   p)   {   
  return   (pNode   !=   p.pNode);   
  };   
  inline   T   &   operator   *   ()   {   
  return   (pNode->val);   
  };   
  inline   void   del()   {   
  if   (pNode)   
  delete   pNode;   
  };   
  inline   H   *   next()   {return   pNode->next;};   
  inline   H   *   prev()   {return   pNode->prev;}   
  inline   operator   H*   (){return   pNode;}   
  protected:   
  H   *   pNode;   
  };   
    
  inline   iterator   begin()   ;   
  inline   iterator   end();   
  inline   iterator   find(const   T   &   n);   
  inline   iterator   erase(iterator   p);   
  protected:   
  ULONG   m_nSize;   
  H   *   m_pHead;   
  };   
    
    
  template   <class   T>   
  CNode<T>::~CNode()   
  {   
  }   
    
  template   <class   T>   
  CNode<T>::CNode():next(NULL),prev(NULL)   {   
  // t<<"CNode::CNode()\n";   
  }   
    
  template   <class   T>   
  CNode<T>::CNode(T   _t):val(_t),next(NULL),prev(NULL)   {   
  // t<<"CNode::CNode(T   t)\n";   
  }   
    
  template   <class   T,   class   H>   
  CList<T,H>::CList():m_nSize(0),m_pHead(new   H)   {   //预置一头接点   
  // t<<"CList::CList\n";   
  m_pHead->next   =   m_pHead;   
  m_pHead->prev   =   m_pHead;   
  }   
    
  template   <class   T,   class   H>   
  CList<T,H>::~CList()   {   
  H   *   p1   =   m_pHead->next,*p2;   
  while   (p1!=m_pHead)   
  {   
  p2   =   p1->next;   
  delete   p1;   
  p1   =   p2;   
  }   
  delete   p1;   
  }   
    
  template   <class   T,   class   H>   
  bool   CList<T,H>::PushFront(T   n)   {   
  // t<<"PushFront     "<<&n<<endl;   
  H   *p   =   new   H(n);   
  H   *p1   =   m_pHead->next;   
  p->next   =   p1;   
  p->prev   =   m_pHead;   
  m_pHead->next   =   p;   
  p1->prev   =   p;   
  m_nSize   ++;   
  return   true;   
  }   
    
    
  template   <class   T,   class   H>   
  T   CList<T,H>::PopFront()   {   
  T   n   =   NULL;   
  if   (m_nSize==0)   
  return   n;   
  H   *p   =   m_pHead->next;   
  m_pHead->next   =   p->next;   
  p->next->prev   =   m_pHead;   
  m_nSize   --;   
  // t<<"popfront     "<<&p->val<<endl;   
  n   =   p->val;   
  delete   p;   
  return   n;   
  }   
    
    
  template   <class   T,   class   H>   
  bool   CList<T,H>::PushBack(T   n)   {   
  // t<<"PushBack     "<<&n<<endl;   
  H   *p   =   new   H(n);   
  H   *p1   =   m_pHead->prev;   
  p->next   =   m_pHead;   
  p->prev   =   p1;   
  m_pHead->prev   =   p;   
  p1->next   =   p;   
  m_nSize   ++;   
  return   true;   
  }   
    
    
  template   <class   T,   class   H>   
  T   CList<T,H>::PopBack(){   
  T   n   =   NULL;   
  if   (m_nSize==0)   
  return   n;   
  H   *p   =   m_pHead->prev;   
  p->prev->next   =   p->next;   
  p->next->prev   =   p->prev;   
  m_nSize   --;   
  // t<<"PopBack     "<<&p->val<<endl;   
  n   =   p->val;   
  delete   p;   
  return   n;   
  }   
    
  template   <class   T,   class   H>   
  CList<T,H>::iterator   CList<T,H>::begin()   {   
  iterator   p(m_pHead->next);     
  return   p;   
  }   
    
  template   <class   T,   class   H>   
  CList<T,H>::iterator   CList<T,H>::end()   {   
  iterator   p(m_pHead);     
  return   p;   
  }   
    
  template   <class   T,   class   H>   
  CList<T,H>::iterator   CList<T,H>::find(const   T   &   n)   {   
  iterator   p1   =   begin();   
  iterator   p2   =   end();   
  while   (p1!=p2)   
  if   ((*p1)==n)   
  break;   
  return   p1;   
  }   
    
  template   <class   T,   class   H>   
  CList<T,H>::iterator   CList<T,H>::erase(iterator   p)   {   
  H   *   n   =   p;   
  H   *   n2   =   n->next;   
  n->prev->next   =   n->next;   
  n->next->prev   =   n->prev;   
  delete   n;   
  return   iterator(n2);   
  }   
  #endif   //   !defined(AFX_LIST_H__9BAE9A88_3C1E_4BE5_A347_293DB317A031__INCLUDED_)