您现在的位置是：首页 >学无止境 >来领略一下带头双向循环链表的风采吧网站首页学无止境

来领略一下带头双向循环链表的风采吧

阿博历练记 2024-06-17 10:14:38
简介来领略一下带头双向循环链表的风采吧

? 博客主页：阿博历练记
?文章专栏：数据结构与算法
?代码仓库：阿博编程日记
?欢迎关注：欢迎友友们点赞收藏+关注哦

在这里插入图片描述

文章目录

?前言

在这里插入图片描述
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
上期阿博带友友们实现了单链表,我们可以看出单链表的尾插以及尾删都是非常复杂的，比如尾插：如果链表为空，我们就需要调用二级指针改变来接收plist的地址，因为首次尾插，plist为空，我们要让plist指向结点，需要改变plist,所以传plist的地址，但是之后，我们只需要改变结构体中的next指针，让它指向我们开辟出来的结点就可以了，此时我们改变的是结构体，就不需要传结构体地址了。再比如我们的尾删：我们需要遍历链表，找到尾结点的前一个结点，这样非常麻烦，而且效率很低，但是双向循环链表就会方便很多，我们可以直接通过尾结点的prev指针找到它的前一个结点，我们尾插的时候就不用再判断链表是否为空了，因为就算链表为空，头、尾结点也不为空，它们此时都是哨兵位，我们尾插的时候改变的一直都是结构体的next指针.
在这里插入图片描述

?双向循环链表

?1.链表的定义

typedef  int  LTDataType;
typedef struct  ListNode
{
	LTDataType  data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

?2.链表的初始化

LTNode* BuyLTNode(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 = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return  phead;
}

?误区

❌错误案例

LTNode* BuyLTNode(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 LTInit(LTNode*phead)
{
    phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
}

在这里插入图片描述

⛳友友们，这里我们通过调试也可以看出plist的值并没有被改变，因为我们传的是plist的值，所以形参的改变不会影响实参，形参只是实参的一份临时拷贝，这里我们要改变的是plist，所以我们要传plist的地址，但是我们还可以通过通过返回值的方式来让plist接收newnode,这种就是值拷贝的方式返回，就是先把newnode的值拷贝给pilst,然后它又是一个局部变量，出完函数作用域就销毁了，但是我们通过plist找到那个开辟出来的结点，因为它在堆区上存放，所以出完函数作用域，那个结点并没有销毁.

?3.链表的尾插

LTNode* BuyLTNode(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  PushBack(LTNode* phead, LTDataType x)
{
	assert(phead);   //就算链表为空，这里也一定不能为空，因为phead是带哨兵位的头结点。
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//LTInsert(phead,x);
}

在这里插入图片描述

?4.链表的头插

1.未定义指针版

void  PushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);

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

?注意先后顺序

在这里插入图片描述
2.定义指针版

void  PushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
	//LTInsert(phead->next,x);
}

在这里插入图片描述

?5.链表的打印

void  LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("guard<==>");
	while (cur != phead)
	{
		printf("%d<==>",cur->data);
		cur = cur->next;
	}
	printf("
");
}

在这里插入图片描述

?6.链表的尾删

bool  LTEmpty(LTNode* phead)
{
	assert(phead);
	return  phead->next == phead;
}
void  PopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	//LTErase(phead->prev);
}

在这里插入图片描述

所以友友们这里我们就可以定义一个布尔值，来判空，这样可以提高我们代码的可读性?.

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

友友们注意这里是个等号，不是赋值号，因为空链表是phead->next和phead相等，而不是赋值.

?7.链表的头删

void  PopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
	//LTErase(phead->next);
}

在这里插入图片描述
这里我们也可以定义两个指针来提高我们代码的可读性???.
在这里插入图片描述

?8.链表的查找

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;
}

友友们注意，这里我们让cur从phead->next处开始遍历，因为哨兵位的头结点不存储有效数据.这个函数同时兼具修改的功能，因为它可以返回结点的地址.

?9.链表任意位置的插入（在pos之前插入）

