# 题目:
小明正使用Microsoft Word打一篇文档,文档只包含a-z的小写字母和空格,在打字过程中可能会一次或多次按下Home键、End键、←方向键、→方向键、Insert键、Backspace键。请编写程序,给定小明在键盘上按键的序列,输出小明屏幕上最终显示的文本。
提示:Home键会将当前光标移至文本开始位置,End键当前光标移至文本尾,←键和→键会使当前光标左移或右移一个位置(如果光标在文档头则无法左移,光标在文档尾则无法右移),Insert键会在插入和替换文本间切换(默认是插入状态),Backspace键会删除当前光标前的一个字符。
输入格式:输入为不超过50000个字符,表示小明的按键序列。包含a-z的小写字母、空格以及字符[、]、{、}、-、=。其中字符“[”表示Home键,“]”表示End键,“{”表示←键,“}”表示→键,“-”表示Insert键,“=”表示Backspace键。 输出格式:输出为在小明屏幕上最终显示的文本。最后一个字母后没有回车或换行
输入样例1: - jilin[i lofe{{-v-} ] universiti=y
复制代码输出样例1: 输入样例2: 输出样例2: 输入样例3: 输出样例3:
本题我想采用双向链表进行处理,但是不知道是哪个地方出现了问题,输出答案错误,求大神救救 我的错误代码: - #include <stdio.h>
- #include <stdlib.h>
- #include <malloc.h>
- typedef struct Node{
- char data;
- struct Node * rLink, * lLink;
- } DblNode, *DblList;
- int main(void) {
- // 初始化双向链表
- DblList first;
- first = (DblList) malloc (sizeof(DblNode));
- first -> rLink = first;
- first -> lLink = first;
- // 光标初始位置为双向链表末尾
- DblList tmp = first -> lLink;
- int insert_flag = 1; // 插入标志
- char ch;
- while((ch = getchar()) != '\n') {
- DblList s, q;
- if (ch == '[') { // 将光标移动到双向链表头
- tmp = first -> rLink;
- } else if (ch == ']') { // 将光标移动到双向链表末尾
- tmp = first -> lLink;
- } else if (ch == '{') { // 将光标向左移动一位
- if (tmp -> lLink)
- tmp = tmp -> lLink;
- } else if (ch == '}') { // 将光标向右移动一位
- if (tmp -> rLink)
- tmp = tmp -> rLink;
- } else if (ch == '-') { // 切换插入模式
- insert_flag = -insert_flag;
- } else if (ch == '=') { // 删除当前节点
- if (tmp != first && tmp != first -> lLink) {
- DblList t = tmp;
- tmp -> rLink -> lLink = tmp -> lLink;
- tmp -> lLink -> rLink = tmp -> rLink;
- tmp = tmp -> lLink;
- free(t);
- }
- } else { // 插入新节点
- s = (DblList) malloc(sizeof(DblNode));
- s -> data = ch;
- q = tmp -> rLink;
- if (insert_flag < 0) {
- s -> lLink = tmp -> lLink;
- q -> lLink = s;
- tmp -> lLink -> rLink = s;
- s -> rLink = q;
- } else {
- s -> lLink = tmp;
- q -> lLink = s;
- tmp -> rLink = s;
- s -> rLink = q;
- }
- tmp = s;
- }
- }
- // 输出双向链表
- DblList p = first -> rLink;
- while(p != first) {
- printf("%c", p -> data);
- p = p -> rLink;
- }
- return 0;
- }
复制代码
问题: 输入样例后,输出与答案不一致: 输入样例: - jilin[i lofe{{-v-} ] universiti=y
复制代码输出的错误答案:
以下是修改后的代码:
- #include <stdio.h>
- #include <stdlib.h>
- #include <malloc.h>
- typedef struct Node {
- char data;
- struct Node *rLink, *lLink;
- } DblNode, *DblList;
- int main(void) {
- // 初始化双链表
- DblList first;
- first = (DblList) malloc(sizeof(DblNode));
- first->rLink = first;
- first->lLink = first;
- // 光标初始位置在双链表尾部
- DblList tmp = first;
- int insert_flag = 1; // 插入标志
- char ch;
- while ((ch = getchar()) != '\n') {
- DblList s, q;
- if (ch == '[') { // 将光标移至双链表头部
- tmp = first;
- } else if (ch == ']') { // 将光标移至双链表尾部
- tmp = first->lLink;
- } else if (ch == '{') { // 光标向左移动一位
- if (tmp != first)
- tmp = tmp->lLink;
- } else if (ch == '}') { // 光标向右移动一位
- if (tmp->rLink != first)
- tmp = tmp->rLink;
- } else if (ch == '-') { // 切换插入模式
- insert_flag = -insert_flag;
- } else if (ch == '=') { // 删除当前节点
- if (tmp != first) {
- DblList t = tmp->lLink;
- t->rLink->lLink = t->lLink;
- t->lLink->rLink = t->rLink;
- if (tmp == t) tmp = t->rLink;
- free(t);
- }
- } else { // 插入新节点
- s = (DblList) malloc(sizeof(DblNode));
- s->data = ch;
- s->lLink = tmp;
- s->rLink = tmp->rLink;
- tmp->rLink->lLink = s;
- tmp->rLink = s;
- if (insert_flag > 0) tmp = s;
- }
- }
- // 输出双链表
- DblList p = first->rLink;
- while (p != first) {
- printf("%c", p->data);
- p = p->rLink;
- }
- return 0;
- }
复制代码
|