点击查看【bilibili】

数据结构：数据在内存里的格式

数组/列表/向量 Array/List/Vector

定义：数组的值一个个连续存在内存里
优点：方便访问数组中的元素，通过数组下标访问相应元素，时间复杂度为 O(1)
缺点：在中间插入值很难
image.png

字符串 String

定义：字符串就是字母,数字,标点符号等组成的数组。需要注意的是，字符串在内存中以 二进制值0 为结尾（\0，不是 字符0）
image.png

多维数组/矩阵 Matrix

定义：矩阵就是数组的数组。
特征：矩阵可以做任意维度
image.png

结构体 Struct

定义：多个不同类型的数据，打包在一起存储
image.png

节点 node

定义：节点是一个结构体，存一个（或多个）变量和一个（或多个）指针

  • 指针 Pointer：特殊变量，指向一个内存地址

image.png

链表 Linked List

定义：链表由多个节点组成，每个节点的指针指向下一个节点。非循环链表的最后一个节点的指针指向 null value。链表在内存中的存储不连续。
优点：链表是一种灵活的数据结构，可以动态增减，插入新节点很方便，也很容易重新排序、两端缩减、分割、倒序等
变种：循环链表、双向链表等；很多复杂的数据结构的实现：队列、栈、树等
image.png

队列 Queue

特征：FIFO，先进先出
操作：入队、出队

栈 Stack

特征：FILO，先进后出
操作：入栈 push、出栈 pop

树 Tree

定义：将链表的节点改一下，改成包含多个指针，就成了树。若节点包含两个指针，即一个节点最多有两个子节点，则为二叉树。
特征：树的最高节点（无父节点）称为 根节点 root，根节点下的所有节点都称为 子节点 children，任何子节点的直属上层节点称为 父节点 parent。没有任何子节点的节点，称为 叶节点 leaf。
性质：根节点到叶节点，是单向连接的

图 Graph

定义：图与树的区别在于，图的节点是随意连接的，包括循环

其他数据结构

除了以上基本结构，还有各种不同性质的新变体，例如：

  • 红黑树 red-black tree
  • 堆 heap
  • …