循环链表-数据结构
- C语言
- 2024-04-07
- 1069热度
- 0评论
循环链表
循环链表分为循环单链表和循环双链表
循环单链表
循环单链表是一种特殊的单链表,其尾节点的 next 指针指向链表的头结点,形成一个环形结构。这种设计在某些情况下是有意义的,具体作用包括:
-
方便遍历:由于尾节点指向头结点,遍历链表时可以从任意节点开始,遍历到尾节点后直接返回到头结点,形成一个循环遍历,而不需要额外的逻辑来判断是否到达了链表的末尾。
-
简化操作:在循环单链表中,任何一个节点都可以作为起点,而无需考虑头结点或尾节点的特殊情况。例如,在插入新节点时,不需要单独处理头结点或尾节点的情况,因为它们都遵循相同的规则。
-
实现算法:某些算法和数据结构的实现会受益于循环单链表的特性。例如,约瑟夫环问题、哈希表的实现等都可以更加简洁和高效地利用循环单链表的特性。
-
提高效率:循环单链表的头结点与尾节点的连接形成了一个闭环,遍历时可以实现更高的效率,因为不需要检查尾节点的
next
指针是否为NULL
。
总的来说,循环单链表的设计简化了一些操作,提高了效率,并且在特定的问题场景下更容易实现相关算法。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
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;
return true;
}
//判断循环单链表是否为空
bool Empty(LinkList L){
if(L->next==L)
{
return true;
}else
{
return false;
}
}
//判断结点p是否为循环单链表的表尾节点
bool isTail(LinkList L, LNode *p){
if(p->next==L)
{
return true;
} else
{
return false;
}
}
int main() {
return 0;
}
循环单链表从头结点找到尾部,时间复杂度为O(n),从尾部找到头结点,时间复杂度为O(1)。
循环双链表
循环双链表(circular doubly linked list)和普通双链表(doubly linked list)是两种常见的链表数据结构,它们在存储方式和特性上有一些区别,以下是它们之间的对比:
-
存储方式:
- 普通双链表:双链表的最后一个节点的 next 指针通常指向 NULL,而第一个节点的 prior 指针也通常指向 NULL,形成一个线性结构。
- 循环双链表:循环双链表的最后一个节点的 next 指针指向头结点,而头结点的 prior 指针指向尾节点,形成一个循环。
-
遍历方式:
- 普通双链表:遍历普通双链表时,需要单独处理头节点和尾节点,因为它们的 next 和 prior 指针指向的位置不同。
- 循环双链表:循环双链表中头节点和尾节点的指针关系是相互的,因此在遍历时无需特殊处理头节点和尾节点。
-
插入和删除操作:
- 普通双链表:在普通双链表中,插入和删除节点时,需要考虑头节点和尾节点的特殊情况,可能需要单独处理。
- 循环双链表:由于循环双链表中头节点和尾节点的指针是相互的,插入和删除节点时的操作更加统一和简化。
-
特性:
- 普通双链表:普通双链表是一个线性结构,头节点的 prior 指针和尾节点的 next 指针通常为 NULL。
- 循环双链表:循环双链表形成一个闭环,头节点的 prior 指针指向尾节点,尾节点的 next 指针指向头节点。
-
应用场景:
- 普通双链表:适用于需要线性存储结构,但不需要循环特性的场景。
- 循环双链表:适用于需要循环特性的场景,例如循环遍历、环形缓冲区等。
总的来说,选择普通双链表还是循环双链表取决于具体的需求和应用场景。普通双链表适用于一般的链表操作,而循环双链表适用于需要循环特性的场景。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct DNode{
ElemType data;
struct DNode *prior,*next; //指针指向下个结点
}DNode,*DLinkList;
//初始化空的循环双链表
bool InitDLinkList(DLinkList &L){
L=(DLinkList) malloc(sizeof(DLinkList)); //分配一个头结点
if(L==NULL) //内存不足,分配失败
{
return false;
}
L->prior=L; //头结点的prior指针指向头结点
L->next=L; //头结点的next指针指向头结点
return true;
}
//判断循环双链表是否为空
bool Empty(DLinkList L){
if(L->next==L)
{
return true;
}else
{
return false;
}
}
//判断结点p是否为循环双链表的表尾节点
bool isTail(DLinkList L, DNode *p){
if(p->next==L)
{
return true;
} else
{
return false;
}
}
int main() {
DLinkList L;
InitDLinkList(L);
L->next=L;
return 0;
}
此时对于上一章节对于双链表插入、删除有错误的代码,在循环双链表中反而可以正常执行了。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct DNode{
ElemType data;
struct DNode *prior,*next; //指针指向下个结点
}DNode,*DLinkList;
//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
}
//删除p的后继结点q
bool DeleteNextDNode(DNode *p){
if(p==NULL)
{
return false;
}
DNode *q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);
return true;
}
int main() {
return 0;
}