数据结构之双链表（C语言）

来源：爱够旅游网

1 链表的分类

链表根据是否带头（哨兵位）、是否双向（单、双）、是否循环三种特性而分为8种不同的链表。上一节我们讲述了最常见的两种链表之一的单链表（不带头单向不循环链表），本节我们来介绍另一种类型：双链表（带头双向循环链表）。

2 双向链表的结构

代码定义如下：

typedef int LTDatatype;//对涉及链表内的int类型进行重命名

typedef struct ListNode
{
	LTDatatype data;//该节点所存储的数据
	struct ListNode* prev;//指向前一个节点的指针
	struct ListNode* next;//指向后一个节点的指针
}LTNode;

3 双向链表的节点创建与初始化

3.1 节点创建函数

在单链表中，若单链表为空，我们便直接将其phead置为NULL。而在双向链表为空时，链表中只剩下一个头节点（哨兵位），在对其初始化时能否将prev与next指针都置为NULL？

解决这一问题需要我们从双向链表的定义入手，双向链表是带头双向循环链表。在上一个问题中prev与next指针都为空，并不是一个循环。故此时的头节点并不能构成一个空的双向链表。正确操作是将头节点的prev指针与next指针都指向头节点自身，形成自循环。如此才是一个空的双向链表。在节点创建的其他方面与单链表的节点创建函数无异。
代码如下：

LTNode* LTBuyNode(LTDatatype x)
{
	LTNode* Newnode = (LTNode* )malloc(sizeof(LTNode));
	//申请一个节点，用一级指针Newnode存储该节点地址
	if (Newnode == NULL)//判断是否申请成功
	{
		perror("malloc fail");
		exit(1);
	}
	//申请成功
	Newnode->data = x;//将节点数据复制给data
	Newnode->prev = Newnode->next = Newnode;//将prev与next指针都指向本节点地址，即Newnode所存储的地址
	return Newnode;
}

3.2 初始化函数

对一个空的双向链表进行初始化即对其头节点进行初始化。我们不妨将头节点命名为phead，内部数据data一般情况下均赋值为**-1**。在3.1中，我们之所以将节点创建函数的返回值类型设置为LTNode*，目的就是为了在初始化函数中直接调用它，再将它的返回值赋值给phead完成初始化。
代码如下：

void Init(LTNode** pphead)//注意这里使用的是二级指针来接受形参
{
	*pphead = LTBuyNode(-1);//对头节点进行初始化
}

在上面函数的形参中我们使用的是二级指针来接受传参，这种传参方式取决于测试文件test.c中的代码编写。具体见下：
test.c：

LTNode* plist = NULL;//定义一个空指针
Init(&plist);//初始化这个指针，使其成为双向空链表的头节点

我们若想避免在初始化函数中使用二级指针来接受传参，可以使用如下编写方式：
test.c：

LTNode* plist = Init();//将Init的返回值直接赋值给plist，在Init内即完成头节点phead的创建

List.c

LTNode* Init()
{
	LTNode* phead = LTBuyNode(-1);//创建头节点并完成初始化
	return phead;
}

4 双向链表插入节点与删除节点的前序分析

5 双向链表尾插法与头插法

5.1 尾插函数

执行尾插操作时关键在于链接建立的顺序。首先我们要让新节点newnode的prev与next指针同原链表连接，然后改变原链表尾节点的位置，让尾节点为新插入的节点newnode。
具体步骤一：
在双向链表中，找尾十分容易，头节点（哨兵位）的prev指针指向即为尾节点。所以让newnode->prev = phead->prev接完成了新节点与尾节点的连接，再让newnode->next = phead接完成了新节点与头节点phead的连接。循环设置的一半完成。
具体步骤二：
原本尾节点的next指针指向的是phead，newnode尾插进来后要使其指向newnode让newnode成为新的尾节点，即phead->prev->next = newnode。然后再将头节点（哨兵位）的prev指针指向新的尾节点newnode，即phead->prev = newnode。注意：步骤二中两步的先后顺序不能发生改变。
如图所示：

void LTPushBack(LTNode* phead, LTDatatype x)
{
	//判断传参不为空
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//步骤一
	newnode->prev = phead->prev;//newnode->prev指向尾节点
	newnode->next = phead;//newnode->next指向头节点
	//步骤二
	phead->prev->next = newnode;//原本尾节点指向新节点newnode
	phead->prev = newnode;//将新节点newnode变为新的尾节点
	//注意步骤二中两步的先后顺序不能发生改变
}

5.2 头插函数

由5.1知，将新节点插入到头节点的前面即尾插（因为是循环链表）。故将新节点插入到头节点的后面即头插。头插法的关键与尾插一致，均为链接建立的顺序。首先我们要让新节点newnode与原链表的第二个节点phead->next建立联系，然后再将新节点newnode与头节点phead连接。
具体步骤一：
首先我们要找到第二个节点phead->next，然后让新节点newnode的next指针指向第二个节点phead->next，即newnode->next = phead->next再将第二个节点phead->next的prev指针指向新节点newnode,即phead->next->prev = newnode。
具体步骤二：
原本phead的next指针是指向第二个节点phead->next，新节点newnode插入进来后要让phead的next指针指向newnode，即phead->next = newnode。然后再让newnode的prev指针指向phead，即newnode->prev = phead。
代码如下：

