11 双向链表

单链表的局限:

在这里插入图片描述
单链表的缺点:逆序访问单链表中的元素耗时大。(时间复杂度:O²)

双向链表的定义

在这里插入图片描述
第0个节点【a1】的pre指针为NULL,要注意
在这里插入图片描述

插入操作:

在这里插入图片描述

删除操作:

在这里插入图片描述

初步实现双链表 代码:

插入代码中要注意:

请添加图片描述
注意:第0个元素的pre指针为NULL

插入的是空双链表中的 第一个元素,示意图:

请添加图片描述

插入的为最后一个元素:

在这里插入图片描述

main.c

//双链表
#include "DLinkList.h"
struct Value
{
	DLinkListNode header;
	int v;
};
int main() {
	int i;
	DLinkList* list = DLinkList_Create();

	struct Value v1;
	struct Value v2;
	struct Value v3;
	struct Value v4;
	struct Value v5;

	v1.v = 1;
	v2.v = 2;
	v3.v = 3;
	v4.v = 4;
	v5.v = 5;

	DLinkList_Insert(list, &v1, DLinkList_Length(list));
	DLinkList_Insert(list, &v2, DLinkList_Length(list));
	DLinkList_Insert(list, &v3, DLinkList_Length(list));
	DLinkList_Insert(list, &v4, DLinkList_Length(list));
	DLinkList_Insert(list, &v5, DLinkList_Length(list));

	for ( i = 0; i < DLinkList_Length(list); i++)
	{
		struct Value* pv = (struct Value*)DLinkList_Get(list, i);
		printf("%d\n", pv->v);
	}

	printf("\n");

	DLinkList_Delete(list, DLinkList_Length(list) - 1);
	DLinkList_Delete(list, 0);

	for (i = 0; i < DLinkList_Length(list); i++)
	{
		struct Value* pv = (struct Value*)DLinkList_Get(list, i);
		printf("%d\n", pv->v);
	}

	DLinkList_Destory(list);
}

DLinkList.h

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

typedef void DLinkList;
//定义包含指针next的结构体
typedef struct _tag_DLinkListNode DLinkListNode;
typedef struct _tag_DLinkListNode
{
	DLinkListNode*  next;
	DLinkListNode*  pre;
};


/*
该方法用于创建并且返回一个空的线性表
*/
DLinkList* DLinkList_Create();

/*
该方法用于销毁一个线性表DLinkList
*/
void DLinkList_Destory(DLinkList* list);

/*
该方法用于将一个线性表DLinkList中的所有元素清空
使得线性表回到创建时的初始状态
*/
void DLinkList_Clear(DLinkList* list);

/*
该方法用于返回一个线性表DLinkList中的所有元素个数
*/
int DLinkList_Length(DLinkList* list);

int DLinkList_Capacity(DLinkList* list);

/*
该方法用于向一个线性表DLinkList的pos位置处插入新元素node
返回值为1表示插入成功,0表示插入失败
*/
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

/*
该方法用于获取一个线性表DLinkList的pos位置处的元素
返回值为pos位置处的元素,NULL表示获取失败
*/
DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

/*
该方法用于删除一个线性表DLinkList的pos位置处的元素
返回值为被删除的元素,NULL表示删除失败
*/
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);


DLinkList.c

#include "DLinkList.h"

typedef struct _tag_DLinkList
{
	DLinkListNode header;//头指针
	int length;//单链表的长度
}TDLinkList; //类型:既代表头结点,又代表整个单链表

DLinkList* DLinkList_Create() {
	TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));

	if (ret) {
		ret->length = 0;
		ret->header.next = NULL;
		ret->header.pre = NULL;
	}
}

void DLinkList_Destory(DLinkList* list) {
	free(list);
}

void DLinkList_Clear(DLinkList* list) {
	((TDLinkList*)list)->length = 0;
	((TDLinkList*)list)->header.next = NULL;
	((TDLinkList*)list)->header.pre = NULL;


}

int DLinkList_Length(DLinkList* list) {
	return ((TDLinkList*)list)->length;
}

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) {
	TDLinkList* tll = (TDLinkList*)list;
	int i = 0;

	int ret = -1;
	ret = (tll != NULL) && (pos >= 0) && (node != NULL);

	if (ret) {
		DLinkListNode* current = (DLinkListNode*)tll;
		DLinkListNode* next = NULL;

		//移动current指针到pos位置
		for (i = 0; (i < pos) && (current->next != NULL); i++)
		{
			current = current->next;
		}

		next = current->next; //

		//关键
		current->next = node;//插入的步骤
		node->next = next;

		if (next) {
			next->pre = node;
		}

		node->pre = current;

		//个人认为这个判定条件不对:如果链表原来长度为5,现在要插入第0个位置【即链表第一个节点】,此if的代码不会被执行,
		//那么第一个节点的pre指针就不能被赋值为NULL,导致问题
		if (tll->length == 0) {
			node->pre = NULL; 
		}


		tll->length++;
	}

	return ret;
}

