1. 综述

1. 定义

数据结构

数据结构是计算机存储、组织数据的方式，包含逻辑结构与物理结构：

逻辑结构描述元素间的抽象关系，分为集合、线性、树形、图形结构
物理结构描述数据在内存中的实际分布，分为顺序存储与链式存储

算法

算法是解决特定问题的有限执行步骤，具备有穷性、确定性、可行性，并拥有输入与输出

2. 复杂度

程序运行需要计算时间和存储空间两种资源，算法对这两种资源的使用程度可以用来衡量该算法的优劣：

时间复杂度：程序运行需要的计算时间
空间复杂度：程序运行需要的存储空间

大 $\mathbf{O}$ 表示法用来表示算法在最坏情况下的渐进时空复杂度。它忽略了常数因子和低阶项，只关注最高阶部分，用于衡量随着输入数据 $n$ 的增长，算法消耗时空资源的增长趋势

3. 分类

基于逻辑结构分类：

集合结构

元素同属一个集合，元素彼此无顺序、层次或连通关系
线性结构

元素之间存在严格的一对一关系。每个元素（除首尾外）有且仅有一个直接前驱和一个直接后继
树形结构

元素之间存在一对多的层次关系。除根结点外，每个结点有且仅有一个直接前驱，可以有多个直接后继
图形结构

元素之间存在多对多的任意关系。任何结点都可以有多个前驱和多个后继

从物理结构看，只有两种原子存储方式：使用连续空间的顺序存储和使用指针的链式存储。其余所有的物理实现，都是这两种方式的组合。

2. 线性结构

1. 线性表

线性表可记为 $L = (a_1, a_2,…, a_n)$ ，其中 $n \geq 0$ ， $n = 0$ 时为空表

根据存储方式的不同，线性表可以分别通过数组和链表来实现

在 STL 中 std::vector 是使用动态数组实现的线性表，std::list 是使用双向链表实现的线性表。

约瑟夫问题是一个经典的使用线性表解决的问题。

Josephus Problem I

Consider a game where there are n children (numbered $1,2,…,n$ ) in a circle. During the game, every second child is removed from the circle, until there are no children left. In which order will the children be removed?

Input

The only input line has an integer n.

Constraints: $1 \leq n \leq 2·10^5$

Output

Print $n$ integers: the removal order.

Example

1 2	Input: 7 Output: 2 4 6 1 5 3 7

考虑一个游戏，有 $n$ 个孩子（编号为 $1, 2, \dots, n$ ）围成一个圈。游戏过程中，每隔一个孩子就将其从圈子中移出，直到不剩任何孩子为止。请问孩子们被移出的顺序是什么？

输入

唯一的输入行包含一个整数 $n$

数据范围： $1 \le n \le 2 \cdot 10^5$

输出

输出 $n$ 个整数：即孩子被移出的顺序

很容易想到，可以用一个线性表来模拟这个过程；因为孩子的总数是 $n$ ，所以显然我们需要移除 $n$ 次，每次移除时我们需要计算出隔一位孩子的位置。

#include <iostream>
#include <vector>
#include <numeric>

constexpr int step = 2;

int main() 
{
	int n{ 0 };
	std::cin >> n;

	std::vector<int> children(n);
	std::iota(children.begin(), children.end(), 1); // 直接填入 1 ~ n

	int pos = 0;
	for (int i = 0; i < n; ++i)
	{
		pos = (pos + step - 1) % children.size();
		std::cout << children[pos] << " ";
		children.erase(children.begin() + pos);
	}

	return 0;
}

这段代码虽然逻辑正确，但 std::vector 的 erase 是一个线性复杂度的操作，循环执行了 $n$ 次，所以时间复杂度是 $\mathbf{O(n^2)}$

使用 <numeric> 头文件中的 std::iota 可以用来直接填充递增序列

既然 erase 需要移动内存效率低下，那我们可以不执行真正的删除。如果我们将走完一圈视作一轮，那么每一轮剩下孩子的规模都将减半。模拟这个过程中记录当前轮次参与游戏的孩子和游戏后剩下的孩子，那么剩下的孩子将是下一轮参与游戏的孩子。不断重复此过程亦可得到正确的序列，而不必真正将数据从数组中移除。

#include <iostream>
#include <vector>
#include <numeric>

constexpr int step = 2;

int main() 
{
	int n{ 0 };
	std::cin >> n;

	std::vector<int> curRound(n);
	std::iota(curRound.begin(), curRound.end(), 1);

	std::vector<int> nextRound;
	nextRound.reserve(n / 2 + 1);

	bool isDelete = false; // 状态交替标志位
	while (!curRound.empty())
	{
		for (const int child : curRound)
		{
			if (isDelete)
			{
				std::cout << child << " ";
			}
			else
			{
				nextRound.emplace_back(child);
			}
			isDelete = !isDelete;
		}
		curRound = std::move(nextRound);
		nextRound.clear();
	}

	return 0;
}

每轮游戏数组的长度都减半，总计算量： $n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots \le 2n$ ，因此时间复杂度为 $\mathbf{O(n)}$

std::vector 的 reverse 和 resize 的区别在于前者只分配空间，不创建元素，只改变了 capacity，而未改变 size；而后者改变了元素个数 size

约瑟夫问题

$n$ 个人围成一圈，从第一个人开始报数，数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号

输入

两个整数 $n,m$ ， $1 \le m, n \le 100$

输出

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

example

1 2	input: 10 3 output: 3 6 9 2 7 1 8 5 10 4

这是完整版的经典约瑟夫问题，它不再是每隔一个人移除一次，而是每隔任意个移除一次。上一题的第二种方法将不再适用，它强依赖于“保留一个、删除一个”的严格交替性质。

但我们依然可以使用线性表来到达“模拟删除，而不真正删除”的优化效果。具体来说，可以使用数组模拟循环链表：

#include <iostream>
#include <vector>

int main()
{
	int n{ 0 }, k{ 0 };
	std::cin >> n >> k;

	std::vector<int> next(n + 1);
	for (int i = 1; i < n; ++i)
	{
		next[i] = i + 1;
	}
	next[n] = 1;

	int cur = 1, prev = n;
	while (cur != next[cur])
	{
		for (int step = 0; step < k - 1; ++step)
		{
			prev = cur;
			cur = next[cur];
		}
		std::cout << cur << " ";
		next[prev] = next[cur];
		cur = next[cur];
	}

	std::cout << cur;
	return 0;
}

想象 $n$ 个孩子围成一圈。代码里定义了一个数组 next，next[i] 的含义就是：“编号为 i 的孩子的下一个人是谁”。让每个孩子都指向他右手边的下一个人，而最后一个孩子 next[n] = 1 指回第一个人。在逻辑上构成了首尾相接的圆环。

for (int step = 0; step < k - 1; ++step) 
{
    prev = cur;
    cur = next[cur];
}

这个 for 循环就是报数的过程。我们要找到第 $k$ 个孩子，只需要让 cur 沿着环向前走 $k-1$ 步，同时 prev 紧跟其后。而 next[prev] = next[cur] 让被淘汰者的前一个人，直接指向他的后一个人，相当于淘汰者直接被删除了，再也没有任何人能链接到他。cur = next[cur] 让当前指针跳到下一个人，准备下一轮游戏。当圈子里只剩一个人时，他的下一个人就是他自己，即 cur == next[cur]，此时 while 循环终止。

该算法时间复杂度为 $\mathbf{O(n \cdot m)}$

经典约瑟夫问题又很多不同解法，问题本身也有不同的版本，将在后续的内容中谈到

Zwei

数据结构与算法