BUAA-DS
题单介绍
[TOC]
# 食用说明
本题单为BUAA-DS的预习参考编程题，难度大部分与DS作业相当，以偏模板的题目为主，少数题目作为课堂拓展（均已说明），与作业和考试相关性小。
由于DS课程环环相扣（比如实现链表需要懂指针，实现树需要懂链表，实现图需要懂树），故建议按照顺序学习食用。
由于大类DS课程阉割过于严重，所以对于不满足于课程内容的同学，笔者墙裂建议找本好教材仔细研读（仓库中有几本不错的书），或者直接按照算法竞赛的要求学习数据结构实现降维打击（知识点清单请参考[OI-Wiki](https://oi-wiki.org/)）。多学点肯定是好事儿，或许等你们学完这课一年或者两年之后就会很感谢当年多学了一些东西的自己。
题目来源不局限于洛谷，每个题目理论上都很方便在所属OJ中找到题解。
DS课程会查重，如果该题单中碰巧和DS作业有相同或者相似的题目，思路可以借鉴，代码必须自己独立写出来。
DS课程要求使用C语言编程。
## 预备内容
这部分内容承上启下，把上学期大家没学好的一部分快速重讲一遍，然后布置两次作业用于巩固。落下比较多的同学建议寒假提前补一补。
如果感觉这些吃不饱，可以移步[函数与结构体](https://www.luogu.com.cn/training/105)和[字符串](https://www.luogu.com.cn/training/104)题单
### 函数与递归
[hanoi again](https://accoding-cn-443.e1.buaa.edu.cn/problem/1073/index)
稍微有点变形的汉诺塔。
[台阶](https://www.luogu.com.cn/problem/P1192) 通过此例子再次理解为什么重复计算多的时候递归很慢，以及解决该问题的方案
[全排列](https://www.luogu.com.cn/problem/P1706)
祖传DS第一次作业题目之一（也是查重重灾区之一），请确保自己理解了全排列的回溯法。
[烤鸡](https://www.luogu.com.cn/problem/P2089)
比较基础的回溯法
[八皇后](https://www.luogu.com.cn/problem/P1219)
回溯法经典问题
[数独](https://www.luogu.com.cn/problem/P1784) 一个经典的搜索题，需要进行一点剪枝
[高精度乘法](https://www.luogu.com.cn/problem/P1303)
练习代码能力用
快速排序qsort的使用，会排结构体，会自定义排序规则
### 数组与字符串
关于传递数组或者指针作为参数，如果想找个不能投机的平台，可以去[LeetCode](https://leetcode-cn.com/problemset/all/)，上面几乎所有的题目都是只让大家实现一个函数，不能也不需要写主函数。
[数组的常见操作](https://leetcode-cn.com/leetbook/detail/all-about-array/) 数组中常用的操作的裸题题单
[约瑟夫问题](https://www.luogu.com.cn/problem/P1996)
可以用数组尝试做这个问题
[二分查找](https://www.luogu.com.cn/problem/P2249)
听说90%的程序员没办法一遍写对二分查找。通过此题可以积累一个正确的二分查找代码模板。
[单词方阵](https://www.luogu.com.cn/problem/P1101)提示一点，注意自己使用的读入函数。
[字符串展开](https://www.luogu.com.cn/problem/P1098)
字符串的基本操作复习题，也曾经出现在往届DS作业中
[单个单词词频统计](https://www.luogu.com.cn/problem/P1308)
其实就是字符串的匹配
[单词数统计](https://leetcode-cn.com/problems/number-of-segments-in-a-string/)
LeetCode上的题目，强迫大家面对指针
[KMP字符串匹配](https://www.luogu.com.cn/problem/P3375)
拓展内容，比较高效的一种字符串匹配算法，有余力的同学可以学习一下，大作业竞速时可以考虑使用
### 指针
[字符串压缩](https://leetcode-cn.com/problems/compress-string-lcci/) LeetCode上的题目，请选择C语言，可强迫使用指针
### 结构体
TODO
理论知识请阅读课本/网络材料
训练的话可以参考上面两个题单
### 输入输出与文件操作
会读入文件，写入文件
通过读文档能学会使用各种输入输出函数
OJ上很难找到这种题目，主要靠大家自己训练
1.26日hzy大佬提供了一个输入输出与文件读写实验，可以吃透那个例子
## 链表
主要是裸题，基本都来自leetcode，你只需要实现一个功能函数即可，函数带来的影响会通过指针或者返回值传给调用它的主函数（不需要自己写）
[链表常见操作](https://leetcode-cn.com/leetbook/detail/linked-list/) 一些链表中常见的题目
[倒数第k个结点](https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/)
比较经典的一个链表题目
[旋转链表](https://leetcode-cn.com/problems/rotate-list/)
本质上方法和上面那个题相同
[有序链表去重](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)
考察链表的基本操作
[合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
就是归并操作，在归并排序中也会遇到
[删除结点](https://leetcode-cn.com/problems/delete-node-in-a-linked-list/)
考察链表的删除操作
[链表排序](https://leetcode-cn.com/problems/insertion-sort-list/) 学习如何正确的将链表进行排序
## 栈
[表达式求值](https://accoding-cn-443.e1.buaa.edu.cn/problem/303/index)
数据结构课程和作业中的常客之一。目前笔者知道的求解该问题的方法有：栈转化为后缀表达式求解；表达式树求解；递归下降求解；$O(n^2)$直接对中缀表达式分治求解。
[括号匹配](https://www.luogu.com.cn/problem/P1739) 涉及到括号序列的问题一般都可以考虑使用栈来做一些事情
[栈](https://www.luogu.com.cn/problem/P1044) 出栈序列计数，是个有趣的问题
[包含min函数的栈](https://www.acwing.com/activity/content/problem/content/362/1/) 操作栈的同时$O(1)$维护栈中元素最小值。
## 队列
[队列安排](https://www.luogu.com.cn/problem/P1160)
队列的简单模拟
[01迷宫](https://www.luogu.com.cn/problem/P1141) 队列在广度优先搜索中的应用
## 树
[二叉树的各类问题](https://leetcode-cn.com/leetbook/detail/data-structure-binary-tree/)
[中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
基础题目，要求实现二叉树的中序遍历
[后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
基础题目，要求实现二叉树的后序遍历
[n叉树最大深度](https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/) 练习多叉树的存储，以及多叉树的遍历
[二叉搜索树](https://www.luogu.com.cn/problem/P5076)
集合了二叉搜索树常用的几个操作，通过本题你将更加深入理解二叉搜索树的性质，以及基本操作的代码实现。本题没有二叉搜索树的删除结点操作，如果想测试删除功能，请移步下一题：普通平衡树。
本题代码可以积累成代码模板，期末复习时可以使用。
[普通平衡树](https://www.luogu.com.cn/problem/P3369)
拓展内容，想手写AVL等平衡树的同学可以尝试此题，普通的二叉搜索树提交本题应该只能拿到88分
[最近公共祖先](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/) 期末考试连续两年考到多叉树最近公共祖先的找法，本题是二叉树的最近公共祖先，二者算法过程非常相似。平时作业中也有考察最近公共祖先的查找
[最近公共祖先](https://www.luogu.com.cn/problem/P3379) 拓展内容，想AC此题你需要额外学习倍增或Tarjan算法或树剖等竞赛常用快速求最近公共祖先的算法
[字典树](https://www.luogu.com.cn/problem/P2580)
字典树是多叉树，通过本题可以学到字典树的一种应用，并亲手实现一遍多叉树的代码（弥补上一个题的遗憾）。另外，DS大作业中使用字典树也可以得到不错的结果，期末考试中也连续两年考察了多叉树。
[网络延时](https://www.acwing.com/problem/content/3218/)
和18级DS期末考试最后一题题目背景完全相同的一个题目。考试题询问的是输入两个结点求最近公共祖先，本题询问的是离得最远的两个点的距离（求树的直径）。
## 查找
[字符串哈希](https://www.luogu.com.cn/problem/P3370)
练习hash表的基本使用，学习一些优秀的hash函数，这会是大作业竞速中拿到高分的必备技能。当然，除了hash表，你也可以尝试使用其他的数据结构去AC本题。
[hashmap](https://leetcode-cn.com/problems/design-hashmap/) 手写一个正儿八经的hash
## 排序
[排序](https://www.luogu.com.cn/problem/P1177)
本题可以用来练习学过的所有的排序算法，题解区有丰富的各种算法的介绍和代码实现
数据结构课程作业和考试有选择填空题，会考察算法的执行过程，所以一定要学会每种排序算法，不要老想着`qsort`投机取巧。
## 图论
[单源最短路弱化版](https://www.luogu.com.cn/problem/P3371)
纯模板题，可以练习dijkstra算法的代码实现
[单源最短路](https://www.luogu.com.cn/problem/P4779)
拓展题目，体会数据结构如何优化算法的时间复杂度
[全源最短路](https://www.luogu.com.cn/problem/P2910)
拓展题目，可自行学习课堂上只提了一下的Floyd算法，也可n次dijkstra算法
[最小生成树](https://www.luogu.com.cn/problem/P3366)
模板题，可以练习两种最小生成树算法，有余力的同学可以在原算法的基础上学习利用数据结构优化