C++数据结构算法（一）_c++ 数据结构 基本算法

数据结构研究什么？

• 数据结构研究的是在抽象层面上一组有特定关系的数据的存储与处理。

学习数据结构就是研究：

• 问题定义

• 数据之间的逻辑关系

• 关系对应的操作

• 问题解决

• 存储实现：如何存储某种逻辑关系

• 运算实现：在特定存储模式下，相关操作是如何实现的

数据结构的基本概念

定义

• 数据结构(data structure) 是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。

比如说在存储学生信息时，一种由学号大小定义的先后关系就是一种线性结构，学号小的在前，学号大的在后;

而如果想将其存在电脑的内存里，每个学生存在内存的哪一个位置就涉及数据的物理结构（或存储结构）了;

假如我们将学生按照学号的顺序存在数组里，那么在内存上就是一段连续的内存空间。

在这里，可以很明显得看出计算机上的算法实现和数学解法之间的区别

• 数学解法是不涉及数据的物理结构的，它只关心数据的逻辑结构。

• 算法因为需要实现成代码，并且利用计算机上有限的资源（比如说cpu、内存）来尽可能高效率地得到问题的答案，所以要考虑数据之间在物理内存上的存储方式。

数据的逻辑结构

逻辑结构

• 逻辑结构指的是数据元素之间的前后关系，与计算机的存储位置无关。

• 通常分为以下几类：

  • 集合：数据结构中的元素属于”同属于一个集合“的关系，除此之外没有其他关系。

  比如“三年二班中的男生”和“三年二班中的女生”就是两个学生集合。

  • 线性结构：数据结构中存在一对一的相互关系。

  比如学生根据学号的前后关系。在班级打印一些信息时，学号小的就会在表格的前面，学号大的就会在班级的后面。

  • 树形结构：数据结构中的元素存在一对多的相互关系。

  比如说学生会中的组织关系。比如学生会主席负责领导副主席，副主席负责领导各部门部长，而各部门部长负责领导副部长、干事等等，除了主席，每一个职位都会有一个直接领导。除了跟元素外，每个节点有且仅有一个前驱，后继数目不限。

数据结构的常见操作

数据结构常见操作

• 创建： 创建一个空的数据结构。

比如创建一个用于记录“三年二班学生学号和姓名”的数据结构。

• 清除： 清空数据结构。

比如清楚记录“三年二班学生学号和姓名”的数据结构。

• 插入： 往数据结构中增加新的节点。

假设”三年二班“新转来一名同学，那么”将该学生的姓名和班级录入学校系统“就是一个插入操作。

• 删除： 把指定的节点从数据结构中去掉。

假设”三年二班“转走了一名同学，那么”将该学生的姓名和班级从学校系统中删除“就是一个删除操作。

• 检索： 检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。

假设一条学生的记录了学生的班级。那么”找到所有三年二班的学生“就是一个检索操作。

• 更新： 改变指定节点的一个或多个字段的值。

假如一个学生改名了，那么”将姓名由小红修改成小芳“就是一个更新操作。

• 访问： 访问数据结构中的某个元素。

• 遍历： 按照某种次序，访问数据结构中的每一个元素。

不同的逻辑结构可能还有自己特定的操作，比如：

• 排序： 把节点按某种指定的顺序重新排列。

例如递增或递减。假如学校进行了一次考试，班级需要给学生进行一次排名，那么”根据考试成绩进行排名“就是一个排序操作。

总结：数据结构作为算法实现中数据的容器，其作用就是通过设计如何利用数据之间的逻辑结构，转化成计算机上合适的的物理结构，从而达到高效进行数据处理和运算的目的。

数据的物理结构（也叫存储结构）

物理结构（也叫存储结构）

• 指数据的逻辑结构在计算机存储空间的存放形式。

Tips: 因为如果要存储一组数据，并且基于该数据快速执行一些操作，就需要清楚且简洁地描述这组数据以及恰当地组织数据之间的关系。

所以我们通常需要关心的有两点:

• 一个是数据元素的机内表示

• 另一个是关系的机内表示

• 数据的机内表示：*

  • 在数据结构中，一个数据就是一个结点（node），而数据的每一个数据项，成为该数据的数据域（data field）。

  例如在学校的档案中，每个学生的数据我们就用一个结点表示，而该学生有关的信息，例如姓名、年龄、班级，都是该学生结点的数据域。在计算机中，不管数据项是整数、浮点数和字符串，都会最终编码成二进制串的形式。在学生数据中，姓名和班级就是两个字符串，而年龄就是一个指定范围内的整数。

