UVa 11988 Broken Keyboard(链表->数组实现)

UVa 11988 Broken Keyboard(链表->数组实现)

 1 /*数组形式描述链表:链表不一定要用指针。
 2 题目链接:UVa 11988 Broken Keyboard
 3 题目大意:
 4     小明没有开屏幕输入一个字符串,电脑键盘出现了问题会不定时的录入 home end 两个键,
 5     我们知道如果录入home则将光标定位到字符首,如果录入end则是将光标定位到字符尾。现
 6     在让你输出这段坏了文本。  表示:home => '[' , end => ']'
 7 举例:
 8     input:    hello[_Tom_]!
 9     output:   _Tom_hello!
10 解题思路:
11     数组中频繁移动元素是很低效的,如有可能,可以使用链表。
12 
13 */
14 #include<bits/stdc++.h>
15 using namespace std;
16 const int maxn=100000+5;
17 int last,cur,next[maxn];
18 char s[maxn];
19 int main()
20 {
21     while(scanf("%s",s+1)==1) {
22         int n=strlen(s+1);
23         last=cur=0;
24         next[0] = 0;
25         for(int i=1; i<=n; i++) {
26             char ch=s[i];
27             if(ch=='[')cur=0;
28             else if(ch==']')cur=last;
29             else {
30                 next[i]=next[cur];
31                 next[cur]=i;
32                 if(cur==last)last=i;
33                 cur=i;
34             }
35         }
36         for(int i=next[0]; i!=0; i=next[i])
37             printf("%c",s[i]);
38         printf("
");
39     }
40     return 0;
41 }