《数据结构和数据库》课程回顾
2.22 | 3.1 | 3.8 | 3.15 |
3.22 | 3.27 | 4.5 | 4.12 |
4.19 | 4.26 | 5.10 | 5.17 |
5.24 | 5.31 | 6.7 | 6.14
- 关系数据库设计理论
- 数据依赖：数据依赖,函数依赖(平凡/非平凡,完全/部分,传递),码
- 范式
- INF：所有属性都是不可分的基本数据项
- 2NF：消除非主属性对码的部分函数依赖
- 3NF：消除非主属性对码的传递函数依赖
- BCNF：每一个决定属性集都包含有候选码
- 关系模式的规范化：步骤，投影分解法
[顶层]
- 元组关系演算
- 关系数据库标准语言SQL
- SQL的特点：综合统一，高度非过程化，面向集合的操作方式，以同一种语法结构提供两种使用方法，语言简洁，易学易用
- 基本表的定义、删除与修改
- 查询：单表查询、连接查询、嵌套查询(in,比较运算符)
[顶层]
- 数据库绪论
- 数据库系统的模式结构：三级模式结构和二级映像功能
- 数据库管理系统：功能、组成
- 关系数据库
- 关系数据结构：关系、关系的性质、关系模式、关系数据库
- 关系的完整性：实体完整性、参照完整性、用户自定义的完整性
- 关系代数：并、差、交、广义笛卡儿积、选择、投影、连接、除
[顶层]
- 排序
- 快速排序：partition算法及其应用
- 选择排序：简单选择排序、堆排序(堆的概念、筛选和建堆的算法思想)
- 归并排序: 2-路归并排序
主要掌握：各种排序算法的思想、稳定性、时空性能分析
- 数据库绪论
- 数据/数据库/数据库管理系统/数据库系统
- 数据管理及其发展阶段
- 数据模型：概念、构成要素
概念模型：实体、联系、E-R模型
层次数据模型、网状数据模型、关系数据模型
[顶层]
- 查找
- 动态查找表：二叉排序树(二叉查找树)
主要掌握：二叉排序树的定义与性质、查找算法、插入和删除的算法思想、查找的时空性能分析
- 散列表：
主要掌握：冲突的解决办法、查找算法、性能分析
- 排序
- 概念：排序、稳定性
- 插入排序：直接插入排序、折半插入排序
- 交换排序: 冒泡排序、快速排序
主要掌握：各种排序算法的思想、稳定性、时空性能分析
[顶层]
- 图
- 图的连通性：利用DFS(BFS)可以求得图的各连通分量
- 最小生成树: 普里姆算法、克鲁斯卡尔算法
- 拓扑排序: 算法思想，判断有向图是否存在环
- 最短路径:
Dijkstra算法思想（有向网中从某个源点到其余各顶点的最短路径）
- 查找
- 概念：静态查找表、动态查找表；查找成功、查找不成功、(平均)查找长度
- 静态查找表：顺序查找、折半查找(二分查找)、分块查找
主要掌握：算法思想、数据结构、算法、时间性能分析(平均查找长度)
[顶层]
- 图的定义和术语：连通分量、生成树
- 图的存储结构: 邻接矩阵、邻接表
- 图的遍历
- 深度优先搜索(DFS)、广度优先搜索(BFS)---会写算法
- 深度优先生成树(森林)、广度优先生成树(森林)
[顶层]
- 树和森林
- 树的存储结构: 双亲表示法,孩子表示法,孩子兄弟表示法
- 森林与二叉树的转换: 二叉链(孩子兄弟链～左右孩子链)
- 树和森林的遍历:
先根(对应二叉树的先序遍历)，后根(对应二叉树的中序遍历)
- 赫夫曼树及其应用
[顶层]
[顶层]
- 树的定义和基本术语
- 二叉树
- 二叉树的定义: 二叉树 vs. 度小于等于2的有序树
- 二叉树的性质: 理解５个性质并拓展
- 特殊的二叉树：满二叉树、完全二叉树
- 二叉树的存储结构：顺序存储、链式存储(二叉链、三叉链)
- 二叉树的遍历：先序、后序、中序、层次遍历
[顶层]
- 队列的定义：特殊的线性表，运算受限FIFO，队头/队尾
- 队列的表示与实现
- 类型定义以及约定，如rear指向什么？
- 队空、队满; 初始化空队、入队、出队
- 难点：循环队列
- 数组的定义与表示：特殊的线性表(元素类型都为原子或者都是定长线性表）
- 特殊矩阵的压缩存储：按规律确定压缩存储方法，重点是地址变换公式
- 稀疏矩阵的压缩存储：三元组顺序表，十字链表
[顶层]
- 栈的定义：特殊的线性表，运算受限FILO，栈顶/栈底
- 栈的表示与实现
- 类型定义以及约定，如top指向什么？
- 栈空、栈满; 初始化空栈、入栈、出栈
- 应用举例：表达式求值
- 栈与递归的实现
- 显式的递归定义(数据结构、递归过程)
- 问题求解的方法：大问题分解成若干小问题来求解
- 例子：阶乘、表的元素查找、Hanoi塔、N皇后
- 递归的实现：系统工作栈
[顶层]
- 基于线性表的算法设计
- 重点是链表
- 注意：链表的表示(循环？头结点？)，结点空间的来源，插入的方法
- 一元多项式的表示及相加
[顶层]
- 单链表
- 类型定义：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)
- 通过画图指导链表中的算法设计
- 其他链表：循环链表、双向链表
- 基于顺序表和链表的算法设计：例2-1和例2-2的实现
[顶层]
- 线性表的逻辑特征
- ADT List的定义
- 基于ADT
List的算法设计 ：例2-1，例2-2
- 线性表的顺序存储(映像)——顺序表
- 特点: 逻辑上相邻，物理上必然相邻;随机存取
- 类型定义：方案1—定长顺序存储；方案2—增量式顺序存储
- 基本操作的实现：插入(上溢,插入位置的合法性)、删除(下溢,删除位置的合法性)
- 线性表的链式存储——链表
- 顺序映像的弱点
- 特点: 逻辑上相邻，物理上未必相邻;非随机存取
- 几个概念：结点、数据域、指针域、指针(链)、头指针
- 类型定义，头结点的引入
[顶层]
- 数据结构、逻辑结构、存储结构、抽象数据类型
- 伪C语言与C语言的区别
- 如何辨别C程序中的标识符？
- 算法的定义、特点，算法的评估(时间复杂度、空间复杂度)
[顶层]
