[C] Fare free in struttura/lista collegata tramite puntatori

[Rotang14]

Salve a tutti, mi servirebbe una mano con una struttura legata da puntatori (anche se per come ce le hanno spiegate all'Università le chiamo liste).
La struttura è la seguente

struct elemento{    int value;
    struct elemento *next;
};

Dopo aver definito tutte le value ecc. ecc. devo confrontare ogni singola value con un valore e cancellare tutte quelle che, dopo un incremento di 1, superano tale valore facendone il free della memoria e restituire il numero di elementi cancellati nel processo.
Nel prototipo della funzione avevo pensato una cosa del genere

int increase_delete ( struct elemento **lista, int N, int soglia );

(dove N è il numero di elementi contenuti nella lista)
Per poi farla in questo modo

int increase_delete( struct elemento **lista, int N, int soglia){
    int count;

    while ( *lista != NULL && ++(*lista)->value <= soglia){
        *lista = (*lista)->next;
        count++;
    }

//MANCA LA PARTE IN CUI LIBERO LA MEMORIA


    return (N-count);
}

Ritornando N-count come numero di elementi cancellati. Come posso fare a liberare tutti gli elementi oltre tale soglia?

[Scara95]

Guarda che effettivamente si chiama lista.

Comunque N non serve come parametro. Per la cancellazione di un elemento:

• Il primo elemento è un caso speciale
• Dopo ti basta fare

  struct elemento *tmp;
  if(check(lista->next->value)) {
    tmp = lista->next;
    lista->next = list->next->next;
    free(tmp);
  }

Ovviamente questo è solo pseudocodice, il resto fallo tu...

[Rotang14]

Guarda che effettivamente si chiama lista.

Comunque N non serve come parametro. Per la cancellazione di un elemento:

• Il primo elemento è un caso speciale
• Dopo ti basta fare

  struct elemento *tmp;
  if(check(lista->next->value)) {
    tmp = lista->next;
    lista->next = list->next->next;
    free(tmp);
  }

Ovviamente questo è solo pseudocodice, il resto fallo tu...

Ok, il procedimento l'ho capito, mi resta oscuro solo quel "check" dello pseudocodice, cosa intendi con ciò?

[Scara95]

Un controllo, nel tuo caso se value supera la soglia.
Ho scritto check perché quel codice è generico, puoi sostituirlo con quello che vuoi

[Rotang14]

Un controllo, nel tuo caso se value supera la soglia.
Ho scritto check perché quel codice è generico, puoi sostituirlo con quello che vuoi

Ok grazie, un ultimo chiarimento, se possibile.
Dal momento che in ingresso ho dato un doppio puntatore alla struttura, dato che la devo modificare (avendola inizializzata nel main) a tmp devo assegnare lista->next in questo modo

tmp = (*lista)->next

mentre per assegnare a lista->next la lista->next->next dovrei fare

(*lista)->next = ((*lista)->next)->next

?
Perchè mi sono sempre intrecciato su queste cose...

[Scara95]

Sì, comunque dato che dopo aver gestito il primo elemento a parte non hai più bisogno di accedere al main potresti anche fare una cosa del genere per comodità

//gestione primo elemento
struct elemento *l = *lista;
//gestione altri elementi usando l
struct elemento *tmp;
if(check(l->next->value)) {
  tmp = l->next;
  l->next = l->next->next;
  free(tmp);
}

Così semplifichi di molto il codice
Ah, ovviamente qui manca il ciclo esterno...

[Rotang14]

Risolto. Posto se a qualcuno dovesse servire qualcosa di simile.

int increase_delete( struct elemento **lista, int N, int thres){    int count=0;


    if( *lista == NULL)
        return 0;


    if( ++(*lista)->value > thres ){
        while ( (*lista)->next != NULL ){
            struct elemento *copied = *lista;
            while ( copied->next->next != NULL ){
                copied = copied->next;
            }
            free ( copied->next );
            copied->next=NULL; //per sicurezza
        }
        free (*lista);
        *lista = NULL;
        return N-1;
    }


    while ( (*lista)->next != NULL && ++(*lista)->next->value <= thres){
        //++(*lista)->value;
        *lista = (*lista)->next;
        count++;
    }


    while ( (*lista)->next != NULL ){
        struct elemento *copied = *lista;
        while ( copied->next->next != NULL ){
            copied = copied->next;
        }
        free ( copied->next );
        copied->next=NULL; //per sicurezza
    }


    return (N-count-1);
}

Ci ho messo tutto sto tempo per risolvere questa dannata funzione.

[Rotang14]

Ok, allora, il problema è cambiato. Mi è stato detto che questa funzione ha un costo decisamente alto, effettivamente ci sono while ovunque, ma era l'unico modo in cui ero riuscito a risolvere.

Mi è stato detto di eliminare gli elementi oltre la soglia usando un unico ciclo

    while ( (*lista)->next != NULL ){        struct elemento *tmp;
        tmp=*lista;
        *lista=(*lista)->next;
        free(tmp);
    }

Ora, l'unico problema è che ciò non fa puntare a NULL il campo lista->next dell'ultimo elemento valido (l'ultimo elemento prima di quelli che verranno eliminati), ma dopo il ciclo punta ad un'area di memoria a cui è stato fatto free.

Come potrei fare?

[Scara95]

int increase_delete(struct elemento **l, int soglia) { 
  int count = 0;
  struct elemento *tmp;
  while((*l)!=NULL) {
    if(++((*l)->value) > soglia) {
      tmp = (*l);
      (*l) = (*l)->next;
      free(tmp);
      ++count;
      continue;
    } else {
      break;
    }
  }
  if((*l) == NULL) {
      return count;
  }
  struct elemento *ls = *l;
  while(ls->next != NULL) {
    if(++(ls->next->value)>soglia) {
      tmp = ls->next;
      ls->next = ls->next->next;
      free(tmp);
      ++count;
    }
  }
  return count;
}

[Rotang14]

int increase_delete(struct elemento **l, int soglia) { 
  int count = 0;
  struct elemento *tmp;
  while((*l)!=NULL) {
    if(++((*l)->value) > soglia) {
      tmp = (*l);
      (*l) = (*l)->next;
      free(tmp);
      ++count;
      continue;
    } else {
      break;
    }
  }
  if((*l) == NULL) {
      return count;
  }
  struct elemento *ls = *l;
  while(ls->next != NULL) {
    if(++(ls->next->value)>soglia) {
      tmp = ls->next;
      ls->next = ls->next->next;
      free(tmp);
      ++count;
    }
  }
  return count;
}

Grazie mille, mi stavo scervellando per niente.