1.未定义指针版

void  LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

?注意先后顺序

在这里插入图片描述
2.定义指针版
在这里插入图片描述

友友们，当我们这个函数写好之后，我们的头插和尾插就可以附用这个函数了，头插就可以写成LTInsert(phead->next,x),尾插就可以写成LTInsert(phead,x),⛳友友们一定要注意尾插不是LTInsert（phead->prev,x）,因为我们是在pos之前插入的，所以我们pos的位置必须是头结点.

?10.链表任意位置的删除（pos位置）

void  LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

在这里插入图片描述

友友们，当我们这个函数写好之后，我们的头删和尾删就可以附用这个函数了，头删就可以写成LTErase（phead->next）,尾删就可以写成LTErase（phead->prev）.

?11.链表的销毁

void  LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		//cur = cur->next;   这里cur已经被释放了，不能在使用了，否则就是野指针
		cur = next;
	}
	free(phead);
	//phead = NULL;   这里置空也没用，因为phead是一级指针，形参的改变不会影响实参，就算把它置空，plist也不会被改变.
}

友友们注意，这里phead=NULL对plist是无效的，因为它们是值传递，形参只是实参的一份临时拷贝，形参的改变不会影响实参.所以我们可以在外面把plist置空，当我们头插，尾插之后一定要注意及时释放，否则就会出现内存泄露.

?List.h代码

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

typedef  int  LTDataType;
typedef struct  ListNode
{
	LTDataType  data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
LTNode* LTInit();    //初始化链表
void  LTPrint(LTNode* phead);   //打印链表
void  PushBack(LTNode* phead, LTDataType x);   //尾插
void  PushFront(LTNode* phead, LTDataType x);  //头插
bool  LTEmpty(LTNode* phead);
void  PopFront(LTNode* phead);        //头删
void  PopBack(LTNode* phead);         //尾删
LTNode* LTFind(LTNode* phead, LTDataType x);  //链表的查找
//在pos之前插入
void  LTInsert(LTNode* pos, LTDataType x);
void  LTErase(LTNode* pos);  //删除pos位置的值
void  LTDestroy(LTNode* phead);  //链表的销毁

?List.c代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
LTNode* BuyLTNode(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 = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return  phead;
}
void  LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("guard<==>");
	while (cur != phead)
	{
		printf("%d<==>",cur->data);
		cur = cur->next;
	}
	printf("
");
}
void  PushBack(LTNode* phead, LTDataType x)
{
	assert(phead);   //就算链表为空，这里也一定不能为空，因为phead是带哨兵位的头结点。
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//LTInsert(phead,x);
}
void  PushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);

	/*newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;*/
	//这里我们也可以提前记录下一结点的地址，这样就不用在意顺序了.
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
	//LTInsert(phead->next,x);
}
bool  LTEmpty(LTNode* phead)
{
	assert(phead);
	return  phead->next == phead;
}
void  PopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
	//LTErase(phead->next);
}
void  PopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	//LTErase(phead->prev);
}
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)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
void  LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}
void  LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		//cur = cur->next;   这里cur已经被释放了，不能在使用了，否则就是野指针
		cur = next;
	}
	free(phead);
	//phead = NULL;   这里置空也没用，因为phead是一级指针，形参的改变不会影响实参，就算把它置空，plist也不会被改变.
}

?test.c代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void  TestList1()
{
	LTNode* plist = LTInit();
	PushBack(plist, 1);
	PushBack(plist, 2);
	PushBack(plist, 3);
	PushBack(plist, 4);
	LTPrint(plist);

	PopBack(plist);
	LTPrint(plist);

	PopBack(plist);
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}
void TestList2()
{

	LTNode* plist = LTInit();
	PushFront(plist, 1);
	PushFront(plist, 2);
	PushFront(plist, 3);
	PushFront(plist, 4);
	PopFront(plist);
	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTInsert(pos, 30);
	}
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}
int  main()
{
	TestList1();
	TestList2();
	return  0;
}

?代码效果展示

在这里插入图片描述

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