链式结构

这篇文章主要解决一个基本问题:使用两个数组来解决链式结构

有一串从左到右编号分别为 i 的小球,其中 i ≥ 1。(A, 1, 3) 代表将 1 号小球移动到 3 号小球的左边,(B, 1, 3) 则代表将 1 号小球移动到 3 号小球的右边。输入的数值为小球个数 n,指令条数 m。

具体代码及注释如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 该函数代表将编号分别为 x 和 y 的小球们相连
void link(int x, int y, vector<int> &left, vector<int> &right) {
    right[x] = y;
    left[y] = x;
}

int main(void) {
    int n, m;
    cin >> n >> m;

<pre><code>// 分别定义左、右连接数组,用于存储每个小球左边和右边的小球编号
vector<int> left(n+1);
vector<int> right(n+1);
for (int i = 1; i <= n; i++) {
    left[i] = i-1;
    right[i] = i + 1;
}
right[n] = 0;

char c;
int ball1, ball2;
while (m--) {
    cin >> c >> ball1 >> ball2;
    link(left[ball1], right[ball1], left, right);
    if (c == 'A') {
        link(left[ball2], ball1, left, right);
        link(ball1, ball2, left, right);
    }
    // B 操作其实与 A 操作是相对的
    else {
        link(ball1, right[ball2], left, right);
        link(ball2, ball1, left, right);
    }
}

int ind;
// 寻找最左边的小球
for (int i = 1; i <= n; i++)
    if (left[i] == 0) {
        ind = i;
        break;
    }
// 输出
while (right[ind] != 0) {
    cout << ind << ' ';
    ind = right[ind];
}
cout << ind << ' ' << endl;

return 0;
</code></pre>

}

个人认为这道题的关键有两点:

  • 理解 link 函数
  • 注意数组的下标

至于 link 函数怎么理解,emmmmm,大家意会一下。在写这个函数之前,我们要给其定义,即它要解决什么问题,这里解决的是“将编号分别为 x 和 y 的小球们相连”。带着这个定义再使用它时就很容易理解了,例如:代码第 30 行。



Leave a Reply

Your email address will not be published. Required fields are marked *