C++实现双向循环链表

2023-07-26 14:34:04 165

本文实例为大家分享了C++实现双向循环链表的具体代码，供大家参考，具体内容如下

一、概念

1.在双链表中的每个结点应有两个链接指针：

lLink->指向前驱结点（前驱指针或者左链指针）

rLink->指向后继结点（后驱指针或者右链指针）

2.双链表常采用带附加头结点的循环链表方式：

first：头指针，不存放数据，或者存放特殊要求的数据。它的lLink指向双链表的尾结点（最后一个结点），

它的rLink指向双链表的首结点（第一个有效结点）。链表的首结点的左链指针lLink和尾结点的右链指针

rLink都指向附加头结点。

二、实现程序

1.DblList.h

#ifndefDblList_h
#defineDblList_h
#include
usingnamespacestd;

template
structDblNode{//链表结点定义
Tdata;
DblNode*lLink,*rLink;//链表前驱（左链）和后继（右链）指针
DblNode(DblNode*left=NULL,DblNode*right=NULL):lLink(left),rLink(right){}//构造函数
DblNode(Tvalue,DblNode*left=NULL,DblNode*right=NULL):data(value),lLink(left),rLink(right){}//构造函数
};

template
classDblList{//双链表（双向循环链表）
public:
DblList();//构造函数：建立附加头结点
~DblList();//析构函数：释放所有存储
voidcreateDblList();//创建双向链表
intLength()const;//计算双链表的长度
boolisEmpty();//判双链表空否
DblNode*getHead()const;//取附加头结点
voidsetHead(DblNode*ptr);//设置附加头结点地址
DblNode*Search(constTx);//在链表中沿后继方向寻找等于给定值x的结点
DblNode*Locate(inti,intd);//在链表中定位第i个结点，d=0按前驱方向，否则按后继方向
boolInsert(inti,constTx,intd);//在第i个结点后插入x，d=0按前驱方向，否则按后继方向
boolRemove(inti,T&x,intd);//删除第i个结点，x带回删除其值，d=0按前驱方向，否则按后继方向
voidOutput();//输出双链表中的数据
private:
DblNode*first;//附加头结点
};

template
DblList::DblList(){
//构造函数：建立附加头结点
first=newDblNode();
if(NULL==first){
cerr<<"动态分配内存空间失败！"<rLink=first->lLink=first;//指向自身
}

template
DblList::~DblList(){//析构函数：释放所有存储
DblNode*current=first->rLink;
while(current!=first){
current->rLink->lLink=current->lLink;//从lLink链中摘下
current->lLink->rLink=current->rLink;//从rLink链中摘下
deletecurrent;//释放空间
current=first->rLink;
}
deletefirst;
first=NULL;
}

template
voidDblList::createDblList(){
//创建双向链表
intn,val;
DblNode*current=first;
cout<<"请输入要输入的个数n:";
cin>>n;
cout<<"请输入要输入的数："<>val;
DblNode*newNode=newDblNode(val);
if(NULL==newNode){
cerr<<"动态分配内存空间失败！"<rLink!=first)
current=current->rLink;//往后继方向移动
newNode->rLink=current->rLink;
current->rLink=newNode;
newNode->rLink->lLink=newNode;
newNode->lLink=current;
current=current->rLink;//current往后移
}
}

template
intDblList::Length()const{
//计算双链表的长度
DblNode*current=first->rLink;
intcount=0;

while(current!=first){
current=current->rLink;
count++;
}
returncount;
}

template
boolDblList::isEmpty(){
//判双链表空否
returnfirst->rLink==first;
}

template
DblNode*DblList::getHead()const{
//取附加头结点
returnfirst;
}

template
voidDblList::setHead(DblNode*ptr){
//设置附加头结点地址
first=ptr;
}

template
DblNode*DblList::Search(constTx){
//在链表中沿后继方向寻找等于给定值x的结点
DblNode*current=first->rLink;
while(current!=first&¤t->data!=x)
current=current->rLink;
if(current!=first)
returncurrent;//搜索成功
else//搜索失败
returnNULL;
}

template
DblNode*DblList::Locate(inti,intd){
//定位
if((first->rLink==first)||(i=0))
returnfirst;
DblNode*current;
if(d==0)
current=first->lLink;//搜索前驱方向
else
current=first->rLink;
for(intj=1;jlLink;
else
current=current->rLink;
}
if(current!=first)//定位成功
returncurrent;
else
returnNULL;
}

template
boolDblList::Insert(inti,constTx,intd){
//插入
DblNode*current=Locate(i,d);//查找第i个结点
if(current==NULL)//i不合理，插入失败
returnfalse;
DblNode*newNode=newDblNode(x);
if(newNode==NULL){
cerr<<"内存空间分配失败！"<lLink=current->lLink;
current->lLink=newNode;
newNode->lLink->rLink=newNode;
newNode->rLink=current;
}
else{//后继方向插入
newNode->rLink=current->rLink;
current->rLink=newNode;
newNode->rLink->lLink=newNode;
newNode->lLink=current;
}
returntrue;
}

template
boolDblList::Remove(inti,T&x,intd){
//删除
DblNode*current=Locate(i,d);//查找第i个结点
if(current==NULL)//i不合理，插入失败
returnfalse;
current->rLink->lLink=current->lLink;//从lLink链中摘下
current->lLink->rLink=current->rLink;//从rLink链中摘下
x=current->data;
deletecurrent;//释放空间
current=NULL;//指向空
returntrue;//删除成功
}

template
voidDblList::Output(){
//输出双链表中的数据
DblNode*current=first->rLink;
while(current!=first){
cout<data<<"";
current=current->rLink;
}
cout<
2.main.cpp
#include"DblList.h"
usingnamespacestd;

intmain(intargc,constchar*argv[]){
intfinished=0,choice,i,x,d,len;//i存储第i个，d:存储方向-》0表示前驱方向，否则为后继方向
DblListL;
DblNode*head=NULL,*current;

while(!finished){
cout<<"\n*********菜单*********\n";
cout<<"1:建立双链表\n";
cout<<"2:双链表的长度\n";
cout<<"3:双链表是否为空？\n";
cout<<"4:取附加头结点\n";
cout<<"5:设置附加头结点地址\n";
cout<<"6:在链表中沿后继方向寻找等于给定值x的结点\n";
cout<<"7:在链表中定位第i个结点，d=0按前驱方向，否则按后继方向\n";
cout<<"8:在第i个结点后插入x，d=0按前驱方向，否则按后继方向\n";
cout<<"9:删除第i个结点，x带回删除其值，d=0按前驱方向，否则按后继方向\n";
cout<<"10:输出双链表中的数据:\n";
cout<<"11:退出\n";
cout<<"请输入选择[1-11]：\n";
cin>>choice;
switch(choice){
case1:
L.createDblList();//建立双链表
break;
case2:
len=L.Length();//双链表的长度
cout<<"双链表的长度为："<>x;
if(L.Search(x)!=NULL)
cout<<"查找成功！"<>i>>d;
current=L.Locate(i,d);
if(current==NULL)
cout<<"定位失败!"<>i>>x>>d;
if(L.Insert(i,x,d))
cout<<"插入成功!"<>i>>d;
if(L.Remove(i,x,d))
cout<<"删除成功，删除的值为："<
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C++实现双向循环链表

热门推荐

随机推荐