首页 > 代码库 > UVa 11998 破碎的键盘(数组实现链表)
UVa 11998 破碎的键盘(数组实现链表)
题意:
输入一行字符,其中包含‘[‘ 和 ‘]’, 意思为键盘上的home 和 end 键, 然后模拟字符在键盘上输入。 输入一行最终的结果
分析:
用数组模拟一个链表, 在链表的头尾插入字母然后输出即可, 方法需要多加练习才能练熟, 其实跟邻接表有点像。
为了方便起见,常常在链表的第一个元素之前放一个虚拟结点。
#include <bits/stdc++.h> using namespace std; const int maxl = 100000 + 7; int main() { char str[maxl]; int cur, last; int next[maxl];//next[index] 就是str[index]的下一个字母是 str[next[index]] //为了方便起见,常常在链表的第一个元素之前放一个虚拟结点。 所以从str+1开始 while(~scanf("%s", str+1)) { int len = strlen(str+1); next[0] = 0;//一开始next指向虚拟节点 cur = last = 0; for(int i = 1 ; i <= len; i++){ if(str[i] == ‘[‘){ cur = 0; } //光标位于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[0]; i != 0; i = next[i]){ printf("%c", str[i]); } puts(""); } }
UVa 11998 破碎的键盘(数组实现链表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。