《数据结构和数据库》课程回顾
8.30 | 9.1 | 9.6 | 9.8 |
9.15 | 9.20 | 9.22 | 9.27 |
9.29 | 10.11 | 10.13 | 10.18 |
10.25 | 11.1 | 11.3 | 11.8 |
11.10 | 11.15 | 11.17 | 11.22 |
11.24 | 11.29 | 12.1 | 12.6 |
12.8 | 12.13
- 文件
- 基本概念
- 常见的文件物理结构
- 顺序文件：连续文件、串联文件
- 索引文件: 静态索引、动态索引
- ISAM(索引顺序存取方法)文件：主索引－柱面索引－磁道索引，溢出区
- VSAM(虚拟存储存取方法)文件：数据集(控制区间)－顺序集(控制区域)－索引集，B+树
- 直接存取文件(散列文件)：桶
- 多关键字文件: 多重表文件，倒排文件
了解每一种文件物理结构的组织方式，检索和修改的方法。
[顶层]
- 边界标识法
- 伙伴系统
- 可利用空间表的结构
- 分配算法: 对分
- 回收算法: 两空闲块互为伙伴才被归并
- 无用单元收集
- 无用单元,悬挂访问
- 引用计数
- 收集无用单元的方法
- 标志算法的三种形式
- 存储紧缩
[顶层]
- 查找
- 哈希表
- 处理冲突的方法
- 开放定址法：二次聚集
- 链地址法：不会引起非同义词之间的冲突
- 再哈希法
- 建立一个公共溢出区
- 哈希表的查找及其分析：算法、平均查找长度、装填因子
- 动态存储管理
- 可利用空间表及分配方法
- 三种结构形式
- 可变分区的分配方法:首次拟合、最佳拟合、最差拟合
- 边界标识法
[顶层]
- 动态查找表
- B-树
- B+树
- 键树
- 定义
- 键树的双链树表示
- 键树的多重链表表示－－Trie树
- 哈希表
- 定义：同义词、冲突
- 哈希函数的构造方法
- 处理冲突的方法
[顶层]
- 动态查找表
- 二叉排序树
- 平衡二叉树
- 平衡二叉树的定义
- 平衡化的四个规律：LL型(向右旋转)、RR型(向左旋转)、LR型(先左旋再右旋)、RL型(先右旋再左旋)
- 平衡的二叉排序树上的插入算法
- 查找的性能分析
- B-树
[顶层]
- 静态查找表
- 折半查找：思想、数据结构、判定树、查找算法、性能分析
- Fibonacci查找，插值查找：思想
- 静态树表的查找：定义、次优查找树的构造、查找算法
索引顺序表的查找：起因、思想、查找算法、性能分析
动态查找表
- 二叉排序树
- 定义与性质
- 查找算法及性能分析
- 插入算法：作为叶子插入
- 删除算法：四种方法，两两对称
[顶层]
- 广义表
- 存储结构：头尾链表示、扩展线性链表示
- m元多项式的表示
- 递归算法
- 查找
- 一些概念：查找表(静态、动态)，关键字，查找(不)成功
- 静态查找表
- 顺序查找：思想、数据结构、算法、性能分析(平均查找长度)
- 折半查找：思想、数据结构
[顶层]
- 有向无环图及其应用
- 关键路径
- 应用背景
- 事件的最早(迟)发生时间、活动的最早(迟)开始时间、关键活动
- 算法：拓扑排序、逆拓扑排序
- 最短路径
- 无权图的最短路径：广度优先搜索
- 单源最短路径：Dijkstra算法（依路径长度递增的次序）
- 每一对顶点之间的最短路径
- 调用Dijkstra算法
- Floyd算法(中间顶点的次序号不大于k, k逐步增加)
- 广义表
- 特点：元素类型可以是原子，也可以是子表
- 操作：求表头，求表尾
[顶层]
- 图的连通性
- 关节点和重连通分量
- 定义：关节点、重连通图、连通度
- 利用深度优先搜索可以求得图的关节点
- 关节点在深度优先生成树中的特点
- low[v]的含义
- 有向无环图及其应用
- 如何判断一个无向图/有向图是否有环？
- 拓扑排序（AOV-网）
- 应用背景
- 对于DAG，拓扑有序序列不一定唯一
- 选择入度为0的输出----可用于检测有向图是否有环
- 若已知图为DAG，则利用DFS可以得到逆拓扑有序序列
[顶层]
- 图的遍历
- 遍历算法的应用
- 基于BFS的算法设计
- 求距顶点v0的各顶点中最短路径长度最长的一个顶点
- 对上面的题目扩展，如何求解呢？
- 有向图的强连通分量：DFS和逆向DFS
- 最小生成树
- 最小生成树的定义和MST性质
- 普里姆算法：最小生成树不断壮大的过程，适于稠密图，T(n)=O(n2)
- 克鲁斯卡尔算法：连通分量不断合并的过程，适于稀疏图,T(n,e)=O(elog2e)
[顶层]
- 图的遍历
- 概念
- 深度优先搜索(DFS): 遍历序列、生成树/森林
- 广度优先搜索(BFS):
遍历序列、生成树/森林
- 图的深(广)度优先遍历算法
- 基于抽象数据类型ADT
Graph 的算法设计
- DFS:
栈／递归；BFS : 队列
- 需要使用顶点的访问标志数组：visited
- 基于某种存储类型的算法设计
- 注意FirstAdjVex,
NextAdjVex的实现
- 时间复杂度：邻接矩阵T(n)=O(n2),邻接表T(n)=O(n＋e)
- 空间复杂度：DFS－跟生成树的深度有关，BFS－跟生成树的宽度有关
- 遍历算法的应用
[顶层]
- 树的计数
- 概念: 树的相似、相等，树的计数问题
- 二叉树的计数问题 vs. 树的计数问题
- 图
- 图的定义和术语：连通分量、生成树/森林
- 图的存储结构: 邻接矩阵、邻接表
- 图的创建
[顶层]
- Huffman编码——前缀编码
- Huffman编码与译码思想
- Huffman编码与译码的实现：三叉静态链表
- 树的高级话题
- 树与等价问题
- 集合的表示----双亲表示法表示的树
- 查找和并集操作的算法和时间复杂度
- 并集操作的改进：降低树的高度
- 回溯法与树的遍历
- 求含n个元素的集合的幂集----依次对集合中元素“取”或“舍”
- 搜索过程是对某棵树的先序遍历，但是无须创建这棵树
[顶层]
- 线索二叉树
- 树和森林
- 树的存储结构: 双亲表示法,孩子表示法,孩子兄弟表示法
- 森林与二叉树的转换: 二叉链(孩子兄弟链～左右孩子链)
- 树和森林的遍历:
先根(对应二叉树的先序遍历)，后根(对应二叉树的中序遍历)
- 赫夫曼树及其应用
- 概念：树的带权路径长度、最优二叉树（赫夫曼树）
- 赫夫曼树的应用及构造算法
- 赫夫曼树的性质：结点数与高度的关系
[顶层]
- 二叉树遍历算法及其应用
- 先序/中序/后序遍历算法的应用
- 层次遍历算法:
队列
- 层次遍历算法的应用
- 线索二叉树
- 概念: 线索、线索链表、线索二叉树、线索化
- 算法
- 如何找树中指定结点在某种序下的直接前驱/后继？
- 如何对二叉树进行线索化？
- 在线索二叉树上如何遍历？
[顶层]
- 二叉树先/中/后序遍历算法及其应用
- 三种遍历的定义与特点
- 遍历算法的递归实现：时间、空间复杂度
- 递归的注意点：递归处理的规律、递归的终止条件
- 递归函数的编写：从函数定义(求解,设置结果)和函数使用(使用函数调用的结果)两个角度考虑
- 二叉基于先/中/后序遍历算法的应用
- 遍历次序对问题求解的影响；
- 结果的表示形式：返回值、变参、全局变量；
[顶层]
- 树的定义和基本术语
- 二叉树
- 二叉树的定义: 二叉树 vs. 度小于等于2的有序树
- 二叉树的性质: 理解５个性质并拓展
- 特殊的二叉树：满二叉树、完全二叉树
- 二叉树的存储结构：顺序存储、链式存储(二叉链、三叉链)
- 二叉树的遍历：先序、后序、中序、层次遍历
[顶层]
- 串是一种特殊的线性表
- 数据元素的类型是字符类型
- 操作的对象：数据元素(字符)—个体、数据元素集合(串)—整体
- 串的表示与实现：
- 定长顺序存储表示--串的顺序映像
- 堆分配存储表示--串的顺序映像
- 块链存储表示--串的链式映像
- 简单的串的模式匹配算法，串的应用
[顶层]
- 栈与递归的实现
- 队列
- 队列的定义：特殊的线性表，运算受限FIFO，队头/队尾
- 队列的表示与实现
- 类型定义以及约定，如rear指向什么？
- 队空、队满; 初始化空队、入队、出队
- 难点：循环队列(假上溢、如何区分队空和队满、如何处理下标下界不为0？)
[顶层]
- 栈的应用举例
- 栈与递归的实现
- 递归与递推
- 显式的递归定义(数据结构、递归过程)
- 问题求解的方法：大问题分解成若干小问题来求解
- 例子：阶乘、表的元素查找、Hanoi塔
- 递归的实现：系统工作栈
[顶层]
- 线性表
- 基于线性表的算法设计(侧重在链表)
- 解题的一般框架
- 影响的因素：表的表示(循环？头结点？)，结点空间的来源，插入的方法 ...
- 一元多项式的表示及相加
- 栈和队列
- 栈的定义：特殊的线性表，运算受限FILO，栈顶/栈底
- 栈的表示与实现
- 类型定义以及约定，如top指向什么？
- 栈空、栈满; 初始化空栈、入栈、出栈
- 应用举例：数制转换、行输入处理程序
[顶层]
- 线性表的链式存储——链表
- 静态链表：与动态链表的区别、静态链表的实现
- 基于链表的算法设计：例2-1，2-2，2-3
- 双向链表：插入、删除
- 其他表示：增加表长、尾指针——结合实际问题，具体对待
- 有序表：特殊的线性表，不是存储结构
[顶层]
- 线性表的顺序存储(映像)——顺序表
- 基本操作的实现：删除(下溢,删除位置的合法性)
- 基于顺序表的算法设计：例2-1和例2-2的实现
- 线性表的链式存储——链表
- 顺序映像的弱点
- 特点: 逻辑上相邻，物理上未必相邻;非随机存取
- 几个概念：结点、数据域、指针域、指针(链)、头指针
- 类型定义：LNode, LinkList
- 基本操作的实现：取第i个元素(GetElem),
插入(ListInsert), 删除(ListDelete),
链表的创建(头插法、尾插法)
- 其他链表：循环链表
注意：
- 本书所陈述的抽象数据类型及其实现在实际的程序设计语言中并未直接提供；
- 一些语言的支持库提供了部分数据结构的实现，如C++ Standard Template Library
中的list类
- 一个基本操作的接口定义是可以根据实际需要而略微变化的,如取第i个元素可以定义为
Status GetElem(LinkList L,int i, ElemType &e )
也可以定义为: LNode *GetElem(LinkList L,int i)
- 通过画图指导链表中的算法设计
[顶层]
- 线性表的逻辑特征
- ADT List的定义
- List的命名是根据惯例，不是一成不变的
- 基本操作及其接口不是一成不变的
- 对于引用参数，在函数的参数说明中应用'&'标出，在调用时引用参数对应的实参不加'&'
同学所提的一些问题见FAQ
- 基于ADT
List的算法设计 ：例2-1，例2-2
- 线性表的顺序存储(映像)——顺序表
- 特点: 逻辑上相邻，物理上必然相邻;随机存取
- 类型定义：方案1—定长顺序存储；方案2—增量式顺序存储
- 基本操作的实现：初始化，插入(插入位置的合法性，上溢)
[顶层]
- 值传递、引用参数->变参
- 如何辨别C程序中的标识符？
- 算法的定义、特点，算法的评估(时间复杂度、空间复杂度)
- 渐进时间复杂度：T(n)=O(f(n)),
n -问题规模
表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。
- 空间复杂度：S(n)=O(f(n))
原地空间：S(n)=O(1)
[顶层]
[顶层]