Appunti su Programmazione e linguaggio C

a cura del prof. Nunzio Brugaletta

Unità

4

le strutture - le tabelle: array di strutture - strutture dei dati: generalità - strutture astratte - array e aritmetica dei puntatori - gestione di una pila - gestione di una coda

Unità 1 - Unità 2 - Unità 3 - Unità 4 - Unità 5 - Unità 6

Le strutture

Una struttura è un insieme di variabili di uno o più tipi, raggruppate da un nome in comune. Anche gli array sono collezioni di variabili come le strutture solo che un array può contenere solo variabili dello stesso tipo, mentre le variabili contenute in una struttura non devono essere necessariamente dello stesso tipo.

Le strutture del linguaggio C coincidono con quelli che in Informatica sono comunemente definiti record. Il raggruppamento sotto un nome comune permette di rappresentare, tramite le strutture, entità logiche in cui le variabili comprese nella struttura rappresentano gli attributi di tali entità.

Per esempio con una struttura possiamo rappresentare l’entità libro i cui attributi potrebbero essere: titolo, autore, editore, prezzo. In tale caso la definizione potrebbe essere:

struct libro {

char titolo[50];

char autore[20];

char editore[20];

long int prezzo;

};

La sintassi del linguaggio prevede, dopo la parola chiave struct, un nome che identificherà la struttura (il tag della struttura). Racchiuse tra le parentesi vengono dichiarate le variabili che fanno parte della struttura (i membri della struttura). È bene chiarire che in questo modo si definisce la struttura logica libro, che descrive l’aspetto della struttura, e non un posto fisico dove conservare i dati. In pratica si può considerare come se si fosse definito, per esempio, come è composto il tipo int: ciò è necessario per poter dichiarare variabili di tipo int.

In C è possibile dichiarare la struttura assieme alle variabili, qui si preferisce tenere distinte le due cose per ragioni di organizzazione dei programmi come si vede nel frammento di programma successivo.

#include <stdio.h>

...

struct libro { /*1*/

char titolo[50];

char autore[20];

char editore[20];

long int prezzo;

};

...

main(){

libro lib1,lib2; /*2*/

...

gets(lib1.titolo); /*3*/

...

printf("%ld",lib2.prezzo); /*4*/

...

}

Nella riga 1 si dichiara il tipo struct libro. La dichiarazione è globale in modo che tutte le funzioni presenti possano accedere a tale definizione. Si evita così di ridefinire la struttura in ogni funzione.

Nella 2 si dichiarano due istanze (lib1 e lib2) di libro (due variabili di tipo struct libro).

La funzione della 3 effettua l’input nella componente titolo della istanza lib1. Per fare riferimento ad una componente deve infatti essere specificata l’istanza oltre che la componente: i due nomi sono separati dal punto. La specifica dell’istanza è indispensabile: ci sono infatti, nel caso in esame, due titolo (quello di lib1 e quello di lib2). Analogo discorso vale per la componente prezzo: la 4 infatti si occupa dell’output di tale componente relativamente all’istanza lib2.

inizio

Le tabelle: array di strutture

La struttura array consente di trattare insiemi di dati omogenei solo che, i dati rappresentati in un array, possono possedere un solo attributo. Per conservare dati individuati da più attributi occorre ricorrere alle tabelle.

Una tabella è un insieme finito di elementi ciascuno costituito da una chiave (informazione che serve per individuare l’elemento) e da un valore (informazioni associate alla chiave). Si può pensare la tabella come ad un quadro con le seguenti caratteristiche:

  1. Un numero di riga (chiave) che è associato alla riga e quindi la individua in maniera univoca
  2. Un numero finito di righe in ognuna della quale è conservato un elemento dell’insieme di dati rappresentato (il valore associato alla chiave)
  3. Un numero finito di colonne in ognuna delle quali è rappresentato un attributo dell’elemento conservato nella riga.

