Cancellazione primi elementi di una lista

di
mauronew
il
6 risposte
M
mauronew
Pochi posts
Iscritto da
feb, 2021
Messaggi:
27

Cancellazione primi elementi di una lista

Ciao a tutti/e,

devo svolgere il seguente esercizio e sono in difficoltà: 

Scrivere una funzione che riceve una testa di una lista di numeri interi e che 
cancella dalla lista tutti i primi elementi che contengono un valore pari

La funzione deve eventualmente modificare l'indirizzo iniziale della lista (testa). 

Ho questa struttura dati: 

typedef struct numero numero;

/* struttura della lista */
struct numero {
    int valore;
    struct numero *prossimo;
};

Ho scritto questa funzione ma non va:

int cancellaPrimiValoriPari (numero *testa) {
    numero *obsoleto = NULL;
    int numeroCancellati = 0;

    while (testa->valore % 2 == 0) {
        obsoleto = testa;
        testa = testa->prossimo;
        free (obsoleto);
        numeroCancellati++;
    }
    return numeroCancellati++;
}

Ho capito che devo usare, nella suddetta funzione, un doppio puntatore a numero ma non capisco come usarlo….

Nel main() invocherei la funzione così:

printf ("\nHo cancellato %d valori\n", cancellaPrimiValoriPari (&testa));

L'intestazione della funzione dovrebbe diventare questa:

int cancellaPrimiValoriPari (numero **testa)

Ma poi non so come usare il doppio puntatore, ho provato a fare dei tentativi ma non è il modo giusto, vorrei capire il funzionamento (e cmq non mi funziona lo stesso)

6 Risposte

  • euscar
    euscar
    Utente Attivo
    Iscritto da
    ago, 2022
    Messaggi:
    149

    Re: Cancellazione primi elementi di una lista

    Vedi se il materiale sulle liste concatenate al seguente link ti può dare una mano:

    https://aguzzoli.di.unimi.it/didattica/algo12/lucidi8.pdf

    Altrimenti ne riparliamo.

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Cancellazione primi elementi di una lista

    Ciao, per iniziare ti consiglio di implementare una funzione

    void elimina_nodo(nodo **ptr)

    che si limita ad eliminare un generico nodo dalla lista.

    Dopodiché sarà banale implementare cancellaPrimiValoriPari() sfruttando la precedente funzione.

  • M
    mauronew
    Pochi posts
    Iscritto da
    feb, 2021
    Messaggi:
    27

    Re: Cancellazione primi elementi di una lista

    Grazie delle risposte…a dire la verità l'esercizio che volevo fare doveva cancellare TUTTI gli elementi di valore pari di una lista (ho scritto i primi perché mi sembrava più facile e volevo capire).

    Ora, dopo averci “sbattuto la testa” per circa 3 ore, dovrei aver risolto il problema, questo è il codice che ho scritto, se qualcuno ha voglia di commentarlo o darmi qualche consiglio è ben accetto!

    /******************************************************************************

Scrivere una funzione che riceve una testa di una lista di numeri interi e che 
cancella dalla lista tutti gli elementi che contengono un valore che sia un 
numero pari.

            -------------    -------------    -------------    -------------
 testa ---> |  4  |     |--->|  2  |     |--->|  3  |     |--->|  2  |     |---> NULL 
            -------------    -------------    -------------    -------------

*******************************************************************************/

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

typedef struct numero numero;

/* struttura della lista */
struct numero {
    int valore;
    struct numero *prossimo;
};

int cancellaValoriPari (numero **testa) {
    numero *n = *testa;
    numero *nPrecedente = NULL;
    numero *obsoleto = NULL;
    int numeroCancellati = 0;

    while (n != NULL) {
        /* elemento pari */
        if (n->valore % 2 == 0) {
            /* 1° elemento della lista */
            if (n == *testa) {
                *testa = (*testa)->prossimo;
                free (n);
                n = *testa;
                //free (obsoleto);
            }
            /* elementi successivi al primo */
            else {
                if (n->prossimo != NULL) {
                    nPrecedente->prossimo = n->prossimo;
                    free (n);
                    n = nPrecedente->prossimo;
                }
                /* ultimo elemento della lista */
                else {
                    free (n);
                    nPrecedente->prossimo = NULL;
                    n = nPrecedente;
                }
            }
            numeroCancellati++;
        }
        /* elemento dispari */
        else {
            nPrecedente = n;
            n = n->prossimo;
        }
    }
    return numeroCancellati;
}

