《数据结构》课程回顾
9.4 | 9.6 | 9.11 | 9.13 |
9.18 | 9.20 | 9.25 | 9.27 |
9.30 | 10.9 | 10.11 | 10.16 |
10.18 | 10.23 | 10.25 | 10.30|
11.1 | 11.6 | 11.8 | 11.13 |
11.15 | 11.20 | 11.22 | 11.27 |
11.29 | 12.4 | 12.6 | 12.11 |
12.13
存储紧缩
文件
[顶层]
- 可利用空间表的结构
- 边界标识法
- 可利用空间表的结构
- 分配算法：空闲块的大小比申请的大，则拆分成2块
- 回收算法：与左邻空闲块、右邻空闲块合并
- 伙伴系统
- 可利用空间表的结构
- 分配算法: 对分
- 回收算法: 两空闲块互为伙伴才被归并
- 无用单元收集
[顶层]
- 哈希表
- 定义：同义词、冲突
- 哈希函数的构造方法
- 处理冲突的方法
- 开放定址法：二次聚集
- 链地址法：不会引起非同义词之间的冲突
- 再哈希法
- 建立一个公共溢出区
- 哈希表的查找及其分析：算法、平均查找长度、装填因子
- 哈希表的插入、删除
- 动态存储管理
[顶层]
- 动态查找表
- B-树
- 定义
- 查找算法：纵向、横向交叉进行
- 插入和删除算法思想
- B-树的查找分析: 结点数与高度的关系
- B+树
- 键树
- 定义
- 键树的双链树表示
- 键树的多重链表表示－－Trie树
[顶层]
- 索引顺序表的查找：起因、思想、查找算法、性能分析
- 动态查找表
- 二叉排序树
- 定义与性质
- 查找算法及性能分析
- 插入算法：作为叶子插入
- 删除算法：四种方法，两两对称
- 二叉排序树
- 平衡二叉树
- 平衡二叉树的定义
- 平衡化的四个规律：LL型(向右旋转)、RR型(向左旋转)、LR型(先左旋再右旋)、RL型(先右旋再左旋)
- 平衡的二叉排序树上的插入算法
- 查找的性能分析
[顶层]
- 查找
- 一些概念：查找表(静态、动态)，关键字，查找(不)成功
- 静态查找表
- 顺序查找：思想、数据结构、算法、性能分析(平均查找长度)
- 折半查找：思想、数据结构、算法、性能分析(平均查找长度)
- Fibonacci查找，插值查找：思想
- 静态树表的查找：定义(PH值：树的带权内路径长度)、次优查找树的构造、查找算法
[顶层]
- 图
- 每一对顶点之间的最短路径
- 调用Dijkstra算法
- Floyd算法(中间顶点的次序号不大于k, k逐步增加)
- 广义表
- 特点：元素类型可以是原子，也可以是子表
- 操作：求表头，求表尾
- 存储结构：头尾链表示、扩展线性链表示
- m元多项式的表示
- 递归算法
- 基本项和归纳项
- 广义表的递归算法：基于头尾链表示或扩展线性链表示
- 第二次课堂练习
[顶层]
- 有向无环图及其应用
- 如何判断一个无向图/有向图是否有环？
- 拓扑排序（AOV-网）
- 应用背景
- 对于DAG，拓扑有序序列不一定唯一
- 选择入度为0的输出----可用于检测有向图是否有环
- 若已知图为DAG，则利用DFS可以得到逆拓扑有序序列
- 关键路径
- 应用背景
- 事件的最早(迟)发生时间、活动的最早(迟)开始时间、关键活动
- 算法：拓扑排序、逆拓扑排序
- 最短路径
- 无权图的最短路径：广度优先搜索
- 单源最短路径：Dijkstra算法（依路径长度递增的次序）
[顶层]
- 图的连通性
- 有向图的强连通分量：DFS和逆向DFS
- 最小生成树
- 最小生成树的定义和MST性质
- 普里姆算法：最小生成树不断壮大的过程，适于稠密图，T(n)=O(n2)
- 克鲁斯卡尔算法：连通分量不断合并的过程，适于稀疏图,T(n,e)=O(elog2e)
- 关节点和重连通分量
- 定义：关节点、重连通图、连通度
- 利用深度优先搜索可以求得图的关节点
- 关节点在深度优先生成树中的特点
- 理解low[v]的含义
- 有向无环图及其应用
[顶层]
- 图的遍历
- 非递归的DFS遍历算法
- 遍历算法的应用
- 基于DFS的算法设计
- 基于BFS的算法设计
- 要求：
- 分析时间、空间复杂度
- 对上面的题目扩展，如何求解呢？
- 图的连通性
- 无向图的连通分量和生成树：基于孩子-兄弟链的BFS(DFS)生成树(森林)的创建算法
[顶层]
- 图的定义和术语
- 子图、连通分量、生成树/森林
- 边(弧)数与顶点数间的关系：(有向)完全图、稀疏图、稠密图
- 网：边(弧)上附加有权值
- 图的存储结构: 邻接矩阵、
邻接表、十字链表(有向图)、邻接多重表(无向图)
- 图的创建：图的种类->顶点数和边(弧)数->顶点信息->边(弧)信息
- 图的遍历
- 概念
- 深度优先搜索(DFS): 深度优先遍历序列、生成树/森林
- 广度优先搜索(BFS): 广度优先遍历序列、生成树/森林
- 图的深(广)度优先遍历算法
- 基于抽象数据类型ADT Graph 的算法设计
- DFS:
栈／递归；BFS : 队列
- 需要使用顶点的访问标志数组：visited
- 基于某种存储类型的算法设计
- 注意FirstAdjVex,
NextAdjVex的实现
- 时间复杂度：邻接矩阵T(n)=O(n2),邻接表T(n)=O(n＋e)
- 空间复杂度：DFS－跟生成树的深度有关，BFS－跟生成树的宽度有关
[顶层]
- 树与等价问题
- 查找和并集操作的算法和时间复杂度
- 改进一：含成员少的子集树根结点指向含成员多的子集的根。
- 改进二：压缩路径
- 回溯法与树的遍历
- 求含n个元素的集合的幂集
----依次对集合中的元素“取”或“舍”
- 搜索过程是对某棵树的先序遍历，但是无须创建这棵树
- 树的计数
- 概念: 树的相似、相等，树的计数问题
- 二叉树的计数问题:先序序列均为12...n的二叉树所能得到的中序序列的数目
- 树的计数问题
- 图
[顶层]
- 树和森林
- 树和森林的遍历:
先根(对应二叉树的先序遍历)，后根(对应二叉树的中序遍历)
- 基于二叉链(孩子-兄弟链)的应用
- 赫夫曼树及其应用
- 概念：树的路径长度、
树的带权路径长度、最优二叉树（赫夫曼树）
- 赫夫曼树的应用及构造算法
- 赫夫曼树的性质：结点的度(0或2)，结点数与高度的关系
- 赫夫曼编码——前缀编码
- 赫夫曼编码与译码的思想
- 赫夫曼编码与译码的实现：赫夫曼树用三叉静态链表存储，赫夫曼编码用动态分配的串存储
- 树的高级话题
- 树与等价问题
- 问题的描述：给定一个集合和作用在该集合上的一个等价关系，需要求该集合的一个等价类划分。
- 涉及集合的3个基本操作
- 集合的表示----双亲表示法表示的树
[顶层]
- 树和森林
- 树的存储结构: 双亲表示法,孩子表示法,孩子兄弟表示法
- 森林与二叉树的转换: 二叉链(孩子兄弟链～左右孩子链)
- Gzip阶段总结
[顶层]
- 层次遍历算法: 辅助数据结构是队列
- 层次遍历算法的应用
- 如何判断一棵二叉树是否是完全二叉树?
- 如何找距指定结点最近或最远的叶子子孙？---问题延伸及解决
- 线索二叉树
- 概念:
线索(指向结点前驱或后继的指针)、
线索链表(包含线索信息的链表)、
线索二叉树(加上线索的二叉树)、
线索化(对二叉树以某种次序遍历使其变成线索二叉树的过程)
- 几种线索二叉树: 注意其表示方法
- 中序线索二叉树：结构对称
- 后序线索二叉树 vs. 先序线索二叉树：互为对称
- 与线索二叉树有关的算法
- 如何找树中指定结点在某种序下的直接前驱/后继？
- 如何对二叉树进行线索化？
- 在线索二叉树上如何遍历？
[顶层]
- 先序/中序/后序遍历算法的应用
- 算法举例
- 释放二叉树的所有结点空间;
- 删除并释放二叉树中以元素值为x的结点作为根的各子树;
- 求位于二叉树先序序列中第k个位置的结点的值;
- 算法设计中需要注意的问题
- (递归)调用函数时要强调函数调用结果的使用；
- 定义函数时要保证从各个出口返回前都已经对结果进行了设置；
- 遍历次序对问题求解的影响；
- 如何处理多个结果?
- 如何传递中间结果?
- 注意分析时间复杂度和空间复杂度
- 先序/中序/后序遍历的非递归算法
[顶层]
- 二叉树的性质: 理解５个性质并拓展
- 特殊的二叉树：满二叉树、完全二叉树
- 二叉树的存储结构：顺序存储、链式存储(二叉链、三叉链)
- 二叉树的遍历：先序、后序、中序、层次遍历
- 二叉树先/中/后序遍历算法及其应用
- 三种遍历的定义与特点
- 遍历算法的递归实现：时间、空间复杂度
假设二叉树中结点个数为n，高度为h，则T(n)=O(n), S(n,h)=O(h)
- 递归的注意点：递归处理的规律、递归的终止条件
- 递归函数的编写：从函数定义(求解,设置结果)和函数使用(使用函数调用的结果)两个角度考虑
- 二叉基于先/中/后序遍历算法的应用
- 遍历算法应用的特点：访问结点-->结合具体问题利用结点的信息进行求解；
- 结果的表示形式：返回值、变参、全局变量；
[顶层]
习题课
[顶层]
- 串
- 串是一种特殊的线性表
- 数据元素的类型是字符类型
- 操作的对象：数据元素(字符)—个体、数据元素的集合(子串)—整体
注意：空串(长度为0的串) vs. 空白串
- 串的表示与实现：
- 定长顺序存储表示--串的顺序映像
- 堆分配存储表示--串的顺序映像，建立串名与串值的映像
- 块链存储表示--串的链式映像，存储密度
- 简单的串的模式匹配算法，串的应用(文本编辑、词索引表)
- 树和二叉树
- 树的定义和基本术语
注意：1) 终端结点为叶子结点；2) 非终端结点为分支结点，
包括根结点；3) 内部结点为除去根结点的分支结点
- 二叉树的定义: 二叉树 vs. 度小于等于2的有序树
[顶层]
- 队列
- 队列的定义：特殊的线性表，运算受限FIFO，队头/队尾
- 队列的表示与实现
- 类型定义以及约定，如rear指向什么？
- 队空、队满; 初始化空队、入队、出队
- 难点：循环队列(假上溢、如何区分队空和队满、如何处理下标下界不为0？)
- 离散事件模拟
- 课堂练习：双向动态链表的创建算法、静态链表的插入算法(参考答案)
[顶层]
- 栈与递归的实现
- 递归与递推
- 显式的递归定义(数据结构、递归过程)
- 问题求解的方法：大问题分解成若干小问题来求解
- 例子：阶乘、表的元素查找、Hanoi塔
- 递归的实现：系统工作栈
- 递归与回溯：N皇后问题
- 布置Gzip程序理解第二阶段任务和检查要求，以及实验二
[顶层]
- 一元多项式的表示及相加
- 栈和队列
- 栈的定义：特殊的线性表，运算受限FILO，栈顶/栈底
- 栈的表示与实现
- 类型定义以及约定，如top指向什么？
- 栈空、栈满; 初始化空栈、入栈、出栈
- 栈的应用举例
- 数制转换
- 行编辑程序
- 表达式求值
- 中缀表达式：算符优先关系，OPND栈和OPTR栈
- 前缀表达式(波兰式)：OPND栈和OPTR栈
- 后缀表达式(逆波兰式)：OPTR栈
[顶层]
- 动态链表与静态链表：例2-1，2-2(算法2.12)，2-3(算法2.17)
- 双向链表：插入、删除操作的实现
- 其他表示：增加表长、尾指针——结合实际问题，具体对待
- 有序表：特殊的线性表，不是存储结构
- 基于链表的算法设计
- 解题的一般框架
- 影响的因素：表的表示(循环？头结点？)，结点空间的来源，插入的方法(头插？尾插？其他？) ...
- 算法举例
[顶层]
- 实验指导：
- 静态链表
- 与动态链表的区别
- 静态链表的内存管理的实现(初始化、分配、释放)
- 静态链表的基本操作的实现。
[顶层]
- 单链表基本操作的实现
- 主要内容：插入(ListInsert_L),
删除(ListDelete_L),
链表的创建(头插法、尾插法)
- 要求:
- 领会头结点的用处
- 通过画图指导链表中的算法设计
- 熟练掌握基本操作的实现,能灵活地对基本操作进行变形并实现
- 循环链表:
- 引入循环链表的原因
- 尾指针表示的意义
- 循环链表与非循环链表的差异
[顶层]
- 线性表的顺序存储(映像)——顺序表
- 基本操作的实现：插入(插入位置的合法性，上溢), 删除(下溢,删除位置的合法性)
问题分析=>正常处理/异常情况与处理=>算法=>算法分析(时间/空间)
- 基于顺序表的算法设计：例2-1和例2-2的实现
- 线性表的链式存储——链表
- 顺序映像的弱点
- 特点: 逻辑上相邻，物理上未必相邻;非随机存取
- 几个概念：结点、数据域、指针域、指针(链)、头指针
- 类型定义：LNode, LinkList
- 基本操作的实现：取第i个元素(GetElem)
FAQ
- "&"的含义: 引用参数, 位运算符, 取地址符
- 引用参数与变参
- LocateElem中compare参数的含义
[顶层]
- 算法的评估
- (渐进)时间复杂度：T(n)=O(f(n)),
n -问题规模
表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。
理解几种常见的增长率(P16,图1.7)
- 空间复杂度：S(n)=O(f(n))
原地空间：S(n)=O(1)
- 线性表的逻辑特征
- ADT List的定义
- List的命名是根据惯例，不是一成不变的
- 基本操作及其接口不是一成不变的
- 对于引用参数，在函数的参数说明中应用'&'标出，在调用时引用参数对应的实参不加'&'
- 基于ADT List的算法设计 ：例2-1，例2-2
- 线性表的顺序存储(映像)——顺序表
- 特点: 逻辑上相邻，物理上必然相邻;随机存取
- 类型定义：方案1—定长顺序存储；方案2—增量式顺序存储
- 基本操作的实现：初始化
[顶层]
- 数据结构、逻辑结构、存储结构
- 数据类型与抽象数据类型
- 抽象数据类型的表示与实现
- 伪C语言与C语言的区别
- C语言中的值传递
- C++中的引用参数->==>用于表达算法中的变参
- 辨别C程序中标识符的规则：算符的优先级和结合性
- 算法和算法分析
参考资料：C语言简介,
程序与算法
[顶层]
[顶层]