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

陈落轩

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

#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 s, q, tmp = first;
    
    int insert_flag = 1;
    char ch;

    while((ch = getchar()) != '\n'){
        tmp = (DblList)malloc (sizeof(DblNode));
        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 * (-1);
        }else if(ch == '='){
            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;
    p = first -> rLink;
    while(p != first){
        printf("%c", p -> data);
        p = p -> rLink;
    }
}

Mike_python小

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

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

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

first = (DblList) malloc(sizeof(DblNode));first->data = '\0';first->rLink = NULL;first->lLink = NULL;

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

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

if (tmp != NULL) {    // 执行操作}

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

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

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

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

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

陶远航

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

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

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

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

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

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

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

isdkz

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

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

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

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

下面是修改后的代码：

#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 s, q, tmp = first;

    int insert_flag = 1;
    char ch;

    while((ch = getchar()) != '\n'){
        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 * (-1);
        }else if(ch == '='){
            if (tmp != first) {
                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;
    p = first -> rLink;
    while(p != first){
        printf("%c", p -> data);
        p = p -> rLink;
    }

    // 释放内存
    p = first -> rLink;
    while(p != first){
        DblList t = p;
        p = p -> rLink;
        free(t);
    }
    free(first);

    return 0;
}

陈落轩

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

具体来说，在 ...

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

陈落轩

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

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

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