用数组来表示链表

Posted on | In

前言

经历一段时间的找实习, 还是深深体会到算法的重要性, 感觉以前没去做做ACM很可惜, 不过也不想太多, 既有个人的原因也有大环境的原因, 最近在看刘汝佳的算法竞赛书, 看到用数组来比较链表和双向链表, 感觉还挺少见, 所以特此来写篇博客记录一下, 加深印象的同时希望也能记住用法.

题目

我和书上一样了, 先上题目, 为了不浪费时间, 我直接上图片了.
image.png

这题目如果是我第一次做的话, 我会直接使用链表也就是stl中的list来放置数据, 当然思路是没有问题的, 但是里面会涉及到很多的插入删除操作, 还是比较复杂的.不过在这里, 书的作者给出了一种新的方法, 用的也是链表, 但是用的是基于数组的链表.
思路是每输入一个字符就把它存起来, 设输入字符串是s[1~n], 则可以用next[i]表示在当前显示屏中s[i]右边的字符编号(即在s中的下标).
为了方便起见, 假设字符串s的最前面还有一个虚拟的s[0], 则next[0]就可以表示显示屏中最左边的字符. 再用一个变量cur表示光标位置, 即当前光标位于s[cur]的右边. cur=0说明光标位于”虚拟字符”s[0]的右边, 即显示屏的最左边.为了移动光标, 还需要用一个变量last表示显示屏的最后一个字符是s[last].

