清华大学邓俊辉数据结构讲义

### 清华大学邓俊辉数据结构讲义 #### 一、绪论 - **课程简介**：本课程由清华大学的邓俊辉教授主讲，是清华大学计算机科学领域的一门核心课程，旨在深入讲解数据结构的基本概念、设计方法以及算法分析技术。 - **教师介绍**：主讲教师为邓俊辉教授，联系方式为[email protected]。此外，还配有三名助教，分别是于泽（[email protected]）、李锐喆（[email protected]）和白彦冰（[email protected]）。 #### 二、基础知识与预备知识 - **大O表示法**：介绍如何使用大O符号来评估算法的时间复杂度和空间复杂度。 - **算法分析**：讲解如何分析算法的效率，包括时间复杂度和空间复杂度，并介绍常见的分析技巧和方法。 #### 三、排序与下界理论 - **排序算法**：本章节主要介绍几种经典的排序算法，如插入排序等，并探讨它们的时间复杂度。 - **下界理论**：讨论在最坏情况下，对某些特定问题排序所需操作次数的最低下限。 #### 四、序列与线性数据结构 - **抽象数据类型与接口**：介绍什么是抽象数据类型(ADT)，并讲解如何通过接口定义数据结构的行为。 - **向量(Vector)**：探讨向量数据结构的设计与实现，包括动态数组的实现细节。 - **列表(List)**：讲解链表的基本原理及其实现方式，如单链表、双链表等。 - **游标(Cursor)**：介绍游标的概念及其在遍历过程中的应用。 - **顺序容器的应用**：结合实际案例，展示不同类型的顺序容器如何应用于具体场景。 - **有序向量**：讨论如何实现有序向量，以及其与普通向量的区别。 - **插入排序**：详细介绍插入排序算法的实现原理与步骤。 - **Java实现**：以Java语言为例，展示如何将上述概念具体化为代码。 - **跳表(Skip List)**：介绍一种高级的数据结构——跳表，探讨其优点及应用场景。 #### 五、栈与队列 - **栈(Stack)**：讲解栈的基本概念、性质和实现方法。 - **栈的应用**：介绍栈在编程中的实际应用，如表达式求值等。 - **递归**：通过栈模拟递归调用的过程，帮助理解递归的工作机制。 - **回溯探查**：利用栈解决回溯类问题，如N皇后问题等。 - **队列(Queue)**：介绍队列的基本概念和特性，以及不同的实现方式。 #### 六、字符串处理 - **字符串表示与实现**：讲解字符串的存储结构和实现方法。 - **模式匹配算法**：介绍几种常用的字符串模式匹配算法，如KMP算法等。 - **Boyer-Moore算法**：详解Boyer-Moore算法的原理及其优化技巧。 #### 七、树形结构 - **树的基本概念**：讲解树的定义、术语以及基本属性。 - **二叉树**：深入探讨二叉树的特性、存储结构及其遍历方式。 - **先序遍历**：介绍先序遍历的基本思想和实现方法。 - **中序遍历**：讲解中序遍历的特点及其应用场景。 - **后序遍历**：解析后序遍历的过程及其实现细节。 - **广度优先遍历**：介绍广度优先遍历的方法及其适用范围。 - **霍夫曼树**：讲解霍夫曼树的构建原理及其在编码中的应用。 #### 八、搜索树 - **二叉搜索树(BST)**：介绍二叉搜索树的基本概念、性质及其操作。 - **AVL树**：探讨平衡二叉搜索树的一种——AVL树，以及其自平衡机制。 - **伸展树(Splay Tree)**：介绍伸展树的特性、操作及其实现。 - **B树**：讲解B树的定义、性质及其在数据库索引中的应用。 - **红黑树(Red-Black Tree)**：探讨另一种平衡二叉搜索树——红黑树的原理与特点。 - **kd树**：介绍kd树的结构特点及在多维空间搜索中的应用。 #### 九、哈希表 - **哈希函数**：讲解哈希函数的设计原则及其对哈希表性能的影响。 - **冲突解决策略**：介绍解决哈希冲突的几种常见方法。 - **Karp-Rabin算法**：探讨一种用于字符串匹配的高效算法。 - **桶排序与基数排序**：介绍两种非比较型排序算法——桶排序和基数排序。 - **MD5散列算法**：讲解MD5散列算法的原理及其安全性。 - **哈希表在编程语言中的应用**：分析哈希表在现代编程语言中的实现及其作用。 #### 十、优先队列 - **基础实现**：介绍优先队列的基本概念及其简单实现方法。 - **二叉堆(Binary Heap)**：探讨二叉堆的数据结构及其作为优先队列的基础。 - **选择排序**：讲解选择排序算法的基本原理。 - **锦标赛排序**：介绍锦标赛排序的实现方法及其与堆排序的关系。 - **堆排序**：探讨堆排序的原理及其与二叉堆之间的联系。 - **左偏堆**：介绍一种高效的优先队列实现方式——左偏堆。 #### 十一、图论 - **图的基本概念**：讲解图的定义、术语及分类。 - **图的表示**：介绍邻接矩阵、邻接表等常见的图表示方法。 - **广度优先搜索(BFS)**：讲解广度优先搜索算法的原理及其在图遍历中的应用。 - **深度优先搜索(DFS)**：介绍深度优先搜索的原理及其在图遍历中的作用。 - **通用搜索算法**：探讨通用搜索框架及其在图遍历中的应用。 - **拓扑排序**：讲解拓扑排序的原理及其应用场景。 - **双连通分量**：介绍双连通分量的定义及其在图中的应用。 - **最小生成树(MST)**：探讨最小生成树问题及其算法解决方案。 - **最短路径问题**：讲解最短路径问题的定义及其求解方法。 - **最大流问题**：介绍最大流问题的定义及其算法解决方案。 #### 十二、高级排序算法 - **快速排序**：详细介绍快速排序的原理及其优化方法。 - **归并排序**：讲解归并排序的实现原理及其实现细节。 - **选择与中位数算法**：介绍选择算法及其在求解中位数问题中的应用。 - **希尔排序**：探讨希尔排序的原理及其优缺点。 以上是对邓俊辉教授所著的《数据结构》课程讲义的主要知识点概述。该讲义不仅涵盖了数据结构领域的基础知识，还涉及了高级主题，为学生提供了全面的学习资源。