首页 > 代码库 > 循环链表的基本操作
循环链表的基本操作
循环链表与普通链表最大的区别在于尾结点的指针域指向什么：普通链表的尾结点的指针域指向空（NULL），而循环链表的尾结点的指针域指向头结点，形成一个环！
#include<iostream>
#include<cstdlib>
using namespace std;
struct Node{
int data;
Node* next;
};
typedef Node* LinkList;
//函数声明
void show();
void InitList(LinkList &L);
void DestroyList(LinkList &L);
void CreateList(LinkList &L,int length);
void ClearList(LinkList &L);
bool EmptyList(LinkList L);
int LengthList(LinkList L);
int GetElem(LinkList L,int index);
int LocateElem(LinkList L,int e);
bool PriorElem(LinkList L,int cur_e,int &pri_e);
bool NextElem(LinkList L,int cur_e,int &next_e);
bool InsertList(LinkList &L,int index,int value);
bool DeleteList(LinkList &L,int index,int &e);
void Print(LinkList L);
int main(){
LinkList L;
int e,index,cur_e,next_e,pri_e,action,length;
show();
while(cin>>action){
switch(action){
case 1:
system("cls");
InitList(L);
break;
case 2:
system("cls");
cout<<"请输入循环链表中的结点个数:"<<endl;
cin>>length;
CreateList(L,length);
cout<<"创建循环链表成功!"<<endl;
break;
case 3:
system("cls");
if(EmptyList(L)){
cout<<"循环链表为空"<<endl;
} else {
cout<<"循环链表不为空"<<endl;
}
break;
case 4:
system("cls");
cout<<"循环链表的长度为:"<<LengthList(L)<<endl;
break;
case 5:
system("cls");
cout<<"请输入结点的索引"<<endl;
cin>>index;
cout<<"第"<<index<<"个结点的值为:"<<GetElem(L,index);
break;
case 6:
system("cls");
cout<<"请输入结点的值"<<endl;
cin>>e;
cout<<e<<"的索引为:"<<LocateElem(L,e);
break;
case 7:
system("cls");
cout<<"请输入结点的值:"<<endl;
cin>>e;
if(PriorElem(L,e,pri_e)){
cout<<e<<"的前驱结点的值为:"<<pri_e<<endl<<endl;
} else {
cout<<"循环链表中不包含"<<e<<endl;
}
break;
case 8:
system("cls");
cout<<"请输入结点的值:"<<endl;
cin>>e;
if(NextElem(L,e,next_e)){
cout<<e<<"的后继结点的值为:"<<next_e<<endl<<endl;
} else {
cout<<"循环链表中不包含"<<e<<endl;
}
break;
case 9:
system("cls");
cout<<"请输入插入的位置和所插结点的值:"<<endl;
cin>>index>>e;
if(InsertList(L,index,e)){
cout<<"插入成功"<<endl;
} else {
cout<<"插入失败"<<endl;
}
break;
case 10:
system("cls");
ClearList(L);
cout<<"已清空循环链表"<<endl;
break;
case 11:
system("cls");
DestroyList(L);
cout<<"已销毁循环链表"<<endl;
break;
case 12:
system("cls");
cout<<"请输入将删除的结点的索引"<<endl;
cin>>index;
if(DeleteList(L,index,e)){
cout<<"第"<<index<<"个元素已经被删除，值为"<<e<<endl<<endl;
} else{
cout<<"删除失败"<<endl;
}
break;
case 13:
system("cls");
cout<<"循环链表的各结点为:"<<endl;
if(!EmptyList(L)){
Print(L);
} else {
cout<<"链表为空"<<endl;
}
cout<<endl<<endl;
}
system("pause");
system("cls");
show();
}
}
void show(){
cout<<"+------------------------------------------------+"<<endl;
cout<<"| |"<<endl;
cout<<"| 1->初始化循环链表 |"<<endl;
cout<<"| 2->创建循环链表 |"<<endl;
cout<<"| 3->判断链表是否为空 |"<<endl;
cout<<"| 4->循环双链表的长度 |"<<endl;
cout<<"| 5->获取结点的值 |"<<endl;
cout<<"| 6->获取结点的位置 |"<<endl;
cout<<"| 7->获取前驱结点 |"<<endl;
cout<<"| 8->获取后继结点 |"<<endl;
cout<<"| 9->插入结点 |"<<endl;
cout<<"| 10->清空循环链表 |"<<endl;
cout<<"| 11->销毁循环链表 |"<<endl;
cout<<"| 12->删除结点 |"<<endl;
cout<<"| 13->打印循环链表 |"<<endl;
cout<<"| |"<<endl;
cout<<"+------------------------------------------------+"<<endl;
}
//初始化循环链表
void InitList(LinkList &L){
L=new Node;
if(!L){
cout<<"初始化失败!"<<endl;
return;
}
L->next=L;
cout<<"初始化成功!"<<endl;
}
//创建循环链表
void CreateList(LinkList &L,int length){
LinkList p=L,q;
for(int i=0;i<length;i++){
q=new Node;
cin>>q->data;
p->next=q;
p=p->next;
}
p->next=L;//注意此时与创建单链表有差异，创建单链表，最后一个结点的指针域为null
//循环链表的末尾指针域指向头结点
}
//销毁循环链表
void DestroyList(LinkList &L){
LinkList p,q;
q=L->next;
while(q!=L){//没到表尾
p=q->next;
delete q;
q=p;
}
delete L;
}
//清空循环链表
void ClearList(LinkList &L){
LinkList p,q;
q=L->next;
while(q!=L){
p=q->next;
delete q;
q=p;
}
//前面一部分与销毁表相同，区别在于销毁表会删除头节点，清空表保留头节点，并使头结点的next指向自己
L->next=L;
cout<<"已清空循环链表"<<endl;
}
//判断是否为空
bool EmptyList(LinkList L){
if(L->next==L){
return true;
} else {
return false;
}
}
//获取长度
int LengthList(LinkList L){
int i=0;
LinkList p=L->next;
while(p!=L){
i++;
p=p->next;
}
return i;
}
//获取第index个结点的值
int GetElem(LinkList L,int index){
if(index<0 || index>LengthList(L)){
cout<<"输入的数值错误"<<endl;
return 0;
}
LinkList p=L->next;
int j=0;
while(j<index){
p=p->next;
j++;
}
return p->data;
}
//获取结点e的位置
int LocateElem(LinkList L,int e){
LinkList p=L->next;
int index=1;
while(p!=L){
if(e==p->data){
return index;
}
index++;
p=p->next;
}
return 0;
}
//获取当前结点的前一个结点的值
bool PriorElem(LinkList L,int cur_e,int &pri_e){
//cur_e不为第一个元素
LinkList p=L->next,q;//p指向第二个元素
q=p->next;//q指向p的下一个元素
while(q!=L){
if(q->data=http://www.mamicode.com/=cur_e){>
循环链表的基本操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。