导图社区 数据结构与算法
- 87
- 14
- 2
- 举报
数据结构与算法
典型排序算法，查找算以及图算法的分析
编辑于2020-08-11 08:26:10
- 相似推荐
- 大纲
数据结构
基本概念和术语
数据
基本单位
数据元素
由数据项组成
不可分割的最小单位
数据项
结构
逻辑结构
数据元素之间的逻辑关系
物理结构
在计算机中存储结构
算法
指令的有序序列
有穷性、确定性、可行性
线性结构
线性表
实现
顺序表
试用于随机存取等操作
插入/删除：O(n)
插入移动次数：n/2
删除移动次数
(n-1)/2
求表长/取第i个数据元素：O(1)
链表
线性链表/单链表
非随机存取的存储结构
插入：s->next=p->next;p->next=s;删除：p->next=p->next->next;复杂度O(n)
静态链表
用一维数组表示，用游标cur来代替指针，第0分量看成头节点
双向链表
结点有两个指针域
删除/插入：O(n)
循环链表
表中最后一个节点的指针域指向头节点
应用
一元多项式的表示和相加
栈和队列
栈
后进后出（仅在表尾进行插删除操作）
实现
顺序栈(Page46、47)
非空栈中的栈顶指针始终在栈顶元素的下一个位置上
插入/删除：top+-1;
链栈
共享栈
应用
数值转换
括号匹配检验
行编译程序
迷宫求解
表达式求值
操作数、运算符、界限符
实现递归
队列
先进先出（在表的一端进行插入，在另一端进行删除操作
实现
链队列
头指针和尾指针
队列为空：头指针和尾指针均指向头节点
循环队列
front\rear,非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置
判断满/空
空
Q.fornt==Q.rear
满
Q。front==(Q.rear+1)%MAxSize
双端队列
串
由字符组成的有限序列
空串or空格串
子串
串中任意连续个字符组成的子序列
数目S=(1+n)n/2+1
实现
定长顺序存储
堆分配存储表示
串的块链存储表示
模式匹配算法
主串S,模式串T
朴素模式匹配算法
O((n-m+1)*n)
KMP算法
next[]数组的计算
三种情况
注意和原串数组下标有些错位，因为next[0]=0
nextval[]数组的计算
当next[j]=k;pj=pk时，next[j]=next[k];
算法时间复杂度
O(n*m),接近于O(n+m)
特点
指示主串的指针不需回溯
串操作应用
数组和广义表
数组
只有存取元素和修改元素值的操作，一般不做插入/删除操作
实现
顺序存储
矩阵的压缩存储
特殊矩阵
n阶对称矩阵
存储下三角/上三角(Page95-96)
下三角
i>=j:i(i-1)/2+j-1
对角矩阵
稀疏矩阵
三元组顺序表
转置运算
将矩阵的行列值互换
将每个三元组中的i和j相互调换
重排三元组之间的次序
行逻辑链接的顺序表
十字链表
广义表
定义
表头：第一个元素
原子a和子表A
表尾：其余元素组成的表
区分：()与(())
任何一个非空列表，其表头可能是原子/列表，其表尾必然是列表
求广义表的深度
括弧的重数
实现
链式存储结构
表结点
标志域、指示表头/表尾的指针域
原子结点
标志域和值域
树形结构
树
结点
终端结点/叶子
分支结点
基本术语
结点的度
结点拥有的子树数
孩子、双亲、兄弟、堂兄弟
深度
有序树、无序树
存储结构
双亲表示法
孩子表示法
孩子兄弟表示法/二叉链表表示法
右指针指向兄弟
树和森林的遍历
树
先根遍历
后根遍历
以二叉链表做为树的存储结构时，先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历实现
森林
森林的先序
对应二叉树的先序遍历
森林的中序
二叉树的中序遍历
二叉树
定义
每个结点至多只有两棵子树（不存在度大于2的结点），子树次序不能颠倒，有左右之分
5种基本形态
性质
在二叉树第i层上至多有2^(i-1)个结点
深度为k的二叉树至多有2^k-1个结点
任何一棵二叉树，叶子结点数为n0，度为2的结点数为n2，则n0=n2+1
完全二叉树
具有n个结点的完全二叉树的深度为ëlognû+1
特点
对任意结点
满二叉树
深度为k且有2^k-1个结点
存储结构
顺序存储结构
链式存储结构
在含有n个结点的二叉链表中有n+1个空链域
子主题
应用
遍历二叉树
前序遍历
VLR
中序遍历
LVR
后序遍历
LRV
已知前序遍历+中序遍历，求后序遍历
前序遍历第一个结点为根结点，中序遍历可断开左右分段
已知后序遍历+中序遍历，求前序遍历
后序遍历最后一个结点是根节点
在二叉树结点的先序、中序、后序遍历中，所有叶子节点的先后顺序相同
前序遍历和中序遍历，得到唯一的一棵二叉树
线索二叉树
作用
加快查找结点的前驱或后继的速度
前序和后序线索化后，空链域为1； 中序线索化后，空链域为2
最优二叉树/赫夫曼树
路径长度
路径上的分支数目
树的带权路径长度
WPL=åwl
构造
page145
赫夫曼编码
前缀编码
二叉树
赫夫曼树的结点个数一定是奇数
森林与二叉树的转换
子主题
一棵树可转换成唯一的一棵没有右子树的二叉树
树的计数
n个结点的不相似的二叉树有--棵Page154
具有n个结点有不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同
内部排序
判断排序方法是否稳定
待排序记录存放在计算机随机存储器中进行的排序
插入排序
直接插入排序
正序时比较次数达n-1，逆序时比较次数为1/2n(n-1)
时间复杂度O(n*n)
是稳定的排序
折半插入排序
时间复杂度为O(n*n)
2-路插入排序
需要n个记录的辅助空间
表插入排序
以修改指针代替移动记录
结果进行重排
先互换，再修改指针域
时间复杂度仍为O(n*n)
希尔排序
先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
将相隔某个“增量”的记录组成一个子序列
时间复杂度比直接插入低
应使增量序列中的值没有除1以外的公因子，并且最后一个增量值必须等于1
是不稳定的排序算法
快速排序
起泡排序
一趟排序：将第一个记录和第二个记录比较，再将第二个与第三个记录比较
若初始为正序序列，则只需进行一趟排序，若初始为逆序序列，则需进行n-1趟排序
时间复杂度O(n*n)
是稳定的排序算法
快速排序
枢轴
O(nlogn)
若初始记录按关键字有序或基本有序时，快速排序将退化为起泡排序，时间复杂度为O(n*n)
空间复杂度
需要一个栈来实现递归，最大深度可降为O(logn)
是不稳定的排序算法
选择排序
简单选择排序
关键字的比较次数为n(n-1)/2
不受记录的初始排列影响
时间复杂度O(n*n)
是一种不稳定的排序
树形选择排序
首先对n个记录的关键字进行两两比较，在其中én/2ù个较小者之间再两两比较，直至选出最小/大的
可用一棵有n个叶子结点的完全二叉树表示
O(nlogn)
堆排序
堆
若看成完全二叉树，则完全二叉树额所有非终端结点的值均不大/小于其左、右孩子结点的值
小顶堆、大顶堆
一个记录大小供交换用的辅助空间，每个待排序的记录仅占有一个存储空间
对n较大的文件比较有效
最坏情况下，时间复杂度O(nlogn)
空间复杂度O(1)
是不稳定的排序方法
归并排序
时间复杂度O(nlogn)
空间复杂度O(n)
是稳定的排序方法
基数排序
MSD与LSD
多关键字排序
查找
查找表
关键字
主关键字、副关键字
性能分析
平均查找长度ASL
静态查找表
查找元素存在性、检索属性
顺序表的查找
顺序查找（可设置哨兵）
在等概率情况下ASL=(n+1)/2
有序表的查找
折半查找
适用于采用顺序存储结构的有序表（对线性链表无法有效地查找
性能分析
近似ASL=log(n+1)-1
索引顺序表的查找
索引表
表有序或者分块有序
确定块的查找可以顺序/折半查找，块中只能顺序查找
性能分析
表长为n,每一块的记录个数为s,则ASL=log(n/s+1)+s/2
与n、s都有关，可能效率不如折半查找
动态查找表
查找过程中进行插入/删除操作
二叉排序树
性质
左子树若不为空，左子树上所有结点的值均小于它的根节点的值
右子树若不为空，右子树上所有结点的值均大于它的根节点的值
它的左、右子树也分别为二叉排序树
中序遍历一棵二叉排序树可得到一个关键字的有序序列
插入
新插入的结点一定是新添加的叶子结点
删除
三种情况
查找
子主题
平衡二叉树AVL
性质
左子树和右子树均为平衡二叉树，且左右子树深度之差的绝对值不超过1.
平衡因子
左子树深度-右子树深度
AVL树只能为1、0、-1
平衡树的生成（调整规律）
单向右旋平衡处理
单向左旋平衡处理
双向旋转（先左后右）平衡处理
先右后左平衡处理
查找性能分析
时间复杂度O(logn)
B-树和B+树
B-树
m阶B-树特性
树中每个结点至多有m棵子树
若根节点不为叶子结点，则至少有两棵子树
除根之外的所有非终端结点至少有ém/2ù棵子树
所有的非终端结点中包含信息数据
(n,A0,K1,A1,....Kn,An)
Ki关键字，Ki<K(i+1)
个数范围
Ai指向子树根结点的指针，A(i-1)所指子树中所有结点的关键字均小于Ki,An所指子树中所有结点的关键字均大于Kn
所有的叶子节点都出现在同一层次上，并且不带信息。
查找分析
Page240-241
插入
溢出
分裂，向上移
删除
下溢
合并
B+树
特性
有n棵子树的结点包含有n个关键字
其他
查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。即无论查找成功与否，每次查找都是走了一条从根到叶子结点的路径。
插入和删除仅在叶子结点进行
键树
度³2的树，树中每个结点中只含有组成关键字的符号
哈希表
对应关系：哈希函数
定义
哈希表、散列、哈希/散列地址Page253
构造方法
直接定址法
关键字/关键字的线性函数值
数字分析法
取关键字的若干数位组成哈希地址
平方取中法
取关键字平方的中间几位为哈希地址
折叠法
分割，再叠加
除数留余法
p选择质数或者不包含小于20的质因数的合数
随机数法
处理冲突的方法
开放定址法
di增量序列
di=1,2,3,...
线性探测再散列
易发生二次聚集
S»1/2(1+1/(1-a))
di=1*1,2*2,...
二次探测再散列
di=伪随机数序列
伪随机探测再散列
再哈希法
链地址法
建立公共溢出区
查找
装填因子
a=表中填入的记录数/哈希表的长度
平均查找长度依赖于装填因子
见Page261
图状/网状结构
基本术语
顶点
弧（有向图）
弧尾
弧的初始点
弧头
弧的终端点
边（无向图）
无向图
eÎ[1,1/2*n(n-1)]
有向图
eÎ[0，n(n-1)]
完全图、有向完全图
e分别取上面的最大值
稀疏图
子图
邻接点、依附、相关联
度
和顶点v相关联边的数目TD(v)
出度
入度
回路或环
简单路径
顶点不重复出现的路径
连通
连通图
图中任意两个顶点间都连通
连通分量
无向图中的极大连通子图
强连通图
有向图中，每两点间都可以相互到达
强连通分量
有向图的极大连通子图
一个连通图的生成树是一个极小连通子图
网
带权的图
存储结构
数组表示法
对于无向图，顶点Vi的度是邻接矩阵中第i行/列的元素之和
对于有向图，第i行元素的和是顶点Vi的出度OD(Vi),第j列元素的和是顶点Vj的入度ID(Vj)
邻接表
每个顶点建立一个单链表
若无向图有n个顶点，e条边，则邻接表需要n个头结点和2e个表结点
为方便计算有向图中顶点的入度，可以建立一个有向图的逆邻接表
十字链表
邻接多重表
图的遍历
深度优先搜索(DFS)
类似于树的先根遍历
时间复杂度
当用邻接表存储图时，O(n+e)
利用递归/栈来实现
广度优先搜索(BFS)
类似于树的按层次遍历
利用队列
时间复杂度
和DFS相同
图的连通性问题
无向图
对无向连通图遍历时，仅需从图中任意一点出发，进行DFS/BFS，便可访问到所有顶点。对非连通图则需从多个顶点进行搜索
生成树
深度/广度优先生成树
有向图
利用DFS求有向图的强连通分量
最小生成树
Prim算法
时间复杂度O(n*n)
试用于求边稠密的网
Kruskal算法
时间复杂度O(eloge)
试用于求边稀疏的网
关节点和重连通分量
关节点
若删去该顶点及其关联的边后，将一个连通分量分割成两个以上的连通分量
两类关节点的特性
重连通图
没有关节点的连通图
利用深度优先搜索可以求得关节点，并由此判断图是否重连通
连通度k
在该连通图上至少删去k个顶点才能破坏连通性
有向无环图
拓扑排序
由某个集合上的一个偏序得到集合上的一个全序
AOV网
顶点表示活动，弧表示活动间的优先关系的有向图
如何进行拓扑排序
在有向图中选一个没有前驱的顶点且输出
从图中删除该顶点和所有以它为尾的弧
重复以上两步，直至全部顶点均已输出，或者当前不存在无前驱的顶点为止。后一种情况说明有向图中有环。
也可利用DFS,按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列
AOE网
顶点表示事件，弧表示活动（activity on edge），权表示活动持续的时间
可用来估算工程的完成时间
源点、汇点
关键路径
路径长度最长的路径，即为完成工程的最短时间
e(i)
活动ai的最早开始时间
l(i)
活动ai最迟必须开始的时间
关键活动
e(i)=l(i)
关键路径上的活动都是关键活动（提前完成非关键活动不能并不能加快工程进度）
ve(i)
事件的最早发生时间
计算时应从ve(0)向前递推
vl(i)
事件的最迟发生时间
计算时从vl(n-1)=ve(n-1)向前后递推
求关键路径的算法
最短路径
从某个源点到其余各顶点的最短路径
Dijkstra算法
内容Page187-189
时间复杂度O(n*n)
每一对顶点之间的最短路径
关系：e=1/2åTD(v)