CS.03.课程学习.02.03.数据结构与算法

深入交流 通用指南&CS攻略
1

课程内容

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

关于 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，找到这些算法的模版题，上去提交。例如，在 洛谷 上测试各种 O(n log n) 排序算法可以这样做：

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

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

2

希望能做个 lab 出来 :grinning: