ds-lab

Author: Clazy Chen @ THU

这是一个为计算机考研的学生复习《数据结构》而设计的实验体系。

背景

这个实验体系主要面向学习邓俊辉《数据结构（C++版）》的学生，即清华大学本校的学生及面向清华大学计算机专业课考试（912）复习的学生；实验体系设计上，与邓俊辉教材的安排不完全一致。

由于市面上的教材种类繁多，我不能保证能够覆盖各种教材的知识点。比如，一些教材中提出的算法，在清华大学的课程体系中可能被放在了《离散数学》《数值分析》等课程里，这些在目前的实验体系设计上尚不完善。

当这个实验体系完工之后，期待能够对同学们有所帮助，也期待有同学能对它作出改进。

前言

在我对笔记的校对工作的过程中，深感《数据结构》目前的代码设计上存在一些问题。现在，另外三门计算机统考科目都已经有了成体系的实验框架，而《数据结构》上则缺少相应的实验框架；同学们更多只能是学习《数据结构》的过程中自己实现一遍书上的代码。

而书上的代码存在以下问题：

1. 写法老旧。很多书上混用C语言风格的C++代码，不能适应现代C++开发的要求，容易让跨考的同学在学习计算机的初期养成陈旧的代码风格，降低开发效率。
2. 没有给同学自由发挥的空间。基本上只能对照书实现。
3. 看上去是“实现简化版的STL”，但很多教材根本就不是按照STL的思路设计的。这导致这些教材上的代码的实现中并没有真的用到STL提供的方法，实现出来的结果也无法和STL的其他部分配合使用。

因此我现在的重心转移到开发《数据结构》的实验框架上。在该实验框架完成之前不再继续笔记的校对工作。这个实验框架的开发结束时间预期在今年暑假，希望能赶上给23届考研的同学使用。该实验框架有以下特点：

1. 框架使用C++17-C++20的标准。

   通过阅读框架代码，您可以学习很多现代C++的编程范式和编程技巧。但不强制您在写自己的程序的时候也使用现代C++标准，您仍然可以实现旧风格的代码。

   因为现在很多编译器对C++20是有限支持，所以并没有用到很多C++20的特性。

   在现代C++的组件中，我放弃了智能指针。

   因为这是一个一旦我使用它，就必须强制使用这个框架的学生也要使用的东西：混用普通指针和智能指针，比全部使用普通指针更加糟糕。为了保持这个实验的向下兼容性，让跨考的零基础同学也能正常使用，我选择了全部使用普通指针的做法。

   我希望同学使用这个框架做实验的时候，能用自己的C++98基础做出来，而不需要强制自己学习现代C++。

   这是一个本框架和真正的现代C++最大的不同。

2. 框架高度模块化、泛型化，具有高度开放性。

   将ADT提炼出最重要的部分作为基类。我实现了样例实现，如 clazy::Vector；您可以自己继承基类，实现自己的数据结构；并通过 alias语法对实验代码中使用的数据结构进行替换。

   对于每个数据结构来说，需要您自己实现的只有最核心的部分，其他部分都是可以复用的。数据结构相关的算法，我同样单独设计了基类和样例实现。当您只想要测自己的数据结构时，算法可以用我给的样例；当您想要测自己的算法时，数据结构可以用我给的样例；您也可以都用自己写的东西。

3. 密切结合STL。

   STL提供了很多资源，但是甚至包括科班学生在内，很多同学不会用。比如 std::function实现的函数模板。就连最简单的 std::copy，很多同学也不知道。在我给出的示例代码中将会演示如何使用这些简单的STL工具。

   另一方面，我给出的实验框架下，您自己实现的数据结构也可以非常自然地嵌入到STL中。比如，您可以对自己设计的 Vector使用 std::sort(begin(V), end(V))这样的排序。

语言

使用这个实验体系，需要预先学习C++语言，关于环境的配置见下文的环境配置节。

总体上，您只需要学到C with class的程度就可以正常使用这个实验体系。对于实验体系中出现的C++的其他语言特性，下面分别进行一个简要的介绍。

功能	实验	框架	附注
类和继承	√	√	OOP的核心
多态和重载	√	√	OOP的重要组成部分
命名空间	√	√	为防止污染命名空间，示例代码全部放入 clazy命名空间中
模板	√	√	示例中的模板可能会非常复杂，您自己实验时不需要这么做
别名		√	使用 using（而非 typedef）规定别名，以让您使用自己的数据结构（算法）替换我的示例
断言		√	使用 assert进行断言，用于检查表达式是否为真
迭代器	○	√	几乎所有迭代器相关的东西，都被我写进框架里了；使用迭代器是为了让您和STL对接
宏			#define是C语言风格的东西。我会展示如何不使用它。
类型推导		√	使用 auto或 decltype自动类型推导，您可以选用以提高编程效率
元组		√	std::tuple用来传多个返回值
常量表达式		√	constexpr用来规定常量表达式
范围循环		√	for (auto x : A)的循环方式
列表初始化		√	int A[] {1, 2, 3}的初始化方式
智能指针		√	框架里使用；但所有开放给用户的地方都不用
匿名函数		√	lambda匿名函数
数字分隔符		√	使用 123'456'789，单引号用于分割数字便于阅读
结构化绑定		√	for (auto [k, v] : dict)的循环（赋值）方式
折叠表达式		√	template <typename... Args>的不定参数模式
模块			现在没有被编译器充分支持。未来可能会考虑
范围		○	现在没有被标准库充分支持。未来可能会考虑
概念		√	利用 concept和 requires进行约束
三路比较		√	使用 <=>进行三路比较，降低重载成本

环境配置

这一小节面向在Windows系统上使用Dev-C++进行开发的同学。

如果您使用的是更“高级”的系统和编辑器，我相信您并不需要我来展示如何进行环境配置。

1. 下载MinGW。

   这是因为，在Dev-C++中自带的MinGW版本太低了。

   进入网站WinLibs - GCC+MinGW-w64 compiler for Windows。

   选择最新版本的MinGW；从这个网站上下载的是免安装版本。

2. 进入Dev-C++，工具—编译选项—由文件夹添加编译设置，选择刚装的MinGW的文件夹。

   编译器：编译时增加加入命令 -std=c++2a -fconcepts -O2。（开启C++20和编译优化开关）一些情况下，您可能需要关闭 -O2，以避免编译器进行了过多的优化。

   目录：C++包含文件里，加入本实验框架中的 headers文件夹。

应该这样就可以了，您可以编译一下 sources文件夹里的 .cpp文件查看效果。

需要指出的是，文件采用的是UTF-8编码，Dev-C++中可能会将注释的中文变成乱码。发生这种情况，可以采用用记事本打开再复制进去等方法将编码转为Dev-C++使用的asci编码。

计划安排

前16章为408共享，后4章为912特有。

第一章：绪论。

第二章：向量。（顺序表）

第三章：列表。（链表）

第四章：栈。

第五章：队列。

第六章：矩阵。

第七章：二叉树。

第八章：树和森林。

第九章：AVL树。

第十章：完全二叉堆。

第十一章：图。

第十二章：查找。

第十三章：B树和B+树。

第十四章：红黑树。

第十五章：散列。

第十六章：串。

第十六章：排序。

第十七章：伸展树。

第十八章：k-d树。

第十九章：跳表。

第二十章：左式堆。