数据结构是计算机科学的关键内容，也是构建高效算法的必要基础。其中涉及的知识，在相关专业的课程系统中始终处于核心位置。本课程旨在围绕各类数据结构的设计与实现，揭示其中的规律原理与方法技巧；同时针对算法设计及其性能分析，使学生了解并掌握主要的套路与手段。讲授的主题从基础的数据结构，一直延伸至新近的研究成果。
Overview
Syllabus
- 第零章 课程相关信息
- 选课之前
- 考核方式
- OJ系统说明
- OJ帐号验证
- 关于课程教材与讲义
- 关于讨论区
- 微信平台
- PA讨论
- PA晋级申请
- 第一章 绪论
- A. 计算
- B. 计算模型
- C. 渐进复杂度
- D. 复杂度分析
- E. 迭代与递归
- F. 动态规划
- XA. 局限
- XB. 下界
- 第二章 向量
- A. 抽象数据类型
- B. 可扩充向量
- C. 无序向量
- D1. 有序向量：唯一化
- D2. 有序向量：二分查找（A）
- D3. 有序向量：Fib查找
- D4. 有序向量：二分查找（B）
- D5. 有序向量：二分查找（C）
- D6. 有序向量：插值查找
- E. 起泡排序
- F. 归并排序
- G. 位图/Bitmap
- 第三章 列表
- A. 循位置访问
- B. 接口与实现
- C. 无序列表
- D. 有序列表
- E. 选择排序
- G. 插入排序
- XD. 习题辅导：LightHouse
- 第四章 栈与队列
- A. 栈ADT及实现
- C. 进制转换
- D. 括号匹配
- E. 栈混洗
- F. 中缀表达式求值
- G. 逆波兰表达式
- H. 队列ADT及实现
- 本章测验
- 第五章 二叉树
- A. 树
- B. 树的表示
- C. 有根有序树=二叉树
- D. 二叉树实现
- E. 先序遍历
- F. 中序遍历
- G. 后序遍历
- H. 层次遍历
- I. 重构
- J. Huffman树
- 第六章 图
- A. 概述
- B. 邻接矩阵
- D. 广度优先搜索
- E. 深度优先搜索
- F1. 拓扑排序之零入度算法
- F2. 拓扑排序之零出度算法
- 本章测验
- 第七章 图应用
- A1. 双连通分量：判定准则
- A2. 双连通分量分解：算法
- A3. 双连通分量分解：实例
- B. 优先级搜索
- C. Dijkstra算法
- D. Prim算法
- 本章测验
- 期末考试
Taught by
Junhui Deng
