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