/* 
 雙向循環(huán)鏈表 
*/
#include <iostream>
using namespace std;
//結(jié)構(gòu)體構(gòu)造鏈表的指針域和數(shù)據(jù)域
struct ChainNode
{
 int data; //節(jié)點(diǎn)數(shù)據(jù) 
 ChainNode *left; //節(jié)點(diǎn)的前驅(qū)指針
 ChainNode *right; //節(jié)點(diǎn)的后繼指針 
};
////////////創(chuàng)建n個(gè)雙向循環(huán)鏈表 并返回鏈表頭指針///////// 
ChainNode* CreateNode(int n)
{
 ChainNode *head = NULL; //鏈表頭節(jié)點(diǎn)
 ChainNode *pCur=NULL,*pNew=NULL; //當(dāng)前節(jié)點(diǎn)，新建節(jié)點(diǎn)
 //初始化頭結(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)都為NULL 
 if (n<1) //沒(méi)有節(jié)點(diǎn) 返回頭節(jié)點(diǎn) 
 {
  return head; 
 } 
 //創(chuàng)建頭節(jié)點(diǎn)并將器左右指針指向空 
 head = new ChainNode; 
 head->left = NULL;
 head->right = NULL; 
 head->data = 0;
 pCur = head;
 //為防止指針互指帶來(lái)的混亂，用pCur節(jié)點(diǎn)保存了頭節(jié)點(diǎn) 也表示當(dāng)前指針移動(dòng)到了頭指針 
 //創(chuàng)建n個(gè)節(jié)點(diǎn) 并連接成鏈表 
 for (int i=0; i<n; i++)
 {
  pNew = new ChainNode; //創(chuàng)建一個(gè)新節(jié)點(diǎn)
  cout<<"請(qǐng)輸入數(shù)據(jù)：";
  cin>>pNew->data;
  pCur->right = pNew; //頭指針的右指針指向新建節(jié)點(diǎn) 
  pNew->left = pCur; //新建節(jié)點(diǎn)的左指針執(zhí)行頭節(jié)點(diǎn) 
  pNew->right = NULL; //用于最后和頭指針進(jìn)行交換 
  pCur = pNew; //指針往下移動(dòng) 
 } 
 //最后將頭指針的左指針指向最后一個(gè)節(jié)點(diǎn)，
 //最后一個(gè)節(jié)點(diǎn)的有指針指向頭指針，構(gòu)成循環(huán) 
 head->left = pCur; 
 pCur->right = head;
 return head; 
}
//////////////輸出鏈表頭節(jié)點(diǎn)/////////////////////// 
void OutList(ChainNode *head) //參數(shù)為頭指針 從頭指針開(kāi)始 
{
  cout<<"鏈表元素輸出如下："<<endl;
  ChainNode *pCur = head->right;
  //重第一個(gè)節(jié)點(diǎn)開(kāi)始輸出 
  //沒(méi)有指向空節(jié)點(diǎn)，則鏈表沒(méi)結(jié)束 輸出鏈表元素 
  while (pCur->right != head)  
  {
   cout<<pCur->data<<" ";
   pCur = pCur->right;
   //當(dāng)前節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn) 可以遍歷鏈表 
  } 
  cout<<pCur->data<<endl;
  //輸入最后一個(gè)元素，它的右指針執(zhí)行head 
}
///////在雙向循環(huán)鏈表后添加n個(gè)節(jié)點(diǎn)//////
ChainNode* AddNode(ChainNode* head, int n)
{
 ChainNode *pNew,*pCur;
 //新添加節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)
 pCur = head; 
 //移動(dòng)到最節(jié)點(diǎn)
 while (pCur->right != head) 
 {
   pCur = pCur->right;
   //當(dāng)前節(jié)點(diǎn)往下移動(dòng) 一直移到最后一個(gè)節(jié)點(diǎn) 
 }
 //新添加n個(gè)節(jié)點(diǎn)并插入鏈表
 for (int i=0; i<n; i++)
 {
  pNew = new ChainNode;
  cout<<"輸入要添加的節(jié)點(diǎn)元素：";
  cin>>pNew->data;
  pCur->right = pNew; //頭指針的右指針指向新建節(jié)點(diǎn) 
  pNew->left = pCur; //新建節(jié)點(diǎn)的左指針執(zhí)行頭節(jié)點(diǎn) 
  pNew->right = NULL; //用于最后和頭指針進(jìn)行交換 
  pCur = pNew; //指針往下移動(dòng) 
 } 
 //最后將頭指針的左指針指向最后一個(gè)節(jié)點(diǎn)，
 //最后一個(gè)節(jié)點(diǎn)的有指針指向頭指針，構(gòu)成循環(huán) 
 head->left = pCur; 
 pCur->right = head;
 return head; 
} 
/////在雙向循環(huán)鏈表中刪除一個(gè)節(jié)點(diǎn)/////// 
ChainNode* DeleteNode(ChainNode* head, unsigned num)
//刪除第num個(gè)節(jié)點(diǎn)
{
 ChainNode *pNew,*pCur,*temp;
 //新添加節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn) ,臨時(shí)交換節(jié)點(diǎn) 
 pCur = head; 
 int ncount = 0; 
 //移動(dòng)到第num-1個(gè)節(jié)點(diǎn)
 while (1)
 {
   ncount++;
   pCur = pCur->right; //當(dāng)前節(jié)點(diǎn)往下移動(dòng) 
   if (num == ncount)
   {
    break; //此時(shí)pCur還是指向了第num個(gè)節(jié)點(diǎn) 
   } 
 }
 //當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的右指針 指向 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
 //當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的左指針 指向 當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn) 構(gòu)成連接
 //最后 刪除當(dāng)前節(jié)點(diǎn) 
 (pCur->left)->right = pCur->right;
 (pCur->right)->left = pCur->left;
 delete pCur;
 return head; 
}
int main()
{
 int num;
 //創(chuàng)建num個(gè)節(jié)點(diǎn)并顯示 
 cout<<"輸入要?jiǎng)?chuàng)建的鏈表節(jié)點(diǎn)個(gè)數(shù):";
 cin>>num;
 ChainNode *head = CreateNode(num);
 OutList(head); 
 //往鏈表后添加n個(gè)節(jié)點(diǎn)
 int addnum;
 cout<<"輸入要添加的節(jié)點(diǎn)個(gè)數(shù):";
 cin>>addnum; 
 AddNode(head, addnum);
 OutList(head); 
 //刪除鏈表的第del個(gè)元素
 int del;
 cout<<"輸入要?jiǎng)h除的第幾個(gè)位置的節(jié)點(diǎn):";
 cin>>del;
 DeleteNode (head, del);
 OutList(head);
 system("pause");
 return 0;
}