数据结构

1 数据结构基本概念

数据：

  • 数据对象 (具有相同性质的数据元素的集合)
    • 数据元素
      • 数据项
  • 数据结构 (相互之间存在一种或多种特定关系的数据元素的集合)
  • 数据类型、抽象数据类型
    • 原子类型 - 其值不可再分
    • 结构类型 - 其值可以再分解成若干分量

1.1 数据结构三要素

  1. 逻辑结构 *(定义)
    • 集合结构
    • 线性结构 - 一对一 。
      • 有开头，有结尾
    • 树形结构 - 一对多
    • (网)图状结构 - 多对多
  2. 数据的运算
    • 增删改查
  3. 物理结构(存储结构) *(实现)
    • 顺序存储
    • 非顺序存储
      • 链式存储
      • 索引存储 - 存储元素信息的同时，建立附加的索引表
      • 散列存储 - Hash存储

数据的存储结构会影响存储空间分配的方便程度，也会影响对数据运算的速度

1.2 算法 Algorithm

算法：对特定问题求解步骤的一种描述，它是指令的有限序列

​ 程序 = 数据结构 + 算法

1.2.1 算法的特性

  • 有穷性 - 一个算法必须在执行有穷步后结束，且每一步都在有穷时间内完成
  • 确定性 - 算法中每条指令必须有确切的含义，对于相同的输入必须得到相同的输出
  • 可行性 - 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  • 输入 - 一个算法有零个或多个输入
  • 输出 - 一个算法有一个或多个输出

1.2.2 好算法的特性

  • 正确性 - 算法应能够正确的解决问题
  • 可读性
  • 健壮性
  • 高效率与低存储量需求

*1.2.3 算法效率的度量

时间复杂度

​ 事先预估算法时间开销T(n)与问题规模n的关系

大O表示法

  • T1(n) = O(n)
  • T2(n) = O(n^2)
  • T3(n) = O(n^3)

复杂度量级排序：常对幂指阶

image-20241125184429729

  • 顺序执行的代码只会影响常数项，可以忽略
  • 只需挑循环中的一个基本操作分析它的执行次数与n的关系即可
  • 如果有多层嵌套循环，只需关注最深层循环 循环了几次

image-20241125185824828

空间复杂度

image-20241126151214824

image-20241126151841651

2 线性表

逻辑结构上 a1-a2-a3-a4-a5

物理结构上分为：

  • 顺序存储
  • 链式存储

2.1 定义和基本操作

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。 L = (a1, a2, … , ai, a(i+1), … , an )

注意：数据元素的位序从1开始

2.2 顺序表

顺序表的特点：

  • 随机访问，可以在O(1)时间内找到第i个元素 -> data[i-1]
  • 存储密度高，每个节点只存储数据元素
  • 要求大片连续空间，拓展容量不方便
  • 插入、删除操作不方便，需要移动大量元素

代码实现：

​ List.cpp

2.3 单链表

单链表的特点：

  • 优点：不要求大片连续空间，改变容量方便
  • 缺点：不可随机存取，要耗费一定空间存放指针

代码实现：

​ LinkList.cpp

考点：

2.4 双链表

解决了单链表无法逆向检索的缺点

代码实现：

​ DoubleLinkList.cpp

2.5 循环链表

2.5.1 循环单链表

特点：从一个结点出发，可以到达任意一个结点。

拓：如果设定 链表L指向末尾结点，可以在循环单链表基础上更高效的提高对头尾操作的效率

代码实现：

​ CircularLinkList.cpp

2.5.2 循环双链表

循环双链表结构图

代码实现：

​ CircularDoubleLinkList.cpp

2.6 静态链表

(早期不支持指针的低级语言 使用这个数据结构 代替单链表)

单链表：各个结点在内存中星罗棋布 静态链表：分配一整片连续的内存空间，各个结点集中安置

特点：容量固定不变, 不可以拓展

  • 优点：增、删 操作不需要大量移动元素
  • 缺点：不能随机存取，只能从头结点开始依次往后查

