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