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