数据结构 - 草莓君的妙妙屋

# 数据结构
简单地梳理一下数据结构课程的主要内容

[TOC]

## 绪论
- 数据结构三要素
    - 逻辑结构
        - 线性结构：一般线性结构、栈、队列、数组、广义表
        - 非线性结构：集合、树形结构、图状结构
    - 存储（物理）结构
        - 顺序存储
        - 链式存储
        - 索引存储
        - 散列存储
    - 数据的运算
- 算法评估
    - 时间复杂度：基本运算的频度
    - 空间复杂度

## 线性表
- 顺序存储：顺序表
- 链式存储：
    - 单链表（指针）
    - 双链表（指针）
    - 循环链表（指针）
    - 静态链表（借助数组实现）

### 顺序表
- 定义
- 基本操作
    - 插入：平均移动 n/2 复杂度O(n)
    - 删除：好1 坏n 平均 (n-1)/2
    - 查找：平均 (n+1)/2
- 常考问题：
    - 就地逆置
    - 扫描的同时移动
    - 两表归并
    - 二分查找
    - 分区间反转

### 链表
- 定义：空间分配、头结点
- 基本单链表
    - 建表：头插法、尾插法
    - 插入、删除
    - 查找：按序号，按值
- 双链表：前后双指针
- 循环链表：头尾相连
- 静态链表 数组，每个元素包含当前值和下一个元素下标

## 栈和队列
- 操作受限线性表
    - 栈：顺序栈、链栈、共享栈
    - 队列：循环队列、链式队列、双端队列
- 推广：
    - 一维数组
    - 多维数组：压缩存储、稀疏矩阵
    - 广义表

### 栈
- 定义：栈顶、栈底、空栈
- 基本操作：初始化、判空、进出、取顶、销毁
- 顺序栈：数组、栈顶指针
- 共享栈：仅两个栈顶指针相邻时满，降低上溢发生的概率
- 链栈：不存在上溢

### 队列
- 定义：队头、队尾
- 基本操作：初始化、判空、出入、读队头
- 具体实现
    - 顺序存储：假溢出
    - 循环队列：顺序+取模
    - 链式存储
    - 双端队列：输入受限、输出受限 两端可以X仅一端可以Y

### 栈和队列应用
- 括号匹配
- 表达式求值：前缀 中缀 后缀转换
- 递归
- 合法序列
- 回文 字符串中心对称
- 判空 满 top=0 or -1两种情况
- 括号匹配
- 层次遍历

### 数组、矩阵
- 数组：行优先、列优先
- 压损存储：
    - 对称矩阵
    - 三角矩阵
    - 三对角矩阵
    - 稀疏矩阵：三元组

## 串
- 定义：字符组成的有限序列
- 存储：定长、堆分配、块链存储
- 基本操作：赋值、复制、判空、比较、连接....
- 模式匹配：
    - 暴力匹配法
    - KMP算法 next数组求解

## 树和二叉树
### 树的基本概念
- 根节点，前驱节点，后继结点，
- 双亲结点，孩子结点，子孙节点，祖先结点，
- 分支节点，叶子结点
- 层次，深度，高度
- 有序树，无序树（左右结点有无区分）
- 路径，路径长度，带权路径长度（所有节点）
- 森林
- 性质
    - 结点数(n) = 结点的度数(i x ni) + 1
    - 度为m的树i层上最多 m^(i-1)个结点
    - 高度为h的m叉树至多有(m^h -1)/(m-1)个结点

### 二叉树
- 定义
- 特殊的二叉树
    - 满二叉树：树中每层含最多结点
    - 完全二叉树：i<=int(n/2) 分支节点 其余为叶子结点 至多有1个度为1的结点
    - 二叉排序树：空树or二叉树且关键字 左<根<右
    - 平衡二叉树：左右子树高度差不超过1的二叉排序树
- 性质
    - 叶子结点树等于度为2的结点数+1  n0 = n2 + 1
    - 第k层上最多2^(k-1)个结点
    - 高度为h的二叉树上最多有2^h - 1个结点
    - 完全二叉树 编号1开始 任意结点i 左子2i 右子2i+1
    - 完全二叉树 i结点 层次 int(log2i) +1
    - n个结点完全二叉树高度 int(log2(n)) + 1
