数据结构与算法基础

数据结构与算法基础

  • 数组与矩阵
  • 线性表（栈、队列）
  • 广义表
  • 树和二叉树
  • 图
  • 排序与查找
  • 算法基础及常见的算法

数组

  • 一维数组
  • 二维数组：按行存储，按列存储
  • 多维数组

稀疏矩阵

  • 选择题，可使用代入法

image-20220915115820786

数据结构

  1. 数据结构的概念
  2. 数据逻辑结构
    • 线性结构（树、图）
    • 非线性结构

线性表-定义

  • 顺序表（空间连续，一维数组）
  • 链表（指针地址+数据，空间不连续）
    • 单链表
    • 循环链表
    • 双向链表
  • 链表的操作
    • 插入
    • 删除

线性表-顺序存储与链式存储对比

性能类别 具体项目 顺序存储 链式存储
空间性能 存储密度 =1，更优 <1
容量分配 事先确定 动态改变，更优
时间性能 查找运算 O(n/2) O(n/2)
读运算 O(1)，更优 O([n+1]/2)，最好情况下为1，最坏为n
插入运算 O(n/2)，最好情况下为0，最坏为n O(1)，更优
删除运算 O([n-1]/2) O(1)，更优

线性表-队列与栈

  • 队列：FIFO先进先出

  • 栈：LIFO先进后出

  • 循环队列：

    • 队空条件：head=tail

    • 队满条件：（tail+1）%size=head

      一般少存储一位，取余判定

广义表

定义：n个表元素组成的优先序列，是线性表的推广。

  • 表头head：表的首个元素
  • 表尾tail：除表头外的其他所有元素
  • 长度：表元素个数
  • 深度：子表元素个数

树与二叉树

  • 结点的度：孩子结点的个数
  • 树的度：最高的结点的度
  • 叶子结点
  • 分支结点
  • 内部结点
  • 父结点
  • 子结点
  • 兄弟结点
  1. 满二叉树
  2. 完全二叉树
  3. 非完全二叉树

二叉树的重要特性：

Snipaste_2022-09-16_11-20-02.png

二叉树遍历

  • 前序遍历（根-左-右）
  • 中序遍历（左-根-右）
  • 后续遍历（左-右-根）
  • 层次遍历

反向构造二叉树

  • 由两种序列可以得到原二叉树

树转二叉树

  • 多个兄弟结点，下方多余兄弟结点

查找二叉树（排序二叉树）

  • 二叉排序树
  • 左孩子小于根
  • 右孩子大于根

最优二叉树（哈夫曼树）

  • 树的路径长度
  • 权
  • 带权路径长度
  • 树的带权路径长度（树的代价）

线索二叉树

  • 为什么要有线索二叉树？

    因为二叉树部分节点为空，需要将这些空间利用起来。

    基本就是前序、中序、后序遍历得来的。

  • 前序线索二叉树

  • 中序线索二叉树

  • 后序线索二叉树

平衡二叉树

  • 平衡二叉树的提出原因

    为了提高查询效率

  • 平衡二叉树的定义

    任何结点的左右子树深度相差不超过1

    每结点的平衡度只能为-1、0或-1

    图-基本概念

  • 无向图：每对顶点之间都有一条线相连，完全图

  • 有向图：没对顶点之间互连，完全图

图的存储-邻接矩阵

  • 无向图：具有对称性，可只存上三角或者只存下三角

图的存储-邻接表

  • 首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。

图的遍历

  • 深度优先：一条路走到底，然后再走另一条（递归/栈）
  • 广度优先：逐个走每条路（队列）

图-拓扑排序

  • 我们把用有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示的活动网络，简称AOV网络。

图的最小生成树

  • 普里姆算法
  • 克鲁斯卡尔算法

算法基础-算法的特性

  • 有穷性
  • 确定性
  • 有效性

算法基础-算法的复杂度

  • 时间复杂度
    • O(1) < O(log2n) < O(n) < O(N*log2n) < O(n的平方) < O(n的3次方) < O(2的n次方)
  • 空间复杂度

查找

  • 顺序查找：
    • 时间复杂度：O(n)
    • 将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败
  • 二分查找：
    • 时间复杂度：O(log2n)
    • 前提：有序数列
  • 散列表：
    • 冲突的解决方法：当计算的存储地址有冲突的时候，继续查找下一个地址(散列函数 h=key%p)
      • 线性探测法
      • 伪随机数法

排序

  1. 排序的概念

    • 稳定与不稳定排序
    • 内排序与外排序

  2. 排序方法分类

    • 插入类排序（直接插入、希尔排序）
    • 交换类排序（冒泡排序、快速排序）
    • 选择类排序（简单选择排序、堆排序）
    • 归并排序
    • 基数排序

  3. 直接插入排序

    • 将一个元素插入到有序数组中

  4. 希尔排序

    • 分组插入

  5. 直接选择排序

    • 每次选择出最小的与当前位置交换

  6. 堆排序（Heap）

    • 特点
      1）完全二叉树
      2）heap中存储的值是偏序
  • 小顶堆（小根堆）：子节点都比父节点大
    • 大顶堆（大根堆）：子节点都比父节点小
  1. 冒泡排序
  2. 快速排序
    • 分治法
  3. 归并排序
  4. 基数排序
    • 按照个位、十位、百位 区分出来排序

Snipaste_2022-09-21_16-13-54.png