数据结构——链表详解

链表

文章目录

  • 链表
    • 前言
    • 认识链表
        • 单链表结构图
        • 带头单循环链表结构图
        • 双向循环链表结构图
        • 带头双向循环链表结构图
      • 链表特点
    • 链表实现(带头双向循环链表实现)
        • 链表结构体
        • (1) 新建头节点
        • (2) 建立新节点
        • (3)尾部插入节点
        • (4)删除节点
        • (5)头部插入节点
        • (6) 头删节点
        • (7) 寻找节点
        • (8) pos位置插入节点
        • (9) 删除pos位置节点
        • (10) 打印链表
        • 测试用例

前言

new一个奶黄包:没关系,这条路我陪你走到底

在这里插入图片描述

认识链表

单链表结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CAU6jKY6-1692328909256)(https://flowus.cn/preview/624afaec-e422-4877-8061-cb639a1325b7)]

带头单循环链表结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4euIvGQg-1692328833369)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image.png)]

双向循环链表结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1uetT2ky-1692328833370)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 1.png)]

带头双向循环链表结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ITJxFGxY-1692328833370)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 2.png)]

链表特点

  • 单链表在内存中,并不是连续存储的(逻辑上连续)。

  • 不支持随机访问

  • 插入时只需要改变指针指向

  • 没有容量的概念

  • 可以高效的在任意位置插入&&删除

  • 缓存利用率低

链表实现(带头双向循环链表实现)

链表结构体

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

(1) 新建头节点

LTNode* ListInit()//建立头节点
{
	LTNode* phead = buyListNode(-1); //建立一个带头节点
	phead->next = phead;      
	phead->prev = phead;

	return phead;
}

(2) 建立新节点

LTNode* buyListNode(LTDataType x)//创建内存初始化数据  
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	// 初始化:注意所对的结构来初始化
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}

(3)尾部插入节点

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyListNode(x);
	LTNode* tail = phead->prev;
  
	tail->next = newnode;
	newnode->prev = tail;

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uzvehYMH-1692328833370)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 3.png)]

(4)删除节点

void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;  //记录上一个节点
	LTNode* tailmove =tail->prev;  //记录上一个节点的上一个节点
  
	tailmove->next = phead;    
	phead->prev = tailmove;
  
	free(tail);
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hCUDDN9I-1692328833371)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 4.png)]

(5)头部插入节点

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyListNode(x); 
	LTNode* first = phead->next;

	newnode->next = first;
	first->prev = newnode;

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vx0P45G2-1692328833371)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 5.png)]

(6) 头删节点

void LTPopFront(LTNode* phead)
{
	assert(phead);  //判断是否有头节点
	assert(phead->next != NULL);  //判断第一个节点是否存在
	LTNode* tail = phead->next;
	LTNode* tailmove = tail->next;

	tailmove->prev = phead;
	phead->next = tailmove;

	tailmove->next = phead;
	phead->prev = tailmove;
	free(tail);
}

在这里插入图片描述

(7) 寻找节点

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			//printf("找到了");
			return cur;//返回指针
		}
      cur=cur->next; //每次都走到下一个节点直到phead
	}
	//printf("找不到");
	return NULL;
}

(8) pos位置插入节点

void LTInsert(LTNode* pos, LTDataType x)//头插尾插都可以调用这个函数 
{
	assert(pos);
	LTNode* newnode = buyListNode(x); //新建一个节点
	LTNode* prev = pos->prev;   //记录pos位置的前一个节点

	newnode->next = pos;   //新节点的下一个节点就是pos
	pos->prev = newnode;   //pos位置节点prve就链接后面

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

在这里插入图片描述

(9) 删除pos位置节点

void LTErase(LTNode* pos)  //删除节点
{
	assert(pos);
	LTNode* prve = pos->prev;
	LTNode* next = pos->next;

	prve->next = next;
	next->prev = prve;

	free(pos);
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1IWfpl22-1692328833371)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 7.png)]

(10) 打印链表

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

测试用例

void test1()
{
	LTNode* ptail = ListInit();
	LTPushBack(ptail, 1);
	LTPushBack(ptail, 3);
	LTPushBack(ptail, 2);
	LTPushBack(ptail, 4);
	LTPushBack(ptail, 5);
	LTPopBack(ptail);
	LTPrint(ptail);
}

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

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

相关文章

Unknown tree updater grow_gpu_histb报错

报错显示:由于xgboost的问题而报错 报错显示:Unknown tree updater grow_gpu_histb 原因是 XGBoost 在尝试使用 GPU 加速时无法识别指定的树更新器。也就是当前xgboost版本中没有grow_gpu_histb组件,所以需要安装正确的版本。 经搜索&#…

银河麒麟服务器v10 sp1 .Net6.0 上传文件错误

上一篇:银河麒麟服务器v10 sp1 部署.Net6.0 http https_csdn_aspnet的博客-CSDN博客 .NET 6之前,在Linux服务器上安装 libgdiplus 即可解决,libgdiplus是System.Drawing.Common原生端跨平台实现的主要提供者,是开源mono项目。地址…

ios swift5 collectionView 瀑布流(两列)

文章目录 1.瀑布流1.1 demo地址1.2 记得把部署的最低版本由8改成11,13甚至更高。不然编译会报错 2.动态计算图片和文字的高度 1.瀑布流 1.1 demo地址 CollectionViewWaterfallLayout - github 1.2 记得把部署的最低版本由8改成11,13甚至更高。不然编译会报错 2.动态计算图片和…

