论坛 › 新手乐园 › 这是一个单链表的递归问题

jsaac 发表于 2020-8-10 22:01:13

这是一个单链表的递归问题

问：一个带头节点的单链表，要删除所有值为X的节点，并释放空间，X不唯一（用递归实现）

这是我的代码：

void Del_X(LinkList L,int x){
        LNode *p;
        if(L==NULL)
                return;
        if(L->data==x){
                p=L;
                L=L->next;
                free(p);
                Del_X(L,x);
        }
        else{
                Del_X(L->next,x);
        }
}

感觉直接free（p）会断链，实际测试也确实有问题，请问问题在哪呢？能怎么改进？{:10_254:}

xieglt 发表于 2020-8-10 22:01:14

还是传参数传错了，要传指向指针的指针。
void Del_X(LinkList * L,int x)
{
        LNode *p;
        if(*L==NULL)
                return;
        if((*L)->data==x)
        {
                p=*L;
                *L=(*L)->next;
                free(p);
                Del_X(L,x);
        }
        else
        {
                Del_X(&((*L)->next),x);
        }
}

sunrise085 发表于 2020-8-10 22:57:02

本帖最后由 sunrise085 于 2020-8-10 22:59 编辑

对于有头结点的链表，你需要考虑头结点；
此外删除一个节点的时候，需要把后面的节点连接到前面的节点上，然后才能删除中间的节点。
看下图，L不是头结点的时候也是一样的

void Del_X(LinkList L,int x){
    LNode *p;
    if(L->next==NULL)// 有头结点，所以需要判断的是下一个节点
            return;
      
    if(L->next->data==x){//头结点是没有数据的，需要判断的是下一个节点的data，然后删除的也是下一个节点
      p=L->next;
      L->next=L->next->next;//你之前的写法，删除一个节点，并没有把链表连接起来
      free(p);
      Del_X(L->next,x);
    }
    else{
      Del_X(L->next,x);
    }
}

Darth_EF 发表于 2020-8-10 23:26:37

楼上说得对

jsaac 发表于 2020-8-11 09:17:42

sunrise085 发表于 2020-8-10 22:57
对于有头结点的链表，你需要考虑头结点；
此外删除一个节点的时候，需要把后面的节点连接到前面的节点上， ...

运行了一下，好像会有问题，且无法输出

大神再试验一下{:10_254:}

我真的搞不懂啊{:10_250:}

jsaac 发表于 2020-8-11 09:21:19

sunrise085 发表于 2020-8-10 22:57
对于有头结点的链表，你需要考虑头结点；
此外删除一个节点的时候，需要把后面的节点连接到前面的节点上， ...

static void Print(LinkList L){
        while(L->next!=NULL){
                L=L->next;
                printf("%d\n",L->data);
        }
        return;
}
这是我的输出函数

xieglt 发表于 2020-8-11 09:27:17

另外，为什么要用递归呢？函数参数传递没搞懂哦。用普通循环结构你的写法就没问题

jsaac 发表于 2020-8-11 09:28:57

xieglt 发表于 2020-8-11 09:27
另外，为什么要用递归呢？函数参数传递没搞懂哦。用普通循环结构你的写法就没问题

我知道循环可以，这不是做题嘛

jsaac 发表于 2020-8-11 09:30:19

xieglt 发表于 2020-8-11 09:27
另外，为什么要用递归呢？函数参数传递没搞懂哦。用普通循环结构你的写法就没问题

指针的指针感觉有点不好懂

xieglt 发表于 2020-8-11 09:30:29

jsaac 发表于 2020-8-11 09:28
我知道循环可以，这不是做题嘛

参数传错了，要传递指针的指针！

jsaac 发表于 2020-8-11 09:33:20

xieglt 发表于 2020-8-11 09:30
参数传错了，要传递指针的指针！

实测可行

xieglt 发表于 2020-8-11 09:55:32

int main(void)
{
        //定义了一个链表头，这是一个指针变量，它的值指向一个地址
        //编译器会在栈里分配一段内存来存储* Head，假设这段内存起始地址为0x12345
        Lnode * Head = NULL;
       
        //初始化链表，假设Head的值 = 0X54321;
        //那么，0x54321就是它指向的地址
        //而0x12345则是这个指针变量的地址，也就是指针的指针
        Head =InitList();
       
        //调用删除节点函数
        //传递指针的值，函数将在栈里分配一段内存，假设这段内存的起始地址为0x12350
        //编译器将把0x54321复制到0x12350这段内存里并传到函数里去。
        //如果0x54321指向的Data == X ，那么free(0x54321)是没有问题的
        //问题出在L= L->next这一句，L的地址是0X12350，这一句相当于把L->next复制到0x12350；
    //而不是复制到Head的地址0X12345,所以Head的值并没有改变。
        Del_X(Head,X)

    //如果是传递指针的指针就不一样
        //同样函数将在栈里分配一段内存，假设这段内存的起始地址为0x12350
        //编译器则将把0x12345复制到0x12350这段内存里并传到函数里去。
        //*L=(*L)->next,就是把(*L)->next复制到0x12345里头,Head的值才得以改变
        Del_X(&Head,X)



        return 0;
}

很拗口，比较难理解，多学多练，慢慢总会理解的。

jsaac 发表于 2020-8-12 00:56:34

xieglt 发表于 2020-8-11 09:55
int main(void)
{
        //定义了一个链表头，这是一个指针变量，它的值指向一个地址


另外，我想知道直接free而并没有连接删除节点前后的两个链表，为什么不会断链呢

查看完整版本: 这是一个单链表的递归问题