数据结构是计算机科学的关键内容，也是构建高效算法的必要基础。其中涉及的知识，在相关专业的课程系统中始终处于核心位置。本课程旨在围绕各类数据结构的设计与实现，揭示其中的规律原理与方法技巧；同时针对算法设计及其性能分析，使学生了解并掌握主要的套路与手段。讲授的主题从基础的数据结构，一直延伸至新近的研究成果。
Overview
Syllabus
- 第零章 课程相关信息
- 选课之前
- 考核方式
- OJ系统说明
- 关于课程教材与讲义
- 关于讨论区
- 微信平台
- PA晋级申请
- 第八章 二叉搜索树
- A. 概述
- B1. BST：查找
- B2. BST：插入
- B3. BST：删除
- C. 平衡
- D1&2. AVL树：重平衡
- D3. AVL树：插入
- D4. AVL树：删除
- D5. AVL树：(3+4)-重构
- 本章测验
- 第十章 高级搜索树
- A1. 伸展树：逐层伸展
- A2. 伸展树：双层伸展
- A3. 伸展树：算法实现
- B1. B-树：大数据
- B2. B-树：结构
- B3. B-树：查找
- B4. B-树： 插入
- B5. B-树： 删除
- C1. 红黑树：动机
- C2. 红黑树：结构
- C3. 红黑树：插入
- C4. 红黑树：删除
- 本章测验
- 第十一章 词典
- A. 散列
- B. 散列函数
- C. 散列：排解冲突(1)
- C. 散列：排解冲突(2)
- D. 桶排序
- F. 计数排序
- 本章测验
- 第十二章 优先级队列
- A1. 需求与动机
- A2. 基本实现
- B1. 完全二叉堆：结构
- B2. 完全二叉堆：插入与上滤
- B3. 完全二叉堆：删除与下滤
- B4. 完全二叉堆：批量建堆
- C. 堆排序
- F1&2. 左式堆：结构
- F3. 左式堆：合并算法
- F4. 左式堆：插入 + 删除
- 本章测验
- 第十三章 串
- A. ADT
- B. 模式匹配
- C1. KMP算法：记忆法
- C2. KMP算法：查询表
- C3. KMP算法：理解next[]表
- C4. KMP算法：构造next[]表
- C5. KMP算法：分摊分析
- C6. KMP算法：再改进
- D1. BM_BC算法：以终为始
- D2. BM_BC算法：坏字符
- D3. BM_BC算法：构造bc[]
- D4. BM_BC算法：性能分析
- E1. BM_GS算法：好后缀
- E2. BM_GS算法：构造gs表
- E3. BM_GS算法：综合性能
- F1. Karp-Rabin算法：串即是数
- F2. Karp-Rabin算法：散列
- 本章测验
- 第十四章 排序
- A1&2. 快速排序：算法A
- A3&4. 快速排序：性能分析
- A7. 快速排序：快速划分（ LGU 版）
- B1. 选取：众数
- B3&4. 选取：通用算法
- C1. 希尔排序：框架 + 实例
- C2. 希尔排序：Shell 序列 + 输入敏感性
- 本章测验
Taught by
Junhui Deng
