双向链表的实现

2024-05-21 18:21
windows
36人已看

									双向链表的实现

上一篇博客我们完成了单链表，实际上在链表的分类中它叫做单向不带头不循环链表，链表的分类如下：

在这里插入图片描述
一、什么是带头链表呢？

上一节我们写单链表的尾插数据，当我们没有头结点的时候，需要将创建的第一个节点作为头结点，这样是不是很麻烦啊，那我们是不是可以在插入节点之前手动创建一个节点，它不存入任何数据，只是充当头的作用，我们需要尾插数据的时候，直接调用尾插的函数即可，头插也只需要将新节点插入这个节点之后，那么这样的节点我们称它为–哨兵卫，也就是带头节点。

在这里插入图片描述

二、什么是双向链表？

上一节我们知道单链表中的一个节点就是一个结构体，它存放了数据域与指针域，但是指针域里只存放了一个指向下一个节点的next指针，而在双向链表中还存放了一个指向上一个节点的prev指针。
在这里插入图片描述
在单链表中我们想访问当前节点的上一个节点里存储的值是比较困难的，而在双向链表中我们可以直接通过prev指针来访问。

三、循环链表

循环链表简单的来说就是让为节点的next指针指向头结点，这样这个链表就形成了一个环。
在这里插入图片描述
那么带头双向循环链表它的结构就如下

了解完以上的基本知识后，我们就可以开始来写我们的双链表。

二、实现双链表

（1）就是定义一个ListNode的结构体作为节点，它有一个数据域存放数据，还有一个指针域存放next指针（指向下一个节点），prev指针（指向上一个节点）。

typedef int ListNodeData;//把int数据的类型改名
typedef struct ListNode
{
ListNodeData data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;//将结构体改名

跟之前单链表一样，我们的双链表需要完成头插，尾插，尾删，头删，任意位置插入与删除以及销毁链表。
在这里插入图片描述

（2）、初始化双链表。

在双链表中初始化也就是给双链表一个哨兵卫，然后让其形成循环–也就是让它的next指针与prev指针都指向自己，哨兵卫的数据只需要存放无意义得值即可。——在这里我们初始化的时候是不是创建了一个新的节点，那我们就可以将创建节点的代码段封装为一个buynode的函数。在初始化的时候调用即可。

#include"ListNode.h"
ListNode* BuyNode(ListNodeData x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(1);
	}
	node->data = x;
	node->next = node;
	node->prev = node;
	return node;
}
void ListNodeInit(ListNode** pptr)
{
	*pptr = BuyNode(-1);
}

这里的-1可以换成其他的数值，在打印时其实没有影响，因为我们打印的时候会从哨兵卫的下一个节点遍历并打印。

（2）、尾插

在这里插入图片描述
从这个图里我们可以看出当我们需要插入新的节点的时候，需要改变4个指针，分别为ptr（哨兵卫）->prev,newnode->next,newnode->prev,ptr->prev->next(哨兵卫的上一个节点也就是原先的尾节点的next指针)

void LNPushBack(ListNode* ptr, ListNodeData x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = ptr;
	newnode->prev = ptr->prev;
	
	ptr->prev->next = newnode;
	ptr->prev = newnode;//这一步不能与上面的这一步换位置
}

为什么不能换位置呢？是因为如果我们现将ptr->prev指针给改变了，那么我们就找不到它的next指针指向的内容了。还有一个需要注意的地方，为什么这里可以传一级指针，解释如下
在这里插入图片描述
（3）打印链表

我们之前说过，为了防止写完后错误太多而不知道哪里查起，我们需要写一个函数就输出一下，检查是否有问题。

void LNPrintf(ListNode* ptr)
{
	ListNode* pcur = ptr->next;
	while (pcur != ptr)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL");
}

这里需要注意的是我们需要从ptr->next的位置开始遍历（因为哨兵卫存的数据是无效的，不需要打印），结束条件就是刚好循环一圈，pcur==ptr。

现在就来看看我们的链表有没有问题
在这里插入图片描述
（4）头插

双向链表中的头插跟单链表的头插也不一样，在这里我们需要将我们的数据插入哨兵卫的后面
在这里插入图片描述
在这里我们需要改变的指针也有四个，但需要注意的是我们需要先将newnode后面的节点与newnode连接，如果我们先连哨兵卫与newnode的话会找不到newnode后面的节点。

void LNPushPront(ListNode* ptr,ListNodeData x)//头插
{
	assert(ptr);
	ListNode* newnode = BuyNode(x);
	newnode->next = ptr->next;
	ptr->next->prev = newnode;
	ptr->next = newnode;
	newnode->prev = ptr;
}

写完之后我们再次打印一下检查
在这里插入图片描述
（5）尾删

在这里插入图片描述
在这里我们只需要改变两个指针，最后再释放掉最后一个节点即可

void LNPopBack(ListNode* ptr)
{
	assert(ptr);
	ListNode* del = ptr->prev;

	ptr->prev = del->prev;
	del->prev->next = ptr;
	free(del);
	del = NULL;
}

打印如下：
在这里插入图片描述
（6）头删

头删与头插一样我们删除的是哨兵卫后面的节点。
在这里插入图片描述
由图我们只需要改变两个指针

void LNPopPront(ListNode* ptr)
{
	assert(ptr);
	ListNode* del = ptr->next;
	del->next->prev = ptr;
	ptr->next = del->next;

	free(del);
	del = NULL;
}

打印如下
在这里插入图片描述
（7）查找数据

查找数据这一步准确的来说是为后面的指定节点后插入节点，删除指定节点做准备，因为在这里当我们找到该数据后返回当前节点。

