数据结构
2018-10-14 19:21:49 417 举报AI智能生成
数据结构 知识结构图（个人整理，仅供参考）
作者其他创作
大纲/内容
图
定义
基本概念及术语
有向图
无向图
简单图
多重图
完全图
子图
连通图
无向图中
强连通图
生成树
顶点的度
边
极
网
稠密图、稀疏图
路径
距离
有向图
存储
邻接矩阵法
邻接表法
邻接多重表
十字链表
遍历
深度优先遍历（DFS）
性能分析
生成树
广度优先遍历（BFS）
性能分析
求解最短路问题
广度优先生成树
应用
最小生成树（MST）
性质
最小生成树不是唯一的
最小生成树的边和权值之和总是唯一的
最小生成树的边数为顶点数减1
算法
Prim算法
Kruskal算法
最短路径
Dijkstra算法
Floyd算法
拓扑排序
有向无环图（DAG图）
一个有向图中不存在环
AOV网
关键路径
AOE网
查找
概念
静态查找
动态查找
线性结构
顺序查找
折半查找
分块查找
树形结构
二叉排序树
二叉平衡树
B树
B+树
散列结构
散列表
散列函数
直接定址法
除留余数法
数字分析法
平方取中法
折叠法
性能分析
散列地址的计算
冲突处理
开放定址法
线性探测法
平方探测法
再散列法
伪随机序列法
拉链法
字符串模式匹配
简单的模式匹配算法
KMP算法
next数组
效率指标
平均查找长度ASL
查找成功
查找失败
排序
概念
稳定性
衡量标准
时间复杂度
空间复杂度
内部排序
插入排序
直接插入排序
折半插入排序
希尔排序
交换排序
冒泡排序
快速排序
选择排序
简单选择排序
堆排序
归并排序
基数排序
外部排序
多路归并排序
绪论
数据结构（三要素）
逻辑结构
线性结构
一般线性表
受限线性表
栈
队列
串
线性表推广
数组
广义表
非线性结构
集合
树形结构
一般树
二叉树
图状结构
有向图
无向图
存储结构（物理结构）
顺序存储
链式存储
索引存储
散列存储
数据的运算
特征
算法定义
对特定问题求解步骤的一种描述
特性（五个）
有穷性
算法必须总是执行有穷步之后结束且每一步都在有穷时间完成
确定性
每一条指令必须有确切含义
可行性
算法是可行的
输入
有零个或多个输入
输出
有一个或多个输出
效率的度量
时间复杂度
T(n)=O(f(n))
规则
T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
T(n)=T1(n)xT2(n)=O(f(n))xO(g(n))=O(f(n)xg(n))
常见渐近时间复杂度
O(1)<O(log2(n))<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
空间复杂度
S(n)=O(g(n))
线性表
顺序存储
顺序表
顺序表最主要的特点是随机访问
基本操作
插入
删除
查找
链式存储
单链表
基本操作
建立
头插法
尾插法
查找
按序号查找
按值查找
插入
前插
后插
删除
双链表
基本操作
插入
删除
循环链表
循环单链表
循环双链表
静态链表
借助数组实现
顺序表和链表的比较
存取方式
顺序表
可以顺序存取也可以随机存取
链表
只能从表头顺序存取
逻辑结构和物理结构
顺序存储
逻辑上相邻的元素物理上也相邻
链式存储
逻辑上相邻的元素物理上不一定相邻
基本操作
查找
按值查找
顺序表无序的情况下，两者时间复杂度均为O(n)
顺序表有序的情况下，采用折半查找则时间复杂度为O(log2(n))
按序号查找
顺序表
支持随机访问，时间复杂度O(1)
链表
平均时间复杂度O(n)
插入、删除
顺序表
平均移动半个表的长度
链表
只需修改相关节点的指针域计科
空间分配
顺序存储
静态存储
一旦空间装满就不能扩充
动态存储
虽然存储空间可以扩村，但需要移动大量元素，效率降低
链式存储
节点空间只在需要的时候申请分配，操作灵活、高效
如何选取？
基于存储考虑
表的长度和存储规模难以估计时不宜采用顺序表
基于运算考虑
运算按序号访问元素时，顺序表优于链表；但在做插入、删除操作时链表优于顺序表
基于环境考虑
顺序表容易实现；链表操作基于指针
栈和队列
栈
特性
后进后出（Last In First Out，LIFO）
顺序存储
顺序栈
基本运算
初始化
判栈空
进栈
出栈
读取栈顶元素
共享栈
链式存储
链栈
队列
特性
先进先出（First In First Out，FIFO）
顺序存储
顺序队列
循环队列
区分队空还是队满
牺牲一个单元来区分队空和队满
队满
(Q.rear+1)%MaxSize==Q.front
队空
Q.front==Q.rear
队列元素个数
(Q.rear-Q.front+MaxSize）%MaxSize
类型中增设表示元素个数的数据成员
队满
Q.size==MaxSize
队空
Q.size==0
两种情况都有
Q.front==Q.rear
类型中增设tag数据成员
队满
tag=1
因插入导致Q.front==Q.rear
队空
tag=0
因删除导致Q.front==Q.rear
链式存储
队空
Q.front==NULL 且 Q.rear==NULL
链式队列
双端队列
两端都可以进行入队和队
数组
一维数组
存储结构关系式
LOC(ai)=LOC(a0)+(i)xL
多维数组
行优先
先行后列
存储关系式
......
列优先
先列后行
存储关系式
......
矩阵的压缩存储
指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间
特殊矩阵
对称矩阵
三角矩阵
三对角矩阵
稀疏矩阵
树与二叉树
树和森林
树
概念
N(N>=0)个结点的有限集合
空树
N=0
非空树
N!=0
有且仅有一个特定的称为根的结点
N>1时，其余结点可分为m(m>0)个互不相交的有限集合，其中，一个集合本身又是一棵树，并且称为根结点的子树
基本术语
度
结点的度
树中一个结点的子节点个数
树的度
树中结点的最大度数
结点
分支结点（非终端结点）
度大于0的结点
每个结点的分支数就是该结点的度
叶子结点（终端结点）
度为0的结点
层次
从树根开始定义，根节点为第1层...
深度
从跟结点开始自顶向下逐层累加
高度
从叶结点开始自底向上逐层累加
树的高度（深度）
树中结点的最大层数
有序树
树中结点的子树从左到右是有次序的，不能交换
无序树
树中结点没有次序，若交换结点位置，则变成一棵不同的树
路径和路径长度
树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的
路径长度是路径上所经过的边的个数
森林
森林是m(m>=0)棵互不相交的树的集合。
性质
树中的结点数等于所有结点的度数加1
度为m的树中第i层上至多有m^(i-1)个结点(i>=1)
高度为h的m叉树至多有(m^h -1)/(m-1)个结点
具有n个结点的m叉树的最小高度为[logm(n(m-1))+1)]
存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
操作
与二叉树的转换
树转换二叉树
森林转换二叉树
二叉树转换森林
遍历
先根遍历
树非空，先访问根节点，再按从左到右的顺序遍历根节点的每一棵子树
后根遍历
先序遍历
根—第一棵树—除去第一棵后的树
中序遍历
第一棵树—根—除去第一棵后的树
应用
并查集
Union(S,Root1,Root2)
Find(S,x)
Initial(S)
二叉树
概念
每个结点至多只有两棵子树，是有序树
与度为2的有序树的区别
度为2的树
至少有3个结点
孩子结点的左右次序是相对于另一孩子而言
二叉树
可以为空
结点次序不是相对于另一结点而言，而是确定的
特殊二叉树
满二叉树
高为h，且含有2^h -1个结点的二叉树
满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2
完全二叉树
高为h，含有n个结点的二叉树，当且仅当每一个结点都与高为h的满二叉树对应时
若i<=┗n/2┛,则结点i为分支结点，否则为叶子结点
叶子结点只可能在层次最大的两层出现
若有度为1的结点，只能有一个，且该结点只有左孩子而无右孩子
按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点
n的取值
n为奇数
每个分支结点都有左子女和右子女
n为偶数
编号最大的分支结点（编号n/2）只有左子女而没有右子女，其余分支都有
性质
非空二叉树上的叶子结点数等于度为2的结点数加1，即N0=N2 +1
非空二叉树上第K层上至多有2^(k-1) 个结点（K>=1）
高度为H的二叉树只有有2^H -1个结点(H>=1)
对完全二叉树按从上到下，从左到右的顺序依次编号1,2,...,N，则有
i>1时，结点i的双亲结点编号为┗i/2┛
i为偶数时，双亲编号i/2，是双亲的左孩子
i为奇数时，双亲编号(i-1)/2，是双亲的右孩子
2i<=N时，结点i的左孩子编号2i，否则无左孩子
2i+1<=N时，结点i的右孩子编号2i+1，否则无右孩子
结点i所在层次（深度）为┗log2 i┛+1
具有N个(N>0)结点的完全二叉树的高度为┏log2 (N+1)┓或┗log2 N┛ +1
存储结构
顺序存储
链式存储
操作
三种遍历
先序遍历 N-L-R
根—左—右
中序遍历 L-N-R
左—根—右
后序遍历 L-R-N
左—右—根
线索二叉树
定义
加上线索的二叉树（线索：指向结点前驱和后继的指针）
构造
遍历
应用
二叉排序树（BST）
或者是一棵空树，或者具有以下特性的树
左子树非空，则左子树所有结点关键字值小于根节点的
右子树非空，则右子树所有结点关键字值大于根节点的
左右子树本身也分别是一棵二叉排序树
操作
查找
插入
删除
效率分析
平均查找长度
平衡二叉树（AVL树）
左右子树高度差绝对值不超过1
操作
插入
旋转
LL平衡旋转（右单旋转）
RR平衡旋转（左单旋转）
LR平衡旋转（先左后右双旋转）
RL平衡旋转（先右后左双旋转）
查找
哈夫曼树
构造
步骤...
哈夫曼编码
0 条评论
下一页
