<学习笔记？> 链表

例题： codevs 4650 破损的键盘

手打版

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 int next[100010];
 9 char s[100010];
10 
11 int main()
12 {
13     while(scanf("%s",s)!=EOF)
14     {
15         memset(next,0,sizeof(next));
16         int l=strlen(s),first=100001,last=100001,k=first;
17         next[first]=-1;
18         for(int i=0;i<l;++i)
19         {
20             if(s[i]=='[')  k=first;
21             else if(s[i]==']')  k=last;
22             else {
23                      int p=next[k];
24                      next[k]=i;
25                      next[i]=p;
26                      k=i;
27                      if(p==-1) last=i;
28             }
29         }
30         for(int i=next[first];i!=-1;i=next[i])
31             printf("%c",s[i]);
32         printf("
");
33     }
34     return 0;
35 }

Stl 版

 1 #include<iostream>
 2 #include<list> // 双端链表 
 3 using namespace std;
 4 
 5 string a;
 6 list<char> b;
 7 list<char>::iterator f;
 8 
 9 int main()
10 {
11     while(cin>>a)
12     {
13 
14         int l=a.length();f=b.begin();
15         for(int i=0;i<l;++i)
16         {
17             if(a[i]=='[') f=b.begin(); //把f移到链表头部
18             else if(a[i]==']') f=b.end(); //把f移到链表尾部
19             else  b.insert(f,a[i]);  // f会随着插入而后移 
20         }
21         while(!b.empty()) 
22         {
23             cout<<b.front();
24             b.pop_front();
25         }
26         cout<<'
';
27     }
28     return 0;   
29 }
30 
31 //http://www.cplusplus.com/reference/list/list/insert/
32 //http://www.cplusplus.com/reference/list/list/push_back/