Gestione di una pila mediante un array

da Cristina | Mag 29, 2019 | Tutorial C

In questo articolo implementeremo la gestione di una pila mediante un array in C.

Nella lezione precedente abbiamo già visto un metodo per la gestione di una pila in C, utilizzando le variabili globali Pila[MAX] e testa di tipo intero. Nell’esempio queste variabili rappresentano l’array e l’indice testa che va da 0 a MAX. Dunque se MAX ad esempio vale 10, testa va da 0 a 10.

La lezione è consultabile al seguente link: pila in C.

In questa lezione impareremo invece a gestire la pila tramite l’uso di funzioni con passaggio di parametri.

Gestione di una pila mediante un array – procedimento

Utilizzeremo dunque queste funzioni di cui elenchiamo i prototipi e le definizioni.

Funzione Push

int Push(int Pila[], int *testa, int n);

Ho costruito questa funzione in modo da prevedere il passaggio dei seguenti parametri:

Pila – il puntatore alla struttura dati (array) che contiene la pila fisicamente;

testa – il puntatore alla testa della pila;

n – l’elemento da inserire.

La funzione restituisce un intero *testa che rappresenta la posizione del puntatore dopo l’inserimento di ciascun valore.

Dunque costruiamo la nostra funzione in questo modo:

Inseriamo l’elemento nella posizione dell’array indicato da *testa. Dopo incrementiamo di uno il valore di *testa:

//inseriamo l’elemento nella posizione indicata da *testa
Pila[*testa]=n;
//incrementiamo di 1 *testa
++*testa;

int Push(int Pila[], int *testa, int n) {
		Pila[*testa]=n;
		++*testa;
		return (*testa);
}

Nel main invochiamo dunque la funzione Push in questo modo:

p=Push(Pila, &p, n);

Dunque in p memorizziamo l’indice ritornato dalla funzione Push.

Funzione Pop

int Pop(int Pila[], int *testa, int n);

La funzione Pop prevede il passaggio dei parametri, Pila, testa ed n. 

La funzione restituisce un intero *testa che rappresenta la posizione del puntatore dopo l’eliminazione del valore al top.

Dunque costruiamo la nostra funzione Pop in questo modo:

Decrementiamo di uno il valore di *testa (cioè il puntatore alla testa della pila). Dopo assegniamo il valore dell’elemento in testa alla pila ad n e restituiamo il nuovo puntatore alla pila.

int Pop(int Pila[], int *testa, int n) {
			--*testa;
			n=Pila[*testa];
			printf("\n -> Elemento rimosso %d" , Pila[*testa]);
			return (*testa);
}

Pertanto nel main invochiamo la funzione Pop in questo modo:

p=Pop(Pila, &p, n);

Quindi in p memorizziamo l’indice ritornato dalla funzione Pop.

Funzione Print

void Print(int Pila[], int testa);

I parametri passati sono quindi:

Pila – il puntatore alla struttura dati;

testa – l’indice della testa della pila.

La funzione non restituisce pertanto alcun valore.

Dunque costruiamo la nostra funzione Print in questo modo:

void Print(int Pila[], int testa) {
	while(testa>=1) 
		printf("indice %d elemento: %d\n", testa, Pila[--testa]);		
}

Con un ciclo while che continua finché l’indice testa è maggiore o uguale a 1, decrementiamo testa e stampiamo il valore corrispondente.

Infatti se ad esempio la pila fosse piena, l’indice testa partirebbe da MAX dove non c’è alcun valore.

Quindi se testa si trova ad esempio in posizione 3, dove non c’è nessun elemento, allora decrementiamo testa di 1 e stampiamo l’elemento corrispondente.

Invochiamo poi la funzione nel programma principale in questo modo:

Print(Pila, p);

Funzione Clear

int Clear(int testa);

Ho costruito questa funzione in modo da prevedere il passaggio come parametro solo dell’indice testa.

Dunque ecco la nostra funzione Clear:

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

Facciamo restituire alla funzione semplicemente 0 che rappresenta l’indice della Pila.

Nel main invochiamo dunque la funzione in questo modo:

p=Clear(p);

Ecco dunque il listato completo della gestione di una pila mediante un array:

#include <stdio.h>

#define MAX 10


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;
}

int Push(int Pila[], int *testa, int n) {
	Pila[*testa]=n;
	++*testa;
	return (*testa);
}

int Pop(int Pila[], int *testa, int n) {
	--*testa;
	n=Pila[*testa];
	printf("\n -> Elemento rimosso %d" , Pila[*testa]);
	return (*testa);
}

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

void Print(int Pila[], int testa) {
	while(testa>=1) 
		printf("indice %d elemento: %d\n", testa, Pila[--testa]);		
}

int main(){
	int scelta;
	int Pila[MAX];
	int n, p=0;
	
	while((scelta=menu_scelta())!=5){
           switch(scelta){
              case 1: 
        	     if(p==MAX)
        		  printf("\nPila piena! " );
        	     else {
        		  printf("\nInserisci un dato: " );
				scanf("%d", &n);
				p=Push(Pila, &p,n);
		     }
                     break;
             case 2:
		    p=Pop(Pila, &p, n);
                    break;
            case 3:
		    p=Clear(p);
                    break;
             case 4: 
		    if(p==0)
        		printf("\nPila vuota! " );
        	     else 
			Print(Pila, p);
			break;
	      case 5: 	
			break;
             }
    }             
    return 0;
}