- 存储结构
    - **顺序**存储 自上而下由左至右编号 存在数组中
    - **链式**存储 data left right
- 二叉树的**遍历**
    - 先序遍历
    - 中序遍历
    - 后序遍历
    - 递归算法与非递归算法的转换
    - 层序遍历
    - 通过遍历构造二叉树：先中，后中，层中；仅先后序无法确定
- 线索二叉树
    - data, left, right, lflag, rflag
    - flag标记指的是子孙结点还是前驱（左） 后继（右）
    - 根据前驱后继又分 前中后序线索二叉树

### 树和森林
- 树的存储结构（树结点孩子个数不固定，无先后顺序）
    - 双亲表示法：数组or链表 每个结点 data paren
    - 孩子表示法：数组 data child链
    - 孩子兄弟表示法：左孩子右兄弟
- 树、森林与二叉树的转换
    - 树->二叉：左孩子右兄弟
    - 森林->二叉：每个树转二叉树，第一棵树作为转换后的根，二三四相继接在根的右侧
    - 二叉树->森林：先转成二叉树森林，再转树森林
- 树和森林的遍历
    - 树
        - 先根遍历  该树对应的二叉树**先序**遍历
        - 后根遍历  该树对应的二叉树**层次**遍历
    - 森林
        - 先序遍历
        - 中序遍历

### 树的应用
- 并查集，操作：并，查，初始化，常用双亲表示法+数组
- 二叉排序树
    - 定义， 中序遍历为递增有序序列
    - 查找，取决于树形
    - 插入，构造，删除
- 平衡二叉树
    - 定义
    - 插入，调整 LL，RR，LR，RL
    - 查找，平均logn
- 哈夫曼树、哈夫曼编码
    - 树的带权路径长度 = 所有叶节点带权路径长度之和
    - 使得 ↑ 最小的树
    - 构造：小的相结合
    - 二进制编码：树根开始左0 右1，前缀编码

## 图
- 定义，顶点集V，边集E
- 有向图、无向图
- 简单图，多重图：重复边，回到自身的边
- 完全图：任意两个结点之间存在边 
    - n顶点无向 n(n-1)/2  
    - 有向 n(n-1)
- 子图
- 连通图，连通分量
- 强连通图，强连通分量： 有向图
- 生成树，生成森林：包含所有顶点的极小连通子图；多个子图组成森林
- 顶点的度，入度，出度
- 边的权
- 稠密图，稀疏图
- 路径，路径长，贿赂

### 存储结构
- 邻接矩阵：
    - 顶点表，边表（邻接矩阵） N\*N
    - 适合存储稠密图
- 邻接表法：
    - 顶点表：data，firstarc  第一个出边
    - 边表：adjvex, nextarc  邻接点，下一边
    - 适合存储稀疏图
- 十字链表法
    - 有向图适用
    - 顶点结点  出边链，入边链
    - 弧结点 头，尾，下一指同头的弧，下一条指同尾的弧
- 邻接多重表
    - 无向图
    - 与十字链表类似  顶点结点仅1个边链

### 遍历
- 深度优先搜索 DFS
    - 递归 栈空间 O(V)
    - 邻接表 O(E + V)
    - 邻接矩阵 O(V^2) 查早每个顶点的邻接结点
    - 类似二叉树先序遍历
- 广度优先搜索 BFS
    - 辅助队列 空间 O(V)最坏
    - 邻接表 O(V + E)
    - 邻接矩阵 O(V^2)
- 图的遍历与连通性
    - 无向图：连通则一次遍历到所有点
    - 有向图：仅能判断是否强连通

### 应用
- 最小生成树
    - 权值之和最小，不唯一
    - Prim：选顶点开始，依次添加距离S集合最近的S外结点  类似dijkstra; 适合稠密图 O(V^2)
    - Kruskal：依次选不构成回路的最小边，添加进集合S；适合稀疏图 O(ElogE)
