题解 UVA11988 【破损的键盘 Broken Keyboard (a.k.a. Beiju Text)】

· · 题解

此题作为链表的基础题目，我们使用指针链表和模拟链表两种方式来解决。

链表本身不难理解，就是这样子滴

每个单位有两个数据：它本身的值和一个指向下面值的指针

具体看代码啦~~~

#include<bits/stdc++.h>

using namespace std;
struct node
{
    char data;
    //data代表原值
    node *next;
    //指向下一个值的指针
};
char s[100001];
//s是原始数组
int main()
{
    while(scanf("%s", s) != EOF)
    {
        node *head, *tail, *now;
        //head指向头部，tail指向尾部，now指向要往哪里插
        head = new node;
        tail = now = head;
        tail -> next = NULL;
        //为三个指针赋初值，分配空间
        int len = strlen(s);
        for (int i = 0; i < len; i++)
        {
            if(s[i] == '[')
                now = head;
            //home键
            else if(s[i] == ']')
                now = tail;
            //end键
            else
            {
                node *p;
                p = new node;
                p -> data = s[i];
                //把值放进去
                p -> next = now -> next;
                //让它的下一个指向now的下一个
                now -> next = p;
                //让now的下一个指向p
                if(now == tail)
                    tail = p;
                //更新tail指针
                now = p;
                //更新now指针
            }
        }
        while(head -> next != NULL)
        {
            head = head -> next;
            printf("%c", head -> data);
        }
        //输出
        printf("\n");
    }
    return 0;
}

数组版的基本原理就是先把所有的值先放到data里，再用一个nxt数组表示nxt[i]表示第i个后是哪个，就可以啦！！！

具体代码：

#include<bits/stdc++.h>

using namespace std;
char s[100001], data[100001];
int nxt[100001], last, head, now, size;
//s为输入数组，nxt和data意义如上所述
int main()
{
    while(scanf("%s", s) != EOF)
    {
        memset(nxt, -1, sizeof(nxt));
        int len = strlen(s);
        head = now = last = 0;
        size = 0;
        //head、now、tail意义跟上个代码一样
        for (int i = 0; i < len; i++)
        {
            if(s[i] == '[')
                now = head;
            else if(s[i] == ']')
                now = last;
            //跟上一个代码no difference
            else
            {
                data[++size] = s[i];
                //先放到data里
                nxt[size] = nxt[now];
                nxt[now] = size;        
                if(now == last)
                    last = size;        
                now = size;
                //然后就跟指针版差不多啦！！！
            }
        }
        for (int i = nxt[head]; i != -1; i = nxt[i])
            printf("%c", data[i]);
        printf("\n");
        //输出
    }
    return 0;
}