• 关系的机内表示：

常用的两种存储结构有两种:

• 一个是顺序存储结构
• 另一个是链式存储结构。

试想：如果学校在一段程序中，想读入一组学生的数据到内存。那我们在程序中怎样存储呢？

一个最直观的想法就是数组。所以学生的数据在内存中的形式就如下图所示：

这样，我们就能按照下标访问该内存中存储的学生的数据。

但如果我们想通过姓名“小明”查找小明的班级，那么就只能从头到尾遍历整个数组，先将每个数据姓名的数据域进行比对，如果和“小明”相匹配，然后再输出“班级”的数据域。

除此之外，如果我们想在下标为“1”的后面插入一个数据，就只能将“1”及其以后的数据全部向后移动一个位置，可见使用数组存储对于下标访问操作是很高效的，但对于插入和删除就比较慢。这就是一种顺序存储结构。

那么，如果我们想在插入和删除两个操作上提速的话，可以想到，相比将所有数据存在一段连续的内存空间里，我们可不可以将其分散存放，但是用一条“链”将数据穿起来，这样就能知道它们之间的前后关系了。于是我们就可以将其以“链表”的形式存储，如下图所示：

这样，如果我们想在“小明”的后面插入一个数据，只需新建一个结点，然后建立新的指针指向关系即可，如下图所示：

但是，如果我们想输入下标“3”访问链表中的第3个元素，就只能从第1个向后沿着指针跳动3次，才可以找到第3个元素的内存位置。

总结：数据结构描述单条数据的信息和数据之间的关系。不同的数据结构会有各自的长处，也会有个各自的短板，需要根据实际场景选择最合适的数据结构。

常见的数据结构举例

常见的数据结构有数组、链表、栈、队列、树、图等。数组和链表在之前已经给过例子了，所以这里我们举例描述一下栈、队列、树和图的使用场景。

其中：

• 数组、链表、栈和队列都在描述数据的线性结构，
• 而树和图分别描述数据的树形结构和图形结构。

• 数据结构的逻辑结构 指的是数据元素之间的前后关系，与计算机的存储位置无关。

• 逻辑结构通常分为以下几类：

  • 集合：数据结构中的元素属于“同属于一个集合”的关系，除此之外没有其他关系。

  • 比如“三年二班中的男生”和“三年二班中的女生”就是两个学生集合。

  • 线性结构：数据结构中存在“一对一”的相互关系。

  • 比如学生根据学号的前后关系。在班级打印一些信息时，学号小的就会在表格的前面，学号大的就会在班级的后面。

  • 树形结构：数据结构中的元素存在“一对多”的相互关系。

  • 比如说学生会中的组织关系。比如学生会主席负责领导副主席，副主席负责领导各部门部长，而各部门部长负责领导副部长、干事等等，除了主席，每一个职位都会有一个直接领导。除了跟元素外，每个节点有且仅有一个前驱，后继数目不限。

高精度运算 

C++自己本身有一些内置的整数类型，比如short、int、long long等。但它们的最大值都有一个限制，即便是unsigned long long能存储的最大数也只有2^{64} - 1264−1。

在进行更大范围的数值计算中，要怎么办呢？

既然一个数字没办法用一个变量装下，可不可以用很多变量？比如说，用一个数组来存储？

• 在使用整数的过程中，并不是只需要把它每一位存下来就好了，还需要：

• 读入用户的输入，
• 还要进行整数之间加减乘除的运算，
• 还要将计算结果输出给用户看。

所以，只有当这些基本操作都实现了，我们才算真真正正实现了一个完整的大整数操作。

Tips: 其实，如果让我们自己在纸上写下一些20位的整数（已经超过long long）的范围，其实我们是知道如何进行计算的。比如说如果两个20位的整数相加，其实就像小学生列竖式一样，逐位相加，维护进位即可。

单精度与高精度

• 单精度：能用一个内置类型存储的整数。
• 高精度：不能用内置类型存储的大整数，通常用数组存储每一个数位。  

区分了单精度和高精度后，就让我们一起来想想使用整数的过程过程中的第一步：存储。

存储

刚才提到，用数组存储高精度大整数，并用一个整型变量维护它的长度。当把大整数存储在数组里时，有两种存储方式可供选择：

• 大端序：数字的高位在地址的低位（也就是和打印顺序一致）。以2021为例：

• 小端序：数字的低位在地址的低位。

通常进行高精度计算时，采取小端序方式，主要的目的是为了方便模拟竖式计算，在后面我们会详细解释。

总结：表示一个高精度数字

• 数位数组，采用小端序的存储方式，将高精度数字的每一位存在数组的每个元素里。

• 长度，表示这个高精度数字十进制位的个数。

• 高精度整数可以由数位数组和长度两部分组成。数位数组存储整数时使用的是小端序。

使用小端序的理由：

1. 因为加法、减法及后面介绍的乘法等，都是从低位算到高位。这样存储符合我们平时习惯的枚举顺序。

2. 因为数位计算结束后，需要更新数位数组的长度。把高位放在数组后面比较方便数组伸缩。

• 高精度整数使用字符串输入。由于存储顺序和打印顺序不一致，所以输入输出时都需要翻转操作。

• 高精度加法、减法和乘法都可分为数位操作和维护长度两部分。维护长度时，注意不要将长度减小到0。

• 以高精度减法为例：

  • 数位操作：

  根据减法竖式计算的规则：从低位开始，逐位相减，若该位不够减，需向下一位借位，并且借一当十。

  上面的例子中，可以发现，第i位的结果等于被减数第i位减去减数第i位和低位的借位。

  • 维护长度在两个数相减时，若我们另初始长度为被减数的长度。

  可以想象，最终计算的差的长度，和被减数相比，很可能变小。

  • 代码实现

  这里，我们总假设被减数大于等于减数。

• 使用小端序的好处

  回顾一下小端序的存储方式：数字的低位在地址的低位。由此，我们可以看到使用小端序的理由：

  1. 因为加法、减法以及后面介绍的乘法等，都是从低位算到高位。这样存储符合我们平时习惯的枚举顺序。
  2. 因为数位计算结束后，需要更新数位数组的长度。把高位放在数组后面比较方便数组伸缩。

时间复杂度

现在，我们分别讨论两个评估算法的指标，时间复杂度和空间复杂度。

最坏情况下时间复杂度

时间复杂度描述的是算法运行时间和输入规模的关系。

它基于以下设定：

• 每条语句运行都需要消耗一定时间;

所以程序的运行时间，和语句的数量有关。

• 运行时需要执行的语句条数和输入的规模相关。

而且通常情况下，输入规模越大，语句越多（一般不会不变因为读入语句的数量就会随着输入规模增长而增长）。如上一节的例子： 数组越长，for循环读入和计算前缀和需要枚举的范围就越长，所以需要运行的计算前缀和的语句条数就越多。

cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; } 

由这两条可以得出结论：

• 算法的运行时间是关于输入规模的一个函数。

• 这个函数被称为该算法的时间复杂度。这里我们用nn表示输入规模，用T(n)T(n)表示算法的运行时间。

但从上一节例子的第一种做法中，我们会发现算法的运行时间不仅和输入规模（也就是数组长度和询问个数）有关，还与具体的询问内容有关。

例如,如果每次询问的区间[x, y][x,y]都满足x = yx=y，算法的运行时间肯定比每次都满足x=1, y=nx=1,y=n要快。我们如何将这种情况考虑进算法的时间评估中呢？

所以，我们评估算法的运行时间，一个很常用的指标是最坏时间复杂度。

• 最坏时间复杂度描述的是在规模为nn的所有可能的输入中，最坏情况下算法的运行时间。

之所以这样做，是因为算法设计的目的是为了解决一类问题，而如果更明确地阐述清楚“解决”的意思，就是在一定的限制条件下（包括时间和空间），对于所有这类问题的具体实例该算法都可以输出正确结果。所以，我们只需要评估该算法在这类问题中“最难的实例”解决问题的时间，并且保证该时间不超过合理的范围内即可。

另外，我们还可以得出一个结论：

• 算法的运行时间可以用算法运行的语句数量近似表示。

也就是说，我们可以将T(n)T(n)定义成算法运行的语句条数。那么对于下面一段代码：

