【日常学习】【非指针链表】Uva11988 - Broken Keyboard (a.k.a. Beiju Text)题解-蒲公英云

【日常学习】【非指针链表】Uva11988 - Broken Keyboard (a.k.a. Beiju Text)题解

这道题目拖了好几天，因为鄙人有两大天敌——链表和树TUT看了这个题材知道原来链表可以不用指针写，不过原理也是一样的，相当于是用数组模拟了个链表而不实用结构体，结构体里的指针就换成了两个变量cur和last了。这道题目本来测出来非常奇怪和合因为UVA AC HDU TLE SPOJ RE我正在奇怪，才发现同名的不同题目有三道TUT

题目的详解已经写在了注释里，上代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000+5;
int last,cur,next[maxn];
char s[maxn];
int main(){
    while (scanf("%s",s+1)==1){
        int n=strlen(s+1);//输入从s[1]开始存储 
        last=cur=0;
        next[0]=0;//0位置的下一个数初始化为0 ，会改变 
        for (int i=1;i<=n;i++){//按照字符的编号排列顺序输出字符，顺序是排列好的编号序列，该序列储存在next中 
            char ch=s[i];
            if (ch=='[') cur=0;
            else if (ch==']') cur=last;
            else {
                next[i]=next[cur];//现在字符位置的下一个是当前光标的下一个【未插入之前当前光标下一个】 a|c 
                next[cur]=i;//当前光标的下一个是现在插入的字符位置，即此时光标还是在原来的前一个字符后面 a|bc 
                if (cur==last) last=i;//如果当前已是最后，最后编号更新 last指向最后一个 next[last]为空 先比较再移动cur 
                cur=i;//移动光标到当前插入字符后面 ab|c 
            }
        }
        for (int i=next[0];i!=0;i=next[i]) printf("%c",s[i]);//注意占位符，另外其实next数组应该初始化为0 
        printf("\n");
    }
    return 0;
}