C++双向循环列表用法实例
本文实例讲述了C++双向循环列表用法。分享给大家供大家参考。具体如下：
/*
双向循环链表
*/
#include<iostream>
usingnamespacestd;
//结构体构造链表的指针域和数据域
structChainNode
{
intdata;//节点数据
ChainNode*left;//节点的前驱指针
ChainNode*right;//节点的后继指针
};
////////////创建n个双向循环链表并返回链表头指针/////////
ChainNode*CreateNode(intn)
{
ChainNode*head=NULL;//链表头节点
ChainNode*pCur=NULL,*pNew=NULL;//当前节点，新建节点
//初始化头结点的前驱和后继节点都为NULL
if(n<1)//没有节点返回头节点
{
returnhead;
}
//创建头节点并将器左右指针指向空
head=newChainNode;
head->left=NULL;
head->right=NULL;
head->data=0;
pCur=head;
//为防止指针互指带来的混乱，用pCur节点保存了头节点也表示当前指针移动到了头指针
//创建n个节点并连接成链表
for(inti=0;i<n;i++)
{
pNew=newChainNode;//创建一个新节点
cout<<"请输入数据：";
cin>>pNew->data;
pCur->right=pNew;//头指针的右指针指向新建节点
pNew->left=pCur;//新建节点的左指针执行头节点
pNew->right=NULL;//用于最后和头指针进行交换
pCur=pNew;//指针往下移动
}
//最后将头指针的左指针指向最后一个节点，
//最后一个节点的有指针指向头指针，构成循环
head->left=pCur;
pCur->right=head;
returnhead;
}
//////////////输出链表头节点///////////////////////
voidOutList(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,intn)
{
ChainNode*pNew,*pCur;
//新添加节点和当前节点
pCur=head;
//移动到最节点
while(pCur->right!=head)
{
pCur=pCur->right;
//当前节点往下移动一直移到最后一个节点
}
//新添加n个节点并插入链表
for(inti=0;i<n;i++)
{
pNew=newChainNode;
cout<<"输入要添加的节点元素：";
cin>>pNew->data;
pCur->right=pNew;//头指针的右指针指向新建节点
pNew->left=pCur;//新建节点的左指针执行头节点
pNew->right=NULL;//用于最后和头指针进行交换
pCur=pNew;//指针往下移动
}
//最后将头指针的左指针指向最后一个节点，
//最后一个节点的有指针指向头指针，构成循环
head->left=pCur;
pCur->right=head;
returnhead;
}
/////在双向循环链表中删除一个节点///////
ChainNode*DeleteNode(ChainNode*head,unsignednum)
//删除第num个节点
{
ChainNode*pNew,*pCur,*temp;
//新添加节点和当前节点,临时交换节点
pCur=head;
intncount=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;
deletepCur;
returnhead;
}
intmain()
{
intnum;
//创建num个节点并显示
cout<<"输入要创建的链表节点个数:";
cin>>num;
ChainNode*head=CreateNode(num);
OutList(head);
//往链表后添加n个节点
intaddnum;
cout<<"输入要添加的节点个数:";
cin>>addnum;
AddNode(head,addnum);
OutList(head);
//删除链表的第del个元素
intdel;
cout<<"输入要删除的第几个位置的节点:";
cin>>del;
DeleteNode(head,del);
OutList(head);
system("pause");
return0;
}
希望本文所述对大家的C++程序设计有所帮助。