思路说起来简单, 但是理解起来倒是不算轻松, 让我们来看看这个算法的核心, next数组, 这里有三个变量, next, i, s, 其中i是索引, s[i]表示当前的字符, next[i]中是下一个字符的在s中的索引, 在这里来看, 很明显, 这是一个链表, next数组就担当了指针的作用. 接下来还有一个小难点, 因为我们是不断读入字符的, 所以next数组在不断放置索引, 也就是说当i = 10的时候, next[1-10]的内容实际上已经固定了, 这个时候如果我们需要移动光标的话, 也就是说遇到’[‘, 我们需要做的不是改变next[1-10]的内容, 而是改变next[0]的内容, 让它指向新的位置, 同时不断的读取新的字符, 如果读取完所有的字符或者遇到’]’, 还不能忘了将next的最后一位置为之前的头部, 比如是1, 因为之前没遇到’[‘之前是从1开始输出的.
为了方便大家理解, 我自己手画了一个结果图, 相信大家看了之后肯定会好理解很多:
image.png

可以看出来很明显next[0]储存的是开头的字符的索引, 在这里也就是11, 然后我们的打印就会从s[11]开始, 也就是打印’B’, 然后继续, 我们看到next[11]的值是12, 所以我们打印s[12], 也就是’e’, 后面我就不说了, 依次类推, 稍微值得注意的是中间的几个0我省略了没有画出来, 下面是代码, 在实现上面也有点技巧, 不那么容易理解.

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
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100000 + 5;
int last, cur, next1[1000005];
char s[maxn];
int main()
{
  while (scanf_s("%s", s + 1) == 1)
  {
    int n = strlen(s + 1);
    last = cur = 0;
    next1[0] = 0;
    for (int i = 0; i <= n; ++i)
    {
      char ch = s[i];
      if (ch == '[')cur = 0;
      else if (ch == ']') cur = last;
      else
      {
        next1[i] = next1[cur];
        next1[cur] = i;
        if (cur == last) last = i;
          cur = i;
      }
    }
    for (int i = next1[0]; i != 0; i = next1[i])
    {
      printf("%c", s[i]);
    }
    cout << endl;
  }
}

这里值得注意的是last是用来保存上一次未遇到’[‘之前输入的最后一个字符的位置, 如果还是不能理解的话, 我个人建议可以用gdb调试下, 每一步可以输出看看next数组的值, 这样就会理解.

这个例子虽然看起来简单, 但是要真正想到能够用这种方式来解决这个问题还是不简单的, 不过复杂的算法带来的效率提升也是很明显的, 不仅代码量很小, 算法复杂度也是O(n), 我们的付出也是得到了回报.

第二题

下面来看第二题, 用两个数组来表示双向链表,为了不浪费敲字的时间我直接上图片了:

image.png
image.png

有了前面的经验, 我们使用双向链表也只是举一反三的事情了, 我们用left[i]和right[i]分别表示编号为i的盒子左边和右边的盒子编号(如果是0, 就表示不存在), 然后我们使用下面的这个辅助函数来将两个节点相互连接;

void link(int L, int R)
{
right[L] = R; left[R] = L;
}

这个函数我们简单看来就是将编号为L的盒子的右边设为R盒子, 将编号为R的盒子的左边设为L盒子, 也就是将L盒子和R盒子放到了一起, L盒子在左边, R盒子在右边.

有了这个辅助函数之后, 我们可以先记录好操作之前X, Y两边的结点, 然后用link函数根据某种顺序将他们连起来. 不过值得注意的是操作4, 这个操作我们不容易通过link这个辅助函数来完成, 不过我们可以先不管这个操作, 我们用标记inv来表示我们是否需要执行操作4(如果inv = 1的时候我们再次执行操作4, inv将会变为0). 当然, 操作1-3也需要根据inv是否为1来进行相应的变化, 不过操作3实际上是不受影响的, 大家可以动手画一下来试试, 在翻转链表前后执行交换操作不影响最后结果 不过操作1, 2是会受到影响的, 如果inv是1, 那么操作1,2需要变成3-op就好了, 所以思路并不麻烦.

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
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
using namespace std;
const int maxn = 100000;
int right[maxn], left[maxn];
void link(int L, int R) {
  right[L] = R;
  left[R] = L;
}
int main() {
  int n, m, kase = 0;
  while (scanf("%d%d", &n, &m) == 2) {
    for (int i = 1; i <= n; ++i) {
      left[i] = i - 1;
      right[i] = (i + 1) % (n + 1);
    }
    right[0] = 1;
    left[0] = n; //上面主要是完成right和left数组的初始化
    int op, X, Y, inv = 0;

    while (m--) {
      scanf("%d", &op);
      if (op == 4)
        inv = !inv;
      else {
        scanf("%d%d", &X, &Y);
        if (op == 3 && right[Y] == X)
          swap(X, Y); //处理掉X,Y相邻的情况, 底下还有解释
        if (op != 3 && inv)
          op = 3 - op; //如果有操作4, 那么需要对操作1,2进行改变
        if (op == 1 && X == left[Y])
          continue; // X已经在Y旁边, 就没必要继续这个操作
        if (op == 2 && X == right[Y])
          continue;

        int LX = left[X], RX = right[X], LY = left[Y], RY = right[Y];
        if (op == 1) {
          link(LX, RX); //把X的左右盒子连接起来
          link(LY, X);  //把X和Y的左边连起来
          link(X, Y); //再把X和Y连起来, 大功告成, 底下的也都是如此
        } else if (op == 2) {
          link(LX, RX);
          link(Y, X);
          link(X, RY);
        } else if (op == 3) {
          if (right[X] == Y) //处理掉X,Y相邻的情况, 上面的swap调用也是这个目的
          {
            link(LX, Y);
            link(Y, X);
            link(X, RY);
          } else //交换X,Y, 前提是X,Y不相邻, 所以已经处理掉X,Y相邻的情况
          {
            link(LX, Y);
            link(Y, RX);
            link(LY, X);
            link(X, RY);
          }
        }
      }
    }
    int b = 0;
    long long ans = 0;
    for (int i = 0; i <= n; ++i) {
      b = right[b];
      if (i % 2 == 1)
        ans += b;
    }
    if (inv && n % 2 == 0)
      ans = (long long)n * (n + 1) / 2 - ans;
    printf("Case %d: %lld\n", ++kase, ans);
  }
  return 0;
}

解释都写在注释上了, 代码也不难理解, 所以这里我也不再过多解释.

总结

在这篇博客里面, 我们总结了用数组来表示链表的两种简单实现, 也打破了我们可能存在一些常规思路, 认为链表只能用指针来实现, 实际上并不是如此, 这些编程方面算法的知识很有趣但是也不容易理解, 需要我们继续努力!