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

发布时间:2020-10-20 15:53:01 作者:typename
来源:脚本之家 阅读:122

双向链表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; 
}*/ 
//************************************************************************************* 


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

推荐阅读:
  1. C++二叉搜索树与双向链表(剑指Offer精简版)
  2. 常见缓存算法和LRU的c++实现

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++ 双向链表 c+

上一篇:jsp前后端分离后是什么

下一篇:python flask实现分页的示例代码

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》