C++标准库为何在八大链表结构选择了它双向循环带头链表的实质性操作

小明的c++笔记本

2024-04-18 帮助1人

学新通

文章目录

✨链表功能动画演示
 ✨逻辑实现text.c
✨头文件List.h
✨函数实现List.c

🚀八大链表结构为何选择了它

C 的STL库选择的最终链表结构为双向循环带头链表
为什么选择了它呢，是因为它的结构更优，虽然形式看似复杂，但的它便利性相比其他链表好得多

C 标准库中把list设计为带头节点的双向循环链表是很合理的，不信你往后看它的操作实现过程相比于单链表来说有多简单，当然你也可以用其他的六种结果来对比，结果一定是双向循环带头链表更胜一筹

认识八种链表的类型

单向带头非循环链表
单向不带头循环链表
单向不带头非循环链表
双向带头循环链表
双向带头非循环链表
双向不带头循环链表
双向不带头非循环链表
双向循环带头链表✨

一些链表图示

常用的两类链表结构
我们在单链表的一系列操作中讲过单链表是在一些OJ题的常考题

单链表只能单向循环链表
循环双向链表就是一个环形，可以逆时针走，可以顺时针走，而双向链表是一个链，只能双向遍历。

🚀初始化和打印

初始化

我们的双向循环链表采用的是带哨兵位的头结点，它的初始化为了避免要传二级指针，可以设置用返回值的函数带回地址
下面一张图再次带你认识带哨兵位的头结点和不带哨兵位的头结点区别

要注意双向循环带头链表的初始化跟单链表有所区别，双向循环链表是不会指向NULL的，它没有节点的时候是下面的这种形式>

其实就是自己的头和尾都指向自己，这才能体现它的循环结构

在初始的时候是需要创建新节点作为头结点的，而且后续的头插，尾插等等都需要创建新节点，为了避免重复操作，直接建立一个BuyListNode函数用来创建新节点

//创建新节点
LTNode* BuyListNode(LTDateType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	if (newNode == NULL)
	{
		exit(-1);
	}
	newNode->date = x;
	newNode->next = NULL;
	newNode->prev = NULL;

	return newNode;
}

//初始化
LTNode* ListInit()
{
	LTNode* phead = BuyListNode(0);

	phead->prev = phead;
	phead->next = phead;
	
	return phead;
}
//用一个指针接收地址
LTNode* list = ListInit();

打印

打印过程图解

//打印
void ListPrint(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

🚀尾插和尾删

尾插

双向循环带头链表的尾插实在比单链表简单得多了，因为它是循环双向链表，你看尾节点的next不就指向头结点的phead吗，那头结点的prev不就指向尾节点吗
是不是就直接省去了像单链表哪样遍历链表找尾的过程，直接将时间复杂度优化到O(1)
那找到尾之后的操作就是连接节点之间的关系，比较简单，直接看图理解

//尾插
void ListPushBack(LTNode* phead,LTDateType x)
{
	assert(phead);
	//新节点
	LTNode* newNode = BuyListNode(x);
	//找尾
	LTNode* tail = phead->prev;
	//连接
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = phead;
	phead->prev = newNode;

}

尾删

尾删也不难，同样的找尾步骤，注意的是要记录好尾节点的前一个节点，让它来当新的尾节点

动画演示>

//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

🚀头插和头删

头插

头插要注意的是不是在哨兵位的头前面插入，而是在哨兵位的头结点的后一个插入，因为哨兵位只是是不存放有效数据的，但它一定是在最前的

动画演示>

//头插
void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newNode = BuyListNode(x);
	//连接
	LTNode* next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;

	newNode->next = next;
	next->prev = newNode;

}

头删

头删也是像尾删一样要记录好要删节点的下一个节点

//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	//链表为空
	assert(phead->next != phead);

	LTNode* next = phead->next;
	LTNode* nextNext = next->next;
	free(next);
	phead->next = nextNext;
	nextNext->prev = phead;

}

🚀查找和插入

查找

