【数据结构C++描述】带头结点的双向循环链表_c++ 双向循环链表

前言

链表是线性表的一种实现形式，它的核心是指针，主要特点是增加与删除不需要移动大量元素，查找某一特定元素较慢，逻辑上相邻的元素物理上不一定相邻。
链表主要分为单链表，双向链表与循环链表。每种链表又可分为带头结点的和不带头结点的。本篇主要介绍带头结点的双向循环链表的基本操作。

操作说明

Define

双向循环链表的每个结点需要有两个指针，一个指向前驱，一个指向后继。

//定义代码示例
class Node
{
public:
	int  data;
	Node* next;
	Node* prior;
public:
	Node()                //构造函数初始化指针数据成员
	{
		next = nullptr;  
		prior = nullptr;
		data = -1;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Creat

创建双向循环链表时需要注意保证每个结点的两个指针都被赋值，且首元素的前驱指针指向尾元素，尾元素的后继指针指向首元素。

//创建代码示例
void Fill(Node *&A)
{   //输入长度
	int N;
	cin >> N;
	//插入头结点
	Node* p;
	p = new Node;
	p->prior = p;
	p->next = p;
	A = p;
	Node* temp = A;
	for (int i = 0; i < N; i++)
	{
		Node* p;
		p = new Node;
		p->data = rand();       //随机生成数据
		temp->next = p;
		A->prior = p;
		p->prior = temp;
		p->next = A;
		temp = temp->next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Insert

插入操作时需要首先判断链表是否为空，插入位置是否超出链表，同时需要注意指针操作的顺序，要“先连线再剪线”。

//插入代码示例
bool Insert(Node* A)
{   
	if (A->next==A)
		return false;  //判断是否为空
	int place;
	cin >> place;
	Node* temp = A;
	int length = 0;  
	while (temp->next != A)
	{
		temp = temp->next;
		++length;
	}
	if (place > length)
		return false;    //判断是否超出长度
	Node* p;
	p = new Node;
	p->data = 0;               //插入值为0
	for (int i = 0; i < place - 1; i++)
		A = A->next;                     //找到插入位置
	p->next = A->next;
	p->prior = A;
	A->next->prior = p;
	A->next = p;
	return true;
}
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

Delete

删除操作与插入操作类似，但是最后需要delete掉对应结点以释放内存。

//删除代码示例
bool Delete(Node* A)
{
	if (A->next==A)
		return false;  //判断是否为空
	int place;
	cin >> place;

	Node* temp = A;
	int length = 0;
	while (temp->next != A)
	{
		temp = temp->next;
		++length;
	}
	if (place > length)
		return false;             //判断是否超出长度
	for (int i = 0; i < place; i++)
		A = A->next;
	A->next->prior = A->prior;     //指针操作
	A->prior->next = A->next;
	delete A;                 //释放内存
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Inverse

转置操作定义两个指针，一个指向头，一个指向尾，两指针同时向中间移动并交换数据，两指针“相遇”时停止移动，此处需注意“相遇”的判断。

//转置代码示例
bool Inverse(Node*& A)
{
	if (A->next==A)
		return false;  //判断是否为空
	Node* Bejin = A->next; 
	Node* Last = A->prior;       //指针赋值
	int n;
	while (Last->next!=Bejin&&Last!=Bejin)    //"相遇"时停止
	{
		n = Last->data;
		Last->data = Bejin->data;
		Bejin->data = n;
		Last = Last->prior;
		Bejin = Bejin->next;
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Output

输出函数需注意中止条件的判断，避免重复循环输出。

//输出代码示例
bool Output(Node* List)
{
	if (List->next == List)
		return false;         //判断是否为空
	Node* temp = List;
	temp = temp->next;
	while (temp != List)            //中止判断
	{
		cout << temp->data << ",";
		temp = temp->next;
	}
	cout << "\n";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

运行展示

主函数

依次实现创建，插入，删除，转置操作，并在每次操作完成后输出链表。最后释放内存。

int main()
{
	srand(time(0));
	Node* List;
	List = new Node;
	Fill(List);
	Output(List);
	Insert(List);
	Output(List);
	Delete(List);
	Output(List);
	Inverse(List);
	Output(List);
	Node* test1 = List->prior;   //清空内存
	while (List != test1)
	{
		Node* temp = List->next;
		delete List;
		List = temp;
	}
	delete List;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

结果