定义：每一个静态链表的结点 包含本身的数据 和下一个结点的数组索引

代码实现：

​ StaticLinkList.cpp

2.7 顺序表和链表的对比

2.7.1 逻辑结构对比

​ 都属于线性表，都是线性结构

2.7.2 物理结构对比

  • 顺序表：
    • 支持随机存取、存储密度高
    • 需要大片连续内存，改变容量不方便
  • 链表：
    • 离散的小空间分配方便，改变容量方便
    • 不可随机存取、存储密度低

2.7.3 基本操作对比

创：

  • 创建顺序表时，因为拓展容量不方便，需要预分配大片连续空间。若分配过大则会浪费内存资源。
  • 创建链表时，只需要声明一个头指针，并可以按需求选择是否分配头结点

销：

  • 销毁顺序表
    • 静态分配内存时，只需要修改Lenght=0，生命周期结束后自动回收
    • 动态(malloc)分配内存时，需要手动free(L.data)
  • 销毁链表，需要一次删除各个结点free()

增删：

  • 顺序表
    • 插入/删除 元素 都要将所有元素 进行前移/后移
    • 时间复杂度O(n), 主要来自于移动元素
  • 链表
    • 插入/删除 只需要修改对应指针即可
    • 时间复杂度O(n), 主要来自于找到目标元素，但一般来说 增删元素 链表的效率要比顺序表高

查：

  • 顺序表 支持随机存取
    • 按位查找 O(1)
    • 按值查找 O(n) ，若表内元素有序，可在O(log2n)时间内找到
  • 链表
    • 按位查找 和 按值查找 都是 O(n)

一般来说，查找元素 顺序表的效率要比链表高

2.7.4 如何选择

顺序表链表
弹性(可扩容)😭😄
增、删😭😄
查😄😭

表长难以估计、经常需要增/删元素 -> 链表 表长可预估、经常需要查询(搜索) -> 顺序表

3 栈

栈：只允许在一端进行插入或删除操作的线性表

特点：先进后出，后进先出 Last In First Out (LIFO)

重要术语：

  • 栈顶：允许插入和删除的一端
  • 栈底：不允许插入和删除的一端
  • 空栈

3.1 顺序栈

使用静态数组实现，并需要记录栈顶指针

设计方式(需要理解不同设计方式 的 不同代码实现)：

  • 初始化时 top=-1;
  • 初始化时 top=0;

缺点：栈的大小不可变

代码实现：

​ SqStack.cpp

3.2 共享栈

两个栈共享同一片内存空间

代码实现：

​ ShStack.cpp

3.3 链栈

链栈相当于是只能对头结点进行后插和后删操作的单链表 链头 = 栈顶

推荐在实现链栈时使用不带头结点的单链表

代码实现：

​ LinkStack.cpp

4 队列

队列(Queue)：只允许在一端插入，在另一端删除的线性表 双端队列：只允许在两端插入，在两端删除的线性表

队头：允许被删除的一端 队尾：允许插入的一端

特点：先进先出(FIFO)

考点：判断输出序列是否合法 对于输入元素个数n，总共有 $\frac{1}{n+1}C^n_{2n}$ (卡特兰数)个序列结果

4.1 顺序队列 (循环队列)

难点：入队时的队列已满判断, 即为什么顺序队列 也叫 循环队列 (用模运算将存储空间在逻辑上变成了“环状”)

考点：队列元素的个数 (Q.rear + MaxSize - Q.front) % MaxSize

代码实现：

​ SqQueue.cpp

4.2 链队列

特点：队列的长度可自由拓展(除非物理机器内存不够)

代码实现(分为带和不带头结点的版本, 代码已全部包含)：

​ LinkQueue.cpp

4.3 双端队列

特点：只允许在两端插入，在两端删除的线性表

还可以延伸为：

  • 双端队列，允许两端插入、两端删除
  • 输入受限的双端队列，允许一端插入、两端删除
  • 输出受限的双端队列，允许两端插入、一端删除
  • 如果退化为只允许单端输入输出，就成了栈
  • 如果退化为只允许单端输入、另一端输出，就成了普通队列

考点：判断输出序列是否合法 对于输入元素个数n，总共有 $A^n_n$ 也就是n!个序列结果

5 栈和队列的应用问题

5.1 栈的括号匹配问题

用栈实现括号匹配： 依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。

匹配失败情况：

  • 左括号单身
  • 右括号单身
  • 左右括号不匹配

代码实现：

​ 栈的括号匹配问题.cpp

5.2 栈的表达式求值问题

5.2.1 三种算术表达式

对于一个算术表达式，由 操作数、运算符、界限符 三部分组成

  • 前缀表达式 (波兰表达式) -> 运算符在两个操作数的前面(+ab)
  • 中缀表达式 -> 运算符在两个操作数的中间(a+b)
  • 后缀表达式 (逆波兰表达式) -> 运算符在两个操作数的后面(ab+)

例：中缀: a+b-c 后缀: ab+c- 前缀: -+abc 例：中缀: a+b-c*d 后缀: ab+cd-* 前缀: -+ab*cd

​ 在进行中缀表达式 转 后缀表达式时，要遵循 左优先原则 同样，在进行中缀表达式 转 前缀表达式时，要遵循 右优先原则

注⚠️： 对于左优先的后缀表达式，先出栈的元素是右操作数 而对于右优先的前缀表达式，先出栈的元素是左操作数

5.2.2 中缀->后缀表达式(栈实现)

5.2.2.png

5.2.3 后缀表达式计算(栈实现)

5.2.3.png

5.3 栈的递归应用

函数调用的特点：最后被调用的函数最先执行结束(LIFO)

本节内容需要理解：函数递归栈的原理

函数调用时，需要用一个函数调用栈存储： 调用返回地址、实参、局部变量

递归调用时，函数调用栈可称为递归工作栈 每进入一层递归，就将递归调用所需信息压入栈顶 每退出一层递归，就从栈顶弹出相应信息

5.4 队列的应用

  • 树的层次遍历
  • 图的广度优先遍历
  • 队列在操作系统中的应用
    • 就绪进程队列 - 多个进程争抢着使用有限的系统资源时 使用队列进行FCFS (First Come First Service) 策略
    • 打印数据缓冲区 FIFO

5.5 矩阵的压缩存储

本节的内容是：矩阵的物理存储方式

一些数据类型的存储结构：

  • 一维数组 - 物理上连续的线性存储
  • 二维数组 - 物理上连续的线性存储，分为行优先存储和列优先存储两种

普通矩阵的存储：二维数组

考点：矩阵下标 映射 一维数组下标

特殊矩阵的存储

  • 对称矩阵 - 只存储对角线和下三角区(或上三角区)的数据

    • 按行/列优先原则将个元素存入一维数组
    • 则数组的长度为 $\frac{n(n+1)}{2}$个 (等差数列求和) (n为行数)
    • 考点：求矩阵元素 ${a_i,_j}$ 的物理存储位置

  • 三角矩阵 - 只存储主对角线和下三角区(或上三角区)的数据

    • 三角矩阵除了主对角线和下三角区 其他的元素都相同为常量C
    • 存储策略：按行优先原则将主对角线和下三角区元素存入一维数组，并在最后一个位置存储C
      • 那么第 $\frac{n(n+1)}{2}$个元素就为C，即数组下标为$\frac{n(n+1)}{2}-1$

  • 三对角矩阵 - 带状矩阵

    • 元素总个数 -> 3n-2
    • 存储策略：按行优先原则 只存储带状部分
    • 当 |i-j|>1 时， 有$a_i,_j$=0 (1<=i, j<= n)

  • 稀疏矩阵的压缩存储

X0 参考文献

该笔记归纳自 https://www.bilibili.com/video/BV1b7411N798