Data Structures 2023
时间与地点
- 时间：1-16 周，周日 18:30 起
- 地点：
- B 班及工科：软件学院一楼 5-104 机房（一楼）
- A 班：软件学院一楼 5-103 机房（一楼）
分数构成
ACM 班
- 期末考试 50%
- 小作业 10%
- 机考 10%
- vector 4%
- priority queue 5%
- map 6%
- 火车票管理系统 15% (bonus 1%)
- B Plus Tree 7%
- 管理系统 8%
工科
- 期末考试 40%
- 小作业 10%
- 机考 10%
- vector 5%
- list 5%
- priority queue 7%
- linked hashmap 8%
- map/B Plus Tree 15% (bonus 1%)
时间表
第 1 周
- 助教介绍、课程安排、作业安排介绍 文件:2023数据结构上机课介绍.pdf
- OOP 复习
- 发布 vector 大作业（仅 ACM） 文件:STLite介绍 (2023).pptx
- 发布 OOP 作业（仅工科）
- 环境配置可参考程序设计环境配置文档
- ACM Class Online Judge: https://acm.sjtu.edu.cn/OnlineJudge
第 2 周
- B 班及工科：字符串专题
- 文件:字符串专题 (2023).pdf
- KMP
- 字符串哈希
- A 班：字符串算法
- 文件:AC自动机 (2023).pptx
- AC 自动机
第 3 周
- 第零次机考（考察第 2 周上机课内容）
- 发布 priority queue 大作业（仅 ACM）
- 发布 vector 大作业（仅工科）
第 4 周
- B 班及工科
- 单调栈
- 单调队列
- 用栈模拟递归
- A 班
- 文件:Dp优化 (2023).pptx
- dp 优化
第 5 周
- 第一次机考（考察第 4 周上机课内容）
- 发布 map 大作业（仅 ACM）
- 发布 list 大作业（仅工科）
第 6 周
- B 班及工科
- 树状数组 文件:树状数组 (2023).pdf
- RMQ（ST 表） 文件:RMQ算法 (2023).pdf
- A 班
- 文件:分块 & 莫队 (2023).pptx
- 分块
- 根号分治
- 莫队算法
第 7 周
- 第二次机考（考察第 6 周上机课内容）
- 发布 priority queue 大作业（仅工科）
第 8 周
- B 班及工科
- 文件:Lca&trie (2023).pptx
- LCA
- 字典树
- A 班
- 文件:LCA与树链剖分 (2023).pdf
- 树链剖分
- LCA
- 发布 BPT（火车票前置）大作业（仅 ACM）
第 9 周
- 第三次机考（考察第 8 周上机课内容）
第 10 周
- B 班及工科：线段树
- A 班：线段树提高
- 文件:线段树提高 (2023).pdf
- 合并
- 可持久化
- 树套树
- 发布 linked hashmap 大作业（仅工科）
第 11 周
- 五一放假
第 12 周
- 第四次机考（考察第 10 周上机课内容）
- 发布火车票大作业（仅 ACM）
第 13 周
- B 班及工科
- 文件:并查集 树哈希 (2023).pptx
- 并查集
- 哈希（树哈希及其应用）
- A 班：启发式专题
- 文件:启发式专题 (2023).pptx
- A*
- IDA*
- 启发式合并
- 发布 map 大作业及 bpt 大作业（仅工科）
第 14 周
- B 班及工科：图算法
- A 班：图论算法
- 文件:图论散讲 (2023).pptx
- 最短路
- 最小生成树较难应用
第 15 周
- 第六次机考（考察所有上机课内容）
第 16 周
- 期末笔试复习
小作业
每次上机课后会发布小作业。
大作业
STLite (ACM)
https://github.com/ACMClassCourse-2022/STLite_ACM
除非有极其特殊的原因，否则不接受任何在截止后的提交，所有代码均以截止前的提交为准！
vector
- ACM: 2023-02-19（第 1 周周日）~ 2023-03-05（第 3 周周日）
priority queue
- ACM: 2023-03-05（第 3 周周日）~ 2023-03-19（第 5 周周日）
map
- ACM: 2023-03-19（第 5 周周日）~ 2023-04-09（第 8 周周日）
STLite (工科)
https://github.com/ACMClassCourse-2022/STLite_Honor
除非有极其特殊的原因，否则不接受任何在截止后的提交，所有代码均以截止前的提交为准！
vector
- 工科: 2023-03-05（第 3 周周日）~ 2023-03-19（第 5 周周日）
list
- 工科: 2023-03-19（第 5 周周日）~ 2023-04-02（第 7 周周日）
priority queue
- 工科: 2023-04-02（第 7 周周日）~ 2023-04-23（第 10 周周日）
linked hashmap
- 工科: 2023-04-23（第 10 周周日）~ 2023-05-07（第 12 周周日）
map/bpt
- 工科: 2023-05-07（第 12 周周日）~ 2023-06-04（第 16 周周日）
火车票 (ACM)
https://github.com/ACMClassCourse-2022/Ticket-System
- BPT: 2023-04-09（第 8 周周日）~ 2023-04-30（第 11 周周日）
- 逻辑: 2023-04-30（第 11 周周日）~ 2023-06-04（第 16 周周日）
助教
| Name | |
|---|---|
| 夏天（总负责助教） | xia_tian@sjtu.edu.cn |
| 冯跃洋（B 班及工科大助教） | fyyvexoben@sjtu.edu.cn |
| 杨晋晟（A 班大助教） | modem514@sjtu.edu.cn |
| 梁亚伦 | liangyalun@sjtu.edu.cn |
| 范棋珈 | qweryy0566@sjtu.edu.cn |
| 刘祎禹 | liu_yiyu@sjtu.edu.cn |
| 陈文韬（工科助教） | leonard_chen@sjtu.edu.cn |
| 钟林昊 | zhongzero@sjtu.edu.cn |
| 董珅 | shen-dong@sjtu.edu.cn |
| 周秉霖 | zhoubinglin@sjtu.edu.cn |
| 陶沐孜（工科助教） | mzi1228@sjtu.edu.cn |
| 胡珂雅 | hu_keya@sjtu.edu.cn |
| 黄健浩 | huang_jh2021@sjtu.edu.cn |
| 王俞皓 | jerx2y@sjtu.edu.cn |
| 彭泉泉 | bartholomew@sjtu.edu.cn |