数据结构与算法
2021-09-18 21:23:54 3 举报排序算法、线性表、树、图
作者其他创作
大纲/内容
概述
数据结构
数据结构就是把数据元素按照一定的关系组织起来的集合， 用来组织和存储数据
分类
逻辑结构
集合结构
同一集合内，元素间无关系
线性结构
一对一
树形结构
一对多
图形结构
多对多
物理结构
顺序存储结构
链式存储结构
算法
根据一定的条件，对一些数据进行计算，得到需要的结果
案例
计算1 ~ 100的和
计算10的阶乘
算法分析
时间复杂度
函数渐近增长
算法函数中的 常数 可以忽略
算法函数中 最高次幂的常数因子 可以忽略
算法函数中 最高次幂越小，算法 效率越高
大O记法
T(n) = O(f(n))
T(n)增长最慢的算法为最优算法
规则
用 常数1 取代运行时间中的所有加法常数
O(3) ---> O(1)
在修改后的运行次数中，只保留高阶项
O(n+3) ---> O(n)
如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数
O(2n^2) ---> O(n^2)
常见的大O阶
线性阶 O(n)
非嵌套循环
平方阶 O(n^2)
嵌套循环
立方阶 O(n^3)
三层嵌套循环
对数阶 O(logn)
常数阶 O(1)
不涉及循环
最坏情况
通常提到的运行时间都指的是 最坏情况下的运行时间
算法复杂度默认指的就是时间复杂度
空间复杂度
java中常见内存占用
计算机访问内存的方式都是 一次1个字节
一个变量引用（机器地址）需要 8个字节 表示
创建一个对象，自身开销是 16个字节，用来保存对象的头信息
一般内存的使用，如果不够8个字节，都会被 自动填充为8字节
数组对象头信息：24字节（16字节对象开销 + 4字节保存长度 + 4字节填充）
S(n) = O(f(n))
嵌入式开发对空间要求高
排序算法
简单排序
冒泡排序
O(N^2) (平方阶)
稳定
选择排序
O(N^2) (平方阶)
不稳定
插入排序
O(N^2) (平方阶)
稳定
高级排序
希尔排序
不稳定
单次查询推荐用
归并排序
O(n*logn) (对数阶)
以空间换时间
稳定
多次查询推荐用
快速排序
O(n*logn) (对数阶)
大数据量时，可能栈溢出
不稳定
线性表
顺序表
底层：数组
物理存储 和 逻辑 上的相邻关系 相同
运行时需改变容量
迭代处理
案例：ArrayList
查询快、增删慢
链表
由一系列的 结点 组成；结点包含指针
物理存储上是非连续的
查询慢、增删快
分类
单向链表
头结点
数据域：null
指针域：指向 第一个真正存储数据的结点
双向链表
头结点
数据域：null
前驱结点：null
后继结点：指向 第一个真正存储数据的结点
案例：LinkedList
循环链表
链表反转
把结点指针的 指向 进行修改
用递归实现
快慢指针
中间值
判断单向链表是否有环问题
查找有环链表入口
约瑟夫问题
栈
只在一端添加、删除
先进后出 FILO
压栈、弹栈
添加元素时，是在链表头，不是结尾
案例
括号匹配问题
逆波兰表达式求值问题
符号表
存储键值对
键具有唯一性
有序符号表
key实现Comparable接口
队列
一端进，另一端出
先进先出 FIFO
树
概念
树是由n（n>=1）个有限结点组成一个具有层次关系的集合
特点
每个结点
有 零个或多个 子结点
根结点
没有父结点
非根结点
只有一个 父结点
子树
当前结点及其后代结点的整体
术语
结点的度
结点子树的个数
叶结点
度为0的结点
分支结点
度不为0的结点
结点的层次
从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
结点的层序编号
从上到下，同层从左到右
连续的自然数
线性序列
树的度
树中所有结点的度的最大值
树的高度(深度)
树中结点的最大层次
森林
m（m>=0）个互不相交的树的集合
将一颗非空树的根结点删去，树就变成一个森林
给森林增加一个统一的根结点，森林就变成一棵树
孩子结点
结点的 直接 后继结点
双亲结点(父结点)
结点的 直接 前驱结点
兄弟结点
同一双亲结点的孩子结点间
二叉树
定义
度不超过2的树 (每个结点最多有两个子结点)
自顶向下生长
分类
普通二叉树
满二叉树
每一个层的结点树都达到 最大值
完全二叉树
叶节点只能出现在 最下层 和 次下层
最下面一层的结点都集中在该层 最左边 的若干位置
除最下层外，其余层都是满的
实现
Node结点类
键值对 key、value
左结点 left
右结点 right
API
插入 put
put(K key, V value)
public
put(Node x, K key, V value)
private
递归实现
获取 get
get(K key)
public
get(Node x, K key)
private
递归实现
删除 delete
delete(K key)
public
delete(Node x, K key)
private
递归实现
大小 size()
最小键 min()
while 循环
递归
min()
public
min(Node x)
private
递归实现
最大键 max()
while 循环
递归
max()
public
max(Node x)
private
递归实现
遍历
基础遍历
前序遍历
根左右
preErgodic()
public
返回 keys 队列
preErgodic(Node x, Queue<K> keys)
private
递归实现
中序遍历
左根右
结果是有序的
midErgodic()
public
返回 keys 队列
midErgodic(Node x, Queue<K> keys)
private
递归实现
步骤
找到当前结点的左子树，如果不为空，递归遍历左子树
把当前结点的key放入到队列中
找到当前结点的右子树，如果不为空，递归遍历右子树
后序遍历
左右根
afterErgodic()
public
返回 keys 队列
afterErgodic(Node x, Queue<K> keys)
private
递归实现
高级遍历
层序遍历
从上往下 从左到右
layerErgodic()
public
返回 keys 队列
实现
结果队列 keys
辅助队列 nodes
把结点node存入nodes 从root开始
弹出node，把node的key存入keys中
如果node有左子结点，存入nodes
如果node有右子结点，存入nodes
重复 2、3、4步，得到最终keys
最大深度 maxDepth()
树的根节点到最远叶子结点的 最长路径上的结点数
maxDepth()
public
maxDepth(Node x)
private
递归实现
案例
折纸问题
堆
特性
完全二叉树
通常用 数组 来实现
数组 0 处舍弃不用
根结点最大: 在 位置1
结点 k
父结点 k/2
左子结点 2*k
右子结点 2*k+1
每个结点都 大于等于 它的两个子结点
两个子结点左右顺序不固定
API
类名
Heap<T extends Comparable<T>>
构造方法
Heap(int capacity)
this.items = (T[]) new Comparable[capacity+1];
容量为capacity + 1
成员方法
插入 insert(T t)
public
结尾插入 新元素上浮
删除最大 delMax()
public
索引1处元素为最大元素
交换索引1处 和 最大索引处的元素
删除最大索引处元素，设为null
索引1处新元素下沉
比较 less(int i, int j)
private
交换 exch(int i, int j)
private
上浮 swim(int k)
private
下沉 sink(int k)
private
成员变量
存储元素的数组 T[] items
元素个数 int n
堆排序
性能 强于 希尔、归并、快速排序
静态API
排序 sort(Comparable[] source)
public
创建堆 createHeap(Comparable[] source, Comparable[] heap)
private
元素数量的一半位置 n/2
之前为非叶子结点
遍历 下沉
之后为叶子结点
比较 less(Comparable[] heap, int i, int j)
private
交换 exch(Comparable[] heap, int i, int j)
private
下沉 sink(Comparable[] heap, int target, int range)
private
优先队列
最大优先队列
最大堆
索引1处元素最大
最大元素相当于优先级最高
API
类名
MaxPriorityQueue<T extends Comparable<T>>
构造方法
MaxPriorityQueue(int capacity)
this.items = (T[]) new Comparable[capacity+1];
容量为capacity + 1
成员方法
插入 insert(T t)
public
结尾插入 新元素上浮
删除最大 delMax()
public
索引1处元素为最大元素
交换索引1处 和 最大索引处的元素
删除最大索引处元素，设为null
索引1处新元素下沉
比较 less(int i, int j)
private
交换 exch(int i, int j)
private
上浮 swim(int k)
private
下沉 sink(int k)
private
成员变量
存储元素的数组 T[] items
元素个数 int n
最小优先队列
最小堆
索引1处元素最小
最小元素相当于优先级最高
API
类名
MinPriorityQueue<T extends Comparable<T>>
构造方法
MinPriorityQueue(int capacity)
this.items = (T[]) new Comparable[capacity+1];
容量为capacity + 1
成员方法
插入 insert(T t)
public
结尾插入 新元素上浮
删除最小 delMin()
public
索引1处元素为最小元素
交换索引1处 和 最大索引处的元素
删除最大索引处元素，设为null
索引1处新元素下沉
比较 less(int i, int j)
private
交换 exch(int i, int j)
private
上浮 swim(int k)
private
下沉 sink(int k)
private
成员变量
存储元素的数组 T[] items
元素个数 int n
索引优先队列
最小堆
辅助数组
pq
存 items 数组中元素的索引
实现最小堆 有序
堆的直接操作对象
qp
pq 数组的逆序
pq 的值等于 qp 的索引
pq 的索引等于 qp 的值
qp 索引与 items 索引对应
API
类名
IndexMinPriorityQueue<T extends Comparable<T>>
构造方法
IndexMinPriorityQueue(int capacity)
this.items = (T[]) new Comparable[capacity+1];
容量为capacity + 1
成员方法
插入 insert(int i, T t)
public
pq 结尾插入 新元素上浮
t 在 items 中的关联索引 i
删除最小 delMin()
public
pq 中索引1处元素为最小元素的索引
交换 pq 中索引1处 和 最大索引处的元素
删除 pq 中最大索引处元素，设为-1
pq 中索引1处新元素下沉
删除 qp、items 中相关内容
删除 delete(int i)
public
得到 items 的索引 i 在 pq 中的位置 k=qp[i]
交换 pq 中索引 k 处和最大处 n 的值
删除 qp、items、pq 相应内容
元素数量减 1
k 处的新元素下沉 sink(k)
修改 changeItem(int i, T t)
public
把 items 中索引 i 对应的元素修改为 t
把 items 中索引 i 对应的元素修改为 t
得到 items 中索引 i 在 pq 中的位置 k=qp[i]
堆调整：下沉、上浮
比较 less(int i, int j)
private
items[pq[i]].compareTo(items[pq[j]]) < 0
交换 exch(int i, int j)
private
交换 pq 和 qp
上浮 swim(int k)
private
下沉 sink(int k)
private
包含 contains(int k)
public
最小元素关联索引 minIndex()
public
成员变量
存储元素的数组 T[] items
元素个数 int n
辅助数组 pq
保存 items 中元素的索引
辅助数组 qp
pq数组 的逆序
平衡树
2-3查找树
定义
2结点
一个键、两条链
3结点
两个键、三条链
自底向上生长
红黑树
5大特性
节点是红色或黑色
根是黑色
所有叶子都是黑色
叶子是NIL节点
每个红色节点必有两个黑色子节点
不能有两个连接的红节点
黑色平衡
从任一节点到其叶子的所有简单路径上有相同数量的黑节点
核心方法
左旋
右旋
变色
Java实现类
java.util.TreeMap
B树
概念
一个结点允许多个key存在
时间复杂度 O(log n)
增删查改
M阶
每个节点最多有 M-1 个key
升序排列
每个节点最多有 M 个子节点
根节点至少有 两个 子节点
B+树
特征
B树的一种变形树
非叶结点仅具有索引作用
只存储key，不存储value
所有叶结点构成一个有序链表
优点
内存相同时，能存更多的key
非叶结点只存key，不存value
叶子结点相连
对整棵树的遍历只需要一次线性遍历叶子结点即可
便于 区间查找和搜索
数据库中的应用
索引
并查集
树型的数据结构
高效操作
查询
元素p和元素q是否属于同一组
合并
元素p和元素q所在的组
结构
每个元素都 唯一 的对应一个结点
每一组数据中的多个元素都在 同一颗树 中
不同组对应的树之间没有任何联系
元素在树中并 没有子父级关系 的硬性要求
核心API
int[] eleAndGroup
索引 表示结点
值 表示结点所在组的标识符
connected(int p, int q)
判断元素p和q是否在同一个分组中
union(int p, int q)
把元素p合并到q所在的分组
时间复杂度
O(N^2)
优化
优化API
int[] eleAndGroup
索引 表示结点
值 表示该结点的父结点
find(int p) 查询
union(int p,int q) 合并
时间复杂度
最坏情况下 O(N^2)
路径压缩
union(int p, int q)
尽可能减小树的深度
把较小的树连接到较大的树上
图
定义
由一组 顶点 和一组能够将两个顶点相连的 边 组成的
特殊的图
自环
平行边
分类
无向图
有向图
无向图
相关术语
相邻顶点
两个顶点通过一条边相连
边依附于两个顶点
顶点的度
依附于该顶点的边的个数
子图
一幅图的所有边的子集 (包含这些边依附的顶点)组成的图
路径
由边顺序连接的一系列的顶点组成
环
至少含有一条边且终点和起点相同的路径
连通图
任意一个顶点都存在一条路径到达另外一个顶点
连通子图
一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图
存储结构
存储内容
所有顶点
所有边
分类
邻接矩阵
二维数组
空间复杂度是 V^2
邻接表
队列数组
Queue[V] adj
索引 是顶点
值 表示：与该顶点相邻的其他顶点
搜索
深度优先
先找子结点，再找兄弟结点
API
boolean[V] marked
索引 代表顶点
值 代表当前顶点是否已经搜索
dfs(Graph g,int v)
找出g图中与v相通的所有顶点
广度优先
先找兄弟结点，再找子结点
API
boolean[V] marked
索引 代表顶点
值 代表当前顶点是否已经搜索
bfs(Graph g,int v)
找出g图中与v相通的所有顶点
层序遍历
路径查找
加权无向图
每条边关联一个权重值或是成本的图模型
边 Edge
顶点v
顶点w
权重weight
API
顶点数量 v
边数量 e
邻接表 Queue<Edge>[] adj
最小生成树
定义
包含所有顶点
无环连通子图
图中权值(权重之和)最小的生成树
原理
树的性质
用一条边连接树中的任意两个顶点都会产生 一个新的环
从树中删除任意一条边，将会得到 两棵独立的树
切分定理
切分
非分 没有交集
将图的所有顶点按照某些规则分为两个 非空 且 没有交集 的集合
横切边
连接两个属于不同集合的顶点的边
在一副加权图中，给定任意的切分，它的 横切边中的权重最小者 必然属于图中的最小生成树
贪心算法
切分定理
Prim算法
顶点切分成两个集合
最小生成树顶点
非最小生成树顶点
最小索引优先队列
索引 --> 顶点
索引值表示图的顶点
值 --> 边权重
值 表示从其他某个顶点到当前顶点的 边权重
kruskal算法
原理
按照边的权重(从小到大)处理它们
将边加入最小生成树中
加入的边 不会 与已经加入最小生成树的边构成 环
直到树中含有 V-1 条边为止
最小优先队列
有向图
定义
一副具有方向性的图
相关术语
出度
由某个顶点指出的边的个数
入度
指向某个顶点的边的个数
有向路径
由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点
有向环
一条至少含有一条边，且起点和终点相同的有向路径
两个顶点间关系
没有边相连
v --> w
w --> v
v --> w
w --> v
w --> v
拓扑排序
概述
给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级
检测有向图中的环
顶点排序
加权有向图
边 DirectedEdge
起点v
终点w
权重weight
API
顶点数量 v
边数量 e
邻接表 Queue<Edge>[] adj
最短路径
定义
总权重最小 的路径
性质
路径具有方向性
权重不一定等价于距离
只考虑连通图
最短路径不一定是唯一的
最短路径树
松驰技术
边的松驰
顶点的松驰
Dijkstra算法
迪杰斯特拉
DirectedEdge[] edgeTo
索引 代表顶点
值 表示从顶点s到当前顶点的最短路径上的 最后一条边
relax(EdgeWeightedDigraph g,int v)
松驰加权有向图g中的顶点v
0 条评论
下一页