DLinkListNode* DLinkList_Get(DLinkList* list, int pos) {
	TDLinkList* tll = (TDLinkList*)list;
	DLinkListNode* ret = NULL;

	int i = 0;

	if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
		DLinkListNode* current = (DLinkListNode*)tll;

		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		ret = current->next;
	}

	return ret;
}

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) {
	TDLinkList* tll = (TDLinkList*)list;

	DLinkListNode* ret = NULL;
	int i = 0;

	if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
		DLinkListNode* current = (DLinkListNode*)tll;
		DLinkListNode* next = NULL;

		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		ret = current->next;
		next = ret->next;	

		current->next = next;//删除的步骤

		if (next) {
			next->pre = current;

			if (current == (DLinkListNode*)tll) { //如果删除的是第一个元素
				next->pre = NULL;
			}
		}

		tll->length--;
	}

	return ret;
}


在这里插入图片描述

最终的代码:

添加“游标”操作

在这里插入图片描述

DLinkList.h

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

typedef void DLinkList;
//定义包含指针next的结构体
typedef struct _tag_DLinkListNode DLinkListNode;
typedef struct _tag_DLinkListNode
{
	DLinkListNode*  next;
	DLinkListNode*  pre;
};


/*
该方法用于创建并且返回一个空的线性表
*/
DLinkList* DLinkList_Create();

/*
该方法用于销毁一个线性表DLinkList
*/
void DLinkList_Destory(DLinkList* list);

/*
该方法用于将一个线性表DLinkList中的所有元素清空
使得线性表回到创建时的初始状态
*/
void DLinkList_Clear(DLinkList* list);

/*
该方法用于返回一个线性表DLinkList中的所有元素个数
*/
int DLinkList_Length(DLinkList* list);

int DLinkList_Capacity(DLinkList* list);

/*
该方法用于向一个线性表DLinkList的pos位置处插入新元素node
返回值为1表示插入成功,0表示插入失败
*/
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

/*
该方法用于获取一个线性表DLinkList的pos位置处的元素
返回值为pos位置处的元素,NULL表示获取失败
*/
DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

/*
该方法用于删除一个线性表DLinkList的pos位置处的元素
返回值为被删除的元素,NULL表示删除失败
*/
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);

DLinkListNode * DLinkList_DeleteNode(DLinkList * list, DLinkListNode * node);

DLinkListNode * DLinkList_Reset(DLinkList * list);

DLinkListNode * DLinkList_Current(DLinkList * list);

DLinkListNode * DLinkList_Next(DLinkList * list);


DLinkList.c

#include "DLinkList.h"

typedef struct _tag_DLinkList
{
	DLinkListNode header;//头指针
	DLinkListNode* slider; //头结点处添加“游标”
	int length;//单链表的长度
}TDLinkList; //类型:既代表头结点,又代表整个单链表

DLinkList* DLinkList_Create() {
	TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));

	if (ret) {
		ret->length = 0;
		ret->header.next = NULL;
		ret->header.pre = NULL;
		ret->slider = NULL;
	}
}

void DLinkList_Destory(DLinkList* list) {
	free(list);
}

void DLinkList_Clear(DLinkList* list) {
	((TDLinkList*)list)->length = 0;
	((TDLinkList*)list)->header.next = NULL;
	((TDLinkList*)list)->header.pre = NULL;

	((TDLinkList*)list)->slider = NULL;	
}

int DLinkList_Length(DLinkList* list) {
	return ((TDLinkList*)list)->length;
}

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) {
	TDLinkList* tll = (TDLinkList*)list;
	int i = 0;

	int ret = -1;
	ret = (tll != NULL) && (pos >= 0) && (node != NULL);

	if (ret) {
		DLinkListNode* current = (DLinkListNode*)tll;
		DLinkListNode* next = NULL;

		//移动current指针到pos位置
		for (i = 0; (i < pos) && (current->next != NULL); i++)
		{
			current = current->next;
		}

		next = current->next; //

		//关键
		current->next = node;//插入的步骤
		node->next = next;

		if (next) {
			next->pre = node;
		}

		node->pre = current;

		//个人认为这个判定条件不对:如果链表原来长度为5,现在要插入第0个位置【即链表第一个节点】,此if的代码不会被执行,
		//那么第一个节点的pre指针就不能被赋值为NULL,导致问题
		if (tll->length == 0) {
			node->pre = NULL; 

			tll->slider = node; //游标默认指向第一个元素
		}


		tll->length++;
	}

	return ret;
}

