我冬春两个学期都选了朱能军老师的SJ结构，这里整合了所有小组实验内容，希望能提供一些参考。
我没有直接使用具有浓厚SJ风格的参考代码，而是参考了Sartaj Sahni的Data Structures, Algorithms, and Aplications in C++，重写了自己的版本。
关于课程安排，一个学期共有一次个人实验和四次小组实验。个人实验当场验收，完成可以作为加分项，这里不提供代码；小组实验需要一起完成代码和报告，三个人一组，验收会按照组号顺序或倒序进行（就我的经历而言），所以每个小组会分到其中一个实验的验收，组号可自选。
最后感谢合作过的三位组员@donghaidiwang @ZhiXinYo @1nv1nce.
- IDE：Visual Studio 2022
- 语言：C++ 20
运行ProjectSetup-Win64.bat即可生成Visual Studio 2022工程文件，内部包含冬春两学期的所有实验，每个实验单独一个solution。
-
第一题
某IT公司收到N份简历，人力资源部X和Y负责挑选简历安排面试。他们把N份简历排成一个圆圈，按逆时针方向编号为1～N。开始时X站在1号简历前，按逆时针方向数到第K份简历，选中；Y站在N号简历前，按顺时针方向数到第M份简历，选中。两人同时取走所选简历后，分别按逆时针和顺时针走到下一份简历前，然后X和Y再重复上述方法取简历，直到取走全部简历，如果两人选中同一份简历，则只输出一个编号。- 要求：输入3个数N、K和M，按取走简历的顺序（先X后Y）输出简历编号。
- 输入样例：
10 4 3
输出样例：
4, 8; 9, 5; 3, 1; 2, 6; 10; 7
-
第二题 某IT公司收到N份简历，人力资源部X和Y负责挑选简历安排面试，Z负责补充新的简历。他们把N份简历排成一个圆圈，按逆时针方向编号为1～N。开始时X站在1号简历前，按逆时针方向数到第K份简历，选中；Y站在N号简历前，按顺时针方向数到第M份简历，选中。两人同时取走所选简历后，分别按逆时针和顺时针走到下一份简历前，每到此时（除非所有简历都已取完），Z都会拿来1份新简历（编号从N+1开始递加），插到X前面，然后X和Y再重复上述方法取简历，直到取走全部简历，如果两人选中同一份简历，则只输出一个编号。
- 要求：要求输入3个数N、K和M，按取走简历的顺序（先X后Y）输出简历编号。
- 输入样例：
5 1 1
输出样例：
1, 5; 6, 4; 7, 3; 8, 2
第二题可能出现简历永远取不完的情况，判定条件的证明见Condition of the Endless Loop in Question 2.pdf。
有一个“T”字型铁路调度系统，它由相互垂直的2条铁轨组成，水平方向的为主铁轨，竖直方向的为辅助铁轨。辅助铁轨用于对车厢次序进行调整，它在主铁轨中间，把主铁轨分成左右两个部分。主铁轨左边的车厢只能从左边开到右边，或者从主铁轨左边进入辅助铁轨；辅助铁轨上的车厢只可以进入主铁轨右边。
-
第一题
现在有n节火车车厢，编号为1、2、...、n，在主铁轨的左边按顺序驶入，要求通过这个调度系统，在主铁轨的右边以指定次序开出（例如：有5节车厢以1、2、3、4、5 的次序进入，要求以3、2、5、4、1的顺序出站）。- 输入数据：
输入共2行，第1行一个正整数n表示车厢数目；第2行是1-n的任意排列，表示n节车厢在主铁轨右边的排列顺序。 - 输出数据：
如果能完成调度，则输出调度过程，否则输出调度失败信息。
- 输入数据：
-
第二题
现在有n节火车车厢，编号为1、2、...、n，在主铁轨的左边以任意的顺序驶入，要求通过这个调度系统，在主铁轨的右边以1、2、...、n的次序开出（例如：有5节车厢以 5、3、1、2、4 的次序进入，要求以1、2、3、4、5的顺序出站）。- 输入数据:
输入共2行，第1行一个正整数n表示车厢数目；第2行是1-n的任意排列，表示n节车厢在主铁轨左边的排列顺序。 - 输出数据:
如果能完成调度，则输出调度过程，否则输出调度失败信息。
- 输入数据:
本实验进一步通过生成全排列、所有出栈序列以及入栈序列的方式检验了算法的正确性，调度成功率为卡特兰数。
文学研究人员需要统计英文小说中某些词出现的次数和位置。试编写一个实现这一目标的文字统计系统，称为“文学研究助手”。
- 要求： 英文小说存于一个文本文件中，并假设小说中的单词一律不跨行，每行的长度不超过120个字符，待统计的词汇集合要一次输入完毕。要求对英文小说扫描一遍就完成统计工作。程序的输出结果是每个单词的出现次数和出现位置所在行的行号。其格式自行设计。
- 输入数据：
输入数据包括两部分，第一部分是要统计的单词，不超过100个，单词之间用空格分隔；第二部分是被统计的文章，可以考虑把这两部分内容放在一个文件中。 - 输出数据： 对出现在文章中的要统计的单词，输出其在文章中出现的次数和所在的行号。
-
左右子树交换
在二叉链表类模板中增加函数成员Revolute()，实现二叉树中所有结点的左右子树交换。 -
标记二叉树
一棵二叉树，根结点标记为(1,1)。
规定：如果一个结点标记为(a,b)，则它的左孩子标记为(a+b,b)，它的右孩子标记为(a,a+b)。
现在已知某个结点的标记为(a,b)，求从根结点开始需要经过多少次左分支和多少次右分支才能达到结点(a,b)。- 输入：第一行只有一个整数n，表示测试的数据组数。接下来n行（第2～n+1）行，每行包括两个整数a和b。
- 输出：n行，每行包括两个整数，分别表示从根结点开始到(a,b)需要经过的左分支数和右分支数。
- 输入样例：
2
42 1
3 4 - 输出样例：
41 0
2 1
模仿无向图的邻接矩阵类模板，完成（带权：非负）有向网的邻接矩阵类模板的设计与实现。要求实现图的基本运算（如增加删除顶点和弧等），并增加如下成员函数：
- CountOutDegree(v)：统计顶点v的出度；
- CountInDegree(v)：统计顶点v的入度；
- ShortestPath(v1,v2)：求两个顶点之间最短路径。
模仿有向图的邻接表类模板，完成（带权：非负）无向网的邻接表类模板的设计与实现。要求实现图的基本运算（如增加删除顶点和边等），并增加如下成员函数：
- CountDegree(v)：统计顶点v的度；
- ConnectedComponent()：求图的连通分量数目；
- 验证Kruskal和Prim两种最小生成树算法，并设计或实现除此以外的另一种最小生成树算法，如“破圈法”等（仅考虑连通图）；
- hasUniqueMinTree()，判断无向网是否存在唯一的最小生成树（仅考虑连通图）。
破圈法中判断回路的方法证明可以参考 https://rivers-shall.github.io/2018/11/19/Necessary-And-Sufficient-Condition-for-Unique-MST/ 。
-
查找3个数组的最小共同元素。
有3个整数数组a[]、b[]和c[], 各有aNum、bNum和cNum个元素（aNum, bNum, cNum ≤ n），且三者都己经从小到大排列。设计并编写算法找出最小共同元素以及该元素在3个数组中出现的位置，若没有共同元素，则显示“NOT FOUND”，要求算法在最坏情况下的时间复杂度为O(n)。- 输入：第一行三个数，表示三个数组元素个数，接下来三行是各有序数组。
- 输出：若存在，则输出四个数，分别表示共同元素以及在3个数组中出现的位置；否则输出“NOT FOUND”。
- 输入样例：
2 4 5
3 4
4 7 8 9
1 2 3 4 5 - 输出样例：
4 2 1 4
-
求两个有序序列的中位数 有两个长度为n的有序序列，如果将这两个序列合并成一个有序序列，则处于第n个位置的元素称为这两个序列的中位数。请设计2种求两个有序序列的中位数的算法，要求其中一种算法在最坏情况下的时间复杂度为O(logn)。
- 输入：第一行一个正整数n，表示两个序列的长度，接下来两行是各有n个元素的有序序列。
- 输出：一个数，就是所求中位数的值。
- 输入样例：
8
1 3 5 7 9 11 13 15
12 14 16 18 20 22 24 26 - 输出样例：
13
-
二叉排序树的验证和拓展
对于在二叉排序树上删除结点的问题，教材中介绍了4种算法，并实现了其中第1种算法。
现要求完成第3种，即移动当前节点左子树到其后继左子树的方式，并用多组测试数据对教材实现的和本题实现的这2种算法进行性能测试，分析比较它们的查找性能。
第二题是按照中位数的严格定义来做的，即中间两个数的平均数（老师挺满意，但还是说按照原题来）。此外，还实现了非等长序列的中位数求解。
-
快速排序算法的改进
对快速排序算法而言，若能合理地选择基准数据元素，使得每次划分后的两个子表中的元素个数尽可能接近，则可以加速排序速度。
请设计1-2种基准数据元素选择策略，从而改进教材中实现的快速排序算法，并利用实验结果进行性能比较。 -
DNA排序 字符串的逆序数是指字符串中逆序字符对的数目。例如：字符串“DAABEC”的逆序数为5，因为D大于右边4个字符，E大于字符C；又如：字符串“AACEDGG” 的逆序数为1（只有E与D逆序），它近似已排好序；而字符串“ZWQM”的逆序数为6，它完全逆序。
现要求对DNA字符串（只由A、C、G、T四个字符组成，长度为m）进行分类。分类方法是根据DNA字符串的逆序数从小到大进行排序（自己实现排序算法），逆序数相等的DNA串再按照字符串的字典序从大到小排列。- 输入：第一行包含两个正整数n和m，其中n（0<n≤100）表示DNA字符串的数目，m（0<m≤50）表示DNA字符串的长度。接下来n行每行为一个长度为m的DNA字符串。
- 输出：输出分类好的DNA字符串，每行一个DNA字符串，一共n行。
- 输入样例：
6 10
AACATTAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT - 输出样例：
CCCGGGGGGA
GATCAGATTT
AACATTAAGG
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA