C++双向循环列表用法实例

本文实例讲述了C++双向循环列表用法。分享给大家供大家参考。具体如下：

/*
 双向循环链表
*/
#include <iostream>
using namespace std;
//结构体构造链表的指针域和数据域
struct ChainNode
{
 int data; //节点数据
 ChainNode *left; //节点的前驱指针
 ChainNode *right; //节点的后继指针
};
////////////创建n个双向循环链表 并返回链表头指针/////////
ChainNode* CreateNode(int n)
{
 ChainNode *head = NULL; //链表头节点
 ChainNode *pCur=NULL,*pNew=NULL; //当前节点，新建节点
 //初始化头结点的前驱和后继节点都为NULL
 if (n<1) //没有节点 返回头节点
 {
  return head;
 }
 //创建头节点并将器左右指针指向空
 head = new ChainNode;
 head->left = NULL;
 head->right = NULL;
 head->data = 0;
 pCur = head;
 //为防止指针互指带来的混乱，用pCur节点保存了头节点 也表示当前指针移动到了头指针
 //创建n个节点 并连接成链表
 for (int i=0; i<n; i++)
 {
  pNew = new ChainNode; //创建一个新节点
  cout<<"请输入数据：";
  cin>>pNew->data;
  pCur->right = pNew; //头指针的右指针指向新建节点
  pNew->left = pCur; //新建节点的左指针执行头节点
  pNew->right = NULL; //用于最后和头指针进行交换
  pCur = pNew; //指针往下移动
 }
 //最后将头指针的左指针指向最后一个节点，
 //最后一个节点的有指针指向头指针，构成循环
 head->left = pCur;
 pCur->right = head;
 return head;
}
//////////////输出链表头节点///////////////////////
void OutList(ChainNode *head) //参数为头指针 从头指针开始
{
  cout<<"链表元素输出如下："<<endl;
  ChainNode *pCur = head->right;
  //重第一个节点开始输出
  //没有指向空节点，则链表没结束 输出链表元素
  while (pCur->right != head)
  {
   cout<<pCur->data<<" ";
   pCur = pCur->right;
   //当前节点指向下一个节点 可以遍历链表
  }
  cout<<pCur->data<<endl;
  //输入最后一个元素，它的右指针执行head
}
///////在双向循环链表后添加n个节点//////
ChainNode* AddNode(ChainNode* head, int n)
{
 ChainNode *pNew,*pCur;
 //新添加节点和当前节点
 pCur = head;
 //移动到最节点
 while (pCur->right != head)
 {
   pCur = pCur->right;
   //当前节点往下移动 一直移到最后一个节点
 }
 //新添加n个节点并插入链表
 for (int i=0; i<n; i++)
 {
  pNew = new ChainNode;
  cout<<"输入要添加的节点元素：";
  cin>>pNew->data;
  pCur->right = pNew; //头指针的右指针指向新建节点
  pNew->left = pCur; //新建节点的左指针执行头节点
  pNew->right = NULL; //用于最后和头指针进行交换
  pCur = pNew; //指针往下移动
 }
 //最后将头指针的左指针指向最后一个节点，
 //最后一个节点的有指针指向头指针，构成循环
 head->left = pCur;
 pCur->right = head;
 return head;
}
/////在双向循环链表中删除一个节点///////
ChainNode* DeleteNode(ChainNode* head, unsigned num)
//删除第num个节点
{
 ChainNode *pNew,*pCur,*temp;
 //新添加节点和当前节点 ,临时交换节点
 pCur = head;
 int ncount = 0;
 //移动到第num-1个节点
 while (1)
 {
   ncount++;
   pCur = pCur->right; //当前节点往下移动
   if (num == ncount)
   {
    break; //此时pCur还是指向了第num个节点
   }
 }
 //当前节点的前一个节点的右指针 指向 当前节点的下一个节点
 //当前节点的下一个节点的左指针 指向 当前节点的上一个节点 构成连接
 //最后 删除当前节点
 (pCur->left)->right = pCur->right;
 (pCur->right)->left = pCur->left;
 delete pCur;
 return head;
}
int main()
{
 int num;
 //创建num个节点并显示
 cout<<"输入要创建的链表节点个数:";
 cin>>num;
 ChainNode *head = CreateNode(num);
 OutList(head);
 //往链表后添加n个节点
 int addnum;
 cout<<"输入要添加的节点个数:";
 cin>>addnum;
 AddNode(head, addnum);
 OutList(head);
 //删除链表的第del个元素
 int del;
 cout<<"输入要删除的第几个位置的节点:";
 cin>>del;
 DeleteNode (head, del);
 OutList(head);
 system("pause");
 return 0;
}

希望本文所述对大家的C++程序设计有所帮助。