使用递归从双向链表中删除元素

Question

我想从双向链表中删除一个元素，但我需要使用递归。我写了函数，但它不起作用。谁能告诉我哪里做错了？

int deleteNode(struct dll_node **front, int data){
    if((*front) == NULL){
        return 0;
    }

    if(data == (*front)->data){
        int tmp = (*front)->data;
        (*front)->next = (*front)->prev;
        (*front)->prev = (*front)->next;
        free(*front);
        return tmp;
    }
    deleteNode((*front)->next, data);
}

Answer 1

有几个问题

你将 data 保存在 tmp 中没有任何意义
你没有正确更新列表
你的递归调用没有给出正确的第一个参数（必须是deleteNode(&(*front)->next, data);，事实上你必须return），注意它是终端所以你也可以使用循环
return 如果两个测试都为假则缺失

可以是：

int deleteNode(struct dll_node **front, int data){
  if((*front) == NULL){
    return 0;
  }

  if(data == (*front)->data){
    struct dll_node * d = *front;

    if (d->prev == NULL) {
      if ((*front = d->next) != NULL)
        (*front)->prev = NULL;
    }
    else if ((d->prev->next = d->next) != NULL)
      d->next->prev = d->prev;

    free(d);
    return data;
  }
  return deleteNode(&(*front)->next, data);
}

要检查的完整代码：

#include <stdio.h>
#include <stdlib.h>

struct dll_node {
  int data;
  struct dll_node * prev;
  struct dll_node * next;
};

int deleteNode(struct dll_node **front, int data){
  if((*front) == NULL){
    return 0;
  }

  if(data == (*front)->data){
    struct dll_node * d = *front;

    if (d->prev == NULL) {
      if ((*front = d->next) != NULL)
        (*front)->prev = NULL;
    }
    else if ((d->prev->next = d->next) != NULL)
      d->next->prev = d->prev;

    free(d);
    return data;
  }
  return deleteNode(&(*front)->next, data);
}

struct dll_node * mk(int d)
{
  struct dll_node * r = malloc(sizeof(struct dll_node));

  r->data = d;
  r->prev = NULL;
  r->next = NULL;

  return r;
}

void pr(struct dll_node * l)
{
  while (l != NULL) {
    printf("%d", l->data);
    if (l->prev)
      printf(" prev:%d\n", l->prev->data);
    else
      putchar('\n');
    l = l->next;
  }
}

int main()
{
  struct dll_node * head = mk(1);
  struct dll_node * a = mk(2);
  struct dll_node * b = mk(3);

  head->next = a;
  a->prev = head;

  b->prev = a;
  a->next = b;

  pr(head);

  puts("\ndel 3");
  deleteNode(&head, 3);
  pr(head);

  puts("\ndel 1");
  deleteNode(&head, 1);
  pr(head);

  puts("\ndel 2");
  deleteNode(&head, 2);
  pr(head);
}

编译与执行：

pi@raspberrypi:/tmp $ gcc -Wall l.c
pi@raspberrypi:/tmp $ ./a.out
1
2 prev:1
3 prev:2

del 3
1
2 prev:1

del 1
2

del 2
pi@raspberrypi:/tmp $ valgrind ./a.out
==8496== Memcheck, a memory error detector
==8496== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==8496== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==8496== Command: ./a.out
==8496== 
1
2 prev:1
3 prev:2

del 3
1
2 prev:1

del 1
2

del 2
==8496== 
==8496== HEAP SUMMARY:
==8496==     in use at exit: 0 bytes in 0 blocks
==8496==   total heap usage: 4 allocs, 4 frees, 1,060 bytes allocated
==8496== 
==8496== All heap blocks were freed -- no leaks are possible
==8496== 
==8496== For lists of detected and suppressed errors, rerun with: -s
==8496== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $

使用递归从双向链表中删除元素

Delete element from doubly linked list using recursive

c

recursion

data-structures

doubly-linked-list