Per esempio potremmo conservare in una tabella i libri utilizzati in un anno scolastico. In ogni riga della tabella sono conservate le informazioni relative ad un libro. Ogni colonna della tabella conterrà un attributo del libro (per es. nella prima colonna ci sarà il titolo, nella seconda l’autore ecc..).

Nel linguaggio C una tabella è rappresentata tramite un array di strutture. Risolviamo, come esempio di applicazione degli array di strutture, il seguente problema:

Acquisiti i dati riguardanti i libri acquistati in un anno scolastico, si vogliono conoscere i dati dei libri che hanno avuto un costo superiore ad un input dato.

Dal punto di vista informatico è un problema di selezione: data una tabella si tratta di riempire una nuova tabella con le copie delle righe della prima tabella che soddisfano ad una certa condizione

/*

Dato un elenco di libri e un prezzo dato in input

fornisce dati sui libri che costano di più

*/

#include <stdio.h>

#define QLIB 5 /* Quantità libri caricati */

/* Implementazione delle strutture dati utilizzate */

struct libro { /*1*/

char titolo[50];

char autore[20];

char editore[20];

long int prezzo;

};

libro libreria[QLIB],libcost[QLIB]; /*2*/

int qlc=-1; /*3*/

/* Funzioni per l’elaborazione delle strutture dati */

void carica();

void ricerca(long int pz);

void comunica();

main(){

long int prezinp;

/* Caricamento libri e acquisizione prezzo */

printf("\n\nComunica titolo libri con");

printf("\ncosto maggiore di un input\n");

carica();

for(;;){ /*4*/

printf("\nPrezzo da confrontare (0 per finire)= ");

scanf("%ld",&prezinp);

if(!prezinp) /*5*/

break;

/* Ricerca libri con costo maggiore */

qlc=-1; /*6*/

ricerca(prezinp);

/* Output titolo libri con costo maggiore */

printf("\nLibri con prezzo maggiore di %ld\n",prezinp);

comunica();

}

return 0;

}

/* Caricamento libri */

void carica(){

int i;

printf("\nInserimento di %d libri",QLIB);

for(i=0;i<QLIB;i++){

fflush(stdin); /*7*/

printf("\nLibro n°%d\n",i+1);

printf("Titolo : ");

gets(libreria[i].titolo); /*8*/

printf("Autore : ");

gets(libreria[i].autore); /*8*/

printf("Editore : ");

gets(libreria[i].editore); /*8*/

printf("Prezzo : ");

scanf("%ld",&libreria[i].prezzo); /*8*/

}

}

/* ricerca libri con costo maggiore */

void ricerca(long int pz){

int i;

for(i=0;i<QLIB;i++){

if(libreria[i].prezzo>pz)

libcost[++qlc]=libreria[i]; /*9*/

}

}

/* Libri con prezzo maggiore */

void comunica(){

int i;

for(i=0;i<=qlc;i++){

puts(libcost[i].titolo); /*10*/

puts(libcost[i].autore); /*10*/

puts(libcost[i].editore); /*10*/

printf("%ld\n",libcost[i].prezzo); /*10*/

}

}

A cominciare dalla 1 sono implementate le strutture elaborate nel programma. Nella riga 1 si dichiara la struttura libro. Tale dichiarazione, come la dichiarazione della costante QLIB, è globale: tutte le funzioni conoscono tale struttura.

Nella 2 sono dichiarati due array di libro: libreria e libcost (due tabelle). Anche in questo caso si tratta di dichiarazioni globali: tutte le funzioni di manipolazione delle strutture possono accedere a tali variabili.

La variabile intera qlc dichiarata in 3 viene utilizzata per indicare la posizione dell’ultimo elemento inserito nella tabella di output. Attualmente la tabella non contiene righe e quindi tale variabile è inizializzata al valore specificato. L’assenza di una analoga variabile per la tabella di input dipende dal fatto che si ipotizza che la quantità di libri caricati nella tabella di input sia sempre QLIB: non è quindi necessario utilizzare una ulteriore variabile.