DLinkListNode* DLinkList_Get(DLinkList* list, int pos) {
	TDLinkList* tll = (TDLinkList*)list;
	DLinkListNode* ret = NULL;

	int i = 0;

	if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
		DLinkListNode* current = (DLinkListNode*)tll;

		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		ret = current->next;
	}

	return ret;
}

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) {
	TDLinkList* tll = (TDLinkList*)list;

	DLinkListNode* ret = NULL;
	int i = 0;

	if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
		DLinkListNode* current = (DLinkListNode*)tll;
		DLinkListNode* next = NULL;

		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		ret = current->next;
		next = ret->next;	

		current->next = next;//删除的步骤

		if (next) {
			next->pre = current;

			if (current == (DLinkListNode*)tll) { //如果删除的是第一个元素
				next->pre = NULL;
			}
		}

		if (tll->slider == ret) {
			tll->slider = next; //当前删除的节点恰好是游标所在的节点,那么游标移动到下一个节点
		}

		tll->length--;
	}

	return ret;
}

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node) {
	TDLinkList* tdll = (TDLinkList*)list;
	DLinkListNode* ret = NULL;
	int i = 0;

	if (tdll) {
		DLinkListNode* current = (DLinkListNode*)tdll;

		for ( i = 0; i < tdll->length; i++)
		{
			if (current->next == node) {
				ret = current->next;
				break;
			}

			current = current->next;	
		}

		if(ret){
			DLinkList_Delete(list, i);
		}
	}

	return ret;
}

DLinkListNode* DLinkList_Reset(DLinkList* list) {
	TDLinkList* sList = (TDLinkList*)list;
	DLinkListNode* ret = NULL;

	if (sList) {
		sList->slider = sList->header.next;
		ret = sList->slider;
	}

	return ret;
}

DLinkListNode* DLinkList_Current(DLinkList* list) {
	TDLinkList* sList = (TDLinkList*)list;
	DLinkListNode* ret = NULL;

	if (sList) {
		ret = sList->slider;
	}

	return ret;


}

DLinkListNode* DLinkList_Next(DLinkList* list) {
	TDLinkList* sList = (TDLinkList*)list;
	DLinkListNode* ret = NULL;

	if (sList && sList->slider) {
		ret = sList->slider;
		sList->slider = ret->next; 
	}

	return ret;//?此处的返回值对吗?

}


DLinkListNode* DLinkList_Pre(DLinkList* list) {
	TDLinkList* sList = (TDLinkList*)list;
	DLinkListNode* ret = NULL;

	if (sList && sList->slider) {
		ret = sList->slider;
		sList->slider = ret->pre;
	}

	return ret;//?此处的返回值对吗?

}

main.c