Alcuni link utili

Indice argomenti linguaggio C

La funzione fopen

La funzione fclose

Funzione fprintf

Funzione fscanf

Allocazione dinamica della memoria con malloc

Typedef struct in C

Esercitazione sulle struct in C

Realizzare un menù di scelta in C

Strutture complesse in C

Come sommare gli elementi della cornice esterna

Come sommare due matrici

Matrice trasposta

Prodotto tra matrici

Ricerca elementi in una matrice

Tavola pitagorica in C

Array multidimensionali

Quick sort in C

Insertion Sort in C

Pila in C

da Cristina | Mag 29, 2019 | Tutorial C

In questa lezione svilupperemo un semplice esercizio sull’uso della pila in C.

Creiamo dunque un programma per la gestione di una pila che permette di inserire dei valori, eliminarli, stamparli e cancellarli tutti in una volta.

Serviranno dunque le funzioni:

Push per l’inseriemento dei dati;

Pop per l’estrazione dei dati;

Clear per cancellare tutti i dati della pila;

Print per stampare tutti i dati dall’elemento in alto a quello in basso.

Per la risoluzione del seguente problema, abbiamo assegnato all’indice testa il valore iniziale 0. Quindi nel caso in cui la testa sia uguale a zero vuol dire che la pila è vuota.

Nell’operazione Push la variabile testa viene incrementata di 1, invece nell’operazione Pop la variabile testa viene decrementata di 1.

Si poteva anche operare assegnando a testa il valore MAX anzichè zero e ragionare in maniera analoga.

Ecco dunque il semplice algoritmo che realizza le operazioni di inserimento ed estrazione di un elemento in un pila in c. Inoltre implementeremo le operazioni di stampa e svuotamento della pila.

Notate come in questa prima soluzione, sviluppata principalmente a scopo didattico, facciamo uso delle variabili globali.

#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;
}

N.B Avremmo anche potuto scrivere nel Push:

	....
        Pila[testa]=n;
        testa++;
        ....

E nel Pop:

         .....
         else {
            testa--;
	    printf("%d", Pila[testa]);
         }
        .....

Questa soluzione, come abbiamo già detto, fa uso delle variabili globali, ma come sappiamo non sempre è bene usarle. Nella prossima lezione implementeremo invece un metodo che non le utilizza. Quindi passeremo i parametri alle funzioni Push(), Pop(), Clear() e Print().

Alcuni link utili

Indice argomenti linguaggio C

La funzione fopen

La funzione fclose

Funzione fprintf

Funzione fscanf

Allocazione dinamica della memoria con malloc

Strutture in C

Typedef struct in C

Esercitazione sulle struct in C

Realizzare un menù di scelta in C

Strutture complesse in C

Come sommare gli elementi della cornice esterna

Come sommare due matrici

Matrice trasposta

Prodotto tra matrici

Ricerca elementi in una matrice

Tavola pitagorica in C

Array multidimensionali

Quick sort in C

Selection sort in C

Merge sort in C

Insertion Sort in C

Stack

da Cristina | Mag 29, 2019 | Tutorial C

In questa lezione studieremo lo stack (o pila), cioè un elenco di dati avente la caratteristica di permettere l’inserimento di nuovi elementi e l’estrazione degli elementi introdotti ma solo da un’unica estremità.

Un elemento nella pila è inserito con una funzione detta Push, mentre un elemento si estrae con la funzione Pop.

La regola è questa: l’ultimo elemento inserito con Push è il primo ad essere estratto con Pop.

Quindi per questo motivo si parla di struttura LIFO (Last in First Out) ovvero l’ultimo elemento ad entrare è anche il primo ad uscire.

La gestione dello stack si può realizzare o con le linked list o appoggiandosi ad un array visto in “verticale” dove l’inserimento e l’estrazione avvengono sempre dallo stesso lato.

La pila inoltre richiede un indice, che contrassegna la prima casella libera del vettore a partire dalla posizione iniziale.

Questo indice lo chiamiamo testa e quando la pila è vuota il suo valore è zero. Nella posizione indicata dall’indice testa dunque estrarremo o inseriremo i dati con le funzioni Pop e Push.

Rappresentazione in figura

Nella figura ecco un esempio di stack con l’indice testa che indica la prima casella libera e dopo l’inserimento, del numero 5, l’indice testa si sposta di 1.

Altre possibili operazioni sono:

Top che restituisce l’elemento superiore dello stack.

isEmpty che restituisce true se lo stack è vuoto, altrimenti false.

isFull che restituisce true se lo stack è pieno, altrimenti vero.

Le operazioni push(), pop(), isEmpty() e top() richiedono tutti tempo O(1), infatti non eseguiamo cicli in nessuna di queste operazioni.

Un tipico esempio di applicazione dello stack si ha nelle Torre di Hanoi, nell’attraversamento degli alberi e in tanti altri algoritmi.

Questa è solo una piccola introduzione sull’uso dello stack, nelle prossime lezioni faremo altri esempi.

Alcuni link utili

Indice argomenti linguaggio C

La funzione fopen

La funzione fclose

Funzione fprintf

Funzione fscanf

Allocazione dinamica della memoria con malloc

Realizzare un menù di scelta in C

Strutture complesse in C

Come sommare gli elementi della cornice esterna

Come sommare due matrici

Matrice trasposta

Prodotto tra matrici

Ricerca elementi in una matrice

Merge sort in C

Insertion Sort in C