循环链表分为
- 循环双链表
- 循环单链表
循环单链表
循环单链表:表尾结点的next指针指向头结点
定义
// 定义一个循环单链表
typedef struct LNode { // 定义一个单链表的类型
int data; // 每一个节点存放的数据类型为int的数据域
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是否是循环单链表的表尾节点
bool IsTail(LinkList L, LNode *p) {
if (p->next==L) {
return true;
}
else {
return false;
}
}
单链表:从一个节点出发只能找到后续的各个节点
循环单链表:从一个节点出发可以找到其他任何一个节点使用循环单链表中在尾部插入一个节点,可以从尾部找一个节点即可,所以这种的方式时间复杂度为O(1)
很多时候对单链表的操作都在表头或者表尾时可以让L指向表尾元素(插入、删除、可能需要修改L)
循环双链表
循环双链表:
表头节点的prior指向表尾节点
表尾节点的next指向头节点
定义
// 定义一个双链表
typedef struct DNode {
int data; //
struct DNode *prior, *next;
}DNode,*DLinkList;
初始化
// 初始化空的循环双链表
bool InitDLinkList(DLinkList L) {
L = (DNode*)malloc(sizeof(DNode)); // 分配一个头节点
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;
}
}
插入节点
// 双链表的插入
// 在p节点之后插入s节点
bool InsertNextDNode(DNode *p,DNode *s) {
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}
删除节点
// 删除p的后继节点
bool DeleteNextDNode(DNode *p, DNode *q) {
p->next = q->next;
q->next->prior = p;
free(q);
return true;
}
版权声明:文章转载请注明来源,如有侵权请联系删除!
文章不错支持一下吧