数据结构
2022-04-14 11:01:47 0 举报AI智能生成
登录查看完整内容
数据结构的思维导图以及南京邮电大学的考研数据结构考试范围
作者其他创作
大纲/内容
n个节点，m>=3叉树，有n-1个分支
基本概念
双亲存储结构
顺序存储结构
孩子存储结构
孩子兄弟存储结构
链式存储结构
树的存储结构
二叉树与树、森林转换
二叉树节点计算
二叉树i层
前序遍历
中序遍历
后序遍历
层次遍历
二叉树的遍历
二叉树
带权路径最短
没有度为1的节点
权值越大，离根越近
特点：
赫夫曼编码
赫夫曼树（最优二叉树）
六、树与二叉树
邻接矩阵
代码
邻 接 表
存储结构
深度优先遍历
广度优先遍历
图的遍历
普里姆是算法
克鲁斯卡尔算法
最小生成树
某一顶点到其余各项定点的最短路径 [时间复杂度O(n²)]
迪杰斯特拉算法：
任意一对顶点间的最短路径
弗洛伊德算法：
最短路径
AOV
拓扑排序
AOE
关键路径
七、图
静态查找
动态查找
顺序查找法
★折半查找法
分块查找
线性结构
左子树小于右子树
二叉排序树
RR
LL
LR
RL
平衡调整4种：
平衡二叉树
m阶B-树，节点中关键字个数范围为[m/2] - 1 ~ m-1
n个分支的节点有n-1个关键字，递增顺序排列
节点内各关键字互不相等且按从小到大排序
叶节点处于同一层 可用空指针表示，是查找失败到达的位置
★B-树
B+树：n个关键字的节点含有n个分支；B-树：n个关键字的节点含有n+1个分支
B+树：除根节点外其余节点关键字个数m/2 <= n <= m ，根节点：2<= n <= m；B-树： m/2-1 <= n <= m-1 ，根节点：1 <= n <= m-1
与B-树不同点
B+树
树形结构
a*key+b
直接定址法
数字分析法
平方取中法
★除留余数法
常用Hash函数的构造方法
★散列表(哈希表)
线性探查法
平方探查法
开放定址法
把同义词用单链表连起来
链地址法
常用Hash冲突处理方法
散列结构
分析及应用
八、查找
关于排序
最坏：O(n²)
最好：O(n)
平均：O(n²)
时间复杂度：
空间复杂度：O(1)
排序
★直接(简单)插入排序
★折半插入排序
核心思想
时间复杂度 O(n²)
空间复杂度 O(1)
希尔排序
插入类排序
★冒泡排序
核心思想：
空间复杂度：O(log₂n)
最好：O(nlog₂n)
平均：O(nlog₂n)
★快速排序
交换类排序
时间复杂度：O(n²)
★简单选择排序
适用：关键字较多的时候，如：1000个关键字选取前10个最小的
最坏：O(nlog₂n)
★堆排序
选择类排序
核心思想：将序列 递归地 分成两部分后进行排序，然后进行归并
空间复杂度：O(n)
★二路归并排序
归并排序
数据元素的关键字可方便拆为d组，且d较小
每组关键字取值范围不大，即r较小
数据元素个数n较大
擅长解决的问题
基数排序
基数类排序
置换-选择排序
最佳归并树
败者树
外部排序（南邮不考）
九、排序
1.1算法的基本概念
1.2数据结构的基本概念
1.3数据抽象和抽象数据类型
1.4描述数据结构和算法
1.5算法分析的基本方法
一、绪论
2.1线性表的定义及基本操作
2.2线性表的顺序存储
2.3线性表的链接存储
二、 线性表
3.1栈和队列的基本概念
3.2栈和队列的顺序存储结构
3.3栈和队列的链式存储结构
3.4表达式计算
3.5递归
三、栈和队列
4.1数组的基本概念
4.2特殊矩阵
4.3稀疏矩阵
四、数组
5.1树的基本概念
5.2.1二叉树的定义及主要特征
5.2.2二叉树的顺序存储和链式存储
5.2.3二叉树的遍历
5.2.4 线索二叉树的基本概念和构造
5.2二叉树
5.3.1树的存储结构
5.3.2森林和二叉树的转换
5.3.3树和森林的遍历
5.3树和森林
5.4.1二叉排序树
5.4.2二叉平衡树
5.4.3哈夫曼(Huffman)树和哈夫曼编码
5.4树和二叉树的应用
五、树和二叉树
6.1图的基本概念
6.2.1邻接矩阵法
6.2.2邻接表表示法
6.2图的存储及基本操作
6.3.1深度优先搜索
6.3.2广度优先搜索
6.3图的遍历
6.4.1拓扑排序
6.4.2关键路径
6.4.3 最小代价生成树
6.4.4最短路径
6.4图的基本应用
6 图
7.1搜索的基本概念
7.2顺序搜索法
7.3二分搜索法
7.4 B-树及其基本操作
7.5散列(Hash)表
7.6搜索算法的分析及应用
7 搜索（Search）
8.1排序的基本概念
8.2简单选择排序
8.3直接插入排序
8.4冒泡排序(bubble sort)
8.5希尔排序(shell sort)
8.6快速排序
8.7堆排序
8.8两路合并排序(merge sort)
8.9基数排序
8.10各种内部排序算法的比较
8.11内部排序算法的应用
8 内排序
南邮811大纲（2022）
十、其他
图状结构
集合结构
非线性结构
数据的逻辑结构
索引存储结构
散列存储结构
数据的物理结构（存储结构）
数据结构
时间复杂度从小到大
排序的时、空复杂度记忆
时间、空间复杂度
算法的目的：分析算法的效率以求改进
分支主题
二、线性表
三、栈
关于队列
判空：front==rear
队满：(rear+1)%max==front
元素个数：(rear-front+maxSize)%maxSize
入队：
出队：
顺序队
判空
队满
入队
出队
链队
四、队列
行有先 A[m][n]求A[3][4]的地址：行有先->(3*n+4)*字符大小
列优先
二维数组
数组
压缩矩阵时常用三角阵代替
对称矩阵
当i<j时，i、j互换，a[i][j] = (i+1)*i/2+j
上三角矩阵：主对角线以上全是0
当i>j时，i、j互换，a[i][j] = (i+1)*i/2+j
下三角矩阵：主对角线一下全是0
（首项+末项）* 项数 +列
三角阵(行有先)
对角阵
特殊矩阵
三元组表示法
伪地址表示法
顺序存储
邻接表表示法
十字链表表示法
链式存储
稀疏矩阵
矩阵
广义表（南邮不考）
五、数组、矩阵、串
0 条评论
回复 删除
下一页