Dalla 4 inizia un ciclo senza fine (non sono previste condizioni per l’uscita dal ciclo: nella for ci sono solo istruzioni vuote). L’uscita dal ciclo è determinata dal verificarsi dall’evento specificato nella 5: l’input nullo nella variabile prezinp.

L’assegnazione della 6 è necessaria per azzerare la tabella di output e prepararla per contenere i risultati di una nuova elaborazione. Il programma infatti permette di specificare più volte il prezzo da cercare e per ogni prezzo fornisce l’elenco dei libri con le caratteristiche richieste.

La funzione fflush() utilizzata nella 7 serve per pulire il buffer associato ad un flusso di dati da eventuali caratteri residui da operazioni precedenti. Il nome simbolico stdin indica lo standard input cioè la tastiera. In definitiva si svuota la zona di memoria associata alla tastiera in modo da preparla per i nuovi dati in ingresso.

Nelle 8 vengono effettuati gli input delle componenti della riga i-esima della tabella libreria.

Nelle 9 in pratica si copia la riga i della tabella libreria nella riga qlc della tabella libcost, copiandone le corrispondenti componenti. L’utilizzo di strutture permette, con un'unica operazione di copia sul nome della struttura, di copiare tutte le componenti.

La funzione comunica restituisce in output la riga i-esima, con le sue componenti, nelle 10.

inizio

Strutture dei dati: generalità

Negli esempi che si sono esaminati si sono incontrati, oltre che dati elementari come, per esempio, quelli di tipo int, float o char, si sono esaminati due tipi di aggregati di dati: gli array e le strutture.

In questa sede ci si propone di esporre altri tipi di aggregati o, come si dice più correttamente altri tipi di strutture di dati. Una trattazione completa delle strutture dei dati va oltre gli scopi dei presenti appunti: qui si vogliono fornire i concetti generali, le operazioni fondamentali e le prime strutture dati.

Per prima cosa occorre distinguere tra:

Le strutture interne sono sostanzialmente riconducibili a due tipi:

  1. Struttura sequenziale: è costituita da un insieme definito di elementi, ognuno costituito da una o più celle di memoria, che sono fisicamente adiacenti in memoria. La caratteristica di essere la struttura composta da un numero definito di elementi, la rende adatta a conservare strutture astratte di tipo statico. Strutture cioè che restano pressocché uguali nel tempo: se si alloca spazio per n elementi, la quantità degli elementi effettivamente presenti in memoria sarà uguale o quasi uguale a tale numero. Il fatto poi che la lunghezza degli elementi sia la stessa per tutti porta ad una facilità di accesso ad un elemento qualsiasi della struttura. Se infatti si vuole conoscere l’indirizzo dell’i-esimo elemento basta calcolare: IND(xi)=INDb+(i-1)l dove con IND(xi) si è indicato l’indirizzo da trovare (l’elemento è xi), INDb è l’indirizzo base (l’indirizzo del primo elemento della struttura), i è la posizione relativa dell’elemento cercato ed l è la lunghezza comune. Il modo come è organizzata tale struttura se da una parte permette di rintracciare facilmente e in maniera rapida, qualsiasi elemento, dall’altra si presenta in maniera rigida: non solo il numero degli elementi non può essere variato (essendo gli elementi adiacenti è necessario predisporre una serie di locazioni di memoria consecutive nelle quali conservare la struttura), ma anche l’inserimento o l’eliminazione di un nuovo elemento fra due già esistenti risultano operazioni se non impossibili, quanto meno estramemente dispendiose (occorre infatti per esempio nel caso di inserimento fra l’elemento xi e l’elemento xi+1, se è possibile se cioè la struttura non è interamente occupata, spostare gli elementi dalla posizione i+1 in poi in modo da creare lo spazio per l’elemento da inserire e quindi procedere con l’inserimento).
  2. Struttura concatenata: è costituita da un insieme di elementi disposti in posizioni qualsiasi della memoria. Ogni elemento è costituito da una parte nella quale è contenuta l’informazione da conservare e un indicatore (puntatore) che fornisce l’indirizzo dell’elemento che deve intendersi successivo logicamente al corrente. L’ultimo elemento contiene, nel puntatore, un valore particolare (puntatore nullo) che permette di riconoscere l’elemento come l’ultimo della catena. Poiché non è possibile calcolare direttamente l’indirizzo di un elemento generico della struttura, per accedere ad esso è necessario, conoscendo l’indirizzo del primo elemento, percorrere sequenzialmente la catena finché non si trova l’elemento cercato. In questa struttura non è necessario conoscere in anticipo la quantità degli elementi che ne dovranno far parte: quando occorre inserire un nuovo elemento basta avere a disposizione una quantità di memoria tale da poter conservare l’elemento. L’aggancio dell’elemento alla struttura è facilitato dall’uso dei puntatori: il prossimo elemento non è quello che si trova conservato nelle locazioni successive rispetto all’elemento considerato (come nella struttura sequenziale), ma quello che segue logicamente cioè quello indicato dal puntatore. L’inserimento dell’elemento Ek fra l’elemento Ei e l’elemento Ei+1, per esempio, è una operazione che può essere compiuta in modo semplice tenendo presente che ogni elemento, per esempio Ek, è formato dall’informazione Ik e dal puntatore Pk. Per effettuare l’inserimento basta sistemare Ek in una zona di memoria disponibile, per esempio all’indirizzo IND(Ek), mettere nel puntatore Pk dell’elemento Ek il valore attualmente contenuto in Pi (in modo che Ei+1 segua Ek), mettere nel puntatore Ei il valore IND(Ek) in modo che Ek risulti il successivo di Ei. La struttura si presta, per le sue caratteristiche, a rappresentare strutture atratte di tipo dinamico; strutture cioè che cambiano frequentemente nel tempo. Un elemento della struttura potrà avere anche un puntatore al precedente e, in questo caso, si parlerà di catena bidirezionale, così come si potrà avere l’ultimo elemento che punta al primo e, in questo caso, si parlerà di catena circolare.

Per riassumere brevemente si può dire che la struttura sequenziale presenta il vantaggio di fornire accesso immediato a qualsiasi elemento della struttura a costo di una rigidità della struttura (numero elementi da conoscere all’atto dell’allocazione, difficoltà di aggiornamento della struttura). La struttura concatenata, al contrario, può conservare elementi finché c’è spazio in memoria, le operazioni di inserimento o cancellazione di elementi vengono svolte in maniera agevole, ma risulta impossibile l’accesso diretto ad un elemento qualunque della struttura.

inizio

Strutture astratte

Gli array, le prime e fondamentali strutture astratte, sono già state introdotte e si è inoltre parlato della loro implementazione in linguaggio C, così come sono state trattate le tabelle. Altre due strutture di cui si vedranno in seguito le implementazioni e le operazioni più comuni sono le pile e le code. Di grafi e alberi si accennerà solo alle definizioni fondamentali.

La pila o stack è una lista di elementi (insieme di elementi ordinati) in cui tutti gli inserimenti o le estrazioni di nuovi elementi avvengono ad un estremo della lista (la cima). La pila viene anche spesso indicata, a causa della gestione degli elementi, come lista LIFO (Last In First Out cioè l’ultimo inserito sarà il primo estratto). In pratica in una pila sono definite due operazioni: l’inserimento in cima di un nuovo elemento (push) e l’estrazione sempre dalla cima di un elemento (pop).

La coda è una lista di elementi in cui gli inserimenti avvengono dopo l’ultimo elemento (fondo della coda) e le estrazioni avvengono dall’estremo opposto (testa della coda). La coda viene anche indicata come lista FIFO (First In First Out cioè il primo inserito sarà anche il primo estratto).

Il grafo è costituito da un insieme di nodi (le informazioni) e archi (collegamenti fra le informazioni). Ogni nodo può essere collegato a più altri nodi stabilendo così più modi di collegare logicamente i dati rappresentati nella struttura. Per esempio se in ogni nodo sono rappresentati i dati riguardanti un alunno di un istituto scolastico, un arco potrebbe portare al prossimo alunno della stessa classe frequentata e un altro arco potrebbe portare al prossimo alunno che risiede nella stessa città dell’alunno preso in esame. In questo modo un cammino (successione di nodi collegati) porta alla conoscenza di tutti gli alunni di una stessa classe e un secondo cammino porta all’elenco degli alunni residenti in un determinato paese. Se gli archi sono orientati (cioè se, essendo collegati i nodi ni ed ni+1, si può andare da ni ad ni+1 ma non viceversa), il grafo si dice orientato.

L’albero è un grafo orientato che presenta le seguenti caratteristiche: esiste un nodo a cui non arrivano ma da cui si dipartono archi (radice), ogni nodo ha un solo arco che arriva ad esso ma può avere più archi che partono da esso, esistono nodi (foglie o nodi terminali) a cui porta un arco ma da cui non partono archi. Gli alberi vengono utilizzati per rappresentare strutture gerarchiche; nella pratica, anche al di fuori delle applicazioni informatiche, si trovano spesso applicazioni di tale struttura (alberi genealogici, famiglie zoologiche).

inizio

Array e aritmetica dei puntatori

Si è già fatto notare che, nel linguaggio C, il nome di un array è praticamente il puntatore al primo elemento della struttura ossia, per quanto detto precedentemente, l’indirizzo base. Ciò porta alla considerazione che l’elemento generico del vettore è accessibile oltre che, come già osservato, cioè come l’elemento di posizione i della struttura, anche come l’elemento il cui indirizzo può essere calcolato a partire dall’indirizzo base, dalla lunghezza dell’elemento e dalla posizione relativa sebbene, per motivi legati alla comprensibilità delle istruzioni, è più opportuno accedere agli elementi di un array utillizzando l’indice.

Programma A

Programma B

#define QEL 5...

void carica(int *v1){ int i; for(i=0;i<QEL;i++){ printf("\nElemento n°%d ",i+1);

scanf("%d",(v1+i));

}

}

...void comunica(const int *v1){ int i; for(i=0;i<QEL;i++) printf("%d ",*(v1+i));}

 

#define QEL 5...

void carica(int *v1){ int i; for(i=0;i<QEL;i++){ printf("\nElemento n°%d ",i+1);

scanf("%d",&v1[i]);

}

}

...void comunica(const int *v1){ int i; for(i=0;i<QEL;i++) printf("%d ",v1[i]);}

 

L’input e l’output, dell’elemento generico di un array di elementi di tipo int, nel Programma B viene effettuato al solito modo. Nel Programma A l’input viene effettuato specificando l’indirizzo dove deve essere conservato il dato. Il nome v1 è un puntatore ed è bene chiarire che sommare il valore di i a tale puntatore significa, come fatto rilevare quando si è trattata la struttura sequenziale, spostarsi all’i-esimo elemento. In altri termini, per esempio: a+1 se a è una variabile di tipo int vuol dire sommare il valore 1 al valore esistente, se invece a è un puntatore a int significa incrementare l’indirizzo contenuto in a di tante posizioni quante ne sono previste dal tipo int.Nel caso dell’istruzione di input l’istruzione v1+i equivale a INDb+(i-1)l infatti v1 rappresenta l’indirizzo base, i-1 nel nostro caso si traduce in i poiché si parte dal valore 0, in quanto a l questo è contenuto implicitamente nella dichiarazione del puntatore (è dichiarato come puntatore ad int, quindi il compilatore conosce la lunghezza degli elementi della struttura). In questo modo l’array viene gestito nella sua rappresentazione come struttura interna.

