Cancellare elementi da una lista

Freebulls

il 08 giu 2020, 18:06

6 risposte

Freebulls

Pochi posts

Iscritto da: giu, 2017

Messaggi:: 3

Cancellare elementi da una lista

08 giu 2020, 18:12

Salve a tutti, sto svolgendo il seguente esercizio: si scriva una funzione che cancelli tutte le occorrenze di un dato elemento da una lista.
Questo è il mio svolgimento

#include <stdio.h>

struct nodo
{
    int info;
    struct nodo *next;
};
typedef struct nodo Nodo;
typedef Nodo *PNodo;

PNodo inizializza()
{
    return NULL;
}

int listaVuota(PNodo l)
{
    return l == NULL;
}

PNodo inserisciInTesta(PNodo l, int el)
{
    PNodo temp;
    temp = malloc(sizeof(Nodo));
    temp -> info = el;
    temp -> next = l;
    return temp;
}

PNodo cancellatutti(PNodo l, int el)
{
PNodo temp, puntCorr , puntPrec ;
    if(listaVuota(l))
    {
        return l;
    }
    while(l -> info == el)
    {
        temp = l;
        l = l -> next;
        free(temp);
    }

    puntCorr=l;
    while(puntCorr !=NULL)
    {
        while(puntCorr !=NULL && puntCorr->info!=el)
        {
            puntPrec = puntCorr;
            puntCorr = puntCorr -> next;
        }

        if(puntCorr ->info==el)
        {
            temp = puntCorr;
            puntCorr = puntCorr -> next;
            puntPrec->next = puntCorr;
            free(temp);
        }
    }
    
    return l;
}

void stampa_lista(PNodo p)
{
    while (p != NULL)
    {
        printf("%d --> ", p->info);
        p=p->next;
    }
    printf("NULL\n");
}

int main()
{
    PNodo lista;
    int i;
    //srand(time(NULL));

    lista = inizializza();


    for(i=0; i<10; i++)
    {
        lista = inserisciInTesta(lista, rand()%3);
    }
    lista = inserisciInTesta(lista, 1);
    lista = inserisciInTesta(lista, 1);

    stampa_lista(lista);
    printf("\n");

    lista = cancellatutti(lista, 1);
    stampa_lista(lista);
}

Questo programma non funziona, o meglio: se metto stampa_lista NEL ciclo while(puntCorr !=NULL) della funzione cancellatutti allora effettivamente mi stampa la lista cancellando uno alla volta tutte le occorrenze, se invece lo metto fuori dal ciclo while non accade nulla. Cosa sbaglio?

Vi ringrazio anticipatamente per il tempo dedicatomi

6 Risposte

A
Alexv
Molto attivo
Iscritto da
giu, 2018
Messaggi:
646
Re: Cancellare elementi da una lista
08 giu 2020, 21:18
Prova ad aggiustare la malloc così
```
temp = (PNodo)malloc(sizeof(Nodo));
```
F
Freebulls
Pochi posts
Iscritto da
giu, 2017
Messaggi:
3
Re: Cancellare elementi da una lista
08 giu 2020, 22:04
Il problema sta soltanto nella funzione cancellatutti, il resto mi sembra funzioni. Lì non uso mai malloc
Grazie comunque
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Cancellare elementi da una lista
09 giu 2020, 01:01
Ciao, innanzitutto toglierei di mezzo inizializza() e listaVuota()... non ha senso utilizzare delle funzioni per delle operazioni tanto banali.

Detto questo passiamo alla funzione cancellatutti(). Consideriamo il seguente frammento di codice:
```
    if(listaVuota(l))
    {
        return l;
    }
    while(l -> info == el)
    {
        temp = l;
        l = l -> next;
        free(temp);
    }
```
Cosa succede nel caso della lista
1 --> 1 --> NULL
?
Il programma crasha in quanto cerca di accedere al membro info di un puntatore nullo.

Consideriamo ora il frammento:
```
    puntCorr=l;
    while(puntCorr !=NULL)
    {
        while(puntCorr !=NULL && puntCorr->info!=el)
        {
            puntPrec = puntCorr;
            puntCorr = puntCorr -> next;
        }

        if(puntCorr ->info==el)
        {
            temp = puntCorr;
            puntCorr = puntCorr -> next;
            puntPrec->next = puntCorr;
            free(temp);
        }
    }
```
Cosa succede nel caso della lista
2 --> 3 --> NULL
?
Il programma crasha in quanto cerca di accedere (nella condizione dell'if) al membro info di un puntatore nullo.

Aggiunti gli opportuni controlli sui puntatori dovrebbe andare, ma ti faccio notare che la funzione potrebbe essere riscritta in modo molto più semplice (e senza usare il puntatore temp) seguendo il seguente schema:
```
Nodo* cancellatutti(Nodo *l, int el)
{
    Nodo *corr = l;
    Nodo *prec = NULL;
    while(corr)
    {
        if(corr->info == el)
        {
            if(prec)
            {
                ...
            }
            else
            {
                ...
            }
        }
        else
        {
            ...
        }
    }
    return l;
}
```
P.S.
Non so se li hai mai utilizzati, ma con i puntatori doppi il tutto poteva essere fatto in modo molto più conciso!

Alexv

Molto attivo

Iscritto da: giu, 2018

Messaggi:: 646

Re: Cancellare elementi da una lista

09 giu 2020, 10:20

Oppure questa


PNodo cancellatutti(PNodo l, int el)
{
	PNodo temp, puntCorr, puntPrec=NULL;
	if (listaVuota(l))
	{
		return l;
	}
	while (l->info == el)
	{
		temp = l;
		l = l->next;
		free(temp);
	}
	puntCorr = l;
	puntPrec = l;
	while (puntCorr != NULL)
	{
		if (puntCorr->info == el)
		{
			temp = puntCorr;
			puntCorr = puntCorr->next;
			puntPrec->next = puntCorr;
			free(temp);
		}
		else
		{
			puntPrec = puntCorr;
			puntCorr = puntCorr->next;
		}
			
	}
	return l;
}

Per quanto riguarda il discorso della malloc, va bene non fare il cast, ma è meglio includere stdlib.h quando la usi, altrimenti il compilatore assume che restituisca un int (vedere la warning). Funziona lo stesso, ma può dare problemi inaspettati durante l'esecuzione.

Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Cancellare elementi da una lista
09 giu 2020, 13:21
@Alexv hai risolto solo il secondo dei 2 problemi di cui ho parlato nel precedente post.
A
Alexv
Molto attivo
Iscritto da
giu, 2018
Messaggi:
646
Re: Cancellare elementi da una lista
09 giu 2020, 14:14
Nippolo ha scritto:
@Alexv hai risolto solo il secondo dei 2 problemi di cui ho parlato nel precedente post.
Hai ragione va controllato che l non sia NULL anche nel primo while.

Devi accedere o registrarti per scrivere nel forum

6 risposte