UVA11988 破碎的键盘（悲剧文本）

​​点击阅读更多查看文章内容

UVA11988 破碎的键盘

紫皮书例题6-4
刚开始学链表想了好久这道题，做个简单的总结。
就用书上的代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 100000 + 5;

int last, cur, nextt[maxn]; //光标位于cur号字符的后面

char s[maxn];

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

        for (int i = 1; i <= n; ++i)
        {//这里是将i打印在cur的后面
            if (s[i] == '[') cur = 0;
            else if (s[i] == ']') cur = last;
            else
            {
                nextt[i] = nextt[cur];
                nextt[cur] = i;
                //前面两行，是将i插入cur后面，这里分了两步，首先把cur后面的字符放到i的后面，然后把i插入cur后面。后面附了一张图，看起来清楚一点。
                if (cur == last) last = i;//这里s[last]代表最后一个字符，如果cur等于last，代表插入的i在last的后面，所以最后一个字符更新为i。
                cur = i;  //移动光标，cur=i，代表i已经插入、
            }
        }
        for (int i = nextt[0]; i != 0; i = nextt[i])
            printf("%c", s[i]);
        printf("\n");
    }

    return 0;
}

插入字符e，首先把c放在e的后面，再把e放在b的后面。