Esercizio

ESERCIZIO NO. 2 : reverse CON RICORSIONE Separazione tra dati e algoritmi ⇒ isolamento delle caratteristiche implementative di un oggetto dalle interfacce e dalle funzionalità del client corrispondente. ⇒ Definizione di un ADT in un programma mono-modulo Data una struttura dati sequenziale generica, il programma la deve rovesciare in modo ricorsivo. Una struttura dati sequenziale può essere: -

lista

-

array

-

file

Una sequenza di oggetti elementari è un concetto astratto. Le operazioni effettuate su di essa devono essere in qualche modo indipendenti dalla stessa. Le operazioni possibili, che costituiscono l’interfaccia, sono: 1. inizializzazione della sequenza → InitSequence Se la sequenza è implementata come •

una lista ⇒ InitSequence porta a NULL il puntatore che la rappresenta

•

un array ⇒ InitSequence ne azzera tutti gli elementi

•

un file ⇒ InitSequence lo apre in scrittura

⇒ Il prototipo della funzione deve essere: void InitSequence (sequence *, char); dove sequence * → puntatore alla sequenza char → parametro che indica il modo richiesto (R, read, o W, write) 2. scansione della sequenza → Next Next deve incrementare di 1 lo scansore della sequenza 130

Se la sequenza è implementata come •

una lista ⇒ Next sposta lo scansore all’elemento successivo, dopo aver controllato che lo stesso scansore non sia NULL

•

un array ⇒ Next incrementa lo scansore di 1, ma non deve andare oltre le dimensioni dell’array

•

un file ⇒ Next sposta il puntatore a file avanti di 1

3. selezione di un elemento della sequenza → GetElement GetElement ritorna l’elemento corrente della sequenza aperta in lettura e non completamente scandita ⇒ Il prototipo della funzione deve essere: elem GetElement (sequence *);

4. inserimento di un elemento nella sequenza → PutElement PutElement inserisce un elemento nella posizione corrente della sequenza aperta in scrittura ⇒ Il prototipo della funzione deve essere: void PutElement (sequence *, elem e); Se la sequenza è, però, un file, la funzione ritorna un intero dato dal sistema operativo. 5. terminazione della sequenza → FineSequence FineSequence ritorna TRUE oppure FALSE se la sequenza è, o meno, stata completamente scandita ⇒ Il prototipo della funzione deve essere: boolean FineSequence (sequence *);

Il rovesciamento della sequenza è un client dell’interfaccia così definita ⇒ chiama le funzioni suddette per ottenere un certo risultato. Il client accede alla sequenza astratta attraverso le operazioni definite, ma non sa come è implementata. 131

Inseq → sequenza di input su cui leggiamo Outseq → sequenza di output su cui scriviamo void reverse (sequence Inseq, sequence Outseq) { elem e;

If (!FineSequence(Inseq)) { e = GetElement;

/* e è una variabile locale; è l’elemento base della sequenza ⇒ può essere un int, un float, un char, una stringa,… */ /* se la sequenza di input non è terminata, leggo l’elemento corrente (⇒ lo appoggio su e) */

Next(Inseq);

/* incremento la sequenza di input */

Reverse (Inseq, Outseq);

/* rovescio */

PutElement (Outseq, e);

/* scrivo e sulla sequenza di output */ /* incremento la sequenza di output */

Next (Outseq); } }

La chiamata ricorsiva consente: •

la lettura della sequenza di input

•

l’appoggio dell’elemento letto su ogni attivazione della funzione

Alla fine della sequenza di input, sullo stack la sequenza è interamente rovesciata ⇒ si può scrivere sulla sequenza di output Un altro client è il main, che deve poter inizializzare entrambe le sequenze di input e di output ⇒ la struttura dati che implementa la sequenza deve essere passata per indirizzo void main() { initsequence (inseq, ‘r’); initsequence (outseq, ‘w’); reverse(inseq, outseq); } Il programma, essendo mono-modulo, non permette di dividere in modo preciso la parte di implementazione (concreta) di una sequenza, dalla parte di utilizzo.

132

typedef InitSequence FineSequence

reverse

main

typedef deve definire concretamente l’oggetto: sequenza come lista ⇒ struct costituita da •

testa della lista

•

scansore dell’elemento corrente

•

modo di accesso

⇒ 2 puntatori: 1) alla lista 2) all’elemento corrente sequenza come array ⇒ struct costituita da •

array di lunghezza predefinita (vs. lista)

•

scansore dell’elemento corrente

•

modo di accesso

133

#include <stdio.h> #define SIZE 15 typedef char elem;

/* componente base dell'array di caratteri della sequenza */

/* definizione concreta dell'oggetto sequenza */ typedef struct sequence{ elem Data[SIZE]; /* sequenza, incognita al main; è un vettore di elementi */ int CurrentEl; /* scansore del vettore */ char AccessMode; /* modo di accesso al vettore */ } Sequence; typedef enum {FALSE, TRUE} boolean; elem *local; Sequence Input, Output; /* prototipi delle funzioni */ void InitSeq(Sequence *, char); void PutElem(Sequence *, elem); boolean FineSeq(Sequence *); elem GetElem(Sequence *); elem Next(Sequence *); void Print(Sequence *); void reverse (Sequence *, Sequence *); /* inizializza la sequenza passata sia in lettura che in scrittura */ void InitSeq (Sequence *S, char modo) { (*S).AccessMode = modo; (*S).CurrentEl = 0; if (modo == 'R') { while(FineSeq(S) == FALSE) { PutElem(S, local[(*S).CurrentEl]); Next(S); } (*S).CurrentEl = 0; } else { while(FineSeq(S) == FALSE) { PutElem(S, ' '); Next(S); } 134

(*S).CurrentEl = 0; } }

/* inserisce un elemento nella posizione corrente */ void PutElem(Sequence *S, elem el) { (*S).Data[(*S).CurrentEl] = el; }

/* prende un elemento dalla posizione corrente */ elem GetElem(Sequence *S) { elem el; return (el = (*S).Data[(*S).CurrentEl]); }

/* indica se la sequenza è stata tutta scandita */ boolean FineSeq(Sequence *S) { if ((*S).CurrentEl == SIZE) return (TRUE); else return (FALSE); }

/* incrementa lo scansore di uno */ elem Next (Sequence *S) { if (FineSeq(S) == FALSE) return (((*S).CurrentEl)++); }

/* stampa a video la sequenza */ void Print(Sequence *S) { (*S).CurrentEl = 0; while (FineSeq(S) == FALSE) { printf("%c", (*S).Data[(*S).CurrentEl]); (*S).CurrentEl++; } (*S).CurrentEl = 0;

135

printf(“\n\n”); }

/* client di Sequence: non sa come è fatta */ void reverse (Sequence *InputSeq, Sequence *OutputSeq) { elem e; if (FineSeq(InputSeq) == FALSE) { e = GetElem(InputSeq); Next(InputSeq); reverse(InputSeq, OutputSeq); PutElem(OutputSeq, e); Next(OutputSeq); } }

/* client di sequence: non sa come è fatta */ int main() { local = "ciao a tutti!!!"; InitSeq(&Input, 'R'); InitSeq(&Output, 'W'); reverse(&Input, &Output); printf("\n\nSequenza iniziale:\n\t"); Print(&Input); printf("\n\nSequenza rovesciata:\n\t"); Print(&Output); return (0); }

136