论坛 › 数据结构与算法 › PTA小明打字 答案错误

陈落轩 发表于 2023-9-26 09:45:08

PTA小明打字 答案错误

# 题目：
小明正使用Microsoft Word打一篇文档，文档只包含a-z的小写字母和空格，在打字过程中可能会一次或多次按下Home键、End键、←方向键、→方向键、Insert键、Backspace键。请编写程序，给定小明在键盘上按键的序列，输出小明屏幕上最终显示的文本。
提示：Home键会将当前光标移至文本开始位置，End键当前光标移至文本尾，←键和→键会使当前光标左移或右移一个位置（如果光标在文档头则无法左移，光标在文档尾则无法右移），Insert键会在插入和替换文本间切换（默认是插入状态），Backspace键会删除当前光标前的一个字符。

输入格式:输入为不超过50000个字符，表示小明的按键序列。包含a-z的小写字母、空格以及字符[、]、{、}、-、=。其中字符“[”表示Home键，“]”表示End键，“{”表示←键，“}”表示→键，“-”表示Insert键，“=”表示Backspace键。输出格式:输出为在小明屏幕上最终显示的文本。最后一个字母后没有回车或换行
输入样例1：jilin universiti=y
输出样例1：i love jilin university
输入样例2：abcd[c-de
输出样例2：cdecd
输入样例3：[[]][][]happy=birthday
输出样例3：happbirthday

本题我想采用双向链表进行处理，但是不知道是哪个地方出现了问题，输出答案错误，求大神救救{:10_266:}我的错误代码：#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 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;
}

isdkz 发表于 2023-9-26 09:45:17

问题出在插入模式的处理上，应该是判断 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;
}

陈落轩 发表于 2023-9-26 09:49:19

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

呜呜还是不行，输出的答案和原来一样{:10_266:}

小甲鱼 发表于 2023-10-10 07:40:12

代码中存在一些问题：

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

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

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

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

查看完整版本: PTA小明打字 答案错误