Operatore ->

Come si vedrà a breve, in C capita molto spesso di accedere ai campi di una struttura tramite un puntatore a tale struttura. Allora, per rendere più compatto e leggibile il codice, il linguaggio mette a disposizione una “scorciatoia”: l’operatore binario infisso ->. Esso deve avere come operando sinistro un puntatore pt a una struttura e come operando destro un’etichetta campo di un campo di tale struttura. Dati tali operandi, *pt -> campo* è esattamente equivalente a (*pt).campo: si deferenzia il puntatore pt e si seleziona il campo campo della struttura puntata, che può così essere letto e/o modificato.

Pila

La pila, o stack, è una delle più semplici e importanti strutture dati. Le principali operazioni su una pila sono:

• init_stack: crea la struttura dati in memoria
• push: inserisce un nuovo elemento
• pop: elimina l’elemento in cima
• top: legge l’elemento in cima
• is_empty: indica se la pila è attualmenet vuota

Ci sono vari modi di implementare una struttura che supporti queste operazioni. Adesso, come esempi di applicazioni della memoria dinamica, si vedranno due possibili implementazini: una basata su un vettore allocato dinamicamente e una basata su una lista concatenata.

Implementazione con un vettore

Una pila basata su un vettore allocato dinamicamente può essere rappresentata dalla seguente struttura stack:

typedef int ITEM;

struct stack {
	ITEM *array;
	int max_size;
	int top;
};

typedef struct stack STACK;

• Una pila è una struttura dati omogenea, cioè contiene valori che sono tutti dello stesso tipo. Siccome l’implementazione della pila non dipende dal tipo degli elementi, in questo codice si usa una typedef per assegnare a esso il nome astratto ITEM: così, per cambiare il tipo degli elementi è sufficiente modificare la typedef.
• I campi della struttura stack servono a tenere traccia di tutte le informazioni necessarie per la gestione della pila:
  • array è un puntatore al vettore di ITEM allocato dinamicamente che conterrà gli elementi della pila
  • max_size indica la dimensione del vettore allocato, ovvero il numero massimo di elementi che la pila può contenere
  • top è l’indice della prima posizione libera del vettore
• Il nome stack non corrisponde di per sè a un tipo, perchè è solo l’etichetta di una struttura: il nome del tipo corrispondente è struct stack. Volendo evitare di scrivere struct stack ogni volta, si usa una typedef per associare a tale tipo un nome più breve: STACk.

Adesso verranno mostrate le implementazioni delle varie operazioni sulla pila. Si noti che, per semplicità, verranno omessi alcuni dettagli, come ad esempio la gestione degli errori e la deallocazione della memoria allocata, che sarebbero importanti in un’implementazione “reale”, destinata all’uso pratico, ma non riguardano strettamente la logica di gestione della struttura dati

init_stack

La funzione init_stack crea dinamicamente una pila in grado di contenere al massimo il numero di elementi passato come argomenti. La pila creata è inizialmente vuota.

STACK *init_stack(int n) {
	STACK *tmp = (STACK *)malloc(sizeof(STACK));
	if (tmp == NULL) {
		// Gestione dell'errore...
		return NULL;
	}
	tmp->array = (ITEM *)calloc(n, sizeof(ITEM));
	if (tmp->array == NULL) {
		// Gestione dell'errore...
		return NULL;
	}
	tmp->max_size = n;
	tmp->top = 0;
	return tmp;
}