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

陈落轩

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

输入格式:

输入为不超过50000个字符，表示小明的按键序列。包含a-z的小写字母、空格以及字符[、]、{、}、-、=。其中字符“[”表示Home键，“]”表示End键，“{”表示←键，“}”表示→键，“-”表示Insert键，“=”表示Backspace键。

输出格式:

输出为在小明屏幕上最终显示的文本。最后一个字母后没有回车或换行

输入样例1：

1. jilin[i lofe{{-v-} ] universiti=y
   

复制代码

输出样例1：

1. i love jilin university
   

复制代码

输入样例2：

1. abcd[c-de
   

复制代码

输出样例2：

1. cdecd
   

复制代码

输入样例3：

1. [[]][][]happy=birthday
   

复制代码

输出样例3：

1. happbirthday
   

复制代码

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

我的错误代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <malloc.h>
   
4. 
   
5. typedef struct Node{
   
6.     char data;
   
7.     struct Node * rLink, * lLink;
   
8. } DblNode, *DblList;
   
9. 
   
10. int main(void) {
    
11.     // 初始化双向链表
    
12.     DblList first;
    
13.     first = (DblList) malloc (sizeof(DblNode));
    
14.     first -> rLink = first;
    
15.     first -> lLink = first;
    
16. 
    
17.     // 光标初始位置为双向链表末尾
    
18.     DblList tmp = first -> lLink;
    
19.     int insert_flag = 1; // 插入标志
    
20. 
    
21.     char ch;
    
22.     while((ch = getchar()) != '\n') {
    
23.         DblList s, q;
    
24.         if (ch == '[') { // 将光标移动到双向链表头
    
25.             tmp = first -> rLink;
    
26.         } else if (ch == ']') { // 将光标移动到双向链表末尾
    
27.             tmp = first -> lLink;
    
28.         } else if (ch == '{') { // 将光标向左移动一位
    
29.             if (tmp -> lLink)
    
30.                 tmp = tmp -> lLink;
    
31.         } else if (ch == '}') { // 将光标向右移动一位
    
32.             if (tmp -> rLink)
    
33.                 tmp = tmp -> rLink;
    
34.         } else if (ch == '-') { // 切换插入模式
    
35.             insert_flag = -insert_flag;
    
36.         } else if (ch == '=') { // 删除当前节点
    
37.             if (tmp != first && tmp != first -> lLink) {
    
38.                 DblList t = tmp;
    
39.                 tmp -> rLink -> lLink = tmp -> lLink;
    
40.                 tmp -> lLink -> rLink = tmp -> rLink;
    
41.                 tmp = tmp -> lLink;
    
42.                 free(t);
    
43.             }
    
44.         } else { // 插入新节点
    
45.             s = (DblList) malloc(sizeof(DblNode));
    
46.             s -> data = ch;
    
47.             q = tmp -> rLink;
    
48.             if (insert_flag < 0) {
    
49.                 s -> lLink = tmp -> lLink;
    
50.                 q -> lLink = s;
    
51.                 tmp -> lLink -> rLink = s;
    
52.                 s -> rLink = q;
    
53.             } else {
    
54.                 s -> lLink = tmp;
    
55.                 q -> lLink = s;
    
56.                 tmp -> rLink = s;
    
57.                 s -> rLink = q;
    
58.             }
    
59.             tmp = s;
    
60.         }
    
61.     }
    
62. 
    
63.     // 输出双向链表
    
64.     DblList p = first -> rLink;
    
65.     while(p != first) {
    
66.         printf("%c", p -> data);
    
67.         p = p -> rLink;
    
68.     }
    
69.     return 0;
    
70. }
    

复制代码

问题：

输入样例后，输出与答案不一致：

输入样例：

1. jilin[i lofe{{-v-} ] universiti=y
   

复制代码

输出的错误答案：

1. ji lvf eilin universitiy

复制代码

最佳答案

月排行榜 / 总排行榜

小甲鱼

2023-9-26 09:45:09

以下是修改后的代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <malloc.h>
   
4. 
   
5. typedef struct Node {
   
6.     char data;
   
7.     struct Node *rLink, *lLink;
   
8. } DblNode, *DblList;
   
9. 
   
10. int main(void) {
    
11.     // 初始化双链表
    
12.     DblList first;
    
13.     first = (DblList) malloc(sizeof(DblNode));
    
14.     first->rLink = first;
    
15.     first->lLink = first;
    
16. 
    
17.     // 光标初始位置在双链表尾部
    
18.     DblList tmp = first;
    
19.     int insert_flag = 1; // 插入标志
    
20. 
    
21.     char ch;
    
22.     while ((ch = getchar()) != '\n') {
    
23.         DblList s, q;
    
24.         if (ch == '[') { // 将光标移至双链表头部
    
25.             tmp = first;
    
26.         } else if (ch == ']') { // 将光标移至双链表尾部
    
27.             tmp = first->lLink;
    
28.         } else if (ch == '{') { // 光标向左移动一位
    
29.             if (tmp != first)
    
30.                 tmp = tmp->lLink;
    
31.         } else if (ch == '}') { // 光标向右移动一位
    
32.             if (tmp->rLink != first)
    
33.                 tmp = tmp->rLink;
    
34.         } else if (ch == '-') { // 切换插入模式
    
35.             insert_flag = -insert_flag;
    
36.         } else if (ch == '=') { // 删除当前节点
    
37.             if (tmp != first) {
    
38.                 DblList t = tmp->lLink;
    
39.                 t->rLink->lLink = t->lLink;
    
40.                 t->lLink->rLink = t->rLink;
    
41.                 if (tmp == t) tmp = t->rLink;
    
42.                 free(t);
    
43.             }
    
44.         } else { // 插入新节点
    
45.             s = (DblList) malloc(sizeof(DblNode));
    
46.             s->data = ch;
    
47.             s->lLink = tmp;
    
48.             s->rLink = tmp->rLink;
    
49.             tmp->rLink->lLink = s;
    
50.             tmp->rLink = s;
    
51.             if (insert_flag > 0) tmp = s;
    
52.         }
    
53.     }
    
54. 
    
55.     // 输出双链表
    
56.     DblList p = first->rLink;
    
57.     while (p != first) {
    
58.         printf("%c", p->data);
    
59.         p = p->rLink;
    
60.     }
    
61.     return 0;
    
62. }

复制代码

跳转到最佳答案楼层

小甲鱼

以下是修改后的代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <malloc.h>
   
4. 
   
5. typedef struct Node {
   
6.     char data;
   
7.     struct Node *rLink, *lLink;
   
8. } DblNode, *DblList;
   
9. 
   
10. int main(void) {
    
11.     // 初始化双链表
    
12.     DblList first;
    
13.     first = (DblList) malloc(sizeof(DblNode));
    
14.     first->rLink = first;
    
15.     first->lLink = first;
    
16. 
    
17.     // 光标初始位置在双链表尾部
    
18.     DblList tmp = first;
    
19.     int insert_flag = 1; // 插入标志
    
20. 
    
21.     char ch;
    
22.     while ((ch = getchar()) != '\n') {
    
23.         DblList s, q;
    
24.         if (ch == '[') { // 将光标移至双链表头部
    
25.             tmp = first;
    
26.         } else if (ch == ']') { // 将光标移至双链表尾部
    
27.             tmp = first->lLink;
    
28.         } else if (ch == '{') { // 光标向左移动一位
    
29.             if (tmp != first)
    
30.                 tmp = tmp->lLink;
    
31.         } else if (ch == '}') { // 光标向右移动一位
    
32.             if (tmp->rLink != first)
    
33.                 tmp = tmp->rLink;
    
34.         } else if (ch == '-') { // 切换插入模式
    
35.             insert_flag = -insert_flag;
    
36.         } else if (ch == '=') { // 删除当前节点
    
37.             if (tmp != first) {
    
38.                 DblList t = tmp->lLink;
    
39.                 t->rLink->lLink = t->lLink;
    
40.                 t->lLink->rLink = t->rLink;
    
41.                 if (tmp == t) tmp = t->rLink;
    
42.                 free(t);
    
43.             }
    
44.         } else { // 插入新节点
    
45.             s = (DblList) malloc(sizeof(DblNode));
    
46.             s->data = ch;
    
47.             s->lLink = tmp;
    
48.             s->rLink = tmp->rLink;
    
49.             tmp->rLink->lLink = s;
    
50.             tmp->rLink = s;
    
51.             if (insert_flag > 0) tmp = s;
    
52.         }
    
53.     }
    
54. 
    
55.     // 输出双链表
    
56.     DblList p = first->rLink;
    
57.     while (p != first) {
    
58.         printf("%c", p->data);
    
59.         p = p->rLink;
    
60.     }
    
61.     return 0;
    
62. }

复制代码

isdkz

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

1. } else if (ch == '-') { // 切换插入模式
   
2.     insert_flag = -insert_flag;
   
3. } else if (ch == '=') { // 删除当前节点
   
4.     if (tmp != first && tmp != first -> lLink) {
   
5.         DblList t = tmp;
   
6.         tmp -> rLink -> lLink = tmp -> lLink;
   
7.         tmp -> lLink -> rLink = tmp -> rLink;
   
8.         tmp = tmp -> lLink;
   
9.         free(t);
   
10.     }
    
11. } else { // 插入新节点
    
12.     s = (DblList) malloc(sizeof(DblNode));
    
13.     s -> data = ch;
    
14.     q = tmp -> rLink;
    
15.     if (insert_flag > 0) { // 修改此处
    
16.         s -> lLink = tmp;
    
17.         q -> lLink = s;
    
18.         tmp -> rLink = s;
    
19.         s -> rLink = q;
    
20.     } else {
    
21.         s -> lLink = tmp -> lLink;
    
22.         q -> lLink = s;
    
23.         tmp -> lLink -> rLink = s;
    
24.         s -> rLink = q;
    
25.     }
    
26.     tmp = s;
    
27. }
    

复制代码

陈落轩

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更新为新插入的节点。