数据结构思维导图

U632650044

2023-04-24

浏览量: 89

数据结构

计算机

算法

数据结构知识总结

树图思维导图提供《数据结构》在线思维导图免费制作，点击“编辑”按钮，可对《数据结构》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：1b7b151819ba98030681e15967ca6810

思维导图大纲

1 绪论

数据结构（三要素）

逻辑结构

线性结构

线性表、队列、栈

非线性结构

集合、树、图

物理结构（存储结构）

顺序存储、索引存储、散列存储

数据的运算

2 线性表

顺序表示

顺序表

链式表示

单链表

双链表

循环链表

静态链表

数组

3 栈和队列

栈

顺序栈

链栈

共享栈

队列

循环队列

删除元素，队首指针+1

Q·front=（Q·front+1）%MaxSize

插入元素，队尾指针+1

出队入队都按顺时针进1

（rear-front+MaxSize）%MaxSize

链式队列

双端队列

矩阵的压缩存储

压缩存储

指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间

特殊矩阵

对称矩阵

三角矩阵

三对角矩阵

各矩阵的下标

稀疏矩阵

4 串

概念

主串

字串

串长

存储结构

模式匹配算法

暴力

O(nm)

KMP算法

O(n +m)

掌握KMP算法的滑动

前缀匹配，next数组

KMP算了进一步优化

5 树与二叉树

二叉树

概念

度为2的树和二叉树的区别

度为2的树至少有3个结点，而二叉树为空

度为2的有序树若只有一个孩子就无须确定左右次序。二叉树无论孩子是否为2都要确定次序

树的性质

树中的节点数等于所有结点的度数加1（结点数等于边数加1

度为m的树中第i层上至多有m^(i-1)个结点

高度为h的m叉树至多有(m^-1)/(m-1)个结点

具有n 个结点的m叉树的最小高度为┎log m (n (m - 1)+1)┒

操作

遍历

线索化二叉树

应用

排序二叉树

平衡二叉树

插入

找离插入点最近的平衡因子＞1的结点

四种旋转

查找

比较次数最多是树的深度

深度为h 的平衡二叉树含有的最少结点: nʰ=n⁽ʰ⁻¹⁾+nʰ⁻²+1 ，n0=0, n1=1, n2=2

非叶子结点的平衡因子均为1

哈夫曼树

从结点中选取最小的两个结点构造树，轮流...

n 个结点能构造出n-1 个结点，所以哈夫曼树结点总数为2n-1

哈夫曼编码

没有一个编码是另一个编码的前缀

树和森林

概念

操作

与二叉树的互换

遍历

应用：并查集

6 图

概念

简单图

完全图

连通图

任意两个顶点都是连通的，即有路径存在即可，不一定是直接相连的边

边数小于n-1必是非连通图

连通分量

无向图中的极大连通子图称为连通分量

强连通图

对于有向图，两顶点之间互相有路径到彼此

图的结构的存储

邻接矩阵

邻接表

十字链表

多重链表

图的遍历

深度优先遍历

先序遍历

广度优先遍历

深层遍历

图的应用

最小生成树

Prim

选择距离最近的顶点连起来

时间复杂度O(V²)

Kruskal

按权值递增的顺序选择合适的边

最短路径

Dijkstra

单源最短路径

每一轮加入一个路径最短的结点

Floyd

从原始邻接矩阵改

时间复杂度O(V³)

拓扑排序

AOV网

关键路径

AOE网

ve()事件(顶点)最早发生时间

Max

vl()事件最晚发生时间

Min

e(i)活动(边)最早开始时间

等于该狐起点的ve

v()最晚开始时间

终点的vl-持续时间

7 查找

概念

静态查找

动态查找

线性结构

顺序查找

无序线性表

查找成功，平均查找长度: (n+1)/2

不成功，n+1

有序线性表

成功，(n+1)/2

不成功，n/2+n/(n+1)

折半查找

适用于有序的顺序表

结合判定树（查找过程的二叉树）

比较次数不会超过树的高度

n个非叶子结点，n+1个叶子结点（失败结点）

查找成功平均查找长度：（1x1+2x2+3x2²+…+hx2⁽ʰ⁻¹⁾）/n =log（n+1）-1

分块查找

树形结构

二叉排序树

二叉平衡树

B树(不支持顺序查找)

m阶树至多有m-1个关键词，至少有「m/2 」-1个关键词

插入

删除

兄弟够借，父子换位

兄弟不够，父子合并(若父结点只有一个关键词，合并后无父结点，要重新调整)

B+树

m阶树至多有m-1个关键词，至少有「m/2 」个关键词

散列结构

散列表

处理冲突的方法

开放定址法

线性探测法

平方探测

避免出现堆积

再散列法

拉链法（不会聚集）

散列函数

除留余数法

H（key）=key%p p取不大于表长m最接近m的质数

平均查找长度

成功

分母是元素个数

失败

待查找数字肯定不在表中

长度为关键字距离第一个空地址的距离，分母是散列函数的除数

效率指标

散列函数

装填因子

处理冲突的的方法

8 排序

概念

稳定性

衡量标准：时间、空间复杂度

内部排序

插入排序

直接插入排序

最坏比较次数n（n-1）/2

折半插入排序

希尔排序

步长d=n/2,

交换排序

冒泡排序

最坏比较次数n（n-1）/2，移动次数3n（n-1）/2

快速排序

选择排序

简单选择排序

比较次数与初始状态无关，始终是（n-1）n/2次

堆排序

定义：大根堆：L（i）≥L(2i)且L(i)≥L(2i+1)

①建堆：从┗n/2┛~1为根的子树进行筛选 ②输出堆顶元素，将堆的最后一个元素放在堆顶，向下筛选

归并排序

基数排序

从个十百千…依次分配、收集

外部排序

归并排序

外部排序经常采用

败者树

置换-选择排序

在工作区中所有记录中选取比MINIMAX记录的关键字大的记录中选取最小的关键字替换MINIMAX，直到选不出时，结束作为一个归并段，再重新开始…

最佳归并树

哈夫曼树的思想

当初始归并段不足以构成一个严格k叉树时，需添加长度为0的“虚段”

（n0-1）%（k-1）=0时，可以构成k叉树

（n0-1）%（k-1）=u时，说明有u个多余，要加上k-u-1个虚段

进阶面试题总结思维导图

U765641931

3.18

树图思维导图提供《进阶面试题总结》在线思维导图免费制作，点击“编辑”按钮，可对《进阶面试题总结》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：fac4f2eaa7b9b4cfd44ba29e73117dbe

算法绪论思维脑图思维导图

U159768862

4.68

树图思维导图提供《算法绪论思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《算法绪论思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：83c7670340b2f9630fecc161a067aa80

思维导图模板

资格考试

计算机

正文

相似思维导图模版

思维导图模版推荐

金属切削原理与刀具思维导图

2023-04-24 22:18:06

地理八年级下册第八章第一节《自然特征与农业》课堂笔记思维导图

首页

我的文件

我的团队

个人中心