C++ | 四、指针、链表

发布时间:2024年01月15日

指针

  • 指针用来储存地址
  • 定义方式,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),因此链表适用于需要频繁增删但是较少查询的场景
  • 性能对比
  • 有关时间复杂度更具体的介绍见我的另一篇文章
文章来源:https://blog.csdn.net/weixin_45055622/article/details/135610964
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。