{"topic":{"id":870,"title":"CS.03.课程学习.02.03.数据结构与算法","slug":"topic","categoryId":12,"createdAt":"2023-05-02 04:41:53.994","bumpedAt":"2023-10-06 06:28:48.241657","views":794,"postsCount":2,"highestPostNumber":2,"likeCount":1,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"课程内容这门课程的内容包括一些解决具体问题的具体算法，一些数据结构和基本的算法复杂度分析。关于算法设计的一些思想（二分、分治、动态规划等），在另一门课程《算法设计与分析》中讲授。关于 ICPC/OI ICPC/OIer应该不太用学这门课，不过只打过ICPC的选手可能常年抄板子，对平衡树和排序算法已经生疏了，可以实现一遍复健一下。如果你对 ICPC 感兴趣，可以把下面的大纲中（除平衡树外？）的内容学会，然后联系 ICPC 校队的同学…","deletedAt":null,"isAnonymous":false,"category":{"id":12,"name":"通用&CS攻略","slug":"guide","color":"ED207B"},"author":{"id":297,"username":"upload_bot","name":null,"avatarUrl":null},"tags":["survive-cs"]},"posts":[{"id":1810,"postNumber":1,"raw":"### 课程内容\n\n这门课程的内容包括一些解决具体问题的具体算法，一些数据结构和基本的算法复杂度分析。关于算法设计的一些思想（二分、分治、动态规划等），在另一门课程《算法设计与分析》中讲授。\n\n### 关于 ICPC/OI\n\nICPC/OIer应该不太用学这门课，不过只打过ICPC的选手可能常年抄板子，对平衡树和排序算法已经生疏了，可以实现一遍复健一下。\n\n如果你对 ICPC 感兴趣，可以把下面的大纲中（除平衡树外？）的内容学会，然后联系 ICPC 校队的同学。可以加西安交大 ICPC 大群，QQ 群号：526350936。\n\n### 我认为应当掌握的内容\n\n> 这个大纲不和课程严格相符，是我认为与本科相关且有价值、应当掌握的内容。这里没有的内容应该都是文科内容，期末一背就行。课程要求是掌握它们的概念，口胡过一遍，我认为如果实现过一遍这些内容这门课就算学好了。打\\*号的内容不必须掌握实现，打两个\\*号的内容是课外的、但我认为很有价值的内容，可以选学。\n\n1. 链表，数组\n2. 各种排序算法\n 1. 冒泡\n 2. 插入\n 3. 桶\n 4. 快速\n 5. 归并\n 6. 堆\n 7. 基数\n3. 树和图的各种存储方式\n4. 数据结构\n 1. 二叉搜索树\n 2. 堆\n 3. 并查集\\*\\*（这个是实现 Kruscal 必须的数据结构，所以应该作为必修知识，但是学校竟然不讲）\n 4. 线段树与懒标记\\*\\*\n5. 各种平衡树\\*\n 1. Treap\n 2. AVL\n 3. 红黑\n 4. B-Tree\n6. 树算法\n 1. DFS\n 2. BFS\n 3. 从中序遍历序列 + 另一种遍历序列恢复树\n7. 图算法\n 1. 最小生成树\n 1. Prim\n 2. Kruscal\n 2. 单源最短路\n 1. Dijkstra\n 1. 朴素\n 2. 堆优化\n 2. Bellman-Ford\n 3. 题外话：SPFA 及其变种与怎么卡掉它们\\*\\*\n 3. 两两最短路 (Floyd)\n8. 字符串\n 1. KMP\n 2. Trie 树\\*\\*\n\n### 我校数据结构与算法课程概况\n\n我校的数据结构与算法课程大纲可以接受，在理论方面问题不大，但是在实践方面问题较大。绝大多数算法/数据结构仅停留在手玩（甚至没有手玩）阶段，没有实现过（实现过与否是天壤之别，对没实现过的算法的理解很可能有问题/遗漏）。对有实验的内容，数据也过水，训练集即测试集，无法保证时间复杂度、空间复杂度和大数据范围下的正确性。\n\n我的建议是，除了简单的数据结构（如链表，存个图之类的内容）不用单独交题外，对其他有难度的算法/数据结构：找个 OJ，找到这些算法的模版题，上去提交。例如，在 [洛谷](https://www.luogu.com.cn) 上测试各种 O(n log n) 排序算法可以这样做：\n\n1. 注册 [洛谷](https://www.luogu.com.cn) 账号\n2. 搜索 `排序`，找到 [【模板】快速排序](https://www.luogu.com.cn/problem/P1177) 这道题\n3. 写代码，提交，直到 AC 所有测试点\n\n可能后期会总结一个洛谷题单，或者制作一个 codelab。","cooked":"

课程内容

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

关于 ICPC/OI

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

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

我认为应当掌握的内容

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

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

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

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

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

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

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

\n","createdAt":"2023-05-02 04:41:53.994","updatedAt":"2023-07-20 12:38:42.314798","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":905,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":4437,"username":"Luxaveil","name":"匿名用户"}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":297,"username":"upload_bot","name":null,"avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":12711,"postNumber":2,"raw":"希望能做个 lab 出来 :grinning:","cooked":"

希望能做个 lab 出来 😀

\n","createdAt":"2023-10-06 06:28:48.241657","updatedAt":"2023-10-06 06:28:48.241657","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":9,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":96,"username":"ch4op","name":"牛肉炒饭","avatarUrl":"/uploads/image/3f/41/3f41608a36622d9b6d3520ea5166dbed806585863bf9a928411f542863b360ae.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}}],"hasMore":false,"lastReadPostNumber":2,"hasUrlPostNumber":true}