问道管理:机器人概念走势活跃,新时达涨停,拓斯达、丰立智能等大涨

机器人概念17日盘中走势活跃,到发稿,拓斯达大涨18%,昊志机电涨近16%,丰立智能涨超13%,步科股份、优德精细涨超10%,新时达涨停,天玑科技、兆龙互联、中大力德涨逾9%。 消息面上,8月16…

设计模式

本文主要介绍设计模式的主要设计原则和常用设计模式。 一、UML画图 1.类图 2.时序图 二、设计模式原则 1.单一职责原则 就是一个方法、一个类只做一件事; 2.开闭原则 就是软件的设计应该对拓展开放,对修改关闭,这在java中体现最明显的就…

spring详解

spring是于2003年兴起的一款轻量级的,非侵入式的IOC和AOP的一站式的java开发框架,为简化企业级应用开发而生。 轻量级的:指的是spring核心功能的jar包不大。 非侵入式的:业务代码不需要继承或实现spring中任何的类或接口 IOC&…

Spring5学习笔记—AOP编程

✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Spring专栏 ✨特色专栏: M…

国企的大数据岗位方向的分析

现如今大数据已无所不在,并且正被越来越广泛的被应用到历史、政治、科学、经济、商业甚至渗透到我们生活的方方面面中,获取的渠道也越来越便利。 今天我们就来聊一聊“大屏应用”,说到大屏就一定要聊到数据可视化,现如今&#xf…

eclipse 导入项目js报错问题

eclipse 导入项目后会出现项目中的js文件报错(红叉),如下图所示,有时候报错的文件很多,需要集中处理。 解决办法: 右键项目名称》Properties》MyEclipse》JavaScript》Include Path,在右侧选择“…

linux 文件权限识别及其修改

一、文件权限认识 在 Linux 系统中,一切皆文件,目录也是一种文件形式叫目录文件,它们的属性主要包含:索引节点(inode),类型、权限属性、链接数、所归属的用户和用户组、最近修改时间等内容。 如下为根目录下目录&…

基于OpenCV的人脸识别和模型训练系统(万字详解)

前言 我们身边的人脸识别有车站检票,监控人脸,无人超市,支付宝人脸支付,上班打卡,人脸解锁手机。 人脸检测是人脸识别系统组成的关键部分之一,其目的是检测出任意给定图片中的包含的一个或多个人脸&#…

网络通信原理IP头部格式(第四十二课)

字段作用解析:1)版本: 指的IP地址的版本 (IPv4 或 IPV6)2)首部长度: 次数据包的首部长度一共是多少,没有加可选项3)优先级与服务类型:表示****数据包是否需要优选传递4)总长度: 表示的是整个数据包的大小,也就****是首部+数据5)标识符、标志、段偏移量:的作用将拆开的…

ts与vue

ts与Vue 如果你已经学习了typeScript,但不知道如何在vue项目中使用,那么这篇文章将会很适合你。参考千峰教育 kerwin视频 1.会自动推导,隐士推导。提示 类型系统。 独立模块。 isolatedModules选项:是否配置为独立的模块。 减少报错 let …

Springboot项目启动后按顺序加载自定义类 (demo)

1. 实现ApplicationRunner接口, 重写run方法 import lombok.extern.slf4j.Slf4j; import org.springframework.boot.ApplicationArguments; import org.springframework.boot.ApplicationRunner; import org.springframework.core.annotation.Order; import org.springframewor…

IDEA项目实践——JavaWeb简介以及Servlet编程实战

系列文章目录 IDEA项目实践——创建Java项目以及创建Maven项目案例、使用数据库连接池创建项目简介 IDEWA项目实践——mybatis的一些基本原理以及案例 IDEA项目实践——动态SQL、关系映射、注解开发 IDEA项目实践——Spring框架简介,以及IOC注解 IDEA项目实践——Spring当…

mysql 03.查询(重点)

先准备测试数据,代码如下: -- 创建数据库 DROP DATABASE IF EXISTS mydb; CREATE DATABASE mydb; USE mydb;-- 创建student表 CREATE TABLE student (sid CHAR(6),sname VARCHAR(50),age INT,gender VARCHAR(50) DEFAULT male );-- 向student表插入数据…

好用的安卓手机投屏到mac分享

工具推荐:scrcpy github地址:https://github.com/Genymobile/scrcpy/tree/master mac使用方式 安装环境,打开terminal,执行以下命令,没有brew的先安装brew brew install scrcpy brew install android-platform-too…

运营商三要素 API:构建安全高效的身份验证系统

当今数字化的世界中,身份验证是各行各业中至关重要的一环。为了保护用户的隐私和数据安全,企业需要寻求一种既安全可靠又高效便捷的身份验证方式。运营商三要素 API 应运而生,为构建安全高效的身份验证系统提供了有力的解决方案。 运营商三要…

【卷积神经网络】卷积,池化,全连接

随着计算机硬件的升级与性能的提高,运算量已不再是阻碍深度学习发展的难题。卷积神经网络(Convolution Neural Network,CNN)是深度学习中一项代表性的工作,CNN 是受人脑对图像的理解过程启发而提出的模型,其…

【C++学习手札】一文带你认识C++虚函数(内层剖析)

食用指南:本文在有C基础的情况下食用更佳 🍀本文前置知识: C初识继承 ♈️今日夜电波:No title —REOL 1:02 ━━━━━━️💟──────── 4:03 …