f(sixleaves) = sixleaves

重剑无锋 大巧不工

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  95 随笔 :: 0 文章 :: 7 评论 :: 0 Trackbacks
链表的思想很简单,要做到活用也不难。一般我是这样做得,从实际问题出发,先高度的概括符不符合链表的特点。能不能用链表简单解决。接着,就是编码。
链表编码要理清细节性思路,最好是简单的画下图,正如改题的链表,本质上是循环链表。last指向最后一个节点。其next指针一定指向头节点。我们把s[0]当做头节点。
 1 
 2 #include <cstdio>
 3 #include <cstring>
 4 const int maxn = 100000 + 5;
 5 int last, cur, next[maxn];
 6 char s[maxn];
 7 int main() {
 8     
 9     while ( scanf("%s", s + 1) == 1) {
10         
11         int n = strlen(s + 1);
12         last = cur = 0;
13         next[0] = 0; // 头结点初始化指向自身
14         
15         for (int i = 1; i <=n; i++) {
16             
17             char ch = s[i];
18             if ('[' == ch ) cur = 0;
19             else if (']' == ch) cur = last;
20             else {
21                 
22                 next[i] = next[cur];  // next[cur]为当前光标的前一个字符,而next[i]就是当前光标要输入的字符,接着,光标还要跳到下个字符。所以我们要把当前字符next指向光标输入的字符。也就是next[cur] = i;但要先保存其next指针给输入字符。其next指针其实就是真相头结点。
23                 next[cur] = i;
24                 if (cur == last) last = i;
25                 cur = i; // 指向下一个节点
26             }
27             
28         }
29         
30         for (int i = next[0];i != 0; i = next[i]) {
31             printf("%c", s[i]);
32         }
33         puts("");
34     }
35     
36     return 0;
37 }

2015/4/12上午12:10:12
posted on 2015-04-12 00:10 swp 阅读(619) 评论(0)  编辑 收藏 引用 所属分类: algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理