//双链表
#include "DLinkList.h"
struct Value
{
	DLinkListNode header;
	int v;
};
int main() {
	int i;
	DLinkList* list = DLinkList_Create();

	struct Value v1;
	struct Value v2;
	struct Value v3;
	struct Value v4;
	struct Value v5;

	v1.v = 1;
	v2.v = 2;
	v3.v = 3;
	v4.v = 4;
	v5.v = 5;

	DLinkList_Insert(list, &v1, DLinkList_Length(list));
	DLinkList_Insert(list, &v2, DLinkList_Length(list));
	DLinkList_Insert(list, &v3, DLinkList_Length(list));
	DLinkList_Insert(list, &v4, DLinkList_Length(list));
	DLinkList_Insert(list, &v5, DLinkList_Length(list));

	for ( i = 0; i < DLinkList_Length(list); i++)
	{
		struct Value* pv = (struct Value*)DLinkList_Get(list, i);
		printf("%d\n", pv->v);
	}

	printf("\n");

	DLinkList_Delete(list, DLinkList_Length(list) - 1);
	DLinkList_Delete(list, 0);

	for (i = 0; i < DLinkList_Length(list); i++)
	{
		struct Value* pv = (struct Value*)DLinkList_Next(list); //此处遍历分析:时间复杂度确实减低了!
		printf("%d\n", pv->v);
	}

	printf("\n");

	DLinkList_Reset(list);
	DLinkList_Next(list);

	struct Value* pv =  (struct Value*)DLinkList_Current(list);
	printf("%d\n", pv->v);

	printf("\n");

	DLinkList_DeleteNode(list, pv);
	pv = (struct Value*)DLinkList_Current(list);
	printf("%d\n\n", pv->v);

	DLinkList_Pre(list);
	pv = (struct Value*)DLinkList_Current(list);
	printf("%d\n\n", pv->v);

	printf("%d\n", DLinkList_Length(list));

	DLinkList_Destory(list);
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/322576.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

智能制造工业互联网建设方案——青创智通工业物联网

智能制造已经成为工业发展的重要趋势。智能制造系统架构与工业物联网建设方案作为实现智能制造的关键环节&#xff0c;对于推动工业转型升级和提升企业竞争力具有重要意义。青创智通工业物联网重点探讨智能制造系统架构与工业物联网建设方案的核心要素、实施步骤和未来发展方向…

vue-echarts踩坑,本地开发可以渲染echarts图表,线上环境图表渲染不出来

main.js全局注册v-chart组件 import VueECharts from "vue-echarts"; Vue.component("v-chart", VueECharts);在页面中使用 如上图&#xff0c;我开始写的静态数据&#xff0c;在data中定义了chartOption1:{…配置项…}, 在接口数据返回之后&#xff0c;…

AI能否真的取代程序员?

一个Java程序员从接到需求到最终开发完功能的流程大致如下 首先是理解原型图&#xff0c;设计表结构根据表结构编写增删改查代码与前端联调&#xff0c;完成功能开发 那么以上步骤AI能不能完成呢&#xff1f; 让我们试一下&#xff1a; 第一步&#xff0c;使用 AI助手 解析流…

【AI】无人零售和边缘计算

目录 一、什么是边缘计算 1.1 边缘计算的定义 1.2 边缘计算的作用 1.3 边缘计算的关键技术 1.4 边缘计算的应用场景 二、边缘计算在无人零售中的应用 一、什么是边缘计算 1.1 边缘计算的定义 边缘计算&#xff08;Edge Computing&#xff09;是一种分布式计算范式&#…

Android 事件机制探讨(1)

事件的传递主要有三个方法&#xff1a;dispatchTouchEvent(事件分发)、onInterceptTouchEvent(事件拦截)、onTouchEvent(事件消费)。如下图&#xff1a; 仔细看的话&#xff0c;图分为3层&#xff0c;从上往下依次是Activity、ViewGroup、View事件从左上角那个白色箭头开始&…

ssm基于WEB技术的在线商品交易平台的设计+vue论文

在线商品交易平台的设计与实现 摘要 近年来&#xff0c;信息化管理行业的不断兴起&#xff0c;使得人们的日常生活越来越离不开计算机和互联网技术。首先&#xff0c;根据收集到的用户需求分析&#xff0c;对设计系统有一个初步的认识与了解&#xff0c;确定在线商品交易平台的…

芯品荟 | 测亩仪市场调研报告

一、产品简介 1、什么是测亩仪&#xff1f; 测亩仪&#xff0c;又称面积测量仪&#xff0c;采用了卫星定位系统与高精度算法技术原理&#xff0c;可以精准测量出土地、水域的距离、周长、面积等数据的有效工具&#xff0c;被广泛应用于农田、林业、水域、公路、机械作业、野外…

OpenAIOps社区线上宣讲会圆满召开,期待您的加入!

2024年1月12日“OpenAIOps社区”线上宣讲会圆满召开&#xff0c;群体智慧协同创新社区的创立为AIOps领域未来发展注入了活力。OpenAIOps社区是一个AIOps开源社区及创新平台&#xff0c;由中国计算机学会(CCF)、清华大学、南开大学、中科院、国防科大、必示科技等单位共同发起&a…

智慧公厕:颠覆传统公共厕所管理的未来之路

公共卫生设施一直是城市管理中的重要环节&#xff0c;而智慧公厕作为一种全新的公用卫生设施&#xff0c;以其融合了物联网、大数据、云计算等新型信息技术的特点&#xff0c;引起了人们的广泛关注。通过智能化手段的管理和服务&#xff0c;智慧公厕不仅解决了传统公厕中存在的…

20240111在ubuntu20.04.6下解压缩RAR格式的压缩包

20240111在ubuntu20.04.6下解压缩RAR格式的压缩包 2024/1/11 18:25 百度搜搜&#xff1a;ubuntu rar文件怎么解压 rootrootrootroot-X99-Turbo:~/temp$ ll total 2916 drwx------ 3 rootroot rootroot 4096 1月 11 18:28 ./ drwxr-xr-x 25 rootroot rootroot 4096 1月…

C语言多线程基础(pthread)

1.线程和进程的概念 线程&#xff1a;进程中的一个实体&#xff0c;是CPU调度和分派的基本单位。可以与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程&#xff0c;同一进程中的多个线程之间可以并发执行&#xff0c;线程在运行中呈现间断…

MYSQL的事务隔离

本章概览 mysql是一个支持多引擎的系统&#xff0c;并不是所有引擎都支持事务&#xff0c;本篇以innodb为例解析mysql在事务支持的实现。提到事务一定会想到ACID(Atomicity、Consistency、Isolation、Durability&#xff0c;即原子性、一致性、隔离性、持久性)&#xff0c;今天…

Open CV 图像处理基础:(一)Open CV 在windows环境初始化和 Java 动态库加载方式介绍

Open CV 在windows环境初始化和 Java 动态库加载方式介绍 目录 Open CV 在windows环境初始化和 Java 动态库加载方式介绍前言OpenCV安装opencv-4.4.0下载安装 加载opencv-4.4.0.jar包jar包引入mavn-init.cmdjar包装载到本地maven仓库pom.xml加载动态库 加载动态库opencv_java44…

如何用Docker部署Nacos服务并结合内网穿透实现公网访问管理界面?

文章目录 1. Docker 运行Nacos2. 本地访问Nacos3. Linux安装Cpolar4. 配置Nacos UI界面公网地址5. 远程访问 Nacos UI界面6. 固定Nacos UI界面公网地址7. 固定地址访问Plik Nacos是阿里开放的一款中间件,也是一款服务注册中心&#xff0c;它主要提供三种功能&#xff1a;持久化…

App加固:不同类型和费用对比

文章目录 [TOC]引言应用程序加固是什么不同类型[App加固](https://www.ipaguard.com/)的费用对比基础加固高级加固云加固 白嫖的混淆加密工具](https://www.ipaguard.com/)-[ipaguard总结参考资料 引言 在当前移动应用市场中&#xff0c;安全性已经成为一个非常重要的话题。为…

ESP系列入门教程(一)——之用继电器简单驱动一个LED【附 ESP32 / ESP8266 通用代码】

ESP系列入门教程<一> 概要技术名词简介● ESP系列简介 硬件连接实现●ESP8266 引脚图●ESP32 引脚图 代码实现●Demo_1&#xff1a;控制LED闪烁●Demo_2&#xff1a;利用继电器驱动LED亮灭 概要 最近在跟着几个大佬的教学视频做项目。陆续会更新记录一些要点&#xff0c…

音频接口选型可应用于安防 音响 车载等产品中 高性能国产芯片

在人工智能兴起之后&#xff0c;安防市场就成为了其全球最大的市场&#xff0c;也是成功落地的最主要场景之一。对于安防应用而言&#xff0c;智慧摄像头、智慧交通、智慧城市等概念的不断涌现&#xff0c;对于芯片产业催生出海量需求。今天&#xff0c;我将为大家梳理GLOBALCH…

腾讯云价格计算器怎么用?太简单了一键报价

腾讯云服务器价格计算器可以一键计算出云服务器的精准报价&#xff0c;包括CVM实例规格价格、CPU内存费用、公网带宽收费、存储系统盘和数据盘详细费用&#xff0c;腾讯云百科txybk.com分享腾讯云价格计算器链接入口、使用方法说明&#xff1a; 腾讯云服务器价格计算器 打开腾…

第9章 通信动力与环境

文章目录 9.1.1 动力与环境的组成9.1.2 动力与环境的特点9.1.3 动力与环境的地位与作用9.1.4 动力与环境的基本要求9.2.1 通信电源的组成和结构9.2.2 交流供电系统1、交流供电系统的组成2、市电交流供电的质量指标3、常用高压电电器4、电力变压器5、常用低压电器6、油机发电机组…

深入解析JavaScript中的函数绑定和命名函数表达式

&#x1f9d1;‍&#x1f393; 个人主页&#xff1a;《爱蹦跶的大A阿》 &#x1f525;当前正在更新专栏&#xff1a;《VUE》 、《JavaScript保姆级教程》、《krpano》、《krpano中文文档》 ​ ​ ✨ 前言 函数是JavaScript中最重要的组成部分之一。但是函数的this绑定和作用…