双向链表--C语言实现数据结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了双向链表--C语言实现数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本期带大家一起用C语言实现双向链表🌈🌈🌈

一、链表的概念🌎

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；简单来说，线性表的链式存储结构生成的表，称作“链表”。

二、链表中数据元素的构成🌎 🌍

每个元素本身由两部分组成：

1、本身的信息，称为“数据域”

2、指向直接后继的指针，称为“指针域”

三、链表的结构🌎 🌍 🌏

1、带哨兵位或者不带哨兵位 🦴

双向链表--C语言实现数据结构

2、循环或者不循环 🦴 🦴

双向链表--C语言实现数据结构

3、单向或者双向 🦴 🦴 🦴
双向链表--C语言实现数据结构

四、双向带哨兵位循环链表的实现🌎 🌍 🌏 🌎

双向链表--C语言实现数据结构

这里先建立三个文件：
1️⃣ ：SeqList.h文件，用于函数声明
2️⃣ ：SeqList.c文件，用于函数的定义
3️⃣ ：Test.c文件，用于测试函数
建立三个文件的目的：将顺序表作为一个项目来进行书写，方便我们的学习与观察。

一、定义双向链表的结构体✅

双向链表的结构为
存储的有效数据data
指向后一个数据地址的指针next
指向前一个数据指针的数据prev


typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;

	struct ListNode* next;

	struct ListNode* prev;
}LTNode;

这里我们使用typedef对我们所存储的数据，以及双向链表结构体重命名，方便我们后续修改 🍊 🍋 🍒

二、接口的实现✅✅

1.双向链表的创建以及初始化

LTNode* CreatNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

LTNode* LTInit()
{
	LTNode* phead = CreatNode(-1);

	phead->next = phead;
	phead->prev = phead;
}

双向链表--C语言实现数据结构

创建哨兵位节点

2、尾插

对链表进行尾插操作，添加数据到链表的尾部🌱 🌿 ☘️

void LTPushBack(LTNode* phead,LTDataType x)
{
	assert(phead);

	LTNode* newnode = CreatNode(x);

	LTNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;

}

首先我们需要创建一个新的节点，然后将我们的双向链表和我们创建的新节点进行链接起来🌱 🌿
双向链表--C语言实现数据结构

3、头插

对链表进行头插操作，添加数据到链表的头部
但注意的是：不是添加到哨兵位的前面🚀 🛸
而是添加到哨兵位下一个节点的前面

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* node = CreatNode(x);
	node->next = phead->next;
	phead->next->prev = node;
	phead->next = node;
	node->prev = phead;
}

双向链表--C语言实现数据结构

4、检查链表当中是否只有哨兵位

bool LTEmpty(LTNode* phead)
{
	return phead == phead->next;
}

5、尾删

对于 双向链表 的尾删，只要找到尾结点的前一个节点改变它和哨兵位的连接关系即可🚀 🛸
如果要找到尾结点的前一个节点，那么我只需要通过
哨兵位的 prev 找到尾，在通过尾的 prev 就可以找到尾结点的前一个节点。然后调整这个节点和哨兵位的链接关系，然后释放尾结点就可以了

但是要注意，当链表只有哨兵位的时候不能进行删除操作！！！✈️

如图所示

双向链表--C语言实现数据结构

void LTPopBack(LTNode* phead)
{
	assert(phead);
	if (LTEmpty(phead))
	{
		printf("链表为空\n");
		return;
	}
	
	LTNode* tail = phead->prev;

	LTNode* tailPrev = tail->prev;
	free(tail);

	tailPrev->next = phead;
	phead->prev = tailPrev;
}

上面说过，如果当链表只有哨兵位的时候不能进行删除操作！！！
所以我们通过了一个函数来检查当前链表是否只有一个哨兵位✈️ ✈️

bool LTEmpty(LTNode* phead)
{
	return phead == phead->next;
}

6、头删

对于头删来说，我需要删除哨兵位的 next 节点，我们
需要连接哨兵位和哨兵位next的next，然后释放哨兵位的next🌟

但是同样需要注意的是：链表当中只有哨兵位的时候我们不能对其删除！！！

如图所示：🌟
双向链表--C语言实现数据结构

void LTPopFront(LTNode* phead)
{
	assert(phead);
	if (LTEmpty(phead))
	{
		printf("链表为空\n");
		return;
	}

	LTNode* next = phead->next->next;

	phead->next = next;
	phead->next->prev = phead;
}

7、查找链表当中元素

当我们需要查找链表当中是否存在某个元素的时候，我们需要链表，看是否存在该个元素🌟🌟