查找就是遍历链表，跟单链表一样的操作，找到了就返回改节点的地址，找不到就返回NULL

//查找
LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

插入

插入是往该数据的前一个位置插入
插入就跟单链表的操作大大不同了，双向循环带头链表的插入比起单链表来说是非常容易的，你把你要在哪个位置插入的指针传给它，它可以直接找到前一个节点，而单链表却没有这个性质

插入功能是和查找功能搭配使用的，用之前先用查找获取把该数据的指针，然后传给插入函数
那你们想想，如果我把phead的指针传给插入函数，那phead的前一个不就是尾节点吗，那不就是相当于尾插吗，同样如果我们把phead的next传给插入函数，哪不就是相当于头插吗！！
所以我们的头插和尾插是不是可以改造成这样子

这样之后我们写头插和尾插就省去了很大时间

//插入
void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);

	LTNode* newNode = BuyListNode(x);


	LTNode* posPrev = pos->prev;

	posPrev->next = newNode;
	newNode->prev = posPrev;
	newNode->next = pos;
	pos->prev = newNode;
}

🚀删除和销毁

删除

删除也是搭配查找函数一起使用，把要的地址传过去即可删除

//删除
void ListErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

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

销毁

销毁就是遍历链表一个一个的free即可

//销毁链表
void ListDestroy(LTNode* phead)
{
	LTNode* cur = phead->next;

	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
//记得最后把销毁链表，还要把list置空
	ListDestroy(list);
	list = NULL;

🚀小结

如果你动手实操了，一定感受到双向循环链表中的一些操作实现是不用考虑像单链表那样的分情况讨论，比如单链表在实现头插的时候不就是要分链表为空和不为空的情况吗，而它却不必考虑这些顾虑，还有很多区别于其他链表的优势，只能你自己去一一感受！！

✨链表功能动画演示

学新通

✨逻辑实现text.c

text.c为工程整体逻辑实现

void menu()
{
	printf("*******************************\n");
	printf("       1.尾插   2.尾删         \n");
	printf("       3.头插   4.头删         \n");
	printf("       5.插入   6查找          \n");
	printf("       7.删除   -1.退出        \n");
	printf("       8.打印                  \n");
	printf("*******************************\n");
	printf(" 请选择>:   \n");

}
void Textmenu()
{
	LTNode* list = ListInit();
	int input = 0;
	LTDateType x1 = 0;
	LTNode* pos = NULL;
	while(input != -1)
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入要尾插的数据，以-1为结束\n");
			scanf("%d", &x1);
			while(x1 != -1)
			{
				ListPushBack(list, x1);
				scanf("%d", &x1);
			}
			printf("尾插成功\n");
			break;
		case 2:
			ListPopBack(list);
			printf("尾删成功\n");
			break;
		case 3:
			printf("请输入要头插的数据，以-1为结束\n");
			scanf("%d", &x1);
			while (x1 != -1)
			{
				ListPushFront(list, x1);
				scanf("%d", &x1);
			}
			printf("头插成功\n");
			break;
		case 4:
			ListPopFront(list);
			printf("头删成功\n");
			break;
		case 5:
			printf("请输入你要在哪里个数据前插入>:\n");
			scanf("%d", &x1);
			 pos= ListFind(list, x1);
			 if (pos != NULL)
			 {
				 printf("请输入你要插入的数据>:\n");
				 scanf("%d", &x1);
				 ListInsert(pos, x1);
				 printf("插入成功\n");
			 }
			 else
			 {
				 printf("无此数据\n");
			 }
			break;
		case 6:
			printf("请输入你要查找的数据\n");
			scanf("%d", &x1);
			pos=ListFind(list, x1);
			if (pos != NULL)
			{
				printf("%d的地址为%p\n", x1, pos);
			}
			else
			{
				printf("链表没有此数据\n");
			}
			break;
		case 7:
			printf("请输入你要删除的数据\n");
			scanf("%d", &x1);
			pos = ListFind(list, x1);
			if (pos != NULL)
			{
				ListErase(pos);
				printf("删除成功\n");
			}
			else
			{
				printf("链表中没有此数据\n");
			}
			break;
		case 8:
			printf("链表数据为：");
			ListPrint(list);
			break;
		case -1:
			printf("退出成功\n");
			break;
		default:
			printf("无此选项，请重新输入！\n");
			break;
		}
	}
	//记得最后把销毁链表，还要把list置空
	ListDestroy(list);
	list = NULL;
	
}

