【数据结构与算法】之双向链表及其实现！

发布于：2024-04-17 ⋅ 阅读:(27) ⋅ 点赞:(0)

​

                                                                                个人主页：秋风起，再归来~

                                                                                            数据结构与算法                             

                                                                       个人格言：悟已往之不谏，知来者犹可追

                                                                                        克心守己，律己则安！

目录

1、双向链表的结构及概念

2、双向链表的实现

2.1 要实现的接口（List.h）

2.2 链表的初始化

2.3 链表的销毁

2.4 链表的打印

2.5 链表的尾插

2.6 链表的尾删

2.7 链表的头插

2.8 链表的头删

2.8 链表的查找

2.9 pos位置插入数据

2.10 pos位置删除数据

3、完整代码

List.h

List.c

Test.c（本人在实现双向链表时的测试代码） 

4、 完结散花

1、双向链表的结构及概念

我们这里要实现的数据结构是带头双向循环的链表（简称双向链表）

下面就是该链表的物理模型啦~

​

2、双向链表的实现

2.1 要实现的接口（List.h）

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

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;//前驱指针
	LTDataType data;
	struct ListNode* next;//后驱指针
}LTNode;

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit();

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

//链表的打印
void LTPrint(LTNode* phead);

//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);

//链表的尾删
void LTPopBack(LTNode* phead);

//链表的头插
void LTPushFront(LTNode* phead, LTDataType x);

//链表的头删
void LTPopFront(LTNode* phead);

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);

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

//删除pos位置节点
void LTErase(LTNode* pos);

2.2 链表的初始化

注意：在初始化的时候一定要让头结点的prev指针和next指针都指向自己！

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit()
{
	//初始化时创建一个带哨兵卫的头结点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		perror("malloc fail!\n");
		return NULL;
	}
	phead->next = phead->prev = phead;
	phead->data = -1;
	return phead;
}

2.3 链表的销毁

注意：我们一定是从链表的头结点（头结点中并没有有效数据的存储）的下一个位置开始销毁链表的！

//链表销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur=phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur!=phead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
}

并且我们在调用链表的销毁函数后依然要手动释放动态内存开辟的phead头结点 ！

为尽量确保接口传递参数的一致性我们并没有传递头结点的地址，所以我们并不能在链表的销毁函数中free我们的头结点！

LTDestroy(plist);
//动态开辟的头结点需要手动释放
free(plist);
plist = NULL;

2.4 链表的打印

遍历链表打印头结点，循环结束的条件是pcur=phead，继续的条件是pcur！=phead

//链表的打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur != phead)
	{
		next = pcur->next;
		printf("%d->", pcur->data);
		pcur = next;
	}
	printf("\n");
}

2.5 链表的尾插

新节点的创建（单独封装成为一个函数）

//新节点的创建
LTNode* ListCreatNode(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;
}

链表的尾插 （在为尾插接口中直接调用创建节点的函数）

//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	LTNode* tail = phead->prev;
	newNode->prev = tail;
	newNode->next = phead;
	tail->next = newNode;
	phead->prev = newNode;
}

2.6 链表的尾删

注意各个节点的指向！

//链表的尾删
void LTPopBack(LTNode* phead)
{
	//尾删的前提是双向链表不为空
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next=phead;
	free(tail);
	tail = NULL;
}

2.7 链表的头插

//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	newNode->next = phead->next;
	newNode->prev = phead;
	phead->next->prev = newNode;
	phead->next = newNode;
}

2.8 链表的头删

//链表的头删
void LTPopFront(LTNode* phead)
{
	//头删的前提是双向链表不为空
	assert(phead && phead->next != phead);
	LTNode* start = phead->next;
	phead->next = start->next;
	start->next->prev = phead;
	free(start);
	start= NULL;
}

2.8 链表的查找

返回值是该指向该数据节点的结构体指针，如没有找到，直接返回空！

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		next = pcur->next;
		pcur = next;
	}
	return NULL;
}

2.9 pos位置插入数据

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	newNode->next = pos->next;
	newNode->prev = pos;
	pos->next->prev = newNode;
	pos->next = newNode;
}

2.10 pos位置删除数据

//删除pos位置节点
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

3、完整代码

List.h

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

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;//前驱指针
	LTDataType data;
	struct ListNode* next;//后驱指针
}LTNode;

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit();

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

//链表的打印
void LTPrint(LTNode* phead);

//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);

//链表的尾删
void LTPopBack(LTNode* phead);

//链表的头插
void LTPushFront(LTNode* phead, LTDataType x);

//链表的头删
void LTPopFront(LTNode* phead);

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);

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

//删除pos位置节点
void LTErase(LTNode* pos);

List.c

#include"List.h"

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit()
{
	//初始化时创建一个带哨兵卫的头结点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		perror("malloc fail!\n");
		return NULL;
	}
	phead->next = phead->prev = phead;
	phead->data = -1;
	return phead;
}

//链表销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur=phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur!=phead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
}

//链表的打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur != phead)
	{
		next = pcur->next;
		printf("%d->", pcur->data);
		pcur = next;
	}
	printf("\n");
}

//新节点的创建
LTNode* ListCreatNode(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;
}

//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	LTNode* tail = phead->prev;
	newNode->prev = tail;
	newNode->next = phead;
	tail->next = newNode;
	phead->prev = newNode;
}

//链表的尾删
void LTPopBack(LTNode* phead)
{
	//尾删的前提是双向链表不为空
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next=phead;
	free(tail);
	tail = NULL;
}

//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	newNode->next = phead->next;
	newNode->prev = phead;
	phead->next->prev = newNode;
	phead->next = newNode;
}

//链表的头删
void LTPopFront(LTNode* phead)
{
	//头删的前提是双向链表不为空
	assert(phead && phead->next != phead);
	LTNode* start = phead->next;
	phead->next = start->next;
	start->next->prev = phead;
	free(start);
	start= NULL;
}

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		next = pcur->next;
		pcur = next;
	}
	return NULL;
}

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	newNode->next = pos->next;
	newNode->prev = pos;
	pos->next->prev = newNode;
	pos->next = newNode;
}

//删除pos位置节点
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

Test.c（本人在实现双向链表时的测试代码） 

#define _CRT_SECURE_NO_WARNINGS

#include"LIst.h"

void TestList1()
{
	LTNode* plist;
	plist = LTInit();//初始化链表
	LTPushBack(plist,1);
	LTPushBack(plist,2);
	LTPushBack(plist,3);
	LTPushFront(plist, 4);
	LTPushFront(plist, 4);
	/*LTPopFront(plist);
	LTPopFront(plist);*/
	LTNode* pos=LTFind(plist, 2);
	printf("删除pos位置之前\n");
	LTPrint(plist);
	LTErase(pos);
	printf("删除pos位置之后\n");
	LTPrint(plist);
	//LTInsert(pos, 5);
	//LTPopBack(plist);
	//LTPopBack(plist);
	//LTPopBack(plist);
	LTDestroy(plist);
	//动态开辟的头结点需要手动释放
	free(plist);
	plist = NULL;
}

int main()
{
	TestList1();

	return 0;
}

4、 完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

​​

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布