数据结构

  2. 主页
  4. 文档
  6. 数据结构
  8. 线性表
  10. 静态链表

静态链表

使用指针实现的链表, 可以在内存中动态的申请/释放结点. 但是动态申请和释放这种灵活的操作比较花时间, 竞赛中常数比较大, 容易超时. 而且不太好调试.

静态链表, 则是静态的, 静态是指链表的结点提前分配好了, 使用中不能申请和释放结点的内存.

优点:

  1. 避免使用指针
  2. 避免动态申请, 提高效率
  3. 调试方便

竞赛中, 因为数据规模是有限的, 所以静态链表使用更多.

单链表的数组实现

指针实现:

struct Node {
 int data;
 Node *next;
};

next指针存放的是data结构体的地址(指针). 如果data 存放在数组里, 那么next就是存放data的数组下标.

所以数组模拟链表的话, 可以使用两个数组

int a[N], nxt[N];

分别存放 数据data 和下个数据的数组下标.

const int N=1e5+10;

int head, idx;
int a[N], nxt[N];

//在头节点后增加一个值为x的节点
void add_head(int x)
{
 idx++;
    a[idx] = x;
    nxt[idx] = head;
    head = idx;
}

//在k后插入节点x
void add(int k, int x)
{
 idx++
    a[idx] = x;
    nxt[idx] = nxt[k];
    nxt[k] = idx;
}

//将下标为k的后面的节点删除，因为指针域存储的是下一个节点
void del(int k)
{
    nxt[k] = nxt[nxt[k]];
}

例题 1 破损的键盘

UVA11988 破损的键盘 Broken Keyboard (a.k.a. Beiju Text)

题意翻译

你在输入文章的时候，键盘上的Home键和End键出了问题，会不定时的按下。你却不知道此问题，而是专心致志地打稿子，甚至显示器都没开。当你打开显示器之后，展现你面前的数一段悲剧文本。你的任务是在显示器打开前计算出这段悲剧的文本。给你一段按键的文本，其中'[‘表示Home键，’]’表示End键，输入结束标志是文件结束符（EOF）。

输入输出样例

  • 输入 #1复制
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University
  • 输出 #1复制
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_Univer

分析

用list加string还是比较好做的. 这里我们用静态数组做下.

next[i]表示下标是i的字符的下一个字符的小标. 为了方便, 将s[0]表示表头. 所以next[0]表示第一个字符.

变量cur表示光标的位置. 即当前光标位于s[cur]的右边. cur = 0 表示光标位于虚拟字符 s[0] 的右边.即屏幕的最左边.

我们还需要last变量, 表示显示屏的最后一个字符是s[last]

参考代码

#include <cstdio>
#include <cstring>

const int N = 100000+5;
int last, cur, next[N];
char s[N];

int main() {
  while(scanf("%s", s+1) == 1) {
        int n=strlen(s+1);
        last = cur = 0;
        next[0] = 0;

        for(int i = 1; i <= n; i++) {
            char ch = s[i];
            if(ch =='[') cur = 0;
            else if(ch==']') cur = last;
            else {
                next[i] = next[cur];
                next[cur] = i;
                if(cur == last) last = i;
                cur = i;
            }
        }

        for(int i = next[0]; i != 0; i = next[i])
         printf("%c", s[i]);
        printf("\n");
 }
 return 0;
}

双向链表

定义

struct Node{
    int lft, rgt, data;
} s[100001];

//或者拆开结构体成多个数组, 减少代码长度

int lft[N], rgt[N], w[N];

下面的代码都没考虑头和尾的特殊情况.

  • 链接 x 和 y
void link(int x, int y)
{
    rgt[x] = y;
    lft[y] = x;
}
  • 插入
//将下标为 y 的结点 插入到 x 的 左边
// x 始终为 head 时, 则是头插法 建立链表.
void inst(int x, int y) {
 int lx = lft[x];
    link(lx, y);
    link(y, x);
}
  • 删除