int main()
{
	Textmenu();
}

✨头文件List.h

List.h为工程头文件（头文件和函数声明）

#pragma once

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

typedef int LTDateType;

typedef struct ListNode
{
	LTDateType date;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

//初始化
LTNode* ListInit();

//打印
void ListPrint(LTNode* phead);

//创建新节点
LTNode* BuyListNode(LTDateType x);

//尾插
void ListPushBack(LTNode* phead, LTDateType x);

//尾删
void ListPopBack(LTNode* phead);

//头插
void ListPushFront(LTNode* phead, LTDateType x);

//头删
void ListPopFront(LTNode* phead);

//查找,找到返回对应数据地址，找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x);

//插入，在pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x);

//删除指定位置
void ListErase(LTNode* pos);

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

✨函数实现List.c

List.c为工程源文件（函数实现）

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

//初始化
LTNode* ListInit()
{
	LTNode* phead = BuyListNode(0);

	phead->prev = phead;
	phead->next = phead;
	
	return phead;
}
//打印
void ListPrint(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

//尾插
void ListPushBack(LTNode* phead,LTDateType x)
{
	assert(phead);
	//新节点
	//LTNode* newNode = BuyListNode(x);
	//找尾
	//LTNode* tail = phead->prev;
	//连接
	//tail->next = newNode;
	//newNode->prev = tail;
	//newNode->next = phead;
	//phead->prev = newNode;
	
	//可用插入函数代替尾插
	ListInsert(phead, x);
}
//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	//LTNode* tail = phead->prev;
	//LTNode* tailPrev = tail->prev;
	//free(tail);
	//tailPrev->next = phead;
	//phead->prev = tailPrev;

	//可用删除函数代替尾删
	ListErase(phead->prev);
}

//头插
void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newNode = BuyListNode(x);
	//连接
	LTNode* next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;

	newNode->next = next;
	next->prev = newNode;

	//可用插入函数代替头插
	//ListInsert(phead->next, x);

}

//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	//链表为空
	assert(phead->next != phead);

	LTNode* next = phead->next;
	LTNode* nextNext = next->next;
	free(next);
	phead->next = nextNext;
	nextNext->prev = phead;

	//可用删除函数代替头删
	//ListErase(phead->next);

}

//查找
LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

//插入
void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);

	LTNode* newNode = BuyListNode(x);


	LTNode* posPrev = pos->prev;

	posPrev->next = newNode;
	newNode->prev = posPrev;
	newNode->next = pos;
	pos->prev = newNode;
}
//删除
void ListErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}
//创建新节点
LTNode* BuyListNode(LTDateType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	if (newNode == NULL)
	{
		exit(-1);
	}
	newNode->date = x;
	newNode->next = NULL;
	newNode->prev = NULL;

	return newNode;
}

//销毁链表
void ListDestroy(LTNode* phead)
{
	LTNode* cur = phead->next;

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

这篇好文章是转载于：学新通技术网

C++标准库为何在八大链表结构选择了它双向循环带头链表的实质性操作

文章目录

photoshop保存的图片太大微信发不了怎么办

Android 11 保存文件到外部存储，并分享文件

word里面弄一个表格后上面的标题会跑到下面怎么办

《学习通》视频自动暂停处理方法

photoshop扩展功能面板显示灰色怎么办

微信公众号没有声音提示怎么办

excel下划线不显示怎么办

怎样阻止微信小程序自动打开

excel打印预览压线压字怎么办

TikTok加速器哪个好免费的TK加速器推荐