但是带头双向循环链表当中不存在NULL

所以停止遍历的时候我们的终止条件为！=·phead

如果找到，返回该节点的地址；如果找不到返回 NULL

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;

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

8、在pos位置之前插入数据

在 pos 位置之前插入，那么通过 pos 的 prev 找到 pos 位置的上一个节点 posPrev ，然后改变 posPrev 和新节点 newnode 之间的链接和 newnode 和 pos 之间的链接

需要同LTFind一起使用

void LTInsert(LTNode* pos, LTDataType x)
{

	LTNode* node = CreatNode(x);

	LTNode* posPrev = pos->prev;
	posPrev->next = node;
	node->next = pos;
	node->prev = posPrev;
	pos->prev = node;
}

代码实现逻辑图如下所示
双向链表--C语言实现数据结构
那么很好，有了这个接口之后，可以把它复用于尾插和头插。

对于尾插来说， pos 位置就是 phead ，因为 phead 的前面就是

链表的尾，在 phead 位置前插入，就是尾插：

void LTPushBack(LTNode* phead,LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

对于头插来说， pos 位置就是 phead->next

为第一个节点的前面，在 phead->next 位置前插入，就是头插：


void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead->next, x);
}

9、删除pos位置的数据

在 pos 位置删除，只要找到 pos 的前一个节点 posPrev

然后找到 pos 的后一个节点 posNext ，然后将这两个节点的 prev 和 next 建立正确的链接关系。然后释放 pos 节点，pos 节点置空。🌟🌟🌟

void LTErase(LTNode* pos)
{
	assert(pos);

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

同样的，这个接口也能复用于尾删和头删。

对于尾删来说，， pos 位置就是 phead->prev

为链表的尾，删除 phead->prev 位置，就是尾删：

为了避免空指针异常，我们需要进行判断

void LTPopBack(LTNode* phead)
{
	assert(phead);
	if (LTEmpty(phead))
	{
		printf("链表为空\n");
		return;
	}
	LTErase(phead->prev);
}

对于头删来说， pos 位置就是 phead->next

为链表的头，删除 phead->next 位置，就是头删：

为了避免空指针异常，我们需要进行判断

void LTPopFront(LTNode* phead)
{
	assert(phead);
	if (LTEmpty(phead))
	{
		printf("链表为空\n");
		return;
	}
	LTErase(phead->next);
}

10、打印双向链表

打印整个链表，就只需要遍历链表，控制好循环的停止条件：
循环终止条件设置为！=phead

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("哨兵位->");
	while (cur != phead)
	{
		printf("%d ", cur->data);

		cur = cur->next;
	}
	printf("\n");
}

11、销毁双向链表

我需要把哨兵位，链表的节点全部删除，那么我就要使用循环来删除。

循环的结束条件为 != phead。在销毁的过程中，每次记住我当前节点的下一个节点，以便迭代🍻🍻

但是由于我们的形参是一级指针

所以不能够将哨兵位正常销毁，我们需要在主函数当中手动将哨兵位置为NULL

void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;

	while (cur != phead)
	{
		LTNode* next = cur->next;

		free(cur);
		cur = next;
	}
	free(cur);
}

12、双向链表的测试

双向链表--C语言实现数据结构

五、源代码💡💡💡

1、LIst.h

#pragma once


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;

	struct ListNode* next;

	struct ListNode* prev;
}LTNode;


//初始化
LTNode* LTInit();

//打印链表
void LTPrint(LTNode* phead);
//尾插
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* pos);
//销毁
void LTDestroy(LTNode* phead);

2、List.c

#define _CRT_SECURE_NO_WARNINGS


#include"List.h"


LTNode* CreatNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

LTNode* LTInit()
{
	LTNode* phead = CreatNode(-1);

	phead->next = phead;
	phead->prev = phead;
}

bool LTEmpty(LTNode* phead)
{
	return phead == phead->next;
}
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("哨兵位->");
	while (cur != phead)
	{
		printf("%d ", cur->data);

		cur = cur->next;
	}
	printf("\n");
}



void LTPushBack(LTNode* phead,LTDataType x)
{
	assert(phead);

	//LTNode* newnode = CreatNode(x);

	//LTNode* tail = phead->prev;

	//tail->next = newnode;
	//newnode->prev = tail;
	//phead->prev = newnode;
	//newnode->next = phead;

	LTInsert(phead, x);
}


void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//LTNode* node = CreatNode(x);
	//node->next = phead->next;
	//phead->next->prev = node;
	//phead->next = node;
	//node->prev = phead;


	LTInsert(phead->next, x);
}


