算法竞赛入门经典（第二版）Uva-11988 学习记录

算法竞赛入门经典（第二版）Uva-11988 学习记录"/>

算法竞赛入门经典（第二版）Uva-11988 学习记录

题目链接
Sample Input
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

Sample Output
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

一开始不用指针实现链表，但是写的时候发现这题用数组实现链表会很麻烦，写不来，于是重新用指针写链表，然而写出来后提交上去显示时间超限T-T…

链表实现的代码：

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
int flag;
typedef struct lt* Next;
struct lt
{char c;Next next;lt():next(NULL){}
};
Next head = NULL;void Free() {Next t = head->next, t2 = t->next;while (t != NULL) {t2 = t->next;free(t);t = t2;}free(head);
}int main()
{Next h2;string letter;while (cin >> letter) {flag = 0;head = new struct lt();h2 = head;for (int i = 0; i < letter.length(); i++) {if (letter[i] != '[' && letter[i] != ']') {if (flag) {Next h = new struct lt();h->c = letter[i];h2 = h;i += 1;while (letter[i] != ']') {Next tmp = new struct lt();tmp->c = letter[i];h2->next = tmp;h2 = tmp;i++;}h2->next = head->next;head->next = h;i -= 1;}else {Next n = new struct lt();n->c = letter[i];h2->next = n;h2 = n;}}else if (letter[i] == '[') {flag = 1;}else if (letter[i] == ']') {flag = 0;h2 = head->next;if (h2 == NULL) {h2 = head;}else {while (h2->next != NULL) {h2 = h2->next;}}}}h2 = head->next;while (h2 != NULL) {cout << h2->c;h2 = h2->next;}Free();putchar('\n');}return 0;
}

重新看一遍自己的代码，觉得可能是释放内存那占了时间，但是去掉Free()函数依然超时

书上的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100100;
int Next[maxn], cur, last;
char s[maxn];int main() {//freopen("D://in.txt", "r", stdin);while (scanf("%s", s + 1) == 1) { // 从数组的第一位开始读数据cur = last = 0;int len = strlen(s + 1);Next[0] = 0; // 链表初始化for (int i = 1; i <= len; i++) {if (s[i] == '[') {cur = 0; // 返回到表头}else if (s[i] == ']') {cur = last;}else {Next[i] = Next[cur]; // attentionNext[cur] = i;if (cur == last) {last = i;}cur = i;}}for (int i = Next[0]; i != 0; i = Next[i]) {cout << s[i];}putchar('\n');}
}

attention：看了好一会儿才明白这行代码什么意思，这行代码的意思是让链表的末尾元素始终指向next[0],如果没有检查文本的过程中没有碰到’ [ ',则链表末尾的元素一直指向next[0]（也就是 0 ），如果碰到’ [ ', 则 [xxx] ,xxx内的元素会一直指向next[0], 也就是真正的表头，比如题目的数据为 [Beiju]

后面的依此类推