Nell’input non è utilizzato l’operatore & poiché in ciò che è scritto è già espresso un indirizzo. Un discorso simile occorre farlo per l’output: v1+i è un puntatore e quindi al programma interessa il valore contenuto nella memoria puntata.

Sui puntatori possono essere quindi effettuate operazioni aritmetiche, è questo infatti quello a cui si fa riferimento quando si parla di aritmetica dei puntattori, solo che bisogna tenere presente il senso che assumono tali operazioni: aggiungere il valore 1 a un puntatore vuol dire spostarsi di tante locazioni di memoria quante ne bastano per trovare il prossimo elemento dello stesso tipo. Da questo punto di vista dovrebbe risultare chiara, per esempio, la convenzione utilizzata nel passaggio di un array a più dimensioni ad una funzione: vengono infatti specificate tutte le dimensioni tranne la prima. Tutto ciò è comprensibile se si tiene presente che un array, per esempio a due dimensioni, è conservato in memoria per righe successive (la prima riga, poi la seconda ecc..); in questo caso la conoscenza della quantità di colonne serve per acquisire conoscenza sulle dimensioni del singolo elemento (in questo caso un elemento è composto da una intera riga dell’array).

inizio

Gestione di una pila

La pila può essere implementata in memoria utilizzando sia una struttura sequenziale se, per esempio, si prevede una dimensione massima che potrà avere la struttura, sia una struttura concatenata. Nel programma seguente viene utilizzata una struttura sequenziale per gestire una pila di libri. In questo programma vengono messe in evidenza principalmente le funzioni per la gestione di una pila.

/*

Gestione di uno STACK con un elenco di libri

*/

#include <stdio.h>

/* Implementazione dello Stack */

#define DIMSTACK 8 /*1*/

struct libro {

char titolo[50];

char autore[20];

char editore[20];

long int prezzo;

};

libro libreria[DIMSTACK];

int cima=-1;

/* Funzioni per la gestione dello Stack */

int pieno(); /*2*/

void push(const libro *lib); /*3*/

int vuoto(); /*2*/

libro pop(); /*3*/

/* Altre funzioni del programma */

void inserisci();

void estrai();

main(){

int scelta;

for(;;){

/* Menu operazioni disponibili */

printf("\nGestione di una pila di libri\n"); /*4*/

printf("\n1) Inserimento di un libro");

printf("\n2) Estrazione di un libro");

printf("\n0) Fine elaborazione\n");

printf("\nScelta operazione (1,2,0) ");

scanf("%d",&scelta);

if(!scelta) /*5*/

break;

/* Richiama funzione scelta */

switch(scelta){

case 1:

inserisci();

break;

case 2:

estrai();

}

}

return 0;

}

/* Inserimento di un libro nella pila */

void inserisci(){

libro buflib; /*6*/

if(pieno()){ /*7*/

printf("\n\aPresenti %d elementi",DIMSTACK);

printf("\nPila piena: inserimento impossibile");

}else{

printf("\nInserimento di un libro"); /*8*/

fflush(stdin);

printf("\nTitolo : ");

gets(buflib.titolo);

printf("Autore : ");

gets(buflib.autore);

printf("Editore : ");

gets(buflib.editore);

printf("Prezzo : ");

scanf("%ld",&buflib.prezzo);

push(&buflib); /*9*/

}

}

/* Estrazione di un libro */

void estrai(){

libro buflib;

if(vuoto()) /*10*/

printf("\n\aPila vuota: estrazione impossibile");

else{

buflib=pop(); /*11*/

puts(buflib.titolo);

puts(buflib.autore);

puts(buflib.editore);

printf("%ld\n",buflib.prezzo);

fflush(stdin);

while(!getchar()=='\n'); /*12*/

}

}

/* Funzioni standard per la gestione di uno stack:

funzione che ritorna lo stato dello stack

*/

int pieno(){ /*13*/

if(cima==DIMSTACK-1)

return 1;

else

return 0;

}

/* Inserimento di un elemento nella pila */

void push(const libro *lib){ /*14*/

libreria[++cima]=*lib;

}

/* Funzione che ritorna lo stato dello stack */

int vuoto(){ /*15*/

if(cima==-1)

return 1;

else

return 0;

}

/* Prelievo di un elemento dalla pila */

libro pop(){ /*16*/

return libreria[cima--];

}

A cominciare dalla 1 viene definita la struttura: la dimensione massima dello stack, la struttura dell’elemento generico, la struttura sequenziale su cui verrà implementata la pila. Il puntatore cima, attualmente inizializzato al valore –1, sarà l’indice utilizzato per rintracciare la posizione dell’elemento su cui effettuare le operazioni. Si ricorda che, in una pila, le operazioni vengono effettuate sempre ad un estremo.

Nelle righe 2 e 3 sono indicate le funzioni utilizzate per la manipolazione della struttura. Le funzioni possiamo raggrupparle in due categorie: le 2 restituiscono informazioni sulla struttura, le 3 forniscono le operazioni ammesse sulla struttura. Qui finisce la definizione della struttura fornita in termini di tipo di dati che ne fanno parte e di funzioni per la loro manipolazione.

Il programma presentato offre un menu di operazioni possibili (visualizzato a cominciare da 4) da cui si esce, tramite 5, digitando un opportuno valore. Il programma consente solo operazioni di inserimento ed estrazione di un libro dalla pila.

La funzione di inserimento prepara nella 6 un buffer su cui conservare temporaneamente il libro da inserire nella struttura. Prima di effettuare l’inserimento nella pila è necessario assicurarsi che ci sia posto: ciò viene fatto, effettuando nella 7 una chiamata alla funzione pieno, affinché si sappia se è possibile effettuare l’inserimento. L’inserimento effettivo viene svolto ricevendo, cominciando da 8, i dati forniti in input nella memoria temporanea buflib e comunicando nella 9 alla funzione push l’indirizzo di tale area di memoria.

La funzione di estrazione di un elemento dalla pila è simile alla funzione di inserimento. Si interroga la pila al fine di conoscere se ci sono elementi da prelevare (linea 10). Se ci sono elementi da prelevare, si riceve dalla funzione pop, chiamata in 11, l’elemento cercato che viene conservato in un buffer appositamente predisposto.

La funzione getchar chiamata nella 12 serve per prelevare un carattere dal buffer di tastiera. Qui, dopo aver pulito il buffer di tastiera, si aspetta che arrivi da tastiera un carattere di newline, utilizzando un ciclo che preleva caratteri finché non si trova quello desiderato.

La funzione pieno, definita nella 13, ritorna al chiamante un indicatore sullo stato della pila: se cima contiene l’indice dell’ultimo elemento la pila è piena.

La funzione push, definita in 14, dopo aver aggiornato cima copia nello stack l’elemento attualmente conservato in una memoria temporanea. Dal modo come è definita tale funzione si può dedurre, come d’altra parte riportato nel programma, che l’operazione di inserimento non controlla se effettivamente c’è posto nella struttura. La funzione, per poter funzionare correttamente, è necessario che sia chiamata condizionatamente ad una risposta ottenuta dal richiamo della funzione pieno. La funzione riceve come parametro passato un puntatore al buffer che contiene l’elemento da inserire. Tale parametro poteva essere anche una variabile di tipo libro. La scelta, nel caso di strutture, di passare un puntatore al posto di una variabile è comune nei programmi in C: passando un puntatore si effettua una elaborazione più veloce (non si spreca tempo nell’effettuare una copia della struttura passata nel parametro. Si consideri che una struttura può contenere parecchi membri) ed inoltre non si occupa memoria per conservare la struttura in una variabile locale.

La funzione vuoto, definita in 15, restituisce indicazioni sulla presenza di elementi nello stack. Per considerazioni analoghe a quelle fatte precedentemente, è necessario chiamarla prima di effettuare l’inserimento.