cin >> m; for (int i = 1; i <= m; ++i) { // 读入询问 int x, y; cin >> x >> y; // 求解答案 cout << sum[y] - sum[x - 1] << endl; }

算法的语句条数为：

11 (cin >> m)

+ 1+1 (int i = 1)

+ m + 1+m+1 (i <= m 对于i从1到m+1各比较一次)

+ m+m (++i对于i从1到m各运行一次)

+ m+m​ (int x, y;对于i从1到m各运行一次)

+ m+m​ (cin >> x >> y;对于i从1到m各运行一次)

+ m+m (cout << sum[y] - sum[x - 1] << endl对于i从1到m各运行一次)

=5m+3=5m+3

可以发现，这样的计算是十分繁琐的。可在实际的算法评估中，这样细节的计算是很没有意义有的，这是因为以下两点：

• 代码的运行时间受语句种和运行环境的影响。

即便对于一条效果相同的语句，不同的实现方式运行的时间也不一样。

参考：c - Is it better to avoid using the mod operator when possible? - Stack Overflow

另外，即便是同一段代码，用不同的编译器编译成可执行程序，放在不同架构的处理器下运行，其运行时间也都是不一样的。

比如在用命令行编译C++程序时，可以加入-march=native参数，会令编译器自动探测编译所在主机，并且针对该目标架构进行特定的优化，使得代码可以运行得更快。

• 代码效率评估只关心数据规模大时的代码效率。

因为我们使用计算机解决问题的场景主要是针对人力所不能及的数据规模，这样才能发挥计算机更加强大的计算能力。

所以，根据上面的例子，如果数据规模很小（m=1）时，可能最后额外的+3就占了所有语句3/83/8的比例。相反，如果数据规模很大（m=100000），那么式子中多出来的3条语句就只占所有语句的3/5000003/500000，就是微不足道的。

由于上面列举的原因，我们统一一种估算方式。我们用以下几个例子先感受一下（其中nn表示输入数据规模）：

• 可以看到，我们在估算算法效率时只保留增长最快的一项除了系数以外的部分，相当于只保留了该式子的“数量级”。

当然，在实际场景中，我们也会针对算法的某个部分分析其效率。

特别的，如果一个算法某个部分的运行时间并不随着输入规模的增长而增长，那我们称其的复杂度为常数

空间复杂度

同样，我们也可以将程序所消耗空间的大小表示成一个与输入规模有关的函数，该函数称为空间复杂度。

但空间复杂度情况数比时间复杂度少，常见的场景就是估算数组大小：

// 假设数据规模最大为N int a; // 常数空间复杂度 int a[N]; // 此时空间复杂度为 O(N) int a[N][N]; // 此时空间复杂度为 O(N^2)

总结

算法运行环境是一个物理的机器，该机器的计算能力和存储空间都是有限的。所以，对于一个算法能不能在有限资源下成功输出结果，我们需要对其时间和空间进行评估。

时间复杂度：

• 时间复杂度通常是该算法在用最坏情况下的时间复杂度，使用大O记号用来表示估算的结果。

空间复杂度：

举例：

// 假设数据规模最大为N int a; // 常数空间复杂度 int a[N]; // 此时空间复杂度为 O(N) int a[N][N]; // 此时空间复杂度为 O(N^2)

子集枚举，顾名思义就是在枚举所有子集。为了解释这句话，我们需要先明确几个概念：

• 集合: 集合就是包含一些对象的整体。

比如一个学校里，“全体同学”就是包含所有同学的集合；“全体男生”就是包含所有男同学的集合，“全体女生”就是包含所有女同学的集合。

• 子集: 子集就是只包含某集合中一部分对象的集合。

比如在学校中的“全体同学”里，“经管系的同学”就是“全体同学”的一个子集。另外，每个非空集合都有两个最特殊的子集。一个是空集，不包含该集合中的任何元素。另一个是该集合本身，包含该集合中的所有元素。

了解了集合和子集的概念以后，我们来看一个例题：

【举例】

假设我们有个集合\{1, 2, 3, \ldots, n\}{1,2,3,…,n}，输出所有满足集合中所有数求和是3的倍数的子集的个数。

【思路】

回顾一下枚举的基本思想：

1. 确定枚举对象、枚举范围和判定条件；

2. 枚举可能的解，验证是否是问题的解。

我们也可以用这个思路解决该问题，那么该题的算法就是：

• 步骤1：枚举所有子集SS。
• 步骤2：如果枚举到的子集SS满足条件，则将其计入答案。

对于步骤2，算法设计是比较直接的。给定集合SS，要想检查它是否满足“所有数求和是3的倍数”这个条件，只需要将所有的数加起来，模3，检查结果是否为0即可。

但是对于步骤1，我们如何枚举一个集合的所有子集呢？这就要涉及到我们的子集枚举算法。

Tips: 主频，表示CPU每秒钟产生脉冲信号的次数（也就是每秒钟的时钟周期个数）。

以2.1GHz为例，一秒钟该CPU可以产生2.1\times10^92.1×109次脉冲信号，如果一台计算机每个时钟周期可以完成1条指令，那么该计算机1s之内就可以运行2.1\times 10^92.1×109条指令。

内存的大小就限制了我们所开变量的大小。比如一个二维数组int a[5000][5000]所耗内存为：

5000 \times 5000 \times 4 \div 1024 \div 1024 \approx 95\text{ MB}5000×5000×4÷1024÷1024≈95 MB

所以，总结一下，为什么需要评价算法呢？

• 是因为在现实生活中，计算资源，包括CPU的计算速度和内存的大小，是有限的，而我们的等待时间也是有限的。所以，我们需要用更快（或内存利用率更高）的算法来应对时间紧张（或者内存紧张）的开发场景。

• 另外，在一些更有针对性的场景（如机器学习场景），在算法开发中，可能有更具体的需求，所以就需要设计更具体的指标（例如机器学习中的准确率、精确率和召回率等）。

时间复杂度和空间复杂度： 

 

 如何判断时间复杂度

 

 例题：

 

O(1)O(1)——常数条语句：交换两个元素

O(n)O(n)——单重循环求数组和 

 

 O(n2)——双重循环求数组中相等元素对数

O(2^nn)O(2nn)——枚举n个数字组成集合的所有子集，输出子集和。

空间复杂度

同样，我们也可以将程序所消耗空间的大小表示成一个与输入规模有关的函数，该函数称为空间复杂度。

但空间复杂度情况数比时间复杂度少，常见的场景就是估算数组大小：

 

 例题，伪代码的时间复杂度：

 

1. 这里，我们引入字典序的概念，并且最终按照字典序的顺序枚举排列。字典序，又叫字母序，是规定两个序列比较大小的一种方式。其规则是对于两个序列a和b：

• 从第一个字母开始比较，如果在第i个位置满足，i没有超过两个序列的长度，小于i处两个序列对应位置的元素都相等，而第i位两个序列对应位置元素不等的话，则若a[i] < b[i]，那么序列a小于序列b，否则序列b小于序列a。
• 若从第一个位置直到其中一个序列的最后一个位置都相等的话，则比较a和b的长度，若a的长度小于b，则序列a小于序列b（此时a是b的前缀），而如果b序列的长度小于a，那么序列b小于序列a。
• 若两个序列长度相等，并且所有元素相等，则序列a等于序列b。

 

 

【取宝石问题】

假设在一个大房间有nn个宝石，每一处宝石用一个坐标(x, y)(x,y)表示。如果你从任意一处宝石的地方出发，依次经过每个放宝石的地方并取走宝石，最终要求回到出发地点，问最短需要走的距离是多少。

在这个情境里，经过不同地点的顺序会改变最终的行走距离。所以，我们要枚举的就是经过1~n一共n个位置的顺序。

• 用next_permutation函数解决“取宝石问题”

因为要用枚举法解决第一个问题，所以，代入到题目的情境中，我们可以设计如下算法：

1. 枚举所有n个点的排列

2. 维护最短距离。检查新枚举的排列产生的行走距离是否比之前的最短距离还短。如果短，就更新答案。

下面是解决这个问题的完整代码： 

#include <bits/stdc++.h>
#define N 15
using namespace std;
int n, id[N];
double x[N], y[N];
 
// 求两个点(x_1, y_1)和(x_2, y_2)之间的直线距离
double dis(double x_1, double y_1, double x_2, double y_2) {
    double dx = x_1 - x_2;
    double dy = y_1 - y_2;
    return sqrt(dx * dx + dy * dy);
}
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        id[i] = i;	// 因为我们枚举标号的排列，所以要将标号存进数组里
    }
    
    double ans = -1;    // 因为最开始ans中没有值，所以我们可以将其设置为一个不合法的值	
    // 用do...while循环是为了防止第一次调用时数组id中的值已经被重排
    // 所以会导致标号为1, 2, ..., n的排列没有被计算。
    do {
        // 求解按照id[1], id[2], ..., id[n], id[1]作为行走路线的总距离。
        double cur = dis(x[id[1]], y[id[1]], x[id[n]], y[id[n]]);
        for (int i = 1; i < n; ++i)
            cur += dis(x[id[i]], y[id[i]], x[id[i + 1]], y[id[i + 1]]);
        
        // 如果当前路线的总距离小于之前最优解，就更新。
        if (ans < 0 || cur < ans) ans = cur;
    } while (next_permutation(id + 1, id + n + 1));	
    
    // 输出答案，这里因为是浮点数，所以我们设置精度为4。
    cout << setprecision(4) << ans << endl;
    return 0;
}