静态链表——UVA11988(破损键盘)

傷城~ 2022-05-14 15:48 144阅读 0赞

转载：[https://blog.csdn.net/gyh\_420/article/details/70175276][https_blog.csdn.net_gyh_420_article_details_70175276]

开始刷数据结构相关的题了，在笔试和面试过程中如果要写出指针形式的链表时间上可能不够。该题很好地训练了怎么使用数组来模拟链表  
破损的键盘（又名：悲剧文本）（Broken Keyboard（a.k.a. Beiju Text）,  
UVa 11988）  
你有一个破损的键盘。键盘上的所有键都可以正常工作，但有时Home键或者End键会自  
动按下。你并不知道键盘存在这一问题，而是专心地打稿子，甚至连显示器都没打开。当你  
打开显示器之后，展现在你面前的是一段悲剧的文本。你的任务是在打开显示器之前计算出  
这段悲剧文本。  
输入包含多组数据。每组数据占一行，包含不超过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\*1012次字符移动。解决方案是采用链表（linked list）。每输入一个字符就把它存起来，设输入字符串是s\[1～n\]，则可以用next\[i\]表示在当前显示屏中s\[i\]右边的字符编号（即在s中的下标）。  
使用了一个next数组来进行位置索引，用cur和last变量来记录字符串删除起始点和终止点。最后输出由i=Next\[0\]开始，i==0时作为停止条件，i = Next\[i\]作为每次循环的刷新。

这里提供两幅图来理解这个算法，next数组里面存的值是指向了下一次next数组索引的序号以及这次我们在字符串数组s中索引到的值。第一幅是无’\[’ ‘\]’的情况  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_27_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_27_color_FFFFFF_t_70 1][]

#include<iostream>
    #include<cstring>
    using namespace std;
    
    const int maxn=30;
    
    int main()
    {
    	char s[maxn];
    	int i,len;
    	int cur,last,next[maxn];//cur表示要输入字符的上一个位置 
    	while(cin>>(s+1))
    	{
    		cur=last=0;next[0]=0;
    		            
    		len=strlen(s);
    		for(i=1;i<=len;i++)
    		{
    			if(s[i]=='[')
    				cur=0;
    			else if(s[i]==']')
    				cur=last;
    			else
    			{
    				next[i]=next[cur];
    				next[cur]=i;
    				if(cur==last)
    					last=i;
    				cur=i;
    			} 
    		}
    		
    		for(i=next[0];i!=0;i=next[i])
    			cout<<s[i];
    		cout<<endl;
    	}
    	return 0;
    }

[https_blog.csdn.net_gyh_420_article_details_70175276]: https://blog.csdn.net/gyh_420/article/details/70175276
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_27_color_FFFFFF_t_70]: /images/20220503/6e20824bffdd4beb8b64d9d0ac67113e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_27_color_FFFFFF_t_70 1]: /images/20220503/654f765e8088434fa1f52a2de11a89d3.png