有哨兵位双向循环链表

这里最好先了解无哨兵位单向非循环链表再来看看这个链表
连接放这里:https://blog.csdn.net/m0_46343224/article/details/127725822
感谢支持哦!

1. 有哨兵位双向循环链表结构

typedef int DLLDataType;

typedef struct DoubleLinkListNode 
{
	struct DoubleLinkListNode* pre;
	DLLDataType data;
	struct DoubleLinkListNode* next;
}DLLNode;
1
2
3
4
5
6
7
8

循环必定要两个结点相互连接，所以有两个指针域

2. 生成一个结点

DLLNode* BuyDLLNode(DLLDataType x)
{
	DLLNode* newnode = (DLLNode*)malloc(sizeof(DLLNode));
	if (newnode == NULL)
	{
		perror("BuyDLLNode:malloc is err:");
		exit(-1);
	}

	newnode->data = x;
	newnode->pre = NULL;
	newnode->next = NULL;

	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

为什么两个指针域初始都指向NULL？

和单链表一样，都是为了尾部结点不需要再进行置空操作

为什么malloc？

堆区可以保留数据，栈区不可以保留数据

3. 初始化链表

DLLNode* DLLInit()
{
	//此时的guard绝对不为NULL，因为malloc检查过了
	DLLNode* guard = BuyDLLNode(-1);

	guard->pre = guard;
	guard->next = guard;

	return guard;
}
1
2
3
4
5
6
7
8
9
10

为什么有哨兵位双向循环链表需要初始化呢？

原因：有哨兵位头节点，这个初始化就是初始化的哨兵位

为什么要自己指向自己呢？

这个问题在后面尾插的时候说明

4. 打印链表

void DLLPrint(DLLNode* guard)
{
	assert(guard);

	DLLNode* cur = guard->next;

	//当cur等于guard时结束
	while (cur != guard)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

为什么后面操作过程中需要对guard断言呢？

初始化中guard绝对不可能为NULL，否则初始化不了，有malloc检查。那么断言的意义是什么，就是防止没有初始化，而是直接guard = NULL进行传参

为什么cur == guard结束呢？

因为是循环，头尾都是相互连接的

5. 尾插

void DLLPushBack(DLLNode* guard, DLLDataType x)
{
	assert(guard);
	
	DLLNode* newnode = BuyDLLNode(x);

	//找到尾结点
	DLLNode* tail = guard->pre;

	//尾部连接新节点
	tail->next = newnode;
	newnode->pre = tail;

	//头部连接
	guard->pre = newnode;
	newnode->next = guard;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

为什么初始化要自己指向自己？

6. 尾删

void DLLPopBack(DLLNode* guard)
{
	assert(guard);
	assert(guard->next != guard);//不能删除哨兵位,当只有一个哨兵位时表示链表为NULL

	DLLNode* tail = guard->pre;
	DLLNode* tailBefore = tail->pre;

	//尾部之前的结点和哨兵位进行连接
	guard->pre = tailBefore;
	tailBefore->next = guard;

	//释放尾结点
	free(tail);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

free后需不需要置空？

无需置空，tail为局部变量，出作用域后无效.并不会改变tail所在位置的指针

7. 头插

void DLLPushFront(DLLNode* guard, DLLDataType x)
{
	assert(guard);

	DLLNode* newnode = BuyDLLNode(x);
	//记录头节点之后的第一个结点
	DLLNode* guardNext = guard->next;

	//新节点和第一个结点连接
	newnode->next = guardNext;
	guardNext->pre = newnode;

	//哨兵位和新节点连接
	guard->next = newnode;
	newnode->pre = guard;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8. 头删

void DLLPopFront(DLLNode* guard)
{
	assert(guard);
	assert(guard->next != guard);

	//记录
	DLLNode* cur = guard->next;
	DLLNode* curNext = cur->next;

	//哨兵位和curNext连接
	guard->next = curNext;
	curNext->pre = guard;

	//释放cur
	free(cur);
	//需不需要置空?
	//无需置空,cur是局部变量出作用域销毁,并不改变什么
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

为什么单链表中需要传二级指针，而这里双向链表无需二级呢？

原因就是有哨兵位头节点，这几个操作并不影响哨兵位头节点的指向

9. 查找

DLLNode* DLLFind(DLLNode* guard, DLLDataType x)
{
	assert(guard);
	//只有哨兵位头节点的时候找不了
	//如果只有哨兵位头节点,则死循环
	assert(guard->next != guard);//只有哨兵位的结点的话无法查找

	DLLNode* cur = guard->next;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		
		cur = cur->next;
	}

	//遍历完没找到返回NULL
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

10. 在pos之前插入

void DLLInsert(DLLNode* pos, DLLDataType x)
{
	//为什么断言?
	//防止pos为NULL时插入
	assert(pos);
	
	//记录
	DLLNode* posBefore = pos->pre;

	//buy一个新节点
	DLLNode* newnode = BuyDLLNode(x);

	//新节点和前一个结点连接
	posBefore->next = newnode;
	newnode->pre = posBefore;

	//新结点和pos连接
	newnode->next = pos;
	pos->pre = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

11. 删除pos位置数据

void DLLErase(DLLNode* pos)
{
	assert(pos);

	//记录pos之前的结点
	DLLNode* posBefore = pos->pre;
	//记录pos之后的结点
	DLLNode* posNext = pos->next;

	//连接pos前后结点
	posBefore->next = posNext;
	posNext->pre = posBefore;

	//释放pos
	free(pos);
	//无需置空,同样原因
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

12. 检查链表是否为NULL

int DLLSearchEmpty(DLLNode* guard)
{
	assert(guard);
	
    //只有哨兵位头结点时为NULL链表
	return guard->next == guard;
}
1
2
3
4
5
6
7

13. 记录链表中结点个数

size_t DLLRecordSize(DLLNode* guard)
{
	assert(guard);

	DLLNode* cur = guard->next;

	size_t size = 0;

	//cur返回到哨兵位时结束
	while (cur != guard)
	{
		++size;
		cur = cur->next;
	}

	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

为什么要用这种方式，而不是每生成一个结点，guard->data++?

举例子:如果类型是char类型,范围是-128 ~ 127,不能

14. 销毁双向链表

void DLLDestroy(DLLNode* guard)
{
	assert(guard);
	//链表为NULL,free掉guard

	DLLNode* cur = guard->next;
	
	//销毁
	while (cur != guard)
	{
		DLLNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}

	//关键一步:释放掉哨兵位
	free(guard);
	//无需置空,局部变量问题
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这里置空必须手动在销毁之后置空