C++ | 四、指针、链表

指针

  • 指针用来储存地址
  • 定义方式,int *ptr;,使用*来表示所定义的变量是指针
  • 取地址符,ptr = &a;,通过&来取得一个普通变量的地址,并储存到指针中
  • 取值(解引用),想要取得一个指针变量所指向地址里储存的值,也是使用符号*,如b = *ptr即会把指针变量ptr存储地址里对应的值赋给b
  • 指针和数组的关系,实际上,数据结构就是基于指针设计的,例如数组int arr[2] = {1, 2};,其数组名arr实际上是一个存储了数组第一个元素地址的指针,比如可以使用int *ptr = arr;来把数组首元素的地址赋值给ptr
  • 指针的加减,指针可以通过加减来读取当前地址的相邻地址,并在使用取值符*(解引用)后可以读取相邻地址里的值,如int data = *(ptr + 2);
  • 空地址,C++中,使用一个特殊的字符nullptr用来表示当前指针不指向任何有效的内存地址,如int *ptr = nullptr;

链表基础知识

  • C++中为什么要使用链表结构
    • 可以充分利用小块的内存空间:因为诸如数组等数据结构,其必须占据一片连续的内存空间,此时如果数据量较大,则一些小内存空间就无法被利用,造成空间浪费;链表在内存中不连续储存,因此可以充分利用内存空间,具体见后面关于链表存储方式的介绍
    • 大小可变:数组不可变大小,因此不够灵活,而链表可以方便的进行增删等操作
    • 增删元素效率高:其它很多数据结构中,以增加元素为例,在增加之后,需要把后续所有元素都进行挪位,此时将严重影响效率,如图;而链表就没有这个问题,只需要改变所增加节点和其前一个节点,就可以完成增加元素的操作
    • 然而,链表也有缺点,就是查询效率低。这是因为链表中想要得到某一个节点的值,那就必须从前序节点依次寻址知道找到该节点
      • 其它数据结构增删效率低
  • 链表的结构:链表由多个节点组成,每个节点包括数据域data和指针域next,分别存储当前节点的数据和下一节点的地址
    • 链表的结构
    • 链表的第一个节点称为头节点head,在C++中,为了简化链表的插入和删除元素操作,通常在头节点前添加一个虚拟头节点dummyNode(可以不添加该虚拟头节点),该虚拟节点的data可以为空,但是next指针指向头节点的地址
    • 最后一个节点的next为nullptr
  • 链表的不同类型
    • 单链表,前面所提到的就是单链表,即单向链表,每个节点只存储下一节点的地址
    • 双链表,即双向链表,每个节点除了next指向下一节点外,还有prev指向上一节点,因此可以双向查询
      • 双链表
    • 循环链表,即头尾相接,也就是最后一个节点的next存储了头节点的地址(这种链表可以用来解决约瑟夫环的问题)
      • 循环链表
  • 链表的存储方式
    • 链表中的各个节点通过指针互相关联,因此不需要连续存储,具体的分配机制依不同的操作系统的内存管理机制而定
      • 链表的存储方式

链表节点结构体(struct)的自定义

  • 结构体struct可以用来自定义用户想要的数据类型,其地位等价于int、float、double这些数据类型(下面有一个结构体示例ListNode)
    • 结构体可以组合多种数据类型,如整型、浮点型、其它结构体等等
    • 定义一个结构体即一种新的数据类型之后,就可以使用该数据类型定义变量了
    • 定义的时候有多种初始化方式,常见的一种是使用构造函数。构造函数也是一种函数,但是它没有返回类型和返回值,另外它和结构体的名称相同,例如对于下面定义的这个ListNode结构体,其构造函数可以写为ListNode(int x) : val(x), next(nullptr) {},这里int x是形参,: val(x), next(nullptr)是一种初始化写法,冒号表示初始化列表的开始,后面表示val被赋值为x,next被赋值为nullptr
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}  // 节点结构的构造函数
};

链表的操作

  • 删除节点
    • 将所删除节点上一节点的next指向所删除节点的下一节点即可
    • 在C++中,由于内存需要自己管理,因此最好把所删除节点的内存手动释放掉
    • 删除节点
  • 添加节点
    • 只要把所添加节点位置的上一节点指向所添加节点,再把所添加节点的next指向下一节点即可
    • 添加节点

时间复杂度性能分析

  • 可以看到,上面添加和删除节点操作本身的时间复杂度为O(1),但是要找到对应的节点位置(即查询)的时间复杂度为O(n),因此链表适用于需要频繁增删但是较少查询的场景
  • 性能对比
  • 有关时间复杂度更具体的介绍见我的另一篇文章

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

15.鸿蒙HarmonyOS App(JAVA)进度条与圆形进度条

15.鸿蒙HarmonyOS App(JAVA)进度条与圆形进度条 progressBar2.setIndeterminate(true);//设置无限模式,运行查看动态效果 //创建并设置无限模式元素 ShapeElement element new ShapeElement(); element.setBounds(0,0,50,50); element.setRgbColor(new RgbColor(255,0,0)); …

排序——计数排序

文章目录 概念思路绝对映射:相对映射 代码实现特性结果演示 概念 计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(nk)(其中k是整数的范围…

typora导出html添加目录

typora导出html添加目录 使用方法 首先要从typora导出html文件,之后用记事本编辑器html文件 找到文档最后面,如图: 用文字编辑类工具打开sideBar.txt,复制其中所有内容【内容在下面】 在如上图的位置插入所复制的内容 打开修改…

【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)