void visualizzaLista (numero *t) {
    numero *n = t;
    if (t == NULL)
        printf ("vuota!");
    else {
        while (n != NULL) {
            printf ("%d ", n->valore);
            n = n->prossimo;
        }
    }
}

int main() {
    numero *testa = NULL;
    numero *nuovo = NULL;
    
    /* creazione lista */
    /* 1° elemento (elemento di testa) */
    testa = (numero*) malloc (sizeof (numero));
    testa->valore = 4;
    testa->prossimo = NULL;
    /* 2° elemento */
    nuovo = (numero*) malloc (sizeof (numero));
    nuovo->valore = 2;
    nuovo->prossimo = NULL;
    testa->prossimo = nuovo;
    /* 3° elemento */
    nuovo = (numero*) malloc (sizeof (numero));
    nuovo->valore = 3;
    nuovo->prossimo = NULL;
    testa->prossimo->prossimo = nuovo;
    /* 4° elemento */
    nuovo = (numero*) malloc (sizeof (numero));
    nuovo->valore = 2;
    nuovo->prossimo = NULL;
    testa->prossimo->prossimo->prossimo = nuovo;
    
    /* output lista inziale */
    printf ("Lista iniziale: ");
    visualizzaLista (testa);
    printf ("\n");
    
    /* cancellazione dei numeri pari */
    printf ("Sono stati cancellati %d valori\n", cancellaValoriPari(&testa));
    
    /* output lista modificata (senza i numeri pari) */
    printf ("Lista modificata: ");
    visualizzaLista (testa);
    
    return 0;
}
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Cancellazione primi elementi di una lista

    Il seguente codice dovrebbe essere equivalente al tuo:

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

typedef struct nodo_
{
    int valore;
    struct nodo_ *next;
}   nodo;

void aggiungi_in_testa(nodo **p, int n)
{
    nodo *nuovo = (nodo*)malloc(sizeof(nodo));
    nuovo->valore = n;
    nuovo->next = *p;
    *p = nuovo;
}

void elimina_nodo(nodo **p)
{
    if(*p)
    {
        nodo *temp = *p;
        *p = (*p)->next;
        free(temp);
    }
}

void cancella_valori_pari(nodo **p)
{
    while(*p)
    {
        if(!((*p)->valore % 2))
        {
            elimina_nodo(p);
        }
        else
        {
            p = &(*p)->next;
        }
    }
}

void stampa_lista(nodo *p)
{
    while(p)
    {
        printf("%d ", p->valore);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    nodo *testa = NULL;
    aggiungi_in_testa(&testa, 2);
    aggiungi_in_testa(&testa, 3);
    aggiungi_in_testa(&testa, 2);
    aggiungi_in_testa(&testa, 4);
    stampa_lista(testa);
    cancella_valori_pari(&testa);
    stampa_lista(testa);
    return 0;
}

    Se vuoi, puoi trarne qualche spunto.

  • M
    mauronew
    Pochi posts
    Iscritto da
    feb, 2021
    Messaggi:
    27

    Re: Cancellazione primi elementi di una lista

    Grazie Nippolo, 

    ci sono alcune cose che vorrei chiarire, ad esempio queste 2 istruzioni nella funzione aggiungi_in_testa():

    nuovo->next = *p;
*p = nuovo;

    non capisco il funzionamento…

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Cancellazione primi elementi di una lista

    La funzione 

    aggiungi_in_testa(nodo **p, int n)

    si limita a creare un nuovo nodo (nuovo) che punterà a quello cui punta p 

    nuovo->next = *p;

    mentre p verrà fatto puntare a nuovo

    *p = nuovo;

    Spero di aver chiarito il tuo dubbio, in caso contrario spiegami di preciso cosa non hai capito.

Devi accedere o registrarti per scrivere nel forum
6 risposte