课程简介
数据结构是计算机科学的关键内容，也是构建高效算法的必要基础。其中涉及的知识，在相关专业的课程系统中始终 处于核心位置。本课程旨在围绕各类数据结构的设计与实现，揭示其中的规律原理与方法技巧；同时针对算法设计及其性能 分析，使学生了解并掌握主要的套路与手段。讲授的主题从基础的数据结构，一直延伸至新近的研究成果。
展开
课程章节
- 第零章
- 选课之前
- 考核方式
- OJ系统说明
- 关于课程教材与讲义
- 关于讨论区
- 微信平台
- PA讨论
- PA晋级申请
- 第一章 绪论
- （a）计算
- （b）计算模型
- （c）大O记号
- （d）算法分析
- （e）迭代与递归
- （xc）动态规划
- 本章测验
- 第二章 向量
- （a）接口与实现
- （b）可扩充向量
- （c）无序向量
- （d1）有序向量：唯一化
- （d2）有序向量：二分查找
- （d3）有序向量：Fibonacci查找
- （d4）有序向量：二分查找（改进）
- （d5）有序向量：插值查找
- （e）起泡排序
- （f）归并排序
- 本章测验
- 第三章 列表
- （a）接口与实现
- （b）无序列表
- （c）有序列表
- （d）选择排序
- （e）插入排序
- （xd）习题辅导：LightHouse
- 本章测验
- 第四章 栈与队列
- （a）栈接口与实现
- （c1）栈应用：进制转换
- （c2）栈应用：括号匹配
- （c3）栈应用：栈混洗
- （c4）栈应用：中缀表达式求值
- （c5）栈应用：逆波兰表达式
- （d）队列接口与实现
- 本章测验
- 第五章 二叉树
- （a）树
- （b）树的表示
- （c）二叉树
- （d）二叉树实现
- （e1）先序遍历
- （e2）中序遍历
- （e4）层次遍历
- （e5）重构
- 本章测验
- 第六章 图
- （a）概述
- （b1）邻接矩阵
- （c）广度优先搜索
- （d）深度优先搜索
- 本章测验
- 第七章 二叉搜索树
- （a）概述
- （b1）BST：查找
- （b2）BST：插入
- （b3）BST：删除
- （c）平衡与等价
- （d1）AVL树：重平衡
- （d2）AVL树：插入
- （d3）AVL树：删除
- （d4）AVL树：(3+4)-重构
- 本章测验
- 第八章 高级搜索树
- (a1)伸展树：逐层伸展
- (a2)伸展树：双层伸展
- (a3)伸展树：算法实现
- (b1)B-树：动机
- (b2)B-树：结构
- (b3)B-树：查找
- (b4)B-树： 插入
- (b5)B-树： 删除
- (xa1)红黑树：动机
- (xa2)红黑树：结构
- (xa3)红黑树：插入
- (xa4)红黑树：删除
- 本章测验
- 第九章 词典
- (b)散列：原理
- (c)散列：散列函数
- (d1)散列：排解冲突(1)
- (d2)散列：排解冲突(2)
- (e)桶/计数排序
- 本章测验
- 第十章 优先级队列
- (a1)需求与动机
- (a2)基本实现
- (b1)完全二叉堆：结构
- (b2)完全二叉堆：插入与上滤
- (b3)完全二叉堆：删除与下滤
- (b4)完全二叉堆：批量建堆
- (c)堆排序
- (xa1)左式堆：结构
- (xa2)左式堆：合并
- (xa3)左式堆：插入与删除
- 本章测验
- 第十一章 串
- (a)ADT
- (b1)串匹配
- (b2)蛮力匹配
- (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)快速排序：算法A
- (a2)快速排序：性能分析
- (a4)快速排序：变种
- (b1)选取：众数
- (b3)选取：通用算法
- (c1) 希尔排序：Shell序列
- (c3)希尔排序：更佳的序列
- 本章测验
- 查询PA成绩
- PA成绩
- 加分
授课教师
-
邓俊辉清华大学 计算机系 副教授
邓俊辉，清华大学计算机系副教授。1993、1995和1997年分别于清华大学计算机系获学士、硕士和博士学位，1997 年起在清华大学任教，主要讲授“数据结构”和“计算几何”。
精华笔记
-
这门课的笔记我是用OneNote做的，然后把它导成了PDF。虽说也有图片，但是清晰度不够高。PDF已经上传至百度云盘。 欢迎大家下载观看。 链接:http://pan.baidu.com/s/1i4Eg8EL 密码:xrcm以下是分章节的链
2016-09-01 22:09:00 by 西交大刘浩
常见问题
1、教材
（1）邓俊辉，数据结构（C++语言版）, 第三版, 清华大学出版社, 2013年9月, ISBN: 7-302-33064-6 ；（2） 邓俊辉，数据结构习题解析（C++语言版）, 清华大学出版社, 2013年9月, ISBN: 7-302-33065-3；（3）注册本课程的学生 ，可免费下载电子版勘误表、样章、示例代码包、讲义等资料，可从http://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/教 材主页直接下载。
2、编程习题平台
课程中的编程作业，需要在实验平台http://dsa.cs.tsinghua.edu.cn/oj/上完成。选修本课的同学，请用与 xuetangX账号相同的邮箱在该平台上注册账号。关于具体的过程与方法，欢迎观看简介视频 http://cm12.c110.play.bokecc.com/flvs/44B36C7761D3412F/2013-10-30/4EB85BB15213CBAD9C33DC5901307461- 10.mp4
3、成绩评定
最终成绩由以下两个方面累计而得：（1）课后测验（共12组，每组5题）：5% x 12 = 60%；（2）编程习题（共 4组，每组3题）：10% x 4 = 40%