数据结构：循环链表（王道2022）

• 循环链表
• • 一、循环单链表
  • • 单链表初始化
  • 二、循环双链表
  • • 双链表的初始化
    • 循环双链表的插入
    • 循环双链表删除

循环链表

一、循环单链表

循环单链表：尾结点的next指针指向头结点
从一个结点出发，可以找到链表中任何一个结点(可以找到前驱结点)

单链表初始化

typedef struct LNode{	//定义循环单链表结点类型 
	ElemType data;  	//每个结点存放一个数据元素
	struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;  

//初始化一个循环单链表
bool InitList(LinkList &L){
	L = (LNode*)malloc(sizeof(Lnode));
	if(L==NULL){
		return false;  //内存不足，分配失败 
	}
	L->next = L; //头结点next指向头结点 
	return true;
}

判断单链表是否为空表

//判断循环单链表是否为空
bool Empty(LinkList L){
	if(L->next == L){
		return true;
	}else{
		return false;
	}
} 

判断结点p是否为循环单链表的表尾结点

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
	if(p->next == L){
		return true;
	}else{
		return false;
	}
} 

从头部找到尾部，时间复杂度为：O(n)
从尾部找到头部，时间复杂度为：O(1)

很多时候对链表的操作实在头部或者尾部，可以让L指向表尾元素（插入、删除时可能需要修改L）

二、循环双链表

表头结点的prior指向表尾结点
表尾结点的next指向表头结点

双链表的初始化

typedef struct LNode{	//定义循环单链表结点类型 
	ElemType data;  	//每个结点存放一个数据元素
	struct LNode *next; //指针指向下一个结点
	struct LNode *prior; //指针指向下一个结点
}LNode,*DLinkList;  

//初始化一个循环单链表
bool InitDLinkList(DLinkList &L){
	L = (LNode*)malloc(sizeof(Lnode));
	if(L==NULL){
		return false;  //内存不足，分配失败 
	}
	L->next = L; //头结点next指向头结点 
	L->prior = L;
	return true;
}

判断双链表是否为空表

//判断循环双链表是否为空
bool Empty(DLinkList L){
	if(L->next == L){
		return true;
	}else{
		return false;
	}
} 

判断结点p是否为循环单链表的表尾结点

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
	if(p->next == L){
		return true;
	}else{
		return false;
	}
} 

循环双链表的插入

//在p结点之后插入s结点
bool InsertNextDNode(LNode *p,LNode *s){
	s->next = p->next; //将结点*s插入到结点*p之后
	p->next->prior = s;
	s->prior = p;
	p->next = s; 
} 

循环双链表的好处，不需要考虑插入区域是否为表尾结点

循环双链表删除

//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);