22: Liste, operazioni principali

Nello scorso articolo abbiamo parlato di liste, in particolare di cosa sono e di come dichiararle. Vediamo ora come inserire dei nodi nella lista. Per far ciò analizziamo insieme un programma in cui l’utente può manipolare una lista: esso, con l’inserimento di un carattere potrà, scegliere se aggiungere/eliminare un nodo dalla lista, finché non inserisce il carattere ‘e’ che termina l’esecuzione del programma. Avremo bisogno di una funzione che stampa la lista, una che aggiunge un nodo e una che ne elimina uno, e si suppone che ogni nodo contenga un intero e che essi debbano essere ordinati all’interno della lista.

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

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

typedef struct nodo Nodo;
typedef Nodo *puntnodo;

void istruzioni(void);
void inserisci(puntnodo *ptr, int n );
void stampa(puntnodo curr);
int vuota(puntnodo ptr);
int cancella(puntnodo *ptr, int n);



int main(){
    
    puntnodo punt=NULL;
    char scelta;
    int valore;
    
    istruzioni();
    printf("inserisci un carattere\n");
    scanf("%c", &scelta);
    
    while(scelta!='e')
    {
        switch (scelta) {
            
                case 'a':             
                    printf("inserisci il valore del nodo\n");
                    scanf("%d", &valore);
                    inserisci(&punt, valore);
                    stampa(punt);
                    break;
                                 
                case 'd': 
                    if(!vuota(punt))
                    {
                        printf("inserire il numero da cancellare\n");
                        scanf("%d", valore);
                        
                        if(cancella(&punt, valore)==valore)
                        {
                           printf("%d cancellato\n", valore);
                           stampa(punt);
                           
                        }
                        else printf("%d non trovato\n", valore);
                    }
                    else printf("la lista e' vuota\n");
                    break;
                                
                 default:
                        printf("scelta non valida\n");
                        istruzioni();
                            break;
        }
        printf("inserisci un carattere\n");
        scanf("%c", &scelta);             
    }
    printf("fine\n");
    return 0;

}

void istruzioni(void)
{
    printf("Inserisci la tua scelta:\n a per aggiungere un nodo,\n d per cancellare un nodo,\n e per uscire.\n");
}

void inserisci(puntnodo *ptr, int n )
{ 
 puntnodo nuovo;
 puntnodo prec;
 puntnodo curr;
 
 nuovo=malloc(sizeof(puntnodo));  //alloca  e inizializza nuovo nodo
 if (nuovo!=NULL) {
     nuovo->valore=n;             
     nuovo->next=NULL;
     
     prec=NULL;
     curr=*ptr;
     
     while(curr!=NULL && n>curr->valore)   //scandisci la lista finché i valori delle celle attraversate sono minori del numero che vogliamo inserire noi
     {
         prec=curr;
         curr=curr->next;
     }
     
     if (prec==NULL) //se prec==NULL vuol dire che la mia lista è vuota e non sono entrato nemmeno una volta nel ciclo while soprastante
     {
         nuovo->next=*ptr;
         *ptr=nuovo;
     }
      
     else 
     { //la lista non è vuota ma contiene già altri elementi, il nuovo nodo verrà inserito tra il nodo chiamato "prec" e il nodo chiamato "curr"
         prec->next=nuovo; 
         nuovo->next=curr;
     }
     
     
     
 }
 else printf("impossibile aggiungere nodo: errore nell'allocazione di memoria\n");
}

void stampa(puntnodo curr)
{
    if (vuota(curr)) 
        printf("la lista e' vuota\n");
    else {
        printf("questa e' la lista:\n");
        while(curr!=NULL)
        {
            printf("%d - - >", curr->valore);
            curr=curr->next;
        }
        printf("NULL\n");
    }
}


int vuota(puntnodo ptr)
{
    return ptr==NULL;//questa è una forma un pò elegante, avremmo potuto anche scrivere un if 
}

int cancella(puntnodo *ptr, int n)
{
    puntnodo prec;
    puntnodo curr;
    puntnodo temp;
    if (n==(*ptr)->valore)
    {
        temp=*ptr;
        *ptr=(*ptr)->next;
        free(temp);//libero la cella di memoria che non mi serve più
        return(n);
    }
    else
    {
        prec=*ptr;
        curr=(*ptr)->next;
        
        while(curr!=NULL && curr->valore!=n)
        {
            prec=curr;
            curr=curr->next;
        }
        if(curr!=NULL)
        {
            temp=curr;
            prec->next=curr->next;
            free(temp);//libero la cella di memoria che non mi serve più
            return(n);           
        }
    }
    return (n-1);//ritorna un valore diverso da quello ricevuto per segnalare che il valore che si voleva cancellare non è stato trovato
}

Oltre alle due funzioni inserisci e cancella, che rispettivamente inseriscono e cancellano un nodo della lista, abbiamo una procedura istruzioni che stampa le istruzioni per far funzionare il programma, una funzione stampa che stampa il contenuto della lista e una funzione vuota, che controlla se la lista e è vuota e restituisce 1 in caso affermativo. Queste ultime 2 funzioni prendono in ingresso il puntatore al primo elemento della lista (testa della lista) per valore (o per copia), in quanto non hanno bisogno di modificare il contenuto della lista.
Le funzioni inserisci e cancella, al contrario, devono modificare il contenuto della lista, quindi prendono in ingresso la testa della lista passata per riferimento (cioè un doppio puntatore). Queste due funzioni hanno inoltre bisogno di 3 puntatori a nodo della lista ausiliari per scandirla (trovare il punto esatto dove andare ad aggiungere/cancellare il modo controllando i valori all’interno del campo “valore” di ciascun nodo) e modificarla: bisogna stare attenti quando si cancella un puntatore che collega due nodi adiacenti ad averlo prima salvato da qualche parte (in un puntatore ad un elemento dello stesso tipo ausiliario appunto), altrimenti si perderebbe l’accesso a tutta la parte della lista che segue il nodo che contiene il puntatore in questione, impedendo tra l’altro anche la deallocazione della memoria precedentemente allocata per la lista stessa.
Si noti che la funzione cancella restituisce un intero pari al valore che si voleva cancellare qualora esso sia presente nella lista, e pari a quello stesso valore decremento di uno altrimenti (è solo uno dei possibili metodi per capire se la cancellazione è andata a buon termine).
Si noti anche l’utilità della funzione vuota qualora l’elemento da inserire/cancellare sia il primo della lista.
La funzione main consiste di un while che permette di chiedere all’utente un carattere di scelta dell’operazione da eseguire finché esso non inserisce il carattere ‘e’ che termina l’esecuzione del programma, il tutto governato dallo switch all’interno del while.
Con le liste chiudiamo qua, come sempre se avete dubbi scriveteci, e continuate a seguirci su Cyberpills!.

Please follow and like us: