[已解决]链表递归删除结点后会自动连接？？

MzJy

#include "SingleLinkedList.h"
#define null NULL

void recursionDelete_3(LNode &l, int x){
    SNode *p;
    if(l==null)
        return ;
    if(l->data==x){
        p=l;
        l=l->next;
        free(p);
        recursionDelete_3(l,x);
    }
    else
        recursionDelete_3(l->next,x);

}

int main(){

    LNode l;
    initLNode(l);
    insertNode_rear(l,1);
    insertNode_rear(l,5);
    insertNode_rear(l,4);
    showLNode(l);
    //recursionDelete(&l,5);
    recursionDelete_2(l,5);
    //recursionDelete_3(l,5);
    showLNode(l);
}


下面是相关头文件
#include <stdio.h>
#include <stdlib.h>

typedef struct SNode {
    int data;
    struct SNode *next;
} SNode, *LNode;

void initLNode(LNode &l) {
    l = NULL;
}

SNode *searchPriorNode(LNode l, int i) {
    if (l == NULL)
        return NULL;
    int index = 1;
    while (l != NULL && index < i) {
        l = l->next;
    }
    return l;
}

void insertNode_rear(LNode &l, int x) {
    SNode *node = (SNode *) malloc(sizeof(SNode));
    node->data = x;
    node->next = NULL;
    if (l == NULL) {
        l = node;
    } else {
        SNode *t = l;
        while (t->next != NULL) {
            t = t->next;
        }
        t->next = node;
    }
}

void showNode(SNode *node) {
    if (node == NULL)
        return;
    printf("value: %-3d      nextAddress :%p\n", node->data, node->next);
}

void showLNode(LNode l) {
    if (l == NULL)
        return;
    while (l != NULL) {
        showNode(l);
        l = l->next;
    }
    printf("\n");
}
为什么在运行结束后，free了数据域为5那个结点，链表中的结点没有断，好像自动连接上了？？？

最佳答案

月排行榜 / 总排行榜

isdkz

2023-5-10 22:53:39

这是因为在递归删除结点时，当要删除的结点不是链表头结点时，递归函数会一直执行到找到要删除的结点，然后将该结点删除，并将该结点前一个结点的next指针指向该结点的下一个结点，从而达到删除该结点的效果。

而在递归函数返回上一层时，由于该结点已经被删除，所以上一层递归函数中的该结点的next指针指向的是该结点的下一个结点，因此链表仍然是连续的。

这也是链表的一个特点，即删除结点时只需要改变前一个结点的next指针即可。

跳转到最佳答案楼层

isdkz

这是因为在递归删除结点时，当要删除的结点不是链表头结点时，递归函数会一直执行到找到要删除的结点，然后将该结点删除，并将该结点前一个结点的next指针指向该结点的下一个结点，从而达到删除该结点的效果。

而在递归函数返回上一层时，由于该结点已经被删除，所以上一层递归函数中的该结点的next指针指向的是该结点的下一个结点，因此链表仍然是连续的。

这也是链表的一个特点，即删除结点时只需要改变前一个结点的next指针即可。

sfqxx

这是因为在递归删除函数 `recursionDelete_3` 中，当要删除的结点 `l` 的数据域等于目标值 `x` 时，会执行如下代码：

1. 
   
2. p=l;
   
3. l=l->next;
   
4. free(p);
   
5. recursionDelete_3(l,x);

复制代码

其中 `p` 指向要删除的结点，将 `l` 指向要删除结点的下一个结点；然后使用 `free` 函数释放 `p` 所指向的内存空间。由于链表是动态分配的，即结点都是通过 `malloc` 函数进行申请并分配内存的，在释放结点所占用的空间之后，该内存空间并不是马上被系统回收和重复利用，而只是被标记成 “可用” 状态，等待下一次动态内存分配调用；因此虽然数据域为5的那个结点已经被销毁，它占用的地址可能会被下一次内存分配使用（如另一个新结点的地址），从而维持整条链表的链接状态，并且可以看到链表中并没有存在数据值为5的结点。这种现象可能出现，但实际上它带来的问题通常是不可控和不安全的，我们应该统一遵循“显式销毁”的原则，即在程序结束前释放所有资源，以防止可能发生的内存泄漏和段错误等问题。
有用请设置最佳答案

MzJy

其实就是递归的时候，L是采用引用的方式，此时的L其实是前一次L的next，所以L=L->next本意是L->next=L->next->next。所以链表在此时就已经连上了