C++ 实现双向链表的实例

双向链表C++ 的实现    

               本文是通过C++ 的知识实现数据结构中的双向链表，这里不多说 了，代码注释很清楚，

实现代码：

//double LinkList implement with C++ template
#include<iostream>
using namespace std;
/*template<typename Type>
class DBListADT
{
   public:
       virtual void Append(const Type &)=0;
       virtual void Insert(const Type &)=0;
       virtual void Remove(const Type &)=0;
};
template<typename T>
class DLinkListNode:public DBListADT<typename T>//此处必须为实现的类型，当然以派生类的模板类型也可以，但是不能是Type
{
   public:
       void Append(const T &);//这边也需要是当前类的类型,不能为Type
       void Insert(const T &);
       void Remove(const T &);


};*/
template<typename T>class DLinkList;
template<typename Type>
class DNode
{
       friend class DLinkList<Type>;//指定前需声明
   public:
       DNode(){next=NULL;prior=NULL;}
       ~DNode(){}
   private:
       DNode *next;
     DNode *prior;
       Type data;
};
template<typename T>
class DLinkList
{
  public:
       DLinkList()
       {
       //   head=new DNode<T>[sizeof(DNode<T>)];
          head=new DNode<T>;
       }
       ~DLinkList()
       {
          if(head->next==NULL)
              delete head;
          else
          {
              DNode<T> *p=head->next;
              DNode<T>*s=NULL;
              while(p)
              {
                 s=p->next ;
                 delete p;
                 p=s;
              }
          }
       }
       void DeleteElement(size_t position)
       {
          DNode<T> *p=head->next;
          size_t index=1;
          for(;index<position;index++)
              p=p->next ;
          if(p==NULL)
              return ;
          p->prior ->next =p->next ;
          p->next ->prior =p->prior ;
          delete p;
       }
       void InsertElement(T data,size_t position);
       void CreateDLinkList(T a[],int n);
       void PrintDLinkList();
   private:
       DNode<T> *head;

};
template<typename T> void DLinkList<T>:: InsertElement (T data,size_t position)
{
 DNode<T> *p=head->next;
 size_t index=1;
 for(;index<position;index++)
     p=p->next;
 if(p==NULL)
     return;
 //DNode<T> *s=new DNode<T>[sizeof(DNode<T>)];
 DNode<T> *s=new DNode<T>;
 s->data=data;
 s->next=p;
 s->prior=p->prior;
 p->prior->next=s;
 p->prior=s;
}
template<typename T> void DLinkList<T>::CreateDLinkList(T a[],int n)
{
 DNode<T>*p=head;
 DNode<T>*s=NULL;
 int i=0;
 for(;i<n;i++)
 {
   // s=new DNode<T>[sizeof(DNode)];
     s=new DNode<T>;
       s->data=a[i];
       p->next=s;
       s->prior=p;
       p=s;
 }
 s->next=NULL;
}
template<typename T>void DLinkList<T>::PrintDLinkList ()
{
   DNode<T> *p=head->next;
   while(p)
   {
       cout<<p->data<<endl;
       p=p->next;
   }
}
int main()
{
  int a[10]={1,2,3,4,5,6,7,8,9,10};
   DLinkList<int>Dlist;
   Dlist.CreateDLinkList(a,10);
   Dlist.DeleteElement (3);
   Dlist.InsertElement(3,3);
   Dlist.PrintDLinkList();
   return 0;
}
//double LinkList implement with C++ Class
//************************************************************
/*#include<iostream>
using namespace std;
class Node
{
   friend class List;
public:
  //Node(int a):next(NULL),prior(NULL),data(a){}
   Node(){}
private:
  Node *next;
   Node *prior;
   int data;
};
class List
{
public:
   List()
   {
       cout<<"create head DBLinkList"<<endl;
       head=new Node[sizeof(Node)];
   };
   ~List()
   {
   if(head->next==NULL)
     {
        delete head;
     }
     else
     {
        Node *p=head->next;
        Node *s;
        delete head;
        while(p)
        {
            s=p->next ;
            delete p;
            p=s;
        }
     }
     cout<<"destructor called to clear DBLinkList"<<endl;
   }
   void CreateDoubleLink(int a[],int n);
   void DeleteElemData(int position);
   void InsertElement(int data,int position);
   void PrintDList();
private:
   Node *head;
};
void List::CreateDoubleLink (int a[],int n)
{

  head->next =NULL;
   Node *s,*p=head;
   int i=0;
   for(;i<n;i++)
   {
    s=new Node[sizeof(Node)];
       s->data =a[i];
       p->next =s;
       s->prior =p;
       p=s;
   }
   s->next =NULL;
}
void List::PrintDList()
{
   Node *p=head->next ;
   while(p)
   {
       cout<<p->data <<endl;
       p=p->next ;
   }
}
void List::DeleteElemData(int position)
{//可以通过重载delete运算符来达到这个效果，则直接用delete就OK了
  Node *p=head->next ;
   //while(p!=NULL&&p->data !=data)
   //   p=p->next ;
   int i=1;
   for(;i<position;i++)
       p=p->next ;
   if(p==NULL)
       return ;
   p->prior ->next =p->next ;
   p->next ->prior =p->prior ;
   delete p;
}
void List::InsertElement (int data,int position)
{//可以重载new运算符来达到这个效果，则直接用new就OK了
  Node *p=head->next ;
   int i=1;
   for(;i<position;i++)
       p=p->next ;
   Node *s=new Node[sizeof(Node)];
   s->data =data;
   s->prior =p->prior ;
   s->next =p;
   p->prior ->next =s;
   p->prior =s;
}
int main()
{
   List Dlist;
   int a[10]={1,2,3,4,5,6,7,8,9,10};
   Dlist.CreateDoubleLink (a,10);
   Dlist.DeleteElemData(3);
   Dlist.InsertElement (3,3);
   Dlist.PrintDList ();
   return 0;
}*/
//*************************************************************************************

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

原文链接：http://blog.csdn.net/typename/article/details/6111728