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

一只书虫仔 · 2020-04-10 08:33:50 · 题解

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

人生很漫长，先不用 STL >_<

\text{Part\ 0} 目录

- $\text{Part\ 1.1}$ 指针简介 - $\text{Part\ 1.1.1}$ 指针的定义 - $\text{Part\ 1.1.2}$ 指针的调用和赋值 - $\text{Part\ 1.2}$ 指针练习 - $\text{Part\ 1.2.1}$ $\text{swap}$ 指针版
- $\text{Part\ 2.1}$ 链表简介 - $\text{Part\ 2.1.1}$ 链表与指针 - $\text{Part\ 2.1.2}$ 链表的前驱与后继 - $\text{Part\ 2.1.3}$ 链表的从头插入和从尾插入+例题（字符串版的链表） - $\text{Part\ 2.2}$ 链表练习 - $\text{Part\ 2.2.1}$ 本题算法+标程

\text{Part\ 1} 指针

\text{Part\ 1.1} 指针简介

指针的主要意义是地址，地址就是比如我们输入的语句

scanf("%d", &a);

中间有一个字符 & 地址调用符，它和指针也有关。

\text{Part\ 1.1.1} 指针的定义

定义一个指针的方法

int *p; //数据类型 *指针名称

我们知道一个指针都是指向一个变量的，刚开始这个指针不指向任何变量，那我们该怎么赋值和为这个指针开辟空间呢？

\text{Part\ 1.1.2} 指针的调用与赋值

让这个指针为 空指针
```
p = NULL;
```
让这个指针赋为 10
```
p = new int;
*p = 10;
```
清除这个指针
```
delete p;
```

调换成变量

int x;
scanf("%d", &x);
int *p;
*p = x;
//改变 *p 的时候 x 也会变
printf("x = %d\n*p = %d", x, *p); //看看是不是一样啊

指针版输入数组第一项

int a[10];
scanf("%d", a + 1);
printf("%d", *(a + 1));//注意 * 和 a + 1 之间要有括号！优先级问题

\text{Part\ 1.2} 指针练习

\text{Part\ 1.2.1} \text{swap} 指针版

主要就是注意主函数内的 \text{swap} 要加上 & 就好。

#include <bits/stdc++.h>

using namespace std;

void Swap (int *p, int *q) {
    int tmp = *p;
    *p = *q;
    *q = tmp;
}

int main () {
    int a, b;
    scanf("%d%d", &a, &b);
    Swap(&a, &b);
    printf("a = %d, b = %d", a, b);
    return 0;
}
//Swap 大写是因为我怕撞了 STL

指针有用于链表。

\text{Part\ 2} 链表

\text{Part\ 2.1} 链表简介

链表这玩意跟数组有异曲同工之妙，只不过他们俩有互相的优点和缺点。

p.s. 博客里的表格会很丑，所以上面这个是后台截图

下面我们正式介绍一下链表吧。链表就是一种很活性的数组，第一项可能在北京，第二项跑哈尔滨去了，第三项跑美国去了，第四项又回来了一点到了欧盟，这就是链表，所以他进行插入很方便，每次用指针就可以插入很多项，但是查询就要从头查询。

\text{Part\ 2.1.1} 链表与指针

首先贯穿链表的需要有这个链表的数值和这个链表的后继，所以要定义一个变量 \text{node} 。

struct node {
    char val[10086]; //数值 
    node *next; //后继 
} *p; //定义节点

然后我们要初始化

void ini () {
    p = new node;
    p->next = NULL;
} 
//我怀疑这个 ini 也撞了 STL ，不过没关系（

下面我们看看怎么用这个吧

\text{Part\ 2.1.2} 链表的前驱与后继

要想调用这个指针内的东西，需要用到 -> ，具体代码如下：

p->val = 5, p->next = NULL;
printf("%d", p->val);

下面看一下怎么插入临时节点

node *tmp = new node;
tmp->val = 10; //创建临时节点
tmp->next = p;
p = tmp; // 把临时节点插入到链表头部

\text{Part\ 2.1.3} 链表的从头插入和从尾插入+例题（字符串版的链表）

输入格式
```
BODY
EVERY
TO
LUCK
GOOD
NOI
```
输出格式
```
NOI GOOD LUCK TO EVERY BODY
```
标程
- 从前端插入


//我自己写的，瞎码的
#include <bits/stdc++.h>

using namespace std;

struct node {
    char val[10086]; //数值 
    node *next; //后继 
} *p; //定义节点 

void ini () {
    p = new node;
    p->next = NULL;
} 

void Headline () {
    node *tmp = new node;
    scanf("%s", tmp->val);
    tmp->next = p; 
    p = tmp;
}

int main () {
    ini();
    for (int i = 1; i <= 6; i++)
        Headline();
    printf("%s %s %s %s %s %s", p->val, p->next->val, p->next->next->val, p->next->next->next->val, p->next->next->next->next->val, p->next->next->next->next->next->val);
    return 0;
}

//按照老师思路写的
#include <bits/stdc++.h>

using namespace std;

struct node {
    char val[10086]; 
    node *next; 
} *head; 

int main () {
    head = NULL;
    while (1) {
        node *tmp = new node;
        scanf("%s", tmp->val);
        tmp->next = head;
        head = tmp;
        for (node *now = head; now != NULL; now = now->next)
            printf("%s ", now->val);
        puts("");
    }
    return 0;
}

从尾端插入

#include <bits/stdc++.h>

using namespace std;

struct node {
    char val[10086]; 
    node *next; 
} *head, *tail; 

int main () {
    head = tail = new node;
    head->next = NULL;
    while (1) {
        node *tmp = new node;
        scanf("%s", tmp->val);
        tmp->next = NULL;
        tail->next = tmp;
        tail = tmp;
        for (node *now = head->next; now != NULL; now = now->next)
            printf("%s ", now->val);
        puts("");
    }
    return 0;
}

\text{Part\ 2.2} 链表练习

本题算法：在 Node 的定义中加上头和尾，然后在字符串中有 [ 和 ] 的地方挪动头和尾的位置即可。

本题标程：

#include <bits/stdc++.h>

using namespace std;

struct node {
    char val;
    node *next;
} *head, *tail, *now;

void ini () {
    head = tail = now = new node;
    //head->next = tail->next = now->next = NULL;
    head->next = NULL;
} 

int main () {
    char s[100086];
    while (scanf("%s", s) != EOF) {
        ini();
        int str = strlen(s);
        for (int i = 0; i < str; i++) {
            if (s[i] == '[') now = head;
            else if (s[i] == ']') now = tail;
            else {
                node *tmp = new node;
                tmp->val = s[i], tmp->next = now->next;
                now->next = tmp;
                now = tmp;
                if (now->next == NULL)
                    tail = now;
            }
        }
        for (now = head->next; now != NULL; now = now->next)
            printf("%c", now->val);
        puts("");
    }
    return 0;
}