[已解决]PTA小明打字 答案错误

陈落轩

# 题目：
小明正使用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：

i love jilin university

输入样例2：

abcd[c-de

输出样例2：

cdecd

输入样例3：

[[]][][]happy=birthday

输出样例3：

happbirthday

本题我想采用双向链表进行处理，但是不知道是哪个地方出现了问题，输出答案错误，求大神救救

我的错误代码：

#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

输出的错误答案：

ji lvf eilin universitiy

最佳答案

月排行榜 / 总排行榜

小甲鱼

2023-9-26 09:45:09

以下是修改后的代码：

#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;
}

跳转到最佳答案楼层

小甲鱼

以下是修改后的代码：

#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;
}

isdkz

问题出在插入模式的处理上，应该是判断 insert_flag 是否大于 0，而不是小于 0。修改代码如下：

} 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;
        q -> lLink = s;
        tmp -> rLink = s;
        s -> rLink = q;
    } else {
        s -> lLink = tmp -> lLink;
        q -> lLink = s;
        tmp -> lLink -> rLink = s;
        s -> rLink = q;
    }
    tmp = s;
}

陈落轩

isdkz 发表于 2023-9-26 09:45
问题出在插入模式的处理上，应该是判断 insert_flag 是否大于 0，而不是小于 0。修改代码如下：

呜呜还是不行，输出的答案和原来一样

小甲鱼

代码中存在一些问题：

在处理'['和']'按键的逻辑中，你应该把tmp设置为first，而不是first -> rLink或first -> lLink，因为first表示了文本的开始或结束位置。tmp将会在插入新节点时向右移动。

在处理'{'和'}'按键的逻辑中，向左移动一位应该是tmp = tmp -> lLink，向右移动一位应该是tmp = tmp -> rLink，并且应该确保tmp不是first，以防止移出文本范围。

在处理'='按键的逻辑中，你需要删除tmp -> lLink，也就是光标前的节点，而不是tmp。并且，你需要确保你不会删除first。

在处理插入新节点的逻辑中，无论是插入模式还是替换模式，新的字符都应该插入tmp和tmp -> rLink之间，然后将tmp更新为新插入的节点。