王道数据结构C语言循环链表基本操作实现

---

一、循环单链表

1.1初始化及判空操作

其实循环链表就是在单链表（双链表）上做一点小小的优化

它是把尾结点的next指向了头结点
如果当前链表为空，也就是只有一个头结点（头结点不放东西）
那么头结点的next是要指向它自己的，形成一个循环

我们判空也只需要判断头结点的next是不是头结点自己

#define _CRT_SECURE_NO_WARNINGS
#include
#include
typedef struct {
	int data;//结点存放的数据类型，这里考试一般把int换成ElemType
	LNode* next;//指向下一个结点的指针
}LNode,*LinkList;

//初始化一个循环单链表
bool Init(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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

1.2判断是否是尾结点

这个也很好搞，尾结点指向头结点嘛，你就看哪个结点的next指向头结点就完了

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

很多时候对链表的操作都是在头部或者尾部，我们普通单链表如果要找最后一个结点，但是只给了头结点，我们只能一个一个往后遍历，时间复杂度为O（n）

然而对于循环单链表来说，如果我们让这个单链表的指针L不是指向头结点，而是指向尾部这个结点，从尾部找到头部只需要往后找一个结点即可，时间复杂度为O（1），而找尾部的话，因为本身指针就是指向尾部，时间复杂度也是O（1）

二、循环双链表

对于循环双链表来说，除了要把尾部结点next指向头结点，还要把头结点的prior指向尾结点

2.1初始化

初始化由于只有一个头，所以头的next指向自己，prior也要指向自己

//循环双链表初始化
typedef struct {
	int data;//考试中一般把int换成ElemType
	DNode* prior;
	DNode* 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2判空

这个和循环单链表判空一样，因为空表的时候就一个头结点，它的next指向自己

bool isTail(DLinkList L, DNode* p) {
	if (p->next == L) {
		return true;
	}
	else {
		return false;
	}
}
1
2
3
4
5
6
7
8

2.3判断尾结点

这个和单循环那里也是一样的，给一个结点，你就看它的next是不是指向头结点就行了

bool isTail(DLinkList L, DNode* p) {
	if (p->next == L) {
		return true;
	}
	else {
		return false;
	}
}
1
2
3
4
5
6
7
8

2.4循环双链表的删除

这个比普通双链表删除更简单，普通的还要判断被删的是不是尾结点

循环的双链表你直接进行下面的三步代码就完了，因为它是一个循环连起来的，是不是尾结点无所谓。

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

1
2
3
4
5