#include<iostream.h>
typedef struct DuLNode               //雙向循環鏈表的存儲結構
{ int data;
  struct DuLNode  *prior;
  struct DuLNode  *next;
}DuLNode,*DuLinkList;


int ListLocate_DuL(DuLinkList L,int x)    //在帶頭結點的雙向循環鏈表L中查找與x相等的所有元素的位序
{int i,count=0; DuLinkList p;
p=L->next; i=1;                    //i的初值為第一個元素的位序
                                   //p的初值為第一個結點的位序
cout<<"請輸入您想要查找的整數元素的值:"<<endl;
cin>>x;

while(p!=L&&p->data!=x)         //尋找數據域的值為x的結點
{p=p->next; i++;}
if(p==L){cout<<"Not Found!"<<endl;}  //沒有找到，顯示NOT FOUND
else
{for(p;p!=L;p=p->next)        //從找到的第一個滿足要求的結點起，繼續往后進行尋找滿足要求的其他結點
if(p->data==x)
{cout<<"您要查找的元素存在！它在鏈表中的位置是:"<<i<<endl<<endl<<endl;
i++;count++;}
else i++;
cout<<"您查找到的滿足要求的元素一共有"<<count<<"個"<<endl<<endl<<endl;
}//所有與x相等的元素都已經找到，顯示其所有結點所在的鏈表中的位置


return L,x;
}


int ListInsert_DuL(DuLinkList &L,int i,int e)  //在帶頭結點的雙向循環鏈表L中第i個位置之前插入元素e
{DuLinkList p,s;
p=L->next; int j=0;                           //P的初值得為第一個結點
                                              //j的初值為0
cout<<"請輸入您想要插入的整數元素:";
cin>>e;
cout<<"請輸入您想要插入的位置";
cin>>i;
while(p->next!=L&&j<i-1){p=p->next;++j;}        //尋找第i-1個結點
if(p->next==L||j>i-1)                          //i小于1或者大于表長+1
{cout<<"您插入的位置不合適，請重新輸入";}
else
{s=(DuLinkList)new int(sizeof(DuLNode));          //生成新結點
 s->data=e;                                       //插入L中
 s->prior=p->prior;            
 p->prior->next=s;
 s->next=p;
 p->prior=s;
cout<<"插入完畢后，現在雙向循環鏈表中的數據為:";  //顯示插入完畢后的雙向循環鏈表 
for(p=L->next;p!=L;p=p->next)
cout<<p->data<<"  ";}
cout<<endl<<endl<<endl;
return L,i,e;
}


int ListDelete_DuL(DuLinkList &L, int i, int e)   //在帶頭結點的雙向循環鏈表中刪除第i個元素，并由e返回其值
{DuLinkList p; int j=0;
p=L->next;
cout<<"請輸入您想要刪除的元素的位置:";
cin>>i;
while(p->next!=L&&j<i-1)                     //尋找第i個結點，并令p指向其前驅
{p=p->next; ++j;}
if(p->next==L||j>i-1)
cout<<"您輸入的位置有誤，請重新輸入";        //刪除的位置不合理
else
{e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
delete(p);                          //刪除并釋放結點
 cout<<"刪除已經完成！現在鏈表中的元素為:";
for(p=L->next;p!=L;p=p->next)
cout<<p->data<<"  ";}               //顯示刪除完畢后的雙向循環鏈表
cout<<endl<<endl<<endl;
return L,i,e;
}



main()             //順位序輸入10個元素，建立并顯示雙向循環鏈表
{DuLinkList L;
DuLinkList p;
DuLinkList q;
int x,e;
L=(DuLinkList)new int(sizeof(DuLNode));  //先建立一個帶頭結點的雙向循環鏈表
L->next=L; L->prior=L;
p=L;
cout<<"請輸入任意10個整數:"<<endl;
for(int i=0;i<10;i++)                
{q=(DuLinkList)new int(sizeof(DuLNode));   //生成10個新結點
 p->next=q;                          //插入結點                              
 q->prior=p; 
 p=q;
 cin>>q->data;                      //輸入元素的值
}
p->next=L; L->prior=p;              //建立頭結點后最后一個結點間的雙向循環
cout<<"雙向循環鏈表已經建立成功，現在鏈表中的10個整數分別為:"<<endl;
for(p=L->next;p!=L;p=p->next)
{cout<<p->data<<"  ";}
cout<<endl<<endl;
while(p->next!=L)        //P的下一個結點不為頭結點L時，執行下列操作
{cout<<"請輸入數字1、2、3、4選擇您想要執行的操作"<<endl<<"1、查找"<<endl<<"2、插入"<<endl<<"3、刪除"<<endl<<"4、不需要再執行操作，退出程序"<<endl;
 cout<<"請選擇:";
 int n;
cin>>n;
if(n==1) 
ListLocate_DuL(L,x);       //對雙向循環鏈表執行查找操作
if(n==2)
ListInsert_DuL(L,i,e);     //對雙向循環鏈表執行插入操作
if(n==3)
ListDelete_DuL(L,i,e);     //對雙向循環鏈表執行刪除操作
if(n==4)
return 0;}                 //不再執行任何操作，退出程序
 
}