void LTPushFront(LTNode* phead, LTDatatype x)
{
	//判断传参不为空
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//步骤一
	newnode->next = phead->next;
	phead->next->prev = newnode;
	//步骤二
	newnode->prev = phead;
	phead->next = newnode;
}

6 双向链表的尾删法与头删法

6.1尾删函数

既然要删除链表中的节点，我们就要保证链表中不能只有一个头节点，即链表不能为空。此外，在删除的过程中，我们要确保双向链表的结构不受到破坏，也就是我们不能直接删除掉对应节点，否则该节点前面的节点与后面的节点就无法连接到一起，故应该先把要删除的节点保存下来，完成上述连接操作后再删除该节点。
代码如下：

void LTPopBack(LTNode* phead)
{
	//链表必须有效且不能为空（只有一个哨兵位）
	assert(phead && phead->next != phead);
	//将尾节点先保存下来
	LTNode* del = phead->prev;
	//步骤一：重新设置尾节点
	del->prev->next = phead;
	phead->prev = del->prev;
	//步骤二：删除原本尾节点（del）
	free(del);
	del = NULL;
}

6.2 头删函数

与6.1中尾删函数步骤相同，先把要删除的节点保存下来，将头节点（哨兵位）与第三个节点连接起来，在将先前所保存的第二个节点删除。
代码如下：

void LTPopFront(LTNode* phead)
{
	//链表必须有效且不能为空（只有一个哨兵位）
	assert(phead && phead->next != phead);
	//将第二个节点先保存下来
	LTNode* del = phead->next;
	//步骤一：重新设置第二个节点
	del->next->prev = phead;
	phead->next = del->next;
	//步骤二：删除原本第二个节点（del）
	free(del);
	del = NULL;
}

7 双向链表在指定位置插入或删除数据

7.1 查找指定节点函数

要想在指定位置插入或删除数据就要先找到指定位置的节点。在双向链表中查找指定节点需要对链表进行遍历。代码如下：

LTNode* Find(LTNode* phead, LTDatatype x)
{
	//判断传参不为空，并且链表不为空（只有一个哨兵位）
	assert(phead && phead->next != phead);
	//从第一个有效节点开始查找，该节点用pcur存储
	LTNode* pcur = phead->next;
	while (pcur != phead)//当查找到头节点（哨兵位）时表示没找到，退出循环
	{
		if (pcur->data == x)//注意这里是判断语句，要用“==”而不是赋值的“=”
		{
			return pcur;//找到指定节点
		}
		pcur = pcur->next;//没找到指定节点，继续向后遍历
	}
	return NULL;//在该链表中不存在指定节点
}

7.2 在指定位置插入数据

与尾插和头插思路一致，先完成新节点newnode与插入位置之后的节点的连接，再完成newnode与插入位置之前的节点的连接。我们以在指定的pos节点之后插入数据为例：
代码如下：

void Insert(LTNode* pos, LTDatatype x)
{
	//判断传参不为空
	assert(pos);
	//创建要插入的节点
	LTNode* newnode = LTBuyNode(x);
	//步骤一：完成与插入位置后的节点的连接
	newnode->next = pos->next;
	pos->next->prev = newnode;
	//步骤二：完成与插入位置前的节点的连接
	newnode->prev = pos;
	pos->next = newnode;
}

7.3 在指定位置删除数据

首先使用查找函数找到pos节点，然后将pos节点的前后节点连接，再将pos节点删除即可。
代码如下：

void LTErase(LTNode* phead, LTNode* pos)
{
	//判断传参不为空，并且pos节点不是头节点（哨兵位）
	assert(pos && pos != phead);
	//步骤一：将pos节点前后的节点连接
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	//步骤二：删除pos节点
	free(pos);
	pos = NULL;
}

8 销毁双向链表与打印函数

8.1 销毁函数

与前文中删除节点类似，只不过销毁时需要借助循环来完成，并且在销毁过程中我们需要保存本次循环删除的节点的下一个节点，并且在后续循环中不断更新。
代码如下：

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur也指向phead，phead还没有被删除
	free(phead);
	phead = NULL;
}

8.2 打印函数

总体与单链表的打印相同，只不过双向链表的打印需要我们跳过头节点（哨兵位）。

void LTPrint(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

9 双向链表全程序及演示结果

9.1 List.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDatatype;

typedef struct ListNode
{
	LTDatatype data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//节点创建函数
LTNode* LTBuyNode(LTDatatype x);

//初始化函数01
//void Init(LTNode** pphead)

//初始化函数02
LTNode* Init();

//尾插函数
void LTPushBack(LTNode* phead, LTDatatype x);

//头插函数
void LTPushFront(LTNode* phead, LTDatatype x);

//尾删函数
void LTPopBack(LTNode* phead);

//头删函数
void LTPopFront(LTNode* phead);

//查找函数
LTNode* LTFind(LTNode* phead, LTDatatype x);

//在pos位置之后插入
void LTInsert(LTNode* pos, LTDatatype x);

//删除POS节点
void LTErase(LTNode* phead, LTNode* pos);

//销毁链表
void LTDestroy(LTNode* phead);

//打印函数
void LTPrint(LTNode* phead);

9.2 List.c文件

#include"List.h"

//节点创建函数
LTNode* LTBuyNode(LTDatatype x)
{
	LTNode* Newnode = (LTNode* )malloc(sizeof(LTNode));
	//申请一个节点，用一级指针Newnode存储该节点地址
	if (Newnode == NULL)//判断是否申请成功
	{
		perror("malloc fail");
		exit(1);
	}
	//申请成功
	Newnode->data = x;//将节点数据复制给data
	Newnode->prev = Newnode->next = Newnode;//将prev与next指针都指向本节点地址，即Newnode所存储的地址
}

//初始化函数01
//void Init(LTNode** pphead)//注意这里使用的是二级指针来接受形参
//{
//	*pphead = LTBuyNode(-1);//对头节点进行初始化
//}

//初始化函数02
LTNode* Init()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

//尾插函数
void LTPushBack(LTNode* phead, LTDatatype x)
{
	//判断传参不为空
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//步骤一
	newnode->prev = phead->prev;//newnode->prev指向尾节点
	newnode->next = phead;//newnode->next指向头节点
	//步骤二
	phead->prev->next = newnode;//原本尾节点指向新节点newnode
	phead->prev = newnode;//将新节点newnode变为新的尾节点
	//注意步骤二中两步的先后顺序不能发生改变
}

//头插函数
void LTPushFront(LTNode* phead, LTDatatype x)
{
	//判断传参不为空
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//步骤一
	newnode->next = phead->next;
	phead->next->prev = newnode;
	//步骤二
	newnode->prev = phead;
	phead->next = newnode;
}

//尾删函数
void LTPopBack(LTNode* phead)
{
	//链表必须有效且不能为空（只有一个哨兵位）
	assert(phead && phead->next != phead);
	//将尾节点先保存下来
	LTNode* del = phead->prev;
	//步骤一：重新设置尾节点
	del->prev->next = phead;
	phead->prev = del->prev;
	//步骤二：删除原本尾节点（del）
	free(del);
	del = NULL;
}

//头删函数
void LTPopFront(LTNode* phead)
{
	//链表必须有效且不能为空（只有一个哨兵位）
	assert(phead && phead->next != phead);
	//将第二个节点先保存下来
	LTNode* del = phead->next;
	//步骤一：重新设置第二个节点
	del->next->prev = phead;
	phead->next = del->next;
	//步骤二：删除原本第二个节点（del）
	free(del);
	del = NULL;
}

//查找函数
LTNode* LTFind(LTNode* phead, LTDatatype x)
{
	//判断传参不为空，并且链表不为空（只有一个哨兵位）
	assert(phead && phead->next != phead);
	//从第一个有效节点开始查找，该节点用pcur存储
	LTNode* pcur = phead->next;
	while (pcur != phead)//当查找到头节点（哨兵位）时表示没找到，退出循环
	{
		if (pcur->data == x)//注意这里是判断语句，要用“==”而不是赋值的“=”
		{
			return pcur;//找到指定节点
		}
		pcur = pcur->next;//没找到指定节点，继续向后遍历
	}
	return NULL;//在该链表中不存在指定节点
}

//在pos位置之后插入
void LTInsert(LTNode* pos, LTDatatype x)
{
	//判断传参不为空
	assert(pos);
	//创建要插入的节点
	LTNode* newnode = LTBuyNode(x);
	//步骤一：完成与插入位置后的节点的连接
	newnode->next = pos->next;
	pos->next->prev = newnode;
	//步骤二：完成与插入位置前的节点的连接
	newnode->prev = pos;
	pos->next = newnode;
}

//删除POS节点
void LTErase(LTNode* phead, LTNode* pos)
{
	//判断传参不为空，并且pos节点不是头节点（哨兵位）
	assert(pos && pos != phead);
	//步骤一：将pos节点前后的节点连接
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	//步骤二：删除pos节点
	free(pos);
	pos = NULL;
}

//销毁链表
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur也指向phead，phead还没有被删除
	free(phead);
	phead = NULL;
}

//打印函数
void LTPrint(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

9.3 test.c文件

运行结果图：

#include"List.h"
void Test01()
{
	/*LTNode* plist = NULL;
	Init(&plist);*/
	//若想让初始化函数Init内不用二级指针来接受传参
	//可按如下方式编写
	LTNode* plist = Init();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPrint(plist);

	LTNode* find = LTFind(plist, 3);
	//LTInsert(find, 66);
	LTErase(plist,find);
	find = NULL;

	LTPrint(plist);
	LTDestroy(plist);
}

int main()
{
	Test01();
}

全文至此结束！！！
写作不易，不知各位老板能否给个一键三连或是一个免费的赞呢(▽)(▽)，这将是对我最大的肯定与支持！！！谢谢！！！(▽)(▽)

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文