课程内容

这门课程的内容包括一些解决具体问题的具体算法，一些数据结构和基本的算法复杂度分析。关于算法设计的一些思想（二分、分治、动态规划等），在另一门课程《算法设计与分析》中讲授。

关于ICPC/OI

ICPC/OIer应该不太用学这门课，不过只打过ICPC的选手可能常年抄板子，对平衡树和排序算法已经生疏了，可以实现一遍复健一下。

如果你对ICPC感兴趣，可以把下面的大纲中（除平衡树外？）的内容学会，然后联系ICPC校队的同学。可以加西安交大ICPC大群，QQ群号：526350936。

我认为应当掌握的内容

这个大纲不和课程严格相符，是我认为与本科相关且有价值、应当掌握的内容。这里没有的内容应该都是文科内容，期末一背就行。课程要求是掌握它们的概念，口胡过一遍，我认为如果实现过一遍这些内容这门课就算学好了。打*号的内容不必须掌握实现，打两个*号的内容是课外的、但我认为很有价值的内容，可以选学。

1. 链表，数组
2. 各种排序算法
   1. 冒泡
   2. 插入
   3. 桶
   4. 快速
   5. 归并
   6. 堆
   7. 基数
3. 树和图的各种存储方式
4. 数据结构
   1. 二叉搜索树
   2. 堆
   3. 并查集**（这个是实现Kruscal必须的数据结构，所以应该作为必修知识，但是学校竟然不讲）
   4. 线段树与懒标记**
5. 各种平衡树*
   1. Treap
   2. AVL
   3. 红黑
   4. B-Tree
6. 树算法
   1. DFS
   2. BFS
   3. 从中序遍历序列+另一种遍历序列恢复树
7. 图算法
   1. 最小生成树
      1. Prim
      2. Kruscal
   2. 单源最短路
      1. Dijkstra
         1. 朴素
         2. 堆优化
      2. Bellman-Ford
      3. 题外话：SPFA及其变种与怎么卡掉它们**
   3. 两两最短路(Floyd)
8. 字符串
   1. KMP
   2. Trie树**

我校数据结构与算法课程概况

我校的数据结构与算法课程大纲可以接受，在理论方面问题不大，但是在实践方面问题较大。绝大多数算法/数据结构仅停留在手玩（甚至没有手玩）阶段，没有实现过（实现过与否是天壤之别，对没实现过的算法的理解很可能有问题/遗漏）。对有实验的内容，数据也过水，训练集即测试集，无法保证时间复杂度、空间复杂度和大数据范围下的正确性。

我的建议是，除了简单的数据结构（如链表，存个图之类的内容）不用单独交题外，对其他有难度的算法/数据结构：找个OJ，找到这些算法的模版题，上去提交。例如，在洛谷 (opens new window)上测试各种O(n log n)排序算法可以这样做：

1. 注册洛谷 (opens new window)账号
2. 搜索排序，找到【模板】快速排序 (opens new window)这道题
3. 写代码，提交，直到AC所有测试点

可能后期会总结一个洛谷题单，或者制作一个codelab。