HashMap工作原理全揭秘 — 核心源码解析 知识盲点概念介绍数据结构数组链表数组VS链表哈希表不同JVM版本HashMap的展现形式 HashMap VS HashTable特性区别对比 hashcodehashCode的作用equals方法和hashcode的关系key为null怎么办执行步骤 核心参数容量探讨负载因子探讨加载因子…

usb个人总结

一、usb工具分析 1、不同的usb抓包工具抓包分析 2、USB抓包分析方式 外接usb分析仪分析 (1)力科usb分析仪 (2)HD-USB12 协议分析仪 (3)沁恒CH552 usb分析仪,软件工具USB2.0 Monitor (4)等等…

PHP留言板实现

完整教程PHP留言板 登陆界面 一个初学者的留言板(登录和注册)_php留言板登录注册-CSDN博客 留言板功能介绍 百度网盘 请输入提取码 进入百度网盘后,输入提取码:knxt,即可下载项目素材和游客访问页面的模板文件。 &…

基于springboot书籍学习平台源码和论文

首先,论文一开始便是清楚的论述了平台的研究内容。其次,剖析平台需求分析,弄明白“做什么”,分析包括业务分析和业务流程的分析以及用例分析,更进一步明确平台的需求。然后在明白了平台的需求基础上需要进一步地设计平台,主要包罗软件架构模式、整体功能模块、数据库设计。本项…

数学建模-Matlab R2022a安装步骤

软件介绍 MATLAB是一款商业数学软件,用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境,主要包括MATLAB和Simulink两大部分,可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程…

行云部署成长之路 -- 慢 SQL 优化之旅 | 京东云技术团队

当项目的SQL查询慢得像蜗牛爬行时,用户的耐心也在一点点被消耗,作为研发,我们可不想看到这样的事。这篇文章将结合行云部署项目的实践经验,带你走进SQL优化的奇妙世界,一起探索如何让那些龟速的查询飞起来!…

【C++干货铺】会旋转的二叉树——AVLTree

个人主页点击直达:小白不是程序媛 C系列专栏:C干货铺 代码仓库:Gitee 目录 前言 AVL树 AVL树的概念 AVL树结点的定义 AVL树的插入 寻找插入结点的位置 修改平衡因子 AVL树的旋转 右单旋 左单旋 先右旋再左旋 先左旋再右旋 AVL树…

SpringBoot多环境配置Maven Profile组

Maven profile组 注意切换配置时 mvn clean下 或者 clean 加install 或者compile 编译 clean之后 install下 或者compile 编译 nohup java -Xms256m -Xmx512m -Dfile.encodingUTF-8 -jar demo.jar --spring.profiles.activeprod > system.log 2>&1 &

数据交付变革:研发到产运自助化的转型之路

作者 | Chris 导读 本文讲述为了提升产运侧数据观察、分析、决策的效率,支持业务的快速迭代,移动生态数据研发部对数仓建模与BI工具完成升级,采用宽表建模与TDA平台相结合的方案,一站式自助解决数据应用需求。在此过程中&#xff…

软件测试|如何使用selenium操作窗口滚动条

简介 我们在进行自动化测试工作的时候,如果页面内容过多,一次性加载耗时太长的话,会使用分段加载来加载页面内容,比如开始只加载页面顶端的内容,而如果要加载更多的数据,就需要我们向下滑动,让…

跳跃游戏,经典算法实战。

🏆作者简介,普修罗双战士,一直追求不断学习和成长,在技术的道路上持续探索和实践。 🏆多年互联网行业从业经验,历任核心研发工程师,项目技术负责人。 🎉欢迎 👍点赞✍评论…

Go 优雅判断 interface 是否为 nil

关注公众号【爱发白日梦的后端】分享技术干货、读书笔记、开源项目、实战经验、高效开发工具等,您的关注将是我的更新动力! 背景 很久之前发过一篇文章:《10个令人惊叹的Go语言技巧,让你的代码更加优雅》,这篇文章中第…

Dockerfile: CMD与ENTRYPOINT区别

CMD和ENTRYPOINT的作用 CMD和ENTRYPOINT这两个命令,我接触到的是用在了Dockerfile中用于构建容器。 CMD:The main purpose of a CMD is to provide defaults for an executing container. CMD的主要用途是为正在执行的容器提供默认值。也就是指定这个容…

如何用ArcGIS制作城市用地适应性评价

01概述 “城市用地适宜性评价是城市总体规划的一项重要前期工作,它首先对工程地质、社会经济和生态环境等要素进行单项用地适宜性评价,然后用地图叠加技术根据每个因子所占权重生成综合的用地适宜性评价结果,俗称“千层饼模式”。 做用地适…

外包干了4年,废了···

有一说一,外包没有给很高的薪资,是真不能干呀! 先说一下自己的情况,大专生,19年通过校招进入湖南某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了&#xff0…

tensorflow报错: DNN library is no found

错误描述 如上图在执行程序的时候,会出现 DNN library is no found 的报错 解决办法 这个错误基本上说明你安装的 cudnn有问题,或者没有安装这个工具。 首先检测一下你是否安装了 cudnn 进入CUDA_HOME下,也就是进入你的cuda的驱动的安装目…

rime中州韵小狼毫 联想词组 滤镜

教程目录:rime中州韵小狼毫须鼠管安装配置教程 保姆级教程 100增强功能配置教程 在 rime中州韵小狼毫 自定义词典 一文中,我们分享了如何在rime中州韵小狼毫须鼠管输入法中定义用户自定义词典;通过自定义词典,我们可以很方便的在…