邓俊辉-《数据结构》上

尽管“数据结构”是一门综合性的课程，但这并不意味着你必须精通所有的相关课程。实际上，你只需掌握若干重要的数学概念及方法，以及C/C++语言编程的基本技巧。

为确认自己是否适宜选修这门课程，不妨对照以下清单做一清点：

C++语言程序设计基础：类、继承、重载、重写、虚方法、模板

离散数学基础: 集合、偏序集、良序、数学归纳法、级数、递归、递推

概率基础: 随机分布、概率、伯努利实验、数学期望、期望值的线性率

授课教师

邓俊辉

邓俊辉，清华大学计算机系副教授。1993、1995和1997年分别于清华大学计算机系获学士、硕士和博士学位，1997年起在清华大学任教，主要讲授“数据结构”和“计算几何”。

邓俊辉《数据结构》

第1章 绪论

§1.1 计算机与算法

§1.2 复杂度度量

§1.3 复杂度分析

§1.4 *递归

§1.5 抽象数据类型

第2章 向量

§2.1 从数组到向量

§2.2 接口

§2.3 构造与析构

§2.4 动态空间管理

§2.5 常规向量

§2.6 有序向量

§2.7 *排序与下界

§2.8 排序器

第3章 列表

§3.1 从向量到列表

§3.2 接口

§3.3 列表

§3.4 有序列表

§3.5 排序器

第4章 栈与队列

§4.1 栈

§4.2 栈与递归

§4.3 栈的典型应用

§4.4 *试探回溯法

§4.5 队列

§4.6 队列应用

第5章 二叉树

§5.1 二叉树及其表示

§5.2 编码树

§5.3 二叉树的实现

§5.4 遍历

§5.5 Huffmann 编码

第6章 图

§6.1 概述

§6.2 抽象数据类型

§6.3 邻接矩阵

§6.4 邻接表

§6.5 图遍历算法概述

§6.6 广度优先搜索

§6.7 深度优先搜索

§6.8 拓扑排序

§6.9 *双连通域分解

§6.10 优先级搜索

§6.11 最小支撑树

§6.12 最短路径

第7章 搜索树

§7.1 查找

§7.2 二叉搜索树

§7.3 平衡二叉搜索树

§7.4 AVL 树

第8章 高级搜索树 高级搜索树

§8.1 伸展树

§8.2 B-树

§8.3 *红黑树

§8.4 *kd -树

第9章 词典

§9.1 词典 ADTADTADT

§9.2 *跳转表

§9.3 散列表

9.4 *散列应用

第10章 优先级队列

§10.1 优先级队列 ADT

§10.2 堆

§10.3 *左式堆

第11章 串

§11.1 串及匹配

§11.2 蛮力算法

§11.3 KMP算法

§11.4 *BM 算法

§11.5 *Karp-Rabin算法

第12章 排序

§12.1 快速排序

§12.2 *选取与中位数

§12.3 *希尔排序

附录