UVa 11998 破碎的键盘(数组实现链表)

题意:

输入一行字符,其中包含'[' 和 ‘]’, 意思为键盘上的home 和 end 键, 然后模拟字符在键盘上输入。 输入一行最终的结果

分析:

用数组模拟一个链表, 在链表的头尾插入字母然后输出即可, 方法需要多加练习才能练熟, 其实跟邻接表有点像。

为了方便起见,常常在链表的第一个元素之前放一个虚拟结点。

#include <bits/stdc++.h>
using namespace std;
const int maxl = + ;
int main()
{ char str[maxl];
int cur, last;
int next[maxl];//next[index] 就是str[index]的下一个字母是 str[next[index]]
//为了方便起见,常常在链表的第一个元素之前放一个虚拟结点。 所以从str+1开始
while(~scanf("%s", str+))
{
int len = strlen(str+);
next[] = ;//一开始next指向虚拟节点
cur = last = ;
for(int i = ; i <= len; i++){
if(str[i] == '['){
cur = ;
}
//光标位于cur后面 cur...|
else if(str[i] == ']'){
cur = last;
}
else{ next[i] = next[cur];
next[cur] = i;
/*注意这两句 当cur = 0, i = 1时,
next[1] = next[0] ------------ 把虚拟节点接到next[1]上
next[0] = 1 ------------ 把0的下一个接为1
这就实现了next0转移到了next1 next0 变为 1
*/
if(cur == last) last = i;
cur = i;
}
} for(int i = next[]; i != ; i = next[i]){
printf("%c", str[i]);
}
puts("");
}
}
上一篇:CSS绘制三角形—border法


下一篇:UVa 11988 Broken Keyboard(链表->数组实现)