void del(int x) {
    int lx = lft[x], rx = rgt[x];
    link(lx, rx);
}

例题 2 移动盒子

UVA12657 移动盒子 Boxes in a Line

题意翻译

你有n个盒子在桌子上的一条线上从左到右编号为1……n。你的任务是模拟四种操作

  • 1 X Y 移动盒子编号X到盒子编号Y的左边（如果X已经在Y的左边了就忽略）
  • 2 X Y 移动盒子编号X到盒子编号Y的右边（如果X已经在Y的右边了就忽略）
  • 3 X Y 交换盒子编号X与盒子编号Y的位置
  • 4 将整条线反转

操作保证合法，X不等于Y

举一个例子，如果n=6，操作 1 1 4然后就变成了2 3 1 4 5 6；再操作 2 3 5就变成了 2 1 4 5 3 6；再操作 3 1 6 就变成 2 6 4 5 3 1；最后操作4，就变成了 1 3 5 4 6 2

输入

最多有10组数据，每个数据会包含两个整数n,m（1≤n,m<100,000）, 接下来是m行数据，表示操作。

输出

对于每组数据，输出他们奇数位置的编号的和。

输入输出样例

  • 输入 #1复制
6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4
  • 输出 #1
Case 1: 12
Case 2: 9
Case 3: 2500050000

分析

如果是数组的话, 10 组 100000 的规模下的移动 一定会超时.

既然是频繁的移动, 而且是左边, 右边的 那就用双向链表好了.

为了不考虑头尾的特殊情况, 使用双向循环链表和头结点.

翻转的话, 如果翻来翻去, 也是很浪费时间的. 但是这道题, 求奇数位置的和, 奇数和偶数位置的和就是总和.

如果数是奇数个的话, 反不反转, 奇数位置还是奇数位置. 偶数个数时, 反转之后, 位置奇数变偶数.

数组实现

#include<bits/stdc++.h>
using namespace std;

const int N = 100006;

int lft[N], rgt[N];
int n, m, rev, opt, x, y;
long long ans;

inline void link(int x, int y)
{
    rgt[x] = y;
    lft[y] = x;
}

void inst(int x, int y) {
 int lx = lft[x];
    link(lx, y);
    link(y, x);
}

void del(int x) {
    link(lft[x], rgt[x]);
}

int main() {
 int c = 1;
 while(scanf("%d %d", &n, &m) == 2) {
  ans = 0; rev = 0;
  for (int i = 1; i <= n; i++) {
   link(i-1, i);
  }
  lft[0] = n;
  rgt[n] = 0;

  for(int i = 1; i <= m; i++) {
   scanf("%d", &opt);
   if(opt == 4) {
    rev = !rev;
    continue;
   }
   scanf("%d %d", &x, &y);

   if(opt != 3 && rev)
    opt = 3 - opt;

   if(opt == 1 && lft[y] != x) {
    del(x); inst(y, x);
   } else if(opt == 2 && rgt[y] != x) {
    del(x); inst(rgt[y], x);
   } else if(opt == 3) {
    if(rgt[y] == x) swap(x, y);
    int ly = lft[y], ry = rgt[y];
    int lx = lft[x], rx = rgt[x];
    if(rgt[x] == y) {
     link(lx, y); link(y, x);
     link(x, ry);
    } else {
     link(lx, y); link(y, rx);
     link(ly, x); link(x, ry);
    }
   }
  }

  int pos = 0;
  for (int i = rgt[0]; i; i = rgt[i]) {
   pos++;
   if(pos & 1)
    ans += i;
  }

  if(rev && n % 2 == 0)
   ans = (long long) n * (n + 1) / 2 - ans;

   printf("Case %d: %lld\n", c++, ans);
 }

 return 0;
}

题单

  1. HDU – 1276 士兵队列训练问题
  2. P1160 队列安排
  3. UVA11988 破损的键盘 Broken Keyboard (a.k.a. Beiju Text)
  4. UVA12657 移动盒子 Boxes in a Line