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

Question

Я хотел написать программу, которая удаляет все вхождения числа из простого связанного списка с помощью рекурсии, поэтому я попытался, но у меня возникла проблема: написанная мной программа стирает все вхождения в списке, но не удаляет тот, который существует в начале (вхождение, которое существует в первом узле), вот код в C:

typedef struct list {
    int data;
    struct list *next;
} list;

list *delete(int x, list *head) {
    if (head->next == NULL)
        return head;
    list *newnode = delete(x, head->next);
    if (newnode->data == x) {
        head->next = head->next->next;
        free(newnode);
    }
    return head;
}

I wi sh кто-то может помочь мне улучшить мой алгоритм, СПАСИБО ЗА ПРЕДЕЛА.

Answer 1

без него удаляется тот, который существует в начале (вхождение, существующее в первом узле),

это из-за этих строк:

   if(head->next == NULL)
       return head;

когда есть только один элемент, который вы возвращаете, не управляя тем, что он может содержать данные для удаления

Вам не нужно иметь рекурсивное определение удаления, и в худшем случае используйте нетерминальная рекурсия.

Можно также добавить рабочие функции для проверки выполнения:

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

typedef struct list {
  int data;
  struct list* next;
} list;

list* delete(int x, list* head)
{
  list ** p = &head;

  while (*p != NULL) {
    if ((*p)->data == x) {
      list * d = *p;

      *p = (*p)->next;
      free(d);
    }
    else
      p = &(*p)->next;
  }
  return head;
}

void print(list * l)
{
  if (l == NULL)
    puts("<empty>");
  else {
    do  {
      printf("%d ", l->data);
      l = l->next;
    } while (l != NULL);
    putchar('\n');
  }
}

list * make(int data, list * next)
{
  list * l = malloc(sizeof(list));

  l->data = data;
  l->next = next;
  return l;
}

int main(int argc, char ** argv)
{
  list * head = make(1, make(2, make(1, NULL)));

  print(head);
  head = delete(1, head);
  print(head);
  head = delete(2, head);
  print(head);

  return 0;
}

Компиляция и выполнение:

/tmp % gcc -Wall l.c
/tmp % ./a.out
1 2 1 
2 
<empty>
/tmp % 

Под valgrind :

/tmp % valgrind ./a.out                                                                    ==14732== Memcheck, a memory error detector
==14732== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==14732== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==14732== Command: ./a.out
==14732== 
1 2 1 
2 
<empty>
==14732== 
==14732== HEAP SUMMARY:
==14732==     in use at exit: 0 bytes in 0 blocks
==14732==   total heap usage: 3 allocs, 3 frees, 48 bytes allocated
==14732== 
==14732== All heap blocks were freed -- no leaks are possible
==14732== 
==14732== For counts of detected and suppressed errors, rerun with: -v
==14732== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
/tmp % 

Answer 2

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

• Вы разыменовываете head без предварительной проверки, является ли оно NULL. Функция не может обрабатывать пустые списки.
• Вы явно возвращаете узел head без проверки его значения, если список содержит один элемент.
• Вы проверяете только второй элемент списка после рекурсии на head->next. Следовательно, первый элемент никогда не проверяется.

Вот модифицированная версия, которая просто проверяет первый узел и рекурсивно проверяет остальную часть списка:

list *delete(int x, list *head) {
    if (head == NULL)
        return head;
    if (head->data == x) {
        list *node = head;
        head = head->next;
        free(node);
        return delete(x, head);
    }
    head->next = delete(x, head->next);
    return head;
}

Answer 3

Этот код:

    if(head->next == NULL)
        return head;

явно заставляет функцию возвращать любой 1-элементный список без изменений. Это создает проблему, которую вы описываете, так что не имеет смысла ее иметь.

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

Это может работать, не проверено:

list * delete(list *head, int value)
{
  if (head == NULL)
    return NULL;
  if (head->data == value)
  {
      list * tail = head->next;
      free(head);
      return delete(tail, value);
  }
  // List was not empty and did not start with the value,
  // so set the tail of the list to the tail without the value.
  head->next = delete(head->next, value);
  return head;
}