【数据结构】原来你叫“带头结点的双向循环链表”啊

🧑‍💻作者: @情话0.0
📝专栏:《数据结构》
👦个人简介:一名双非编程菜鸟,在这里分享自己的编程学习笔记,欢迎大家的指正与点赞,谢谢!

聚类

在这里插入图片描述

centos安装jenkins

xshell

带头结点的双向循环链表

《新星计划》


前言

  上篇博客带大家认识了单链表,单链表结点中只有一个指向其后继的指针,使得单链表只能从头结点依次向后遍历。对于插入、删除操作得从头遍历,尤其是在链表尾部,还有一点就是无法一步的访问到某个节点的前驱节点,也就是说访问前驱节点的时间复杂度为O(n)。为了避免这样的缺点,便引出了双向循环链表

Audio


一、什么是带头结点的双向循环链表?

  首先,它是一个链表,通过指针将所有的结点连接在一起;其次,循环链表表示整个链表从头到尾构成一个环,链表尾结点的next指针指向头结点;再者,双向表示链表结点有两个指针prev和next,分别指向其前驱结点和后继节点;最后,带头结点表示链表的第一个有效结点前附加一个结点,头结点的数值域不设任何信息。带头结点的双向循环链表如下图所示:

测试类型

在这里插入图片描述

以太网

看似带头结点的双向循环链表的结构更为复杂,但是对于之前单链表的尾插尾删操作更为简单。

ACM 模式

二、带头结点的双向循环链表基本操作实现

注意: 该链表带头结点,所以在进行任何的插入删除操作都无需传二级指针,因为对于头指针的指向并不会改变,只会改变链表的结点结构体本身。但是在销毁操作下,就必须传二级指针,因为销毁操作是将头结点也要删除掉,也就意味着会改变头指针的指向。

硬件设计

双链表中结点类型的描述如下:

typedef int DHCListNode; //每个结点的数值类型为 int

typedef struct DHCList
{
	DHCListNode data;
	struct DHCList* prev;  //前驱指针
	struct DHCList* next;  //后继指针
}DHCList;

1. 动态申请一个结点

DHCList* BuyDHCListNode(DHCListNode data)
{
	DHCList* newNode = (DHCList*)malloc(sizeof(DHCList));
	if (newNode == NULL)
	{
		return NULL;
	}
	newNode->data = data;
	newNode->next = NULL; //对于没一个刚申请的结点让其前驱指针和后继指针都指向NULL
	newNode->prev = NULL;
	return newNode;
}

2. 初始化链表

在对链表的任何操作之前得先创建一个头结点,根据双向循环的特性,需让头结点的prevnext指针都指向其自己。

低功耗蓝牙

DHCList* ListInit()
{
	DHCList* pHead = BuyDHCListNode(0);
	if (pHead == NULL)
	{
		return NULL;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
	return pHead;
}

3. 链表查找

从链表的头结点的后继结点开始逐一匹配,直到找到值相同的结点进行返回,若当查找结点一直后继到头结点时意味着没有该结点,就返回NULL

街景地图

DHCList* ListFind(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

4. 在链表的pos位置之前插入元素

void ListInsert(DHCList* pos, DHCListNode data)
{
	assert(pos);
	DHCList* newNode = BuyDHCListNode(data);
	//以下四步不能混乱,如果先执行了三四步,那么就无法通过pos结点找到newnode结点的前驱结点。
	newNode->next = pos;
	newNode->prev = pos->prev;
	pos->prev->next = newNode;
	pos->prev = newNode;
}

在这里插入图片描述

AMBA协议

5. 删除在链表的pos位置的元素

void ListErase(DHCList* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

6. 链表尾插

链表的尾删可以用链表pos位置插入进行复用,因为链表的插入是在pos位置之前插入,所以在链表尾插的函数里直接将pos改为头结点即可。

函数式编程

void ListPushBack(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	ListInsert(pHead, data);
}

7. 链表尾删

l链表的尾删同样也可以进行复用,直接将pos改为尾结点即可,也就是头结点的前驱节点

链下扩容

void ListPopBack(DHCList* pHead)
{
	assert(pHead);
	ListErase(pHead->prev); //头结点的前驱节点(链表尾结点)
}

8. 链表头插

链表头插即为将待插结点插在头结点之后

跳槽

void ListPushFront(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	ListInsert(pHead->next, data); //
}

9. 链表头删

void ListPopBack(DHCList* pHead)
{
	assert(pHead);
	ListErase(pHead->prev); //删除头结点的后继结点
}

10. 链表清空

该函数意为将链表中除头结点之外的所有结点都销毁。

ICPC比赛

void ListClear(DHCList* pHead)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		pHead->next = cur->next;
		free(cur);
		cur = pHead->next;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
}

11. 链表销毁

void ListDestory(DHCList** pHead)  //参数为二级指针
{
	assert(pHead);
	ListClear(*pHead);  //先清空链表,再释放掉头节点即可。
	free(*pHead);
	*pHead = NULL;
}

三、源代码及运行结果展示

1.DCHListNode.h

结构体创建及函数声明

CubeMX配置CAN

#include <stdio.h>
#include <assert.h>
#include <malloc.h>

typedef int DHCListNode;

typedef struct DHCList
{
	DHCListNode data;
	struct DHCList* prev;
	struct DHCList* next;
}DHCList;

DHCList* ListInit();

DHCList* BuyDHCListNode(DHCListNode data);

DHCList* ListFind(DHCList* pHead, DHCListNode data);

void ListPushBack(DHCList* pHead, DHCListNode data);

void ListPushFront(DHCList* pHead, DHCListNode data);

void ListPopBack(DHCList* pHead);

void ListPopFront(DHCList* pHead);

void ListInsert(DHCList* pos, DHCListNode data);

void ListErase(DHCList* pos);

void ListPrint(DHCList* pHead);

void ListClear(DHCList* pHead);

void ListDestory(DHCList** pHead);

void TestList();

2.DCHListNode.c

方法实现

mysql 触发器详解

#include "DCHListNode.h"

DHCList* BuyDHCListNode(DHCListNode data)
{
	DHCList* newNode = (DHCList*)malloc(sizeof(DHCList));
	if (newNode == NULL)
	{
		return NULL;
	}
	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

DHCList* ListInit()
{
	DHCList* pHead = BuyDHCListNode(0);
	if (pHead == NULL)
	{
		return NULL;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
	return pHead;
}

DHCList* ListFind(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void ListPushBack(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	ListInsert(pHead, data);
}

void ListPushFront(DHCList* pHead, DHCListNode data)
{
	assert(pHead);
	ListInsert(pHead->next, data);
}

void ListPopBack(DHCList* pHead)
{
	assert(pHead);
	ListErase(pHead->prev);
}

void ListPopFront(DHCList* pHead)
{
	assert(pHead);
	ListErase(pHead->next);
}

//在pos之前插入
void ListInsert(DHCList* pos, DHCListNode data)
{
	assert(pos);
	DHCList* newNode = BuyDHCListNode(data);
	newNode->next = pos;
	newNode->prev = pos->prev;
	pos->prev->next = newNode;
	pos->prev = newNode;
}

void ListErase(DHCList* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

void ListPrint(DHCList* pHead)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d----", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void ListClear(DHCList* pHead)
{
	assert(pHead);
	DHCList* cur = pHead->next;
	while (cur != pHead)
	{
		pHead->next = cur->next;
		free(cur);
		cur = pHead->next;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
}

void ListDestory(DHCList** pHead)
{
	assert(pHead);
	ListClear(*pHead);
	free(*pHead);
	*pHead = NULL;
}

void TestList()
{
	DHCList* pHead = ListInit();
	ListPushBack(pHead, 1);
	ListPushBack(pHead, 2);
	ListPushBack(pHead, 3);
	ListPushBack(pHead, 4);
	ListPrint(pHead);

	ListPushFront(pHead, 0);
	ListPrint(pHead);

	ListPopFront(pHead);
	ListPrint(pHead);

	ListPopBack(pHead);
	ListPrint(pHead);

	ListClear(pHead);
	ListPrint(pHead);

	ListDestory(&pHead);
	//ListPrint(pHead);
}

3.test.c

主函数

Spring MVC

#include "DCHListNode.h"

int main()
{
	TestList();
	return 0;
}

结果展示:

在这里插入图片描述

wcss


总结

  带头结点的双向循环链表的结构比较复杂,所以对链表进行插入删除操作时一定要注意指针指向的先后顺序;还有就是传递的参数为一级指针即可,只有在删除链表时才需传二级指针。
  文章若有不足的地方还请大佬指正!!!

gradle

在这里插入图片描述

植被类型分布

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注