Удалить все узлы из списка, которые соответствуют условию, на которое влияет другой список

Question

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

Определить функцию, которая, учитывая два списка целых чисел L1 и L2 и целое число n> 0, удаляет из первого списка узлы, для которых сумма содержимого L1 и L2 в соответствующей позиции (относительно исходные позиции) кратно n. Если L2 заканчивается, рассмотрите только содержание L1 вместо суммы.

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

моя проблема в том, что я не могу понять, как правильно строить различные случаи (L1 должен быть всегда! = NULL, поэтому у меня есть: L1! = NULL && L2! = NULL или L1! = NULL && L2 == NULL ).

Может ли кто-нибудь объяснить мне, какую процедуру нужно выполнить, и где я ошибаюсь?

Это моя попытка:

    struct data
    {
       int d;
       struct data *next;
    };

    typedef struct data Nodo;
    typedef Nodo *LIST;


    void function(LIST *l1, LIST l2, int n)
    {
      LIST p, head_1, head_2;

        while((*l1 != NULL && l2 != NULL)&&((*l1)->d + l2->d) % n == 0)
        {
           p = *l1;
           *l1 = (*l1)->next;
           free(p);
        }

        while((*l1 != NULL) && ((*l1)->d + l2->d) % n == 0)
        {
            p = *l1;
            *l1 = (*l1)->next;
            free(p);    
        }

        if (*l1 != NULL)
        {
           head_1 = *l1;
           head_2 = l2;

           while(head_1->next != NULL)
           {
              if (((head_1->next->d + head_2->next->d) % n) == 0)
              {
                p = head_1->next;
                head_1->next = head_1->next->next;
                free(p);
              }
              else
              {
                head_1 = head_1->next;
                head_2 = head_2->next;
              }
           }
         }
      }

Пример:

L1: 4-> 4-> 11-> 3-> 4-> 8-> 7-> NULL

L2: 5-> 1-> 5-> 1-> 5

ВЫХОД (L1): 4-> 4-> 4-> 7-> NULL

Answer 1

У вас проблема логики с последовательными циклами:

while((*l1 != NULL && l2 != NULL)&&((*l1)->d + l2->d) % n == 0) {
  ...
}
while((*l1 != NULL) && ((*l1)->d + l2->d) % n == 0){
  ...
}

если сумма элементов не кратна n , вам нужно перейти к следующему элементу, но вы не выполните

Кроме того, чтобы скрыть указатель с typedef , как вы делаете с typedef Nodo *LIST;, это опасно и это хороший способ создать проблему, я рекомендую вам никогда этого не делать .

Вы можете сделать это:

void removeIf(Nodo ** l1, Nodo * l2, int n)
{
  while ((*l1 != NULL) && (l2 !=  NULL)) {
    if ((((*l1)->d + l2->d) % n) == 0) {
      /* cell must be removed */
      Nodo * rm = *l1;

      *l1 = (*l1)->next;
      free(rm);
    }
    else {
      /* cell not removed */
      l1 = &(*l1)->next;
    }

    l2 = l2->next;
  }

  // case where l2 is shorter than l1
  while (*l1 != NULL) {
    if (((*l1)->d % n) == 0) {
      /* cell must be removed */
      Nodo * rm = *l1;

      *l1 = (*l1)->next;
      free(rm);
    }
    else {
      /* cell not removed */
      l1 = &(*l1)->next;
    }
  }
}

---

Создание полной программы для

• L1: 4-> 4-> 11-> 3-> 4-> 8-> 7

• L2: 5-> 1-> 5-> 1-> 5

• N: 2

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

struct data {
  int d;
  struct data *next;
};

typedef struct data Nodo;

void removeIf(Nodo ** l1, Nodo * l2, int n)
{
  while ((*l1 != NULL) && (l2 !=  NULL)) {
    if ((((*l1)->d + l2->d) % n) == 0) {
      /* cell must be removed */
      Nodo * rm = *l1;

      *l1 = (*l1)->next;
      free(rm);
    }
    else {
      /* cell not removed */
      l1 = &(*l1)->next;
    }

    l2 = l2->next;
  }

  // case where l2 is shorter than l1
  while (*l1 != NULL) {
    if (((*l1)->d % n) == 0) {
      /* cell must be removed */
      Nodo * rm = *l1;

      *l1 = (*l1)->next;
      free(rm);
    }
    else {
      /* cell not removed */
      l1 = &(*l1)->next;
    }
  }
}

Nodo * make(int v, Nodo * n)
{
  Nodo * r = malloc(sizeof(Nodo));

  r->d = v;
  r->next = n;
  return r;
}

void del(Nodo ** pl)
{
  while (*pl != NULL) {
    Nodo * n = *pl;

    *pl = (*pl)->next;
    free(n);
  }
}

int main()
{
  Nodo * l1 = make(4, make(4, make(11, make(3, make(4, make(8, make(7, NULL)))))));
  Nodo * l2 = make(5, make(1, make(5, make(1, make(5, NULL)))));

  removeIf(&l1, l2, 2);

  /* show result */
  for (Nodo * l = l1; l != NULL; l = l->next)
    printf("%d ", l->d);
  putchar('\n');

  /* free resources */
  del(&l1);
  del(&l2);

  return 0;
}

Компиляция и исполнение:

pi@raspberrypi:/tmp $ gcc -pedantic -Wall -Wextra ll.c
pi@raspberrypi:/tmp $ ./a.out
4 4 4 7 
pi@raspberrypi:/tmp $ 

Исполнение под valgrind :

pi@raspberrypi:/tmp $ valgrind ./a.out
==3758== Memcheck, a memory error detector
==3758== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3758== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3758== Command: ./a.out
==3758== 
4 4 4 7 
==3758== 
==3758== HEAP SUMMARY:
==3758==     in use at exit: 0 bytes in 0 blocks
==3758==   total heap usage: 13 allocs, 13 frees, 1,120 bytes allocated
==3758== 
==3758== All heap blocks were freed -- no leaks are possible
==3758== 
==3758== For counts of detected and suppressed errors, rerun with: -v
==3758== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)
pi@raspberrypi:/tmp $