#include<iostream>
using namespace std;
template<class T>
struct DblNode{
T data;
DblNode<T> *lLink,*rLink;
DblNode(DblNode<T> *l=NULL,DblNode<T> *r=NULL){lLink=l;rLink=r;}
DblNode(T value,DblNode<T> *l=NULL,DblNode<T> *r=NULL){data=value;lLink=l;rLink=r;}
};
template<typename T>
class DblList{
private:
DblNode<T>* first;//头节点
public:
DblList(T uniqueval){
first= new DblNode<T>(uniqueval);
first->rLink=first;
first->lLink=first;//左右都指向自己
}
DblList(DblList<T>& L){
DblNode<T> *p=L.first->rLink;
if(p==NULL)exit(-1);
first= new DblNode<T>;//给新开的链表定义头节点
DblNode<T> *h=first;
while(p!=L.first){
DblNode<T>* t= new DblNode<T>;//给新链表增加新节点，存放被拷贝的链表的数据
h->rLink=t;
t->lLink=h;
t->data=p->data;//插入
p=p->rLink;
h=h->rLink;//向后移动
}
h->rLink=first;
first->lLink=h;//最后一个结点的rLink需要指向头节点，头节点的lLink需要指向最后一个结点，形成双向循环链表
}
~DblList(){
DblNode<T>* cur=first->rLink;
while(cur!=first){
cur->rLink->lLink=cur->lLink;
cur->lLink->rLink=cur->rLink;//删除
delete cur;
cur=first->rLink;
}
delete first;
first=NULL;//头节点也要删除
}
void makeEmpty(){//清空链表
DblNode<T>* cur=first->rLink;
while(cur!=first){
cur->rLink->lLink=cur->lLink;
cur->lLink->rLink=cur->rLink;
delete cur;
cur=first->rLink;
}
first->rLink=first;//最后只剩头节点
}
DblNode<T>* locate(int i,int d){//d为开始搜索的方向，按照方向找第i个节点
if(first==first->rLink||i==0)return first;
DblNode<T>* cur;
if(d==0)cur=first->lLink;
else cur=first->rLink;//d=0按前驱方向，否则按后继方向
for(int j=1;j<i;++j){//之前已经先走一步，之后找第i个节点只用走i-1步，因为d不变，方向一定，从而步数一定
if(cur==first)break;
else if (d==0)cur=cur->lLink;
else cur=cur->rLink;
}
if(cur!=first)return cur;
else return NULL;
}
bool IsEmpty(){
return first->rLink==first;
}
bool Insert(int i,const T& x,int d){//建立含x值的新节点，将其按照d指定的方向插入第i个节点后
DblNode<T>* cur=locate(i,d);
if(cur==NULL)return false;
DblNode<T> *newNd = new DblNode<T>(x);
if(d==0){//插入在第i个节点左侧
newNd->lLink=cur->lLink;//新节点的左边内容是老节点的左边内容
cur->lLink=newNd;//老节点的左边变成新节点
newNd->lLink->rLink=newNd;//新节点的左边一个节点的右边内容变为新节点
newNd->rLink=cur;//新节点右边内容变为老节点
}
else{//插入在第i个节点右侧
newNd->rLink=cur->rLink;//新节点的右边内容是老节点的右边内容
cur->rLink=newNd;//老节点的右边变成新节点
newNd->rLink->lLink=newNd;//新节点的右边一个节点的左边内容变为新节点
newNd->lLink=cur;//新节点左边内容变为老节点
}
return true;
}
bool Remove(int i,int d){
DblNode<T>* cur=locate(i,d);
if(cur==NULL)return false;
cur->lLink->rLink=cur->rLink;//当前节点的左边节点的右边内容 变为 当前节点的右边内容
cur->rLink->lLink=cur->lLink;//当前节点的右边节点的左边内容 变为 当前节点的左边内容
delete cur;//删除已经被孤立的节点
return true;//删除成功
}
void output(int d){//d=0按照前驱方向，否则按照后继方向
DblNode<int>* cur;
if(!d)cur=first->lLink;
else cur=first->rLink;
while(cur!=first){
cout<<cur->data<<" ";
if(!d)cur=cur->lLink;
else cur=cur->rLink;
}
cout<<endl;
}
};
int main()
{
DblList<int>L(1);
L.Insert(0,7,0);
L.Insert(0,8,0);
L.Insert(0,9,0);
L.Insert(1,6,0);
L.output(0);//逆序
L.output(1);//正序
L.makeEmpty();
cout<<endl;
L.Insert(0,9,1);
L.Insert(0,8,1);
L.Insert(0,7,1);
L.Insert(0,6,1);
L.Remove(2,0);
L.output(0);
L.output(1);
int k;
k=L.locate(3,1)->data;
cout<<k<<endl;
DblList<int>L1(L);
L.output(0);
L.output(1);
return 0;
}