Algoritmi e Strutture Dati

Creazione di una lista in C

È fondamentale che p_next sia un puntatore autoreferenziante in quanto deve puntare alla struttura stessa. Infatti è stato dichiarato di tipo struct numero, ovvero dello stesso tipo della struct.

Dopo aver dichiarato la struttura numero occorre tenere traccia del punto dove la lista ha inizio (head), e per creare una lista vuota ad esempio, è possibile scrivere: struct numero* testa = NULL. In questo modo è stata dichiarata una variabile che punta sempre al primo nodo della lista, che però in questo caso è vuota, ed è stata posta pari a NULL.

Per inserire un nuovo nodo nella lista il primo passo da seguire è "allocare memoria per il nuovo nodo da inserire" utilizzando il malloc(), poi occorre "salvare i dati in quel nuovo nodo appena allocato": per conferire maggiore leggibilità e scorrevolezza al programma, il C, visto che l'accesso di un membro di una struttura è un'operazione importantissima,

mette a disposizione un operatore fatto apposta che è la "freccetta", composta dal trattino e il simbolo di minore: ->, che ha la stessa semantica dell'istruzione (*nuovo).valore=2. È possibile anche far acquisire da tastiera il valore utilizzando l'istruzione scanf("%d",&nuovo->valore).

Adesso la variabile puntatore "nuovo" sta puntando al nodo che dovrà essere inserito, e la variabile puntatore "testa" sta puntando al primo nodo della lista. Per l'inserimento in testa del nodo occorre prima di tutto modificare il puntatore p_next del nuovo nodo in modo che punti a quello che era l'inizio della testa, e poi occorre far puntare "testa" al nuovo nodo.

Esistono anche le liste doppiamente linkate, nelle quali ciascun nodo è costituito da un valore, un puntatore al nodo precedente ed un puntatore al nodo successivo: 151.2.2.

Stack

Lo Stack è una struttura dati dinamica molto simile

Ad una lista nella quale però le operazioni di inserimento, cancellazione e prelievo di dati possono avvenire soltanto in testa. I dati vengono estratti secondo una politica LIFO (Last In First Out), ovvero l'ultimo elemento inserito è il primo ad essere estratto. Le operazioni ammesse su uno stack sono:

• newStack(): crea uno stack vuoto.
• stackPush(el): inserisce l'elemento el in cima allo stack.
• stackTop(): restituisce il valore dell'elemento in cima allo stack.
• stackPop(): toglie l'elemento in cima allo stack.
• stackIsEmpty(): restituisce 1 se lo stack è vuoto, 0 altrimenti.
• stackDestroy(): elimina lo stack.

Per implementare queste funzionalità occorre definire un indice "testa" il quale viene inizializzato con il valore 0 (significa pila vuota): nell'operazione Push la variabile testa viene incrementata di 1, invece nell'operazione Pop la variabile testa viene decrementata di 1. Viene mostrata

#include <stdio.h>
#define MAX 3

int testa;
int Pila[MAX];

int menu_scelta(void){
    int selezione = 0;
    do{
        printf("\n");
        printf("\n1 -> Aggiungi un dato");
        printf("\n2 -> Estrai un dato");
        printf("\n3 -> Svuota pila");
        printf("\n4 -> Stampa pila");
        printf("\n5 -> Esci");
        printf("\n");
        printf("\nEffettua una scelta: ");
        scanf("%d", &selezione);
    }while (selezione<1 || selezione>5);
    return selezione;
}

void Push() {
    int n;
    if(testa==MAX)
        printf("\n -> Pila piena");
    else {
        printf("\nInserisci un dato: ");
        scanf("%d", &n);
        Pila[testa++]=n;
    }
}

void Pop() {
    if(testa==0)
        printf("\n - Pila vuota");
    else
        printf("%d", Pila[--testa]);
}

void Clear() {
    testa=0;
    printf("\n -> Pila svuotata");
}

void Print() {
    int i;
    if(testa==0)
        printf("\n -> Pila vuota");
    else

for(i=testa-1;i>=0;i--)
    printf("indice i: %d elemento %d\n", i, Pila[i]);
}

int main(){
    int scelta;
    while((scelta=menu_scelta())!=5){
        switch(scelta){
            case 1:
                Push();
                break;
            case 2:
                Pop();
                break;
            case 3:
                Clear();
                break;
            case 4:
                Print();
                break;
            case 5:
                break;
        }
    }
    return 0;
}

1.2.3. Coda

Una tipica struttura dati astratta è la coda. Si tratta di un oggetto sul quale è possibile compiere due operazioni fondamentali: inserire un dato ed estrarre un dato. Quando si estrae un dato dalla coda, si ottiene il più vecchio tra i dati inseriti, ossia quello inserito per primo. Per questo motivo, la coda è una struttura di tipo FIFO (First In, First Out: il primo dato inserito è il primo a essere estratto). In altre parole, la coda è una lista in cui l'inserimento avviene ad una estremità (coda), mentre cancellazione e prelievo di dati avvengono all'altra estremità (testa). La struttura serve dunque a gestire situazioni simili a quelle che si

verificano quando più persone devono accedere a un servizio, ad esempio una biglietteria, e si mettono in coda. L'operazione di "inserimento in coda" avviene quando arriva una nuova persona; l'operazione di "estrazione dalla coda" avviene quando lo sportello si libera e una nuova persona viene servita, nell'ordine d'arrivo.

Le operazioni primitive che deve garantire una coda sono:

• void CodaCrea(Coda *C): crea una coda vuota.
• int CodaIn(Coda *C, Atomo A): inserisce un nuovo atomo (elemento) in fondo alla coda. Questa operazione è chiamata anche enqueue, che significa accodamento di un elemento.
• int CodaOut(Coda *C, Atomo *A): cancella (consuma) l'atomo in testa. Questa operazione è chiamata anche dequeue, che significa estrazione di un elemento.
• int CodaVuota(Coda *C): verifica se la coda è vuota.

Rispetto alla gestione della pila (stack), la coda presenta principalmente una differenza sostanziale che comporta

• Una pila cresce solo da un lato e quindi basta, utilizzando una struttura sequenziale, tenere conto solo di un puntatore (cima) all'ultimo elemento inserito: se l'indicatore raggiunge, in valore, la dimensione della struttura sequenziale, la pila è piena.
• Una coda ha necessità di utilizzare due puntatori (testa e fondo): uno per i prelievi e uno per gli inserimenti. Anche in questo caso si utilizzerà una struttura sequenziale per implementare la coda solo che, stavolta, il puntatore fondo può raggiungere il valore della dimensione della struttura sequenziale, senza che tale condizione comporti come conseguenza il riempimento della coda. La struttura che si sta esaminando è di tipo dinamico, e quindi i prelievi e gli inserimenti si susseguono: può darsi che siano già stati prelevati, per esempio, tutti gli elementi meno uno. In tale caso la zona

di memoriariservata alla struttura è praticamente vuota.
Ci sono 2 modi possibili per implementare una coda: come lista concatenata oppure come array circolare, si mostra soltanto la seconda modalità:


#include <stdio.h>
#define MAX 3
int fine;
int inizio=0;
int Coda[MAX];

int menu_scelta(void){
    int selezione = 0;
    do{
        printf("\n" );
        printf("\n1 -> Aggiungi un dato" );
        printf("\n2 -> Estrai un dato");
        printf("\n3 -> Svuota pila");
        printf("\n4 -> Stampa pila");
        printf("\n5 -> Esci");
        printf("\n" );
        printf("\nEffettua una scelta: " );
        scanf("%d", &selezione );
    } while (selezione<1 || selezione>5);
    return selezione;
}

void Push() {
    int n;
    if(fine==MAX) 
        printf("\n -> Coda piena" );
    else { 
        printf("\nInserisci un dato: " );
        scanf("%d", &n);
        Coda[fine++]=n;
    }
}

void Pop() {
    if(fine==inizio) 
        printf("\n - Coda vuota" );
    else { 
        //stampo
    }
}

l'’elemento che ora viene buttato fuori

printf("%d", Coda[inizio]);
for(int i=inizio+1;i<=fine;i++){
    //scaliamo tutti gli elementi a sinistra di un posto
    Coda[i-1]=Coda[i];
}
//decremento fine perché un elemento è uscito dalla coda
fine--;

void Clear() {
    fine=inizio;
    printf("\n -> Coda svuotata" );
}
void Print() {
    if(fine==inizio) 
        printf("\n -> Coda vuota" );
    else 
        for(int i=inizio;i<fine;i++){
            printf("%d elemento: %d\n", i, Coda[i]);
        }
}
int main(){
    int scelta;
    while((scelta=menu_scelta())!=5){
        switch(scelta){
            case 1:
                Push();
                break;
            case 2:
                Pop();
                break;
            case 3:
                Clear();
                break;
            case 4:
                Print();
                break;
            case 5: 
                break;
        }
    }
    return 0;
}

Un grafo è una coppia (V, E), dove V è un insieme di nodi, chiamati vertici, ed E è un insieme di coppie di nodi, chiamati archi. Un grafo (V,E) è non orientato se l'insieme degli archi E è un insieme di coppie non ordinate.

Un grafo (V,E) è orientato (o diretto) se l'insieme degli archi E è una relazione binaria tra vertici. In tal caso dati due nodi A e B, gli archi A-B e B-A saranno distinti fra loro.

I grafi sono uno strumento di rappresentazione (modellazione) di problemi. La soluzione di molti problemi può essere ricondotta alla soluzione di opportuni problemi su grafi. Ad esempio si mostra la modellazione con grafi delle relazioni studenti-corsi di una università:

In un grafo orientato, un arco (w,v) si dice incidente da w a v, mentre l'arco v si dice adiacente a w. È chiaro che in un grafo non orientato, incidenze e adiacenze sono simmetriche. Altra importante in un grafo orientato