La funzione pop della 16 ha un funzionamento analogo alla push, solo che qui le operazioni hanno verso opposto: dalla pila al buffer.

inizio

Gestione di una coda

La gestione di una coda presenta dei punti in comuni con la gestione della pila, le funzioni che verranno presentate avranno dei punti in comune con le corrispondenti della pila.

Rispetto alla gestione della pila, la coda presenta principalmente una differenza sostanziale che comporta delle soluzioni implementative differenti rispetto a quelle usate nel primo caso.

Per i motivi espressi prima è opportuno, in questo caso, utilizzare una struttura circolare. Se la struttura sequenziale prevede n elementi si conviene di adottare le seguenti convenzioni:

Sarà inoltre opportuno fare in modo che testa punti una posizione prima del primo elemento e che fondo punti all’ultimo inserito. Così facendo se da una parte si sarà costretti a non utilizzare un elemento della struttura (quello a cui punta testa), dall’altra la condizione testa == fondo sarà indicativa del fatto che la coda è vuota.

In seguito si esaminerà la nuova struttura con le sue caratteristiche. Il resto del programma può essere identico a quello visto prima per la gestione dello stack.

/* Implementazione della Coda */

#define DIMCODA 8 /*1*/

struct libro {

char titolo[50];

char autore[20];

char editore[20];

long int prezzo;

};

libro libreria[DIMCODA];

int testa=-1;

int fondo=-1;

/* Funzioni per la gestione della Coda */

int piena(); /*2*/

void aggiungi(const libro *lib);

int vuota();

libro elimina();

/* Funzioni standard per la gestione di una coda:

funzione che ritorna informazioni sullo stato della coda

*/

int piena(){

int numel;

numel=(fondo>=testa)?(fondo-testa):(fondo+DIMCODA-testa); /*3*/

if(numel==DIMCODA-1) /*4*/

return 1;

else

return 0;

}

/* Aggiunge un elemento alla coda */

void aggiungi(const libro *lib){

fondo = ++fondo % DIMCODA; /*5*/

libreria[fondo]=*lib; /*6*/

}

/* Funzione che ritorna informazioni sullo stato della coda */

int vuota(){

if(testa==fondo) /*7*/

return 1;

else

return 0;

}

/* Elimina un elemento dalla coda */

libro elimina(){

testa = ++testa % DIMCODA; /*8*/

return libreria[testa]; /*9*/

}

A cominciare da 1 è definita la struttura che è molto simile alla pila tranne per il fatto che qui ci sono due puntatori. Le funzioni di gestione, il cui prototipo si trova in 2, sono anche esse formalmente uguali a quelle di gestione dello stack: cambieranno solo le operazioni di aggiornamento dei puntatori.

La funzione piena calcola in 3 il numero di elementi contenuti come differenza dei valori contenuti nei due puntatori della struttura. Poiché la struttura è circolare potrebbe essere che il valore di fondo sia minore del valore contenuto in testa: in tal caso bisogna effettuare una correzione su tale valore. In ogni caso fondo deve essere inteso maggiore di testa. In 4 viene controllato se la coda è piena; è già stato fatto osservare che una posizione di memoria resta inutilizzata.

Nella 5 si calcola il valore di fondo in relazione al fatto che si sta utilizzando una struttura circolare. Viene effettuata una operazione in modulo (l’operatore % è appunto l’operatore che restituisce il resto della divisione intera fra gli operandi): prima viene effettuato l’aggiornamento di fondo ad indicare che c’è un nuovo elemento, poi si calcola il resto in modo tale che il risultato sia sempre un numero compreso fra 0 e DIMCODA-1. L’elemento, attualmente conservato in un deposito temporaneo, viene poi copiato, in 6, nella posizione individuata da fondo.

Come osservato prima la 7 fornisce la condizione per sapere se la coda è vuota.

L’elemento da eliminare si trova, come messo in evidenza in 9, nella posizione testa che è calcolata in 8 sempre tenendo conto che si tratta di una struttura circolare.

 

Inizio