PTA 7-2 小明打字 链表使用求助

陈落轩

想用双向链表写，但是一直报段错误，不知道原因，求大神救救

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.     DblList first;
    
12.     first = (DblList) malloc (sizeof(DblNode));
    
13.     first -> rLink = first;
    
14.     first -> lLink = first;
    
15.     DblList s, q, tmp = first;
    
16.    
    
17.     int insert_flag = 1;
    
18.     char ch;
    
19. 
    
20.     while((ch = getchar()) != '\n'){
    
21.         tmp = (DblList)malloc (sizeof(DblNode));
    
22.         if(ch == '['){
    
23.             tmp = first -> rLink ;
    
24.         }else if(ch == ']'){
    
25.             tmp = first -> lLink;
    
26.         } else if (ch == '{') {
    
27.             if (tmp -> lLink)
    
28.                 tmp = tmp -> lLink;
    
29.         } else if (ch == '}') {
    
30.             if (tmp -> rLink)
    
31.                 tmp = tmp -> rLink;
    
32.         } else if (ch == '-') {
    
33.             insert_flag = insert_flag * (-1);
    
34.         }else if(ch == '='){
    
35.             DblList t = tmp;
    
36.             tmp -> rLink -> lLink = tmp -> lLink;
    
37.             tmp -> lLink -> rLink = tmp -> rLink;
    
38.             tmp = tmp -> lLink;
    
39.             free(t);
    
40.         }else{
    
41.             s = (DblList) malloc(sizeof(DblNode));
    
42.             s -> data = ch;
    
43.             q = tmp -> rLink;
    
44.             if(insert_flag < 0){
    
45.                 s -> lLink = tmp -> lLink;
    
46.                 q -> lLink = s;
    
47.                 tmp -> lLink -> rLink = s;
    
48.                 s -> rLink = q;
    
49.             }else{
    
50.                 s -> lLink = tmp;
    
51.                 q -> lLink = s;
    
52.                 tmp -> rLink = s;
    
53.                 s -> rLink = q;
    
54.             }
    
55.             tmp = s;
    
56.         }
    
57.     }
    
58. 
    
59.     // 输出
    
60.     DblList p;
    
61.     p = first -> rLink;
    
62.     while(p != first){
    
63.         printf("%c", p -> data);
    
64.         p = p -> rLink;
    
65.     }
    
66. }

复制代码

Mike_python小

段错误通常是由访问非法内存引起的。在你的代码中，可能出现段错误的原因有几个：

1. 在程序一开始，你分配了一个空间用于创建链表的头结点first，但是没有给头结点first赋初值，导致后续操作时可能出现未定义的行为。

解决方法：在分配内存后，初始化头结点的数据和指针为空。

2. first = (DblList) malloc(sizeof(DblNode));
3. first->data = '\0';
4. first->rLink = NULL;
5. first->lLink = NULL;

复制代码

2. 在插入节点时，你使用了tmp指针，但是没有确保tmp指针不为空。

解决方法：在每次使用tmp指针之前，进行判空处理。

2. if (tmp != NULL) {
3.     // 执行操作
4. }

复制代码

3. 在插入节点时，你没有检查插入位置的前驱节点和后继节点是否为空。

解决方法：在插入节点之前，检查前驱节点和后继节点是否为空。

2. if (q != NULL && tmp != NULL) {
3.     // 执行插入操作
4. }

复制代码

请根据以上建议修改你的代码，并在需要时添加其他必要的错误处理。希望能帮助到你解决问题！如果还有其他疑问，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！
回答可能有误，多多谅解！

陶远航

你的代码在插入节点时有一些问题，在某些情况下可能会导致段错误（Segmentation Fault）。

具体来说，在以下两种情况下，你分别将 tmp 指针指向了一个已经释放的内存地址：

1. 当输入字符为 [ 时，你将 tmp 指向了双向链表中第一个节点，这个节点是在初始化时分配的内存，而不是通过动态分配获得的，因此在后续的操作中不应该被释放。

2. 当输入字符为 = 时，你删除了当前节点，但是在释放当前节点之前，你先将 tmp 指向了它。在释放节点之后访问同一块内存是未定义行为，有可能导致程序崩溃。

下面是修改后的代码，修复了上述问题。同时，还添加了一些注释来帮助理解：

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. }
    

复制代码

希望这可以帮到你！
如果问题已经解决，请设置最佳答案

isdkz

这个代码中有几个问题导致了段错误：

1. 在输入字符时，每次都使用malloc动态分配内存，但是并没有及时释放，导致内存泄漏。

2. 在输入字符时，对于特定字符（如'['、']'、'{'、'}'、'-'等），直接将指针指向了特定位置，但是并没有判断这些位置是否存在，导致了访问了非法内存。

3. 在删除节点时，没有判断被删除的节点是否为第一个节点，如果是第一个节点，需要将first指向第二个节点。

下面是修改后的代码：

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.     DblList first;
    
12.     first = (DblList) malloc (sizeof(DblNode));
    
13.     first -> rLink = first;
    
14.     first -> lLink = first;
    
15.     DblList s, q, tmp = first;
    
16. 
    
17.     int insert_flag = 1;
    
18.     char ch;
    
19. 
    
20.     while((ch = getchar()) != '\n'){
    
21.         if(ch == '['){
    
22.             tmp = first -> rLink ;
    
23.         }else if(ch == ']'){
    
24.             tmp = first -> lLink;
    
25.         } else if (ch == '{') {
    
26.             if (tmp -> lLink)
    
27.                 tmp = tmp -> lLink;
    
28.         } else if (ch == '}') {
    
29.             if (tmp -> rLink)
    
30.                 tmp = tmp -> rLink;
    
31.         } else if (ch == '-') {
    
32.             insert_flag = insert_flag * (-1);
    
33.         }else if(ch == '='){
    
34.             if (tmp != first) {
    
35.                 DblList t = tmp;
    
36.                 tmp -> rLink -> lLink = tmp -> lLink;
    
37.                 tmp -> lLink -> rLink = tmp -> rLink;
    
38.                 tmp = tmp -> lLink;
    
39.                 free(t);
    
40.             }
    
41.         }else{
    
42.             s = (DblList) malloc(sizeof(DblNode));
    
43.             s -> data = ch;
    
44.             q = tmp -> rLink;
    
45.             if(insert_flag < 0){
    
46.                 s -> lLink = tmp -> lLink;
    
47.                 q -> lLink = s;
    
48.                 tmp -> lLink -> rLink = s;
    
49.                 s -> rLink = q;
    
50.             }else{
    
51.                 s -> lLink = tmp;
    
52.                 q -> lLink = s;
    
53.                 tmp -> rLink = s;
    
54.                 s -> rLink = q;
    
55.             }
    
56.             tmp = s;
    
57.         }
    
58.     }
    
59. 
    
60.     // 输出
    
61.     DblList p;
    
62.     p = first -> rLink;
    
63.     while(p != first){
    
64.         printf("%c", p -> data);
    
65.         p = p -> rLink;
    
66.     }
    
67. 
    
68.     // 释放内存
    
69.     p = first -> rLink;
    
70.     while(p != first){
    
71.         DblList t = p;
    
72.         p = p -> rLink;
    
73.         free(t);
    
74.     }
    
75.     free(first);
    
76. 
    
77.     return 0;
    
78. }
    

复制代码

陈落轩

陶远航 发表于 2023-9-24 19:19
你的代码在插入节点时有一些问题，在某些情况下可能会导致段错误（Segmentation Fault）。

具体来说，在 ...

大神好像还是不行....结果好像对不上

陈落轩

isdkz 发表于 2023-9-24 19:19
这个代码中有几个问题导致了段错误：

1. 在输入字符时，每次都使用malloc动态分配内存，但是并没有及时 ...

谢谢大神，但好像还是答案错误