C语言--带哨兵位的双向循环链表的创建及使用详解-3. 链表操作

3.1 初始化

带哨兵位的双向链表的初始化需要创建一个哨兵位，同时将头指针和尾指针都指向哨兵位的地址，物理图如下：
在这里插入图片描述
代码如下：

//初始化的本质是创建一个不放数据的节点，返回该节点地址
LN* ListInit()
{
	LN* phead = BuyList(0);//创建的哨兵位节点
	phead->next = phead;//头节点指向哨兵位自己
	phead->prev = phead;//尾节点指向哨兵位自己
	return phead;//返回创建的哨兵位的地址
}

3.2 显示

形参 phead 来接收整个链表的头地址 phead 的值，通过 phead 来访问显示链表中的数据。代码如下：

//显示操作仅对链表内部内容进行操作，仅需要哨兵位节点就可以访问所有数据
void ListPrint(LN* phead)
{
	//phead指向的是哨兵位的位置，第一个数据在哨兵位之后
	LN* cur = phead->next;//寻找第一个数据的位置
	
	//循环结构，当尾指针指向哨兵位时完成一个循环
	//当链表里面仅剩哨兵位时，cur指向的仍为phead,循环直接结束
	while (cur != phead)
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.3 尾插

将最后一个节点tail 的next 指向新的节点newnode，新的节点newnode 的next 指向 phead，新的节点newnode 的prev 指向最后一个节点 tail 的地址，phead 的prev 指向新节点newnode 的地址.
在这里插入图片描述

//尾插需要链表的哨兵位节点与要插入的数据，不需要返回任何值
void ListPushBack(LN* phead, LTDataType x)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错

	LN* tail = phead->prev;//找尾节点
	LN* newnode = BuyList(x);//新建节点
	//将新节点链接到尾节点tail之后，再与哨兵位链接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

3.4 头插

将第一个数据节点first 的prev 指向新的节点newnode，新的节点newnode 的prev 指向 phead，新的节点newnode 的next 指向第一个节点 first的地址，phead 的next 指向新节点newnode 的地址.
在这里插入图片描述

//头插需要链表的哨兵位节点与要插入的数据，不需要返回任何值
void ListPushFront(LN* phead, LTDataType x)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错

	LN* first = phead->next;//找到第一个数据的位置
	LN* newnode = BuyList(x);//新建节点
	//将新节点插入哨兵位之后，first之前
	first->prev = newnode;
	newnode->prev = phead;
	newnode->next = first;
	phead->next = newnode;
}

3.5 尾删

pead 的prev 指向倒数第二个数据pretail 的地址，prevtail 的next 指向phead 的地址,释放tail 的空间。
在这里插入图片描述

//尾删仅需要找到尾节点的位置，改变节点位置即可，不需要返回任何值
void ListPopBack(LN* phead)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错
	assert(phead->next != phead);//断言，当链表内容为空的时候报错

	LN* tail = phead->prev;//寻找尾节点
	LN* prevtail = tail->prev;//寻找尾节点之前的节点
	//改变链接顺序，将倒数第二个节点与哨兵位链接起来
	prevtail->next = phead;
	phead->prev = prevtail;
	//释放最后一个节点的空间
	free(tail);
	tail = NULL;
}

3.6 头删

pead 的next 指向第二个数据second 的地址，second 的prev 指向phead 的地址,释放first 的空间。
在这里插入图片描述

//头删仅需要找到第一个数据的的位置，改变节点位置即可，不需要返回任何值
void ListPopFront(LN* phead)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错
	assert(phead->next != phead);//断言，当链表内容为空的时候报错

	LN* first = phead->next;//寻找第一个数据存放节点
	LN* second = first->next;//寻找第二个数据存放节点
	//改变链接顺序，将第二个节点与哨兵位链接起来
	second->prev = phead;
	phead->next = second;
	//释放第一个节点的空间
	free(first);
	first = NULL;
}

3.7 查找

通过给定的数据，以遍历的方式寻找该数据，如果存在，则返回该数据的位置，不存在则返回空。

//查找需要被查找具体的数据，并且返回该数据的位置
LN* ListFind(LN* phead, LTDataType x)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错

	LN* cur = phead->next;//第一个数据的位置
	while (cur != phead)//最坏情况为找一圈也不见要查找的数据
	{
		if (cur->data == x)//找到数据则返回地址
		{
			return cur;
		}
		cur=cur->next;
	}
	return NULL;//为找到数据则返回空
}

3.8 指定位置前插入

将指定数据节点pos 的prev 指向新的节点newnode，新的节点newnode 的prev 指向 prevpos，新的节点newnode 的next 指向pos的地址，prevpos 的next 指向新节点newnode 的地址.
在这里插入图片描述

//指定位置前插入需要指定的位置以及需要插入的数据
void ListInsert(LN* pos, LTDataType x)
{
	assert(pos);//断言，在链表哨兵位节点被误删时报错

	LN* prev = pos->prev;//找到指定位置前一个数据的位置
	LN* newnode = BuyList(x);//定义新的节点
	//将新的节点插入指定节点前面
	newnode->next = pos;
	pos->prev = newnode;
	newnode->prev = prev;
	prev->next = newnode;

}

3.9 指定位置删除

nextpos 的prev 指向prevpos 的地址，prevpos 的next 指向nextpos 的地址,释放pos 的空间。

在这里插入图片描述

//指定位置删除仅需指定的位置即可
void ListErase(LN* pos)
{
	assert(pos);//断言，在链表哨兵位节点被误删时报错

	LN* PosNext = pos->next;//找到指定位置后一个数据的位置
	LN* PosPrev = pos->prev;//找到指定位置前一个数据的位置
	//将指定位置前的数据与指定位置后的数据链接起来
	PosNext->prev = PosPrev;
	PosPrev->next = PosNext;
	//释放指定位置的空间
	free(pos);
	pos = NULL;
}

3.10 链表销毁

通过哨兵位，将所有的链表空间一个一个的释放，最后将哨兵位的空间释放。

//链表销毁需要对整个链表进行操作
void ListDstroy(LN* phead)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错

	LN* cur = phead->next;//找到第一个数据的位置
	while (cur != phead)
	{
		LN* next = cur->next;//找到下一个数据的位置
		free(cur);//释放当前数据的空间
		cur = next;//cur重新变为存在数据的对一个位置
	}
	//释放哨兵位节点空间
	free(phead);
	phead = NULL;
}

秒客网