Liste

Sommario

Stack

Uno stack (detto anche “pila”) è uno speciale tipo di struttura dati che gode di queste caratteristiche:

è una lista di elementi;
non ha una lunghezza predefinita;
è possibile inserire un elemento solo in testa, operazione detta push;
è possibile estrarre un elemento solo dalla testa, operazione detta pop;

Lo stack è una struttura dati che presenta caratteristiche differenti da un array:

non ha un accesso diretto ai suoi elementi;
non ha una lunghezza predefinita, ma può crescere o diminuire in modo dinamico;
protegge i suoi elementi interni, in quanto è possibile estrarre l’ultimo elemento, o inserire un nuovo elemento.

Lo stack viene definito come una coda “LIFO” ovvero Last in First Out, ovvero l’ultimo che entra è anche il primo che esce.

Lo stack è utile per tutta una serie di problemi di gestione dati dove non è possibile sapere in anticipo quanti saranno gli elementi di una lista. Di contro questa flessibilità implica la mancanza di un accesso diretto ad ogni singolo elemento, tuttavia questo semplifica e rende più sicuro l’utilizzo dello stack.

Nel mondo reale strutture di tipo stack rappresentano bene scenari dove vengono accumulati elementi in un contenitore sicuro, senza accesso diretto, e di cui è quindi possibile controllare l’accesso. Si pensi a scenari dove è necessario memorizzare una sequenza di valori secondo un ordine predefinito, oppure quando bisogna stabilire la precedenza dei calcoli in una operazione algebrica, o memorizzare i passaggi di un percorso in un labirinto.

Stack in linguaggio C/C++

Una prima possibile soluzione in C è quella di usare un array. Ma siccome un array ha una una dimensione fissa, dobbiamo gestire quella situazione in cui continuando ad aggiungere un nuovo elemento, si superano i limiti dell’array. Per farlo dobbiamo quindi creare un nuovo array, copiarci dentro i valori del vecchio array, e poi cancellarlo.

Dobbiamo poi chiaramente gestire con le variabili count e len rispettivamente il numero di elementi presenti e la lunghezza attuale dell’array (che deve essere sempre maggiore dei valori effettivamente contenuti).

Vediamo il codice:

#include <iostream>
using namespace std;

int push(char value, char data[], int count, int len) {
    if (count >= len) {
        len += 10;
        char* newData = new char[len];
        for (int i=0; i<count; i++) {
            newData[i] = data[i];
            data = newData;
        }
        delete[] data;
    }
    data[count] = value;
    return len;
}

char pop(char data[], int count) {
    return data[count];
}

int main()
{
    int len=10;
    char* data = new char[len];
    int count=0;
    len = push('a', data, count, 10);
    count++;
    len = push('b', data, count, 10);
    count++;
    len = push('c', data, count, 10);
    count++;
    count--;
    cout << pop(data, count);
    count--;
    cout << pop(data, count);
    count--;
    cout << pop(data, count);
    return 0;
}

Questa soluzione funziona, ma ha dei grossi difetti:

occupa spazio in memoria inutilizzato;
ogni volta che bisogna ricreare l’array, il sistema deve ricopiare tutti i valori nel nuovo array;
per stack molto grandi occorre molta memoria per duplicare l’array.

Non è quindi una soluzione efficace. La vera soluzione passa dall’uso invece dei puntatori.

Creiamo quindi una struct che contiene il valore char da memorizzare ed un secondo attributo che contiene un puntatore al valore successivo:

struct record {
    char value;
    record* next;
};

la struct quindi contiene sia il dato che vogliamo salvare, sia il puntatore al dato successivo.

Per creare uno stack sarà sufficiente quindi la prima volta creare un nuovo record, che chiamiamo “top”, assegnargli il valore, ed assegnare il puntatore next a NULL. Ogni volta che si vuole fare push, creiamo un nuovo valore, ma questa volta assegnamo next il puntatore a top. Se si vuole fare pop procediamo al contrario: assegnamo a top il puntatore next di top, ed eliminiamo il record.

Vediamo il codice:

record* push(record* top, char value) {
    record* newTop = new record;
    newTop->value = value;
    newTop->next = top;
    return newTop;
}

record* pop(record* top) {
    record* newTop = top->next;
    delete top;
    return newTop;
}

Vediamo come si usa:

int main()
{
    record* top = NULL;
    top = push(top, 'a');
    top = push(top, 'b');
    top = push(top, 'c');
    cout << top->value;
    top = pop(top);
    cout << top->value;
    top = pop(top);
    cout << top->value;
    top = pop(top);

    return 0;
}

Coda FIFO

La coda FIFO è una lista dove ogni elemento inserito si mette in coda. In questo caso il primo ad uscire è il primo che è entrato, e così via fino ad esaurire la coda. Un esempio nel mondo reale è la coda alla cassa del supermercato, dove l’ordine di uscita è il medesimo di quello di entrata.

Le code sono strutture dati fondamentali in numerose applicazioni, come nei sistemi operativi, nei processi di processamento dati, nella gestione di elaborazioni con priorità, nella gestione dei siti web, ecc.

Coda in linguaggio C/C++

Nello stack il punto di ingresso ed uscita è lo stesso, e quindi è sufficiente usare la stessa variabile.

Con le code invece la gestione dell’ingresso è del tutto separata dall’uscita. Vediamolo con il codice. Prima di tutto definiamo il record:

struct record {
	char value;
	record* next;
};

Definiamo la funzione di inserimento, enqueue:

record* enqueue(record* last, char value) {
	record *newrecord = new record;
	newrecord->value = value;
	newrecord->next = last;
	return newrecord;
}

Come si può vedere prima viene creato il nuovo record, lo si collega all’elemento di coda esistente e poi lo si restituisce: esso è la nuova coda della file. Fin qui tutto lineare.

Quando invece si esegue un dequeue, dobbiamo gestire 3 situazioni:

La lista è vuota: non dobbiamo fare nulla, e restituiamo un puntatore a NULL;
La lista ha un solo elemento: è sufficiente cancellarlo, e restituiamo un puntatore a NULL;
la lista da 2 o più elementi: in questo caso dobbiamo necessariamente scorrere tutta la lista, ed abbiamo bisogno di due variabili:

current: rappresenta l’elemento corrente della lista
next: rappresenta il prossimo elemento

Quindi ci spostiamo ciclicamente “avanti nella fila” fino a quando current sarà il secondo elemento e next il primo (cioè quando diventa vero che next->next != NULL).
A questo punto cancelliamo next e facciamo puntare current->next a NULL, e restituiamo last invariato.

Vediamo nel codice:

record* dequeue(record *last) {
   if (last == NULL) {
      return NULL;
   }
   record *current = last;
   if (current->next == NULL) {
       delete current;
       return NULL;
   }
   record *next = current->next;
   while (next->next != NULL) {
      current = current->next;
      next = current->next;   
   }
   current->next = NULL;
   delete next;
   return last;
}

Scriviamo poi una funzione di stampa ed il main per verificare:

void print(record *last) {
	record *current = last;
	while (current != NULL) {
		cout << current->value << "->";
		current = current->next;
	}
	cout << endl;
}

int main()
{
    cout << "Aggiungo a,b,c" << endl;
	record* last = enqueue(NULL, 'a');
	last = enqueue(last, 'b');
	last = enqueue(last, 'c');
	print(last);
	cout << "Rimuovo primo" << endl;
	last = dequeue(last);
	print(last);
	cout << "Aggiungo d,e" << endl;
	last = enqueue(last, 'd');
	last = enqueue(last, 'e');
	print(last);
    cout << "Rimuovo primo" << endl;
	last = dequeue(last);
	print(last);
	
	return 0;
}

Lista concatenata

Le liste concatenate sono liste generiche di lunghezza variabile. Esse offrono caratteristiche simili alle code FIFO, solo che offrono la possibilità di accedere ad ogni singolo elemento, e di rimuovere ed inserire elementi in qualsiasi posizione. Non sono però liste veloci, per accedere ad un elemento bisogna scorrere tutta la lista per trovare l’elemento che ci interessa.

Prima di tutto definiamo una struct node, che rappresenta il singolo elemento della lista. Ogni elemento punta al successivo, come nelle code FIFO.

struct node
{
	int data;
	struct node *next;
};

A questo punto definiamo una funzione di aggiunta:

node* add(node* current, int value) {
	current->data = i;
	current->next = new node;
	cout << "Aggiunto nodo: " << current << endl;
	return current->next;
}

Con questa funzione possiamo inserire un valore all’attributo data e creare un nuovo nodo.

A questo punto possiamo creare quanti nodi vogliamo.

Per farlo possiamo utilizzare ad esempio un ciclo for come il seguente, che inserisce n valori da 0 ad i.

node *current = new node;
int num;
cout << "Indica quanti nodi vuoi inserire: ";
cin >> num;
for (int i=0; i<num; i++) {
	current = add(current, i);
}

Per gestire il nodo corrente (l’ultimo) aggiorniamo il suo puntatore all’ultimo nodo appena creato. Quindi se creiamo 5 nodi, avremo il nodo 0 che ha un puntatore al nodo 1, che ha un puntatore a nodo 2 e così via fino a 5. Tuttavia se aggiorniamo il valore di current al puntatore successivo perdiamo il riferimento al primo nodo della lista (non c’è modo di tornare indietro). Quindi ci serve un puntatore first che punta al primo nodo della lista e che non modifichiamo mai.

Qui lo stesso codice con questo accorgimento:

node *first = new node;
node *current = first;
int num;
cout << "Indica quanti nodi vuoi inserire: ";
cin >> num;
for (int i=0; i<num; i++) {
	current = add(current, i);
}

Questo sistema abbiamo due soli puntatori, first che punta al primo elemento, e current che punta all’ultimo elemento. La dimensione della lista non ha limiti, e per accedere ad un elemento qualsiasi ci basta questa funzione:

node* get(node *current, int index) {
	if (index == 0) {
		return current;
	} else {
		return get(current->next, index-1);
	}
}

Per esempio se vogliamo il terzo elemento della lista scriveremo:

node *third = get(first, 3);

In pratica get è una funzione ricorsiva che avanza nella lista fino al nodo desiderato.

E’ importante osservare che se si perde il riferimento a first non solo non si riesce ad accedere ai dati ma si genera un memory leak, ovvero quando dei nodi sono allocati in memoria ma non sono raggiungibili in nessun modo.

Se vogliamo eliminare un nodo introduciamo la funzione remove che elimina l’ultimo nodo:

node* remove(node *current) {
	node *temp = current->next->next;
	delete current->next;
	current->next = temp;
	return current->next;
}

Per capire come funziona vediamo come si richiama:

current = get(first, num-2);
current = remove(current);
num--;

Prima di tutto si porta il puntatore current indietro di due nodi rispetto alla testa (l’ultimo è il futuro nodo – non contiene alcun valore – ed il penultimo è l’effettivo ultimo nodo con un valore ). A questo punto la funzione remove memorizza il nodo futuro in una variabile temporanea e poi cancella l’ultimo nodo popolato. Infine aggancia il futuro nodo al penultimo nodo.

Sembra complicato ma non lo è, e per capirlo vediamo un esempio di programma completo con quanto visto finora.

#include <iostream>
#include <string.h>
#include <cstdlib>

using namespace std;

struct node
{
	int data;
	struct node *next;
};

node* add(node* current, int value) {
	current->data = value;
	current->next = new node;
	return current->next;
}

node* get(node *current, int index) {
	if (index == 0) {
		return current;
	} else {
		return get(current->next, index-1);
	}
}

node* remove(node *current) {
	node *temp = current->next->next;
	delete current->next;
	current->next = temp;
	return current->next;
}

void print(node *first) {
	node* current = first;
	cout << "Ecco la lista dei nodi: " << endl;
	while (current->next != NULL) {
		cout << "Indirizzo: " << current << " -  Valore:" << current->data << " -> Indirizzo (succ): " << current->next << endl;
		current = current->next;
	}
	cout << "Indirizzo testa lista (vuoto): " << current << endl;
}

int main() {
	node *first = new node;
	node *current = first;
	int num;
	cout << "Indica quanti nodi vuoi inserire: ";
	cin >> num;
	for (int i=0; i<num; i++) {
		current = add(current, i);
	}
	cout << "Inseriti " << num << " nodi" << endl;
	print(first);
	int action;
	do {
		cout << "Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: ";
		cin >> action;
		if (action==1) {
			current = get(first, num-2);
			current = remove(current);
			num--;
			print(first);
		}
		if (action == 2) {
			current = add(current, num);
			num++;
			print(first);
		}
		
	} while (action != 0);
	return 0;
}

Il programma stampa gli indirizzi dei puntatori della lista e con questo output si dimostra il funzionamento:

Indica quanti nodi vuoi inserire: 1
Inseriti 1 nodi
Ecco la lista dei nodi: 
Indirizzo: 0x6312153a12b0 -  Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo testa lista (vuoto): 0x6312153a1af0

Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 2
Ecco la lista dei nodi: 
Indirizzo: 0x6312153a12b0 -  Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 -  Valore:1 -> Indirizzo (succ): 0x6312153a1b10
Indirizzo testa lista (vuoto): 0x6312153a1b10

Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 2
Ecco la lista dei nodi: 
Indirizzo: 0x6312153a12b0 -  Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 -  Valore:1 -> Indirizzo (succ): 0x6312153a1b10
Indirizzo: 0x6312153a1b10 -  Valore:2 -> Indirizzo (succ): 0x6312153a1b30
Indirizzo testa lista (vuoto): 0x6312153a1b30

Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 2
Ecco la lista dei nodi: 
Indirizzo: 0x6312153a12b0 -  Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 -  Valore:1 -> Indirizzo (succ): 0x6312153a1b10
Indirizzo: 0x6312153a1b10 -  Valore:2 -> Indirizzo (succ): 0x6312153a1b30
Indirizzo: 0x6312153a1b30 -  Valore:3 -> Indirizzo (succ): 0x6312153a1b50
Indirizzo testa lista (vuoto): 0x6312153a1b50

Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 1
Ecco la lista dei nodi: 
Indirizzo: 0x6312153a12b0 -  Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 -  Valore:1 -> Indirizzo (succ): 0x6312153a1b10
Indirizzo: 0x6312153a1b10 -  Valore:2 -> Indirizzo (succ): 0x6312153a1b50
Indirizzo testa lista (vuoto): 0x6312153a1b50

Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 1
Ecco la lista dei nodi: 
Indirizzo: 0x6312153a12b0 -  Valore:0 -> Indirizzo (succ): 0x6312153a1af0
Indirizzo: 0x6312153a1af0 -  Valore:1 -> Indirizzo (succ): 0x6312153a1b50
Indirizzo testa lista (vuoto): 0x6312153a1b50

Inserisci 1 se vuoi rimuovere un nodo, 2 per aggiungere, 0 per terminare: 0

Home

Programmazione

Sviluppo del Software

C/C++

Java

HTML

Javascript

NodeJS

Esercizi di programmazione

Introduzione alla programmazione

Progettazione

Ciclo di vita del Software

Progettazione del software

Tecnologie

Sistemi operativi

Architetture degli elaboratori

Tecnologie Web

Intelligenza Artificiale

Esercizi di Tecnologie

OpenCV

SpringBoot

Strumenti

Progetti Web

Strumenti web

Strumenti sviluppo

Introduzione all'Informatica