void LTPopBack(LTNode* phead)
{
	assert(phead);
	/*if (LTEmpty(phead))
	{
		printf("链表为空\n");
		return;
	}
	
	LTNode* tail = phead->prev;

	LTNode* tailPrev = tail->prev;
	free(tail);

	tailPrev->next = phead;
	phead->prev = tailPrev;*/

	if (LTEmpty(phead))
	{
		printf("链表为空\n");
		return;
	}
	LTErase(phead->prev);
}


void LTPopFront(LTNode* phead)
{
	assert(phead);
	/*if (LTEmpty(phead))
	{
		printf("链表为空\n");
		return;
	}

	LTNode* next = phead->next->next;

	phead->next = next;
	phead->next->prev = phead;*/

	if (LTEmpty(phead))
	{
		printf("链表为空\n");
		return;
	}
	LTErase(phead->next);
}


LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;

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

void LTInsert(LTNode* pos, LTDataType x)
{

	LTNode* node = CreatNode(x);

	LTNode* posPrev = pos->prev;
	posPrev->next = node;
	node->next = pos;
	node->prev = posPrev;
	pos->prev = node;
}

void LTErase(LTNode* pos)
{
	assert(pos);

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;

	while (cur != phead)
	{
		LTNode* next = cur->next;

		free(cur);
		cur = next;
	}
	free(cur);
}

3、test.c

#define _CRT_SECURE_NO_WARNINGS

#include"List.h"

void test1()
{
	printf("尾插：");
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTDestroy(plist);
	printf("\n");
}


void test2()
{
	printf("头插：");
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPushFront(plist, 5);
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
	printf("\n");
}

void test3()
{
	printf("尾删：");
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	 LTPopBack(plist);
	 LTPopBack(plist);
	 LTPopBack(plist);
	 LTPopBack(plist);

	LTPrint(plist);
	LTDestroy(plist);
	printf("\n");
}

void test4()
{
	printf("头删：");
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);

	LTPopFront(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	

	LTPrint(plist);
	LTDestroy(plist);
	printf("\n");

}

void test5()
{
	printf("pos之前插入");
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPushFront(plist, 5);
	LTNode* pos = LTFind(plist,5);
	
	if (pos != NULL)
	{
		LTInsert(pos, 9);

	}

	LTPrint(plist);
	LTDestroy(plist);
	printf("\n");

}

void test6()
{
	printf("删除pos的值：");
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPushFront(plist, 5);
	LTNode* pos = LTFind(plist, 3);
	if (pos != NULL)
	{
		LTErase(pos);
	}
	LTPrint(plist);
	LTDestroy(plist);
	printf("\n");

}
int main()
{
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
	return 0;
}

六、感谢与交流✅

🌹🌹🌹如果大家通过本篇博客收获了,对顺序表有了新的了解的话
那么希望支持一下哦如果还有不明白的，疑惑的话，或者什么比较好的建议的话，可以发到评论区，
我们一起解决，共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯

双向链表--C语言实现数据结构文章来源地址https://www.toymoban.com/news/detail-445102.html

到了这里，关于双向链表--C语言实现数据结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

双向链表--C语言实现数据结构

一、链表的概念🌎

二、链表中数据元素的构成🌎 🌍

三、链表的结构🌎 🌍 🌏

四、双向带哨兵位循环链表的实现🌎 🌍 🌏 🌎

一、定义双向链表的结构体✅

二、接口的实现✅✅

1.双向链表的创建以及初始化

2、尾插

3、头插

4、检查链表当中是否只有哨兵位

5、尾删

6、头删

7、查找链表当中元素

8、在pos位置之前插入数据

9、删除pos位置的数据

10、打印双向链表

11、销毁双向链表

12、双向链表的测试

五、源代码💡💡💡

1、LIst.h

2、List.c

3、test.c

六、感谢与交流✅

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

双向链表--C语言实现数据结构

一、链表的概念🌎

二、链表中数据元素的构成🌎 🌍

三、链表的结构🌎 🌍 🌏

四、 双向带哨兵位循环链表的实现🌎 🌍 🌏 🌎

一、定义双向链表的结构体✅

二、接口的实现✅✅

1.双向链表的创建以及初始化

2、尾插

3、头插

4、检查链表当中是否只有哨兵位

5、尾删

6、头删

7、查找链表当中元素

8、在pos位置之前插入数据

9、删除pos位置的数据

10、打印双向链表

11、销毁双向链表

12、双向链表的测试

五、源代码💡💡💡

1、LIst.h

2、List.c

3、test.c

六、感谢与交流✅

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

四、双向带哨兵位循环链表的实现🌎 🌍 🌏 🌎