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