导图社区数据结构

数据结构

数据结构的知识点来啦！数据结构的知识但复杂难懂，很多人在期末复习时都无从下手，下图从数据结构基本概念、线性表、栈和队列、树与二叉树、查找技术等知识点进行详细的归纳与总结，期末考试轻松拿高分！

提示: 本内容由社区用户上传并分享。平台不对内容的真实性、合法性、知识产权归属及是否侵害第三方权利进行事前审核或保证。本内容可能包含受版权保护的图片、字体或其他第三方素材，使用前请自行确认授权范围。

编辑于2019-12-31 06:06:19

CleFke

他的近期作品查看更多>>

数据结构
数据结构的知识点来啦！数据结构的知识但复杂难懂，很多人在期末复习时都无从下手，下图从数据结构基本概念、线性表、栈和队列、树与二叉树、查找技术等知识点进行详细的归纳与总结，期末考试轻松拿高分！

数据结构

社区模板帮助中心，点此进入>>

CleFke

他的近期作品查看更多>>

数据结构
数据结构的知识点来啦！数据结构的知识但复杂难懂，很多人在期末复习时都无从下手，下图从数据结构基本概念、线性表、栈和队列、树与二叉树、查找技术等知识点进行详细的归纳与总结，期末考试轻松拿高分！

相似推荐
大纲

英语词性
- 65.3k
- 6.6k
- 2.4k
- 578
- 0
Ethan
互联网9大思维
- 41.7k
- 984
- 2.5k
- 403
- 0
MindMaster
组织架构-单商户商城webAPP 思维导图。
- 19.9k
- 3
- 186
- 9
- 1
Kacyun
法理
- 30.4k
- 67
- 376
- 49
- 1
Dasein
刑法总则
- 40.9k
- 149
- 969
- 155
- 0
Dasein
【华政插班生】文学常识-先秦
- 7.0k
- 4
- 70
- 2
- 0
Dasein
【华政插班生】文学常识-秦汉
- 4.1k
- 0
- 54
- 10
- 0
Dasein
文学常识：魏晋南北朝
- 4.9k
- 3
- 90
- 20
- 0
Dasein
【华政插班生】文学常识-隋唐五代
- 5.7k
- 8
- 98
- 6
- 0
Dasein
【华政插班生】文学常识-两宋
- 4.0k
- 5
- 70
- 8
- 0
Dasein

数据结构

数据结构基本概念

数据

数据元素

最小的数据元素是数据项

数据结构

逻辑结构

存储结构

順式存储结构

链接存储结构

线性表

顺序表

单链表

栈和队列

先进后出

栈顶

可插可删

栈底

不可操作

队列

先进先出

队头

出队

队尾

入队

树与二叉树

二叉树

几种特殊的二叉树

斜树

满二叉树

完全二叉树

二叉树的遍历

前序

中序

后序

层序

二叉树的存储结构

順式存储结构

二叉链表

最优二叉树

哈夫曼算法

带全路径长度

路径长度与结点权值乘积之和

哈夫曼树（最优二叉树）

带全路径长最小

n 个叶子结点的哈夫曼树有 2n-1 个结点

构造哈夫曼树

递归取最小两个权值结点合并

哈夫曼编码

等长编码

n 个字符需要 log2 n

不等长编码

堆与优先队列

每个结点的值都小于或等于其左右孩子的值（小根堆），反之则为大根堆

图的逻辑结构

基本术语

度入度出度

无向完全图

n 个顶点的无向完全图有 n ✖️ （ n-1 ） /2 条边

有向完全图

n 个顶点的有向完全图有 n ✖️ （ n-1 ）条边

连通图

无向图任意顶点均有路径

连通分量

无向非连通图的最大连通子图

强连通图与强连通分量

类比上述强适用于有向图的场景

图的遍历

深度优先遍历 DFT

依次

广度优先遍历 BFT

按层

图的存储结构

邻接矩阵

深度遍历与广度遍历的时间复杂度均为 O （ n^2

空间代价为 O （ n^2

邻接表

查找顶点所有邻接点所需时间为 O （ e ）深度遍历与广度遍历的时间复杂度均为 O （ n+e

空间代价为 O （ n+e

最小生成树

Prim 算法

从起点出发，依次找最近

Kruskal 算法

加入最短边，合并，直到连通为止

最短路径

Dijkstra 算法

按长度递增次序产生最短路径

有向无环图

AOV 网与拓扑排序

AOV

顶点表示活动，弧表示活动之间的优先关系

拓扑排序

从起点到终点的一个序列即为拓扑排序

AOE 网关键路径

AOE

对比 AOV 网，路径带权

关键路径

最早开始时间与最晚开始时间相等的活动所在的路径

关键活动

关键路径上的活动

查找技术

线性表查找技术

顺序查找 O （ n

折半查找 O （ log2n

树表查找技术

二叉排序树

左子树所有结点值小于根结点

右子树所有结点值大于根结点

左右子树也是二叉排序树

查找性能在 O （ log2n ） O （ n ）之间

平衡二叉树

根结点的左右子树深度最多差

根结点的左右子树也是平衡二叉树

不平衡情况调整

顺时针旋转，改子树位置

逆时针旋转，改子树位置

左子树逆时针，再改子树位置

整体顺时针，改子树位置

右子树顺时针，再改子树位置

整体逆时针，改子树位置

散列表查找技术

散列函数

直接定址法

除留取余法

平方取中法

处理冲突的方法

开放定址法

平均查找长度

排序技术

插入排序

直接插入排序

适用于基本有序序列

希尔排序

交换排序

起泡排序

快速排序

选择排序

简单选择排序

堆排序

归并排序

二路归并排序

适用个数较多序列

时间复杂度

直接插入排序简单选择排序起泡排序

O（n^2

堆排序快速排序归并排序

O（nlog2n

希尔排序

O（n^2）～O（nlog2n

空间复杂度

归并排序

O（n

快速排序

O（log2n）～O（n

其他

O（1

稳定性

稳定

直接插入排序起泡排序归并排序

不稳定

希尔排序快速排序简单选择排序堆排序