Удалить элемент из двусвязного списка с помощью рекурсии - PullRequest
Новая
       68

Удалить элемент из двусвязного списка с помощью рекурсии

0 голосов
/ 06 мая 2020

Я хочу удалить элемент из двусвязного списка, но мне нужно использовать рекурсию. Я пишу функцию, но она не работает. Может кто подскажет, где я ошибся? 

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

1 Ответ

0 голосов
/ 06 мая 2020

есть несколько проблем

  • вы сохраняете данные в tmp даром
  • вы неправильно обновляете список
  • ваш рекурсивный вызов не дает правильный первый аргумент (должен быть deleteNode(&(*front)->next, data);, а на самом деле вы должны return это), обратите внимание, что это терминал, поэтому вы также можете использовать al oop
  • возврат отсутствует, если два теста ложны

Это может быть: 

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