数据结构之循环链表

循环链表和单链表的区别：

1：单链表的表尾节点的next指针指向NULL，而循环链表的表尾节点指针next指向头结点

2：单链表从一个节点出发只能找到后续的各个节点，而循环链表从一个节点出发可以找到其他任意一个节点
3：时间复杂度不同

定义循环单链表：

带头结点：

方法：和普通单链表的定义方法相同

typedef struct Linklist
{
	Elemtype data;
	struct LNode* next;
}LNode,Linklist*;
1
2
3
4
5

循环链表的初始化：

方法：和普通单链表的初始化方法基本相同，不同之处在于循环链表的头结点next指向头结点

bool INitlist(Linklist& L)
{
	L = (Node*)malloc(sizeof(LNode));
	if (L == NULL)
		return false;
	L->next = L;
	return true;
}
1
2
3
4
5
6
7
8

循环链表的判空操作：

方法：和普通单链表的判空方法基本相同，不同之处在于循环链表的判空是判断头结点的指针是否指向头结点，而普通单链表的判空是判断头结点的指针是否指向NULL

bool Empty(Linklist& L)
{
	if (L->next = L)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

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

方法：和普通单链表的判断方法基本相同，不同之处在于循环链表的判空是判断p节点的指针是否指向头结点，而普通单链表的判空是判断p节点的指针是否指向NULL

bool istail(Linklist& L)
{
	if (p->next == L)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

双链表和循环双链表的区别：

1：普通双链表表头节点的prior指向NULL，表尾节点的next指向NULL，而循环双链表表头节点的prior指向表尾节点，表尾节点的next指向头结点

定义循环双链表：

带头结点：

方法：和定义普通双链表的方法相同

typedef struct DNode
{
	ElemType data;
	struct DNode* prior, * next;
}LNode,Linklist*;
1
2
3
4
5

循环双链表的初始化：

方法：和普通双链表的初始化基本相同，不同点在于循环双链表的两个节点指针指向的都是表头，而普通双链表两个节点指针指向的是NULL

bool InitList(Linklist& L)
{
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL)
		return false;
	L->prior=L:
	L->next = L;
	return true;
}
1
2
3
4
5
6
7
8
9

循环链表的判空操作：

方法：和普通双链表的初始化基本相同，不同点在于循环双链表的表尾节点指针指向的是表头，而普通双链表的表尾节点指针指向的是NULL

bool Empty(Linklist& L)
{
	if (L->next == L)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

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

方法：和普通双链表的判断方法基本相同，不同之处在于循环链表的判空是判断p节点的指针是否指向头结点，而普通双链表的判空是判断p节点的指针是否指向NULL

bool istail(Linklist& L)
{
	if (p->next == L)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

双链表的插入：

在此之前，我们学习过普通双链表的插入操作，有一个特殊情况是当插入的元素是最后一个元素时，我们无法找到它的前驱结点，也就是说p->next->prior = s不成立，由此我们进行了判断操作：判断插入的节点是否为表尾节点。

bool InitList(DNode*p,DNode*s)
{
	s->next = p->next;
	p->next->prior = s;
	s->prior = p; p->next = s;
}
1
2
3
4
5
6

但在循环双链表的插入操作中，插入的元素是否为表尾元素并不是我们所担心的问题，因为表尾元素它是指向头结点的，由此我们是能够找到该节点的前驱指针。

双链表的删除：

在之前我们学到过普通双链表的删除操作，当要删除的元素为最后一个节点时，我们没办法找到它的前驱节点，也就是q->next->prior = p无法实现。

bool DelteNextDNode(DNode* p)
{
	if (p == NULL)
		return false;
		DNode*q=p->next;
	if (q == NULL)
		return false;
	p->next = q->next;
	if (q->next != NULL)
		q->next->prior = p;
	free(q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

但在循环双链表的删除操作中，删除的元素是否为表尾元素并不是我们所担心的问题，因为表尾元素它是指向头结点的，由此我们是能够找到该节点的前驱指针。