链表的游标实现 - 一道算法题

链表的游标实现 - 一道算法题

输入包含多组数据。每组数据占一行，包含不超过100000个字母、下划线、字符“[”或

者“]”。其中字符“[”表示Home键，“]”表示End键。输入结束标志为文件结束符（EOF）。输
入文件不超过5MB。对于每组数据，输出一行，即屏幕上的悲剧文本。

//样例输入：
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University
//样例输出：
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

---

【分析】
最简单的想法便是用数组来保存这段文本，然后用一个变量pos保存“光标位置”。这
样，输入一个字符相当于在数组中插入一个字符（需要先把后面的字符全部右移，给新字符
腾出位置）。
很可惜，这样的代码会超时。为什么？因为每输入一个字符都可能会引起大量字符移
动。在极端情况下，例如，2500000个a和“[”交替出现，则一共需要0+1+2+…+2499999=6*10 12次字符移动。**

解决方案是采用链表（linked list）。每输入一个字符就把它存起来，设输入字符串是
s[1～n]，则可以用next[i]表示在当前显示屏中s[i]右边的字符编号（即在s中的下标）(1)。
提示6-3：在数组中频繁移动元素是很低效的，如有可能，可以使用链表。
为了方便起见，假设字符串s的最前面还有一个虚拟的s[0]，则next[0]就可以表示显示屏
最左边的字符。再用一个变量cur表示光标位置：即当前光标位于s[cur]的右边。cur=0说明
光标位于“虚拟字符”s[0]的右边，即显示屏的最左边。

对于这种游标的, 一般理解都是一步一步调试, 从而慢慢了解思路

源代码如下:

#include<stdio.h>
#include<string.h>
#include <stdlib.h>
const int maxn = 100000 + 5;
int last, cur, next[maxn]; //光标位于cur号字符的后面 
char s[maxn];
int main() 
{
while (scanf("%s", s + 1) == 1)
    {
int n = strlen(s + 1); //输入保存在s[1]，s[2]...中   
last = cur = 0;  
next[0] = 0;
for (int i = 1; i <= n; i++)
        {
            char ch = s[i];  
if (ch == '[')
                cur = 0;    
else if (ch == ']')
                cur = last;     
else
            {
next[i] = next[cur];
next[cur] = i;
if (cur == last) 
last = i; //更新"最后一个字符"编号
                cur = i; //移动光标  
            }   
        }    
for(int i = next[0]; i != 0; i = next[i])  
printf("%c", s[i]);   
printf("\n"); 
    }  

system("pause");
return 0; 
}