- 最短路径
    - Dijkstra：
        - 单源最短路径
        - 依次添加距离源点最近的结点，更新源点到其他各点的最短长度
        - path数组记录前驱节点用于溯源
        - 稀疏图 O(V^2)
    - Floyd：
        - 计算各顶点间的最短路径；
        - 方阵序列，依次在路径中加入新点，更新各点距离
        - 用辅助矩阵path记录路径
        - 稠密图 O(V^3) 比V次dijkstra高效 加上的额外因子小
- 关键路径
    - AOE网 边表示活动
    - 关键路径、关键活动  （减少这些时间可加快整体速度）
    - 事件V 最早最迟发生时间
    - 活动E 最早最迟开始时间
- 拓扑排序
    - 有向无环图 DAG图
    - AOV网  顶点表示活动
    - E边关系 先后关系
    - 拓扑排序产生序列依次消解
    - 可判断是否有环

## 查找
评价指标：平均查找长度ASL 成功和失败
### 线性结构
- 顺序查找
    - 哨兵
    - 成功 (n+1)/2, 失败 n + 1
    - 有序时，可降低失败的平均查找长度 n/2 + n/(n+1)
- 折半查找
    - 有序顺序表
    - low，high，mid
    - 成功 log(n+1) - 1
    - 失败看具体情况计算ASL
- 分块查找
    - 顺序查找+折半查找
    - 块间有序，块内无序
    - n 分 b块 每块s
    - s = √n 时候中最高效

### 树形结构（略）
- B树
- B+树

### 散列结构
- 散列函数，散列表
- 散列函数构造
    - 直接定址法
    - 除留余数法
    - 数字分析法
    - 平方取余法
    - 折叠法
- 冲突处理
    - 开放定址法：线性探测、平方探测法、再散列法
    - 拉链法
- 性能分析 装填因子：记录数/散列表长度

## 排序
- 排序的稳定性：相等大的元素排序后的相对位置变化与否
- 衡量标准：时空复杂度

### 算法描述
- 内部排序
    - 插入排序
        - 直接插入：有序|无序 两个区域，无序区域元素直接插入有序区域，边判断边移动
        - 折半插入：在直接插入的基础上通过折半查找插入位置，找到位置后统一移动元素
        - 希尔排序：用步长将表分为几个子表，在子表内直接插入排序，缩小步长继续排序 e.g. 步长 n/2, n/2/2
    - 交换排序
        - 冒泡排序：从后往前，两两比较交换，一趟排序没有交换即完成。
        - 快速排序：划分操作（左右比较向中移动找枢轴），一次确定一个元素的最终位置，左右递归排序。时间效率与是否平均划分有关。
    - 选择排序
        - 简单选择排序：每一趟排序选取一个无序区域最小元素和无序区第一个元素交换
        - 堆排序：大根堆小根堆，
            - 建堆 从最后一个有孩子的结点开始向上调整O(n) 
            - 删除 头尾交换，向下调整
            - 插入 插入末端向上调整
            - 排序 建堆 进行n-1次删除操作 O(n) + (n-1) * O(logn) O(nlogn)
    - 归并排序：由小到大前后两个子表归并
    - 基数排序：多次分配、收集
- 外部排序：多路归并排序

### 排序算法的比较

|算法名|时间复杂度|空间复杂度|稳定性|表的条件|备注|
|-|-|-|-|-|-|
|直接插入排序 |好O(n); 坏,平均O(n^2) |O(1) |稳定 | | |
|希尔排序 |O(n^3/2) |O(1) |不稳定 |仅顺序存储| |
|冒泡排序 |好O(n); 坏,平均O(n^2) |O(1) |稳定 | | 有序子序列全局有序 |
|**快速排序** |坏O(n^2); 好,平均**O(nlogn)** |O(logn)|**不稳定** |皆可，实现有差异|坏：基本有序|
|简单选择排序|O(n^2) |O(1)|不稳定| | |
|**堆排序** |**O(nlogn)** |O(1) |**不稳定** | | |
|**归并排序** |**O(nlogn)** |O(n) |**稳定** | |  |
|基数排序 |O(d+r) |O(r)|稳定 |d:分配数 r:队列数 | |

文章信息

标题：数据结构

作者：快刀切草莓君

分类：计算机基础课程

发布时间：2020年5月23日

最近编辑：2020年5月27日

浏览量：1460

↑