查找节点跟打印节点有点相似，只需要我们遍历节点，如果存在该元素，返回节点即可，如果不存在返回NULL。

ListNode* LNFind(ListNode* ptr, ListNodeData x)
{
	assert(ptr);
	ListNode* pcur=ptr->next;
	while (pcur != ptr)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

我们需要在test函数里接收其返回值，如果不为空则打印存在，如果返回空，则打印不存在该元素
在这里插入图片描述

（8）在指定位置后插入数据

在查找函数中我们返回了当前节点，我们只需要插入即可
在这里插入图片描述
在这里我们改变了四个指针，理由同上我们先改后面的指针。

void LNPushZD(ListNode* ptr, ListNode* pos, ListNodeData x)
{
	assert(ptr && pos);
	ListNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next->prev = newnode;
	newnode->prev = pos;
	pos->next = newnode;
}

注意这里的pos不能为空，所以我们需要给其断言一下，更加完善我们的代码。此外如果你可以试着在指定位置前插入。

测试一下：
在这里插入图片描述
（9）删除指定节点

当我们找到需要删除的节点后我们只需要将前面的节点与其后面的节点连接即可，再释放掉这个节点。

void LNPopZD(ListNode* ptr, ListNode* pos)
{
	assert(ptr && pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos;
	free(pos);
	pos = NULL;
}

测试如下
在这里插入图片描述
（10）删除链表

当我们使用完这个链表之后我们需要删除我们的链表
跟之前打印相似我们只需要遍历链表，遍历一个删除一个，需要强调的是我们在末尾需要将我们的哨兵卫也要释放，并且让其指向NULL。

void LNDestroy(ListNode* ptr)
{
	assert(ptr);
	ListNode* pcur = ptr->next;
	while (pcur != ptr)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(ptr);
	ptr = NULL;
}

在这里插入图片描述

因为删除链表的过程我们看不见，但打印我们的链表后会暂停一段时间，这段时间就是我们的销毁过程，大家可以自己试试。

下面我就给出所有的代码。
ListNode.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int ListNodeData;
typedef struct ListNode
{
	ListNodeData data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
void ListNodeInit(ListNode**pptr);
void LNPushBack(ListNode* ptr, ListNodeData x);
void LNPrintf(ListNode* ptr);//打印双向链表
void LNPushPront(ListNode* ptr,ListNodeData x);//头插
void LNPopBack(ListNode*ptr);//尾删
void LNPopPront(ListNode* ptr);//头删
ListNode* LNFind(ListNode* ptr, ListNodeData x);//查找元素
void LNPushZD(ListNode* ptr, ListNode* pos, ListNodeData x);//指定位置后插入
void LNPopZD(ListNode* ptr, ListNode* pos);//删除指定节点
void LNDestroy(ListNode* ptr);//销毁链表

ListNode.c

#include"ListNode.h"
ListNode* BuyNode(ListNodeData x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(1);
	}
	node->data = x;
	node->next = node;
	node->prev = node;
	return node;
}
void ListNodeInit(ListNode** pptr)
{
	*pptr = BuyNode(-1);
}
void LNPushBack(ListNode* ptr, ListNodeData x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = ptr;
	newnode->prev = ptr->prev;
	
	ptr->prev->next = newnode;
	ptr->prev = newnode;//这一步不能与上面的这一步换位置
}
void LNPrintf(ListNode* ptr)
{
	ListNode* pcur = ptr->next;
	while (pcur != ptr)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL");
}
void LNPushPront(ListNode* ptr,ListNodeData x)//头插
{
	assert(ptr);
	ListNode* newnode = BuyNode(x);
	newnode->next = ptr->next;
	ptr->next->prev = newnode;
	ptr->next = newnode;
	newnode->prev = ptr;
}
void LNPopBack(ListNode* ptr)
{
	assert(ptr);
	ListNode* del = ptr->prev;

	ptr->prev = del->prev;
	del->prev->next = ptr;
	free(del);
	del = NULL;
}
void LNPopPront(ListNode* ptr)
{
	assert(ptr);
	ListNode* del = ptr->next;
	del->next->prev = ptr;
	ptr->next = del->next;

	free(del);
	del = NULL;
}
ListNode* LNFind(ListNode* ptr, ListNodeData x)
{
	assert(ptr);
	ListNode* pcur=ptr->next;
	while (pcur != ptr)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
void LNPushZD(ListNode* ptr, ListNode* pos, ListNodeData x)
{
	assert(ptr && pos);
	ListNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next->prev = newnode;
	newnode->prev = pos;
	pos->next = newnode;
}
void LNPopZD(ListNode* ptr, ListNode* pos)
{
	assert(ptr && pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos;
	free(pos);
	pos = NULL;
}
void LNDestroy(ListNode* ptr)
{
	assert(ptr);
	ListNode* pcur = ptr->next;
	while (pcur != ptr)
	{
		ListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(ptr);
	ptr = NULL;
}

test.c

#include"ListNode.h"

void test()
{
	ListNode* phead = NULL;
	ListNodeInit(&phead);
	LNPushBack(phead, 0);
	LNPushBack(phead,1);
	LNPushBack(phead,2);
	/*LNPushPront(phead, 100);
	LNPopBack(phead);
	LNPopPront(phead);*/
	//ListNode*ret=LNFind(phead, 0);
	/*if (ret != NULL)
	{
		printf("找到了\n");
	}
	else
		printf("没找到\n");*/
	//LNPushZD(phead, ret, 3);
	//LNPopZD(phead, ret);
	LNPrintf(phead);
	LNDestroy(phead);
	LNPrintf(phead);
}

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

顺序表与链表部分我已经写完了，下一篇博客我们就来比较一下顺序表与链表之间的优劣。