Alcuni esercizi di programmazione in linguaggio C

Indice degli argomentiAlcuni esercizi di programmazione in linguaggio C.......................................................................1

Indice degli argomenti......................................................................................................................1Premessa...........................................................................................................................................2Dati strutturati...................................................................................................................................2

Uso di typedef..............................................................................................................................2Strutture di controllo........................................................................................................................5

Uso di if condizionale...................................................................................................................5Ciclo for per gestire una matrice..................................................................................................6Cicli equivalenti...........................................................................................................................7

Vettori e puntatori............................................................................................................................7Ricerca di una stringa in un vettore di stringhe (vers. 1).............................................................8Ricerca di una stringa in un vettore di stringhe (vers. 2 della sola funzione)..............................9Strutture pila e coda (statiche) realizzate con un vettore..............................................................9Passaggio di parametri al main...................................................................................................12

Visibilità e funzioni........................................................................................................................13Visibilità delle variabili in blocchi annidati...............................................................................13Potenza.......................................................................................................................................13Calcolo delle radici di un’equazione di 2° grado.......................................................................14Scambio dei valori di due variabili (ver. 1)................................................................................15Scambio dei valori di due variabili (ver. 2)................................................................................16

Dati strutturati.................................................................................................................................18Ricorsività......................................................................................................................................18

Massimo Comun Divisore..........................................................................................................18Media ricorsiva...........................................................................................................................20Polinomio...................................................................................................................................20

Algoritmi vari.................................................................................................................................21Ricerca binaria............................................................................................................................21Operazioni diverse su strighe di caratteri...................................................................................22

Strutture dinamiche........................................................................................................................25Liste............................................................................................................................................25Pile e code (strutturate come lista).............................................................................................28Alberi..........................................................................................................................................32

Input Output...................................................................................................................................35Esempio di scrittura, lettura e aggiornamento di un file............................................................35

1

PremessaQuanto avete sotto gli occhi non è un manuale di linguaggio C, non serve per imparare a programmare, non è nemmeno un eserciziario completo ma è semplicemente un insieme scelto e annotato di esempi tratti dalle esercitazioni o proposti nei temi d’esame del corso di Informatica A di Ingegneria Gestionale. Si sono cercati di evidenziare i punti che presentano le maggiori difficoltà e sono causa di errori ricorrenti per gli studenti, le cui osservazioni e domande, anche se talvolta a loro insaputa, hanno consentito la raccolta. Si ringraziano anticipatamente quanti vorranno contribuire a migliorarla.Gli esercizi, suddivisi in base all’argomento, sono riportati in forma completa, ad esempio nel caso di una funzione viene inclusa anche la codifica del modulo che la richiama. Così se da un lato non si evita una certa ripetitività e monotonia, dall’altro si facilita l’estrazione del singolo esercizio e quindi la modifica e il test. La suddivisione è in parte arbitraria in quanto lo stesso esempio potrebbe spesso trovarsi in capitoli diversi. Alle soluzioni compatte ed eleganti sono state preferite quelle più facilmente leggibili.Per la codifica si è usato il formato di carattere courier new, siete invitati ad usarla come punto di partenza per le vostre variazioni e sperimentazioni: ogni linguaggio, naturale o artificiale che sia, si apprende infatti soprattutto con la pratica. È opinione di chi scrive che lo studio di un linguaggio di programmazione (nella fattispecie il C) abbia anche un valore formativo nell’apprendimento di un metodo per affrontare i problemi che si presentano nella realtà lavorativa.Concludendo questo lavoro ha un duplice scopo: di fornire una serie di programmi completi come input per esperimenti di laboratorio e di offrire alla vista un insieme di codifiche che sono più facili da leggersi da un foglio (o dallo schermo di un computer) che dalla lavagna durante le esercitazioni.

Dati strutturati

Uso di typedefIl modo, a mio parere più chiaro, per definire un tipo di dato fornito di struttura è quello di usare le parole chiave typedef struct. Il programma che segue definisce (nel file .h) alcuni tipi di dati e alcune funzioni, che si possono pensare come modelli informatici di note entità ed operatori della geometria elementare del piano. Si spera che la rappresentazione di un mondo geometrico che tutti conoscono aiuti ad eliminare anche nella sua corrispondenza informatica ogni residua ambiguità.Per illustrare le due possibili modalità di chiamata, le funzioni che richiedono in input un triangolo sono state implementate in modo differente e cioè ad AreaT viene passato come parametro il “puntatore” alla variabile “triangolo”, a Baricentro invece, viene passato il valore. Perché le funzioni possano ritornare al chiamante non solo un numero ma anche un punto bisogna che questo sia stato definito come un tipo dato. Chi legge è invitato ad accrescere questa “libreria” di funzioni a suo piacimento, si consiglia per esempio di programmare il calcolo del punto di intersezione fra due rette che presenta qualche interesse anche dal punto di vista informatico a causa dei diversi casi particolari che si possono presentare.Il file .c, esempio di come si può costruire un programma di test della codifica di una funzione, merita qualche commento, in quanto ha una struttura che ritroveremo in seguito. Esso è composto da un ciclo while che si interrompe quando viene fornita la risposta ‘0’, le altre risposte fanno prendere al processo diversi rami alternativi (comando switch case), ciascuno dei quali corrisponde all’esecuzione di una diversa funzione.

2

file: piano.h/* costante booleana */typedef enum {falso, vero} boolean;

/* punto nel piano */typedef struct {

float x;float y;} punto;

/* retta (o segmento) per due punti */ typedef struct {

punto p1;punto p2;} segmento;

/* triangolo (individuato dai suoi vertici) */typedef struct {

punto p1;punto p2;punto p3;} triangolo;

/* verifica se tre punti sono allineati */ boolean Ver_All(punto p1, punto p2, punto p3){ boolean all = falso; float temp1, temp2; temp1 = (p1.x - p2.x) * (p1.y - p3.y); temp2 = (p1.x - p3.x) * (p1.y - p2.y);

if(temp1 == temp2) all = vero; return all;}

/* calcolo del punto medio di un segmento */punto PuntoM (segmento seg_) {

punto punto_medio;punto_medio.x = (seg_.p1.x + seg_.p2.x) / 2.0;punto_medio.y = (seg_.p1.y + seg_.p2.y) / 2.0;return (punto_medio);

}

/* calcolo dell'area (con segno) di un triangolo (passato mediante puntatore) */float AreaT (triangolo *ptri) {

return((ptri->p1.x * ptri->p2.y +ptri->p3.x * ptri->p1.y +ptri->p2.x * ptri->p3.y -ptri->p3.x * ptri->p2.y -ptri->p1.x * ptri->p3.y -ptri->p2.x * ptri->p1.y) / 2.0);

}

/* calcolo del baricentro di un triangolo (passato come valore) */punto Baricentro (triangolo tri){

punto punto_b;punto_b.x = (tri.p1.x + tri.p2.x + tri.p3.x) / 3.0;

3

punto_b.y = (tri.p1.y + tri.p2.y + tri.p3.y) / 3.0;return (punto_b);

}

/* stampa delle coordinate di un punto */void StampaP (punto P){

if ((P.x != NULL) && (P.y != NULL))printf("\n x: %5.2f y: %5.2f\n", P.x, P.y);

else printf("\n punto invalido o inesistente\n");

}

file: piano.c#include <stdio.h>#include "piano.h"

void main() {punto punto1, punto2, punto3, punto4;segmento segmento1;triangolo triangolo1;boolean allineamento;int scelta = -1;while(scelta != 0) {printf("\n 0: per finire, 1: allineamento, 2: punto medio,\n 3: area

triangolo, 4: baricentro\n");scanf("%d", &scelta);switch(scelta) {

case 1:printf("\nAscissa e ordinata del primo punto: ");scanf("%f %f", &punto1.x, &punto1.y);printf("\nAscissa e ordinata del secondo punto: ");scanf("%f %f", &punto2.x, &punto2.y);printf("\nAscissa e ordinata del terzo punto: ");scanf("%f %f", &punto3.x, &punto3.y);

allineamento = Ver_All(punto1, punto2, punto3);if(allineamento == vero)

printf("\ni punti sono allineati");elseprintf("\ni punti non sono allineati");

break;

case 2:printf("\nAscissa e ordinata del primo punto: ");scanf("%f %f", &segmento1.p1.x, &segmento1.p1.y);printf("\nAscissa e ordinata del secondo punto: ");scanf("%f %f", &segmento1.p2.x, &segmento1.p2.y);

punto4 = PuntoM(segmento1);StampaP(punto4);break;

case 3:printf("\nAscissa e ordinata del primo punto: ");scanf("%f %f", &triangolo1.p1.x, &triangolo1.p1.y);printf("\nAscissa e ordinata del secondo punto: ");scanf("%f %f", &triangolo1.p2.x, &triangolo1.p2.y);printf("\nAscissa e ordinata del terzo punto: ");scanf("%f %f", &triangolo1.p3.x, &triangolo1.p3.y);

4

printf("\n area del triangolo: %5.2f", AreaT(&triangolo1));break;

case 4:printf("\nAscissa e ordinata del primo punto: ");scanf("%f %f", &triangolo1.p1.x, &triangolo1.p1.y);printf("\nAscissa e ordinata del secondo punto: ");scanf("%f %f", &triangolo1.p2.x, &triangolo1.p2.y);printf("\nAscissa e ordinata del terzo punto: ");scanf("%f %f", &triangolo1.p3.x, &triangolo1.p3.y);

punto4 = Baricentro(triangolo1);StampaP(punto4);break;}

} }

Strutture di controllo

Uso di if condizionaleIl programma usoif illustra la condizione if, in esso l’istruzione scanf ritorna nella variabile cc il numero di dati letti correttamente, basta perciò inserire un valore che non sia intero per uscire dal ciclo e terminare così il ciclo di esecuzione del programma.

file: usoif.c/* ordinamento di tre numeri (esempio di if) */#include<stdio.h>void main() { int a, b, c, cc;

printf("\nfornisci i tre interi da ordinare): "); cc = scanf("%d %d %d", &a, &b, &c);

while(cc == 3) { if((a <= b) && (b <= c)) printf("\n %d %d %d", a, b, c); else if((a <= c) && (c <= b)) printf("\n %d %d %d", a, c, b); else if((b <= a) && (a <= c)) printf("\n %d %d %d", b, a, c); else if((b <= c) && (c <= a)) printf("\n %d %d %d", b, c, a); else if((c <= a) && (a <= b)) printf("\n %d %d %d", c, a, b); else printf("\n %d %d %d", c, b, a); printf("\nfornisci i tre interi da ordinare): "); cc = scanf("%d %d %d", &a, &b, &c); }}

5

Ciclo for per gestire una matriceIl ciclo for è il modo più semplice per percorrere una struttura a una o più dimensioni (vettore, matrice, array). Il programma che segue calcola e stampa i coefficienti dello sviluppo binomiale fino alla decima potenza, usando il noto algoritmo che consiste nel calcolo dei coefficienti dello sviluppo della potenza n-ma sommando a due a due da quelli della potenza n-1-ma. Il programma è composto da due coppie di cicli for annidati dei quali: quello esterno (indice i) visita le righe della matrice M, quello interno percorre gli elementi della riga dal primo (j = 0), fino alla diagonale principale (j = i).

file: usofor.c/* uso del ciclo for con una matrice calcolo dei coefficienti dello sviluppo della potenza di un binomio */#include<stdio.h>#define DIM 11

void main() { long int M[DIM][DIM]; int i, j;

/* costruzione della matrice */ for(i = 0; i < DIM; i++) for(j = 0; j < i+1; j++) { if((j == 0)||(j == i)) M[i][j] = 1; else

M[i][j] = M[i-1][j-1] + M[i-1][j]; }

/* stampa della matrice */ for(i = 0; i < DIM; i++) { for(j = 0; j < i+1; j++)

printf(" %4ld ", M[i][j]); printf("\n"); }}

Output della esecuzione di usofor:

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1

6

Cicli equivalentiSi possono costruire strutture logiche equivalenti con cicli for, while e do-while, la scelta dipende dalla convenienza e dal gusto personale. Nell’esempio che segue viene riscritto in tre modi l’algoritmo di calcolo della potenza di un numero (con esponente intero).(prima di ogni insieme di istruzioni dovranno trovarsi le seguenti dichiarazioni e istruzioni:

float base, ris;int espon;

if(espon < 0) { espon = -espon;

base = 1.0 / base; } )

/* (1) ciclo for */ for(ris = 1.0; espon > 0; espon--) ris = ris * base; /* fine ciclo for */

/* (2) ciclo while */ ris = 1.0; while(espon > 0) { ris = ris * base; espon--; } /* fine ciclo while */

/* (3) ciclo do while */ ris = 1.0; if (espon) {

do { ris = ris * base; espon--; } while(espon > 0);

} /* fine ciclo do while */

Vettori e puntatoriUn puntatore è un insieme di celle di memoria usate per contenere l’indirizzo di un dato di un particolare tipo, la sua definizione deve fare riferimento anche al tipo di dato.Questo è un punto molto importante da cui deriva la possibilità di un’algebra dei puntatori.Allora (vedi il programma che segue):char *p2; definisce p2 come indirizzo di una variabile carattere,char *p1 = “ABC”; definisce p1 come indirizzo di una variabile carattere che viene inizializzato con l’indirizzo della stringa di caratteri “ABC”.

#include <stdio.h>void main(){ char *p1 = "ABC"; char *p2;

7

p2 = p1; *p1 = 'X'; printf("p2: %s \n", p2); /* viene stampata la stringa XBC */}

Ricerca di una stringa in un vettore di stringhe (vers. 1)Il programma contiene il vettore di puntatori char *nomi[ ] inizializzato con indirizzi di stringhe già definite, l’ultimo indirizzo contiene NULL per segnalare la fine del vettore degli indirizzi. La funzione find_name ricerca una stringa passata fra quelle puntate.Nella seconda versione la funzione è identica ma ha una forma diversa, invece di eseguire la somma direttamente sul puntatore, viene utilizzato un indice.

file: ricerca.c/******************************************************************* Programma che ricerca la prima occorrenza di una specificata** stringa di caratteri in un array di stringhe. versione 1 *****************************************************************/

#include <stdio.h> #include <stdlib.h> #include <string.h>

#define SIZE 20

char * find_name(char **, char *);

int main(void) { char *nomi[ ] = { "Priamo", "Achille", "Ettore", "Andromaca", NULL };

/* nomi: doppio puntatore a carattere ** ** nomi[ ]: vettore di puntatori a carattere ** ** nomi[0][0]: contiene 'P' ** ** nomi[1][1]: contiene 'c' ** ** nomi[3][0]: contiene 'A' ** ** (ogni stringa ha lunghezza diversa) */

char nuovo_nome[SIZE], *nome_punt;

printf("inserisci il nome da cercare.\n"); scanf("%s", nuovo_nome); nome_punt = find_name(nomi, nuovo_nome);

printf("nome: %s\n",nome_punt); printf("nome %s%strovato\n", nuovo_nome,

(nome_punt == NULL) ? " non " : " "); return (0); } /* End of main */

/**************************************************************** ** Funzione find_name. Questa funzione ricerca in un array di ** nomi un dato nome. ** Ritorna il puntatore al nome trovato o NULL se non e' stato ** trovato. ** array e' il puntatore al vettore di puntatori ai nomi ** esistenti ** stringa e' il puntatore alla stringa fornita (nuovo nome) ***************************************************************/

8

char * find_name(char **array, char *stringa) { for (; *array != NULL; array++) /* per ogni nome */ {

if (strcmp(*array, stringa) == 0) return(*array);

}return(*array); /* ritorna il puntatore */

} /* End of find_name */

Ricerca di una stringa in un vettore di stringhe (vers. 2 della sola funzione)

char * find_name(char *array[ ], char *stringa) { int i; for (i = 0; array[i] != NULL; i++) /* per ogni nome */ {

if (strcmp(array[i], stringa) == 0) return(array[i]);

}return(NULL); /* ritorna il puntatore */

} /* End of find_name */

Strutture pila e coda (statiche) realizzate con un vettore Pila e coda sono strutture composte da componenti ordinati, perciò naturalmente modellabili da vettori, nell’esempio si fa riferimento a numeri interi, ma può essere usato ogni altro tipo di dato eventualmente fornito di una sua ulteriore struttura interna. Un vettore è un oggetto statico cioè non non è possibile modificare dinamicamente la quantità di memoria, fissata in fase di compilazione, che limita il numero massimo di elementi contenibili.In una pila o coda gli elementi vengono inseriti e tolti uno alla volta, con questa differenza: nella pila l’ultimo elemento inserito è il primo che viene tolto (Last In First Out), nella coda gli elementi vengono tolti seguendo l’ordine di arrivo (First In First Out). Nel primo caso allora basta conoscere quanti sono gli elementi contenuti per sapere la posizione su cui operare, nell’altro bisogna invece conservare la posizione sia dell’ultimo inserito sia di quello che, fra i presenti, è stato inserito per primo.Per la coda si pone anche il problema di riutilizzare lo spazio: quando è stata usata l’ultima posizione del vettore (quella cui corrisponde l’indice più elevato) bisogna poter tornare a riusare la prima posizione, se libera. Il calcolo della posizione è quindi basato su una funzione ciclica (la divisione in modulo per la lunghezza del vettore).Le caratteristiche descritte sono rispecchiate più sotto nelle definizioni dei tipi dato pila e coda e nelle funzioni che gestiscono questi oggetti. Come nei casi già incontrati il main contiene una possibile codifica per eseguire le funzioni.

file: pilacoda.c#include<stdio.h>#define MAX_SZ 5

typedef struct { int Info[MAX_SZ]; int numelem; } Pila;

9

typedef struct { int Info[MAX_SZ]; int numelem; int first; } Coda;

int InserInPila(Pila *p, int elm) { int ret = NULL; if (p->numelem < MAX_SZ) { p->Info[p->numelem++] = elm; ret = 1; } return (ret);}

int TogliDaPila(Pila *p) { int ret = NULL; if (p->numelem > 0) ret = p->Info[--(p->numelem)]; return (ret);}

void StampaPila(Pila *p) { int i; printf("Pila: "); for(i = 0; i < p->numelem; i++) printf("%4d", p->Info[i]); printf("\n");}

int InserInCoda(Coda *c, int elm) { int i, ret = NULL; if(c->numelem < MAX_SZ) { if(c->numelem == 0) c->first = 0; i = (c->first + c->numelem++) % MAX_SZ; c->Info[i] = elm; ret = 1; } return (ret);}

int TogliDaCoda(Coda *c) { int reso = NULL; if(c->numelem != 0) { reso = c->Info[c->first]; c->numelem--; c->first = (c->first + 1) % MAX_SZ; } return (reso);}

void StampaCoda(Coda *c) { int i,k; printf("Coda: "); for(i = 0;i < c->numelem; i++) { k = (c->first + i) % MAX_SZ; printf("%4d", c->Info[k]); } printf("\n");}void main() {

10

Pila pila1; Coda coda1; pila1.numelem = 0; coda1.numelem = 0;

InserInPila(&pila1,1); StampaPila(&pila1); InserInPila(&pila1,2); StampaPila(&pila1); InserInPila(&pila1,3); StampaPila(&pila1); printf("%4d\n",TogliDaPila(&pila1)); StampaPila(&pila1); printf("\n"); InserInCoda(&coda1,10); StampaCoda(&coda1); InserInCoda(&coda1,11); StampaCoda(&coda1); InserInCoda(&coda1,12); StampaCoda(&coda1); printf("\n"); printf("%4d\n",TogliDaCoda(&coda1)); printf("\n"); StampaCoda(&coda1); printf("\n"); printf("%4d\n",TogliDaCoda(&coda1)); printf("\n"); StampaCoda(&coda1); printf("\n"); InserInCoda(&coda1,20); InserInCoda(&coda1,21); InserInCoda(&coda1,22); InserInCoda(&coda1,23); StampaCoda(&coda1); printf("\n"); printf("%4d\n",TogliDaCoda(&coda1)); printf("\n"); printf("%4d\n",TogliDaCoda(&coda1)); printf("\n"); StampaCoda(&coda1);

}

Output della esecuzione di pilacoda:Pila: 1Pila: 1 2Pila: 1 2 3 3Pila: 1 2

Coda: 10Coda: 10 11Coda: 10 11 12

10

Coda: 11 12

11

Coda: 12

11

Coda: 12 20 21 22 23

12

20

Coda: 21 22 23

Passaggio di parametri al mainAnche il modulo main è una funzione che riceve sempre due parametri in formato standard: un intero e un puntatore a un vettore di puntatori a stringhe di caratteri (che dichiariamo nella testata del main rispettivamente int argc, char **argv ). La prima stringa è sempre il nome del programma eseguibile, il parametro intero è la lunghezza del vettore, le altre stringhe indirizzate dal vettore sono i parametri che vengono passati al programma nel comando di esecuzione. Ovviamente se non vengono passati parametri la variabile intera contiene 1.L’esempio riguarda la conversione di temperature da gradi Celsius a Fahrenheit, le temperature possono essere passate come parametri di esecuzione o da tastiera alla richiesta.L’istruzione sscanf legge una stringa alla volta dalla memoria convertendone il formato in double. file: ctofar.c#include <stdio.h>void convert(double);void main(int argc, char **argv){ double c_temp; if (argc == 1) { /* ottieni la temperatura in Celsius da stdin */ printf("inserisci la temperatura in gradi Celsius: \n"); if (scanf("%lf", &c_temp) !=1) { printf("temperatura invalida \n"); } else { convert(c_temp); } } else { /* conversione della riga comandi */ int i; for (i = 1; i < argc; ++i) { if (sscanf(argv[i], "%lf", &c_temp) != 1)

printf("%s temperatura non valida\n", argv[i]); else

convert(c_temp); } } } void convert(double c_temp) { double f_temp = (c_temp * 9.0 / 5.0 + 32); printf("%5.2f Celsius: %5.2f Fahrenheit\n", c_temp, f_temp); }

Output della esecuzione di:ctofar 0 –4 15 32 51 –170.00 Celsius: 32.00 Fahrenheit-4.00 Celsius: 24.80 Fahrenheit15.00 Celsius: 59.00 Fahrenheit

12

32.00 Celsius: 89.60 Fahrenheit51.00 Celsius: 123.80 Fahrenheit-17.00 Celsius: 1.40 Fahrenheit

Visibilità e funzioni

Visibilità delle variabili in blocchi annidatiLe variabili definite in un blocco (insieme di comandi racchiusi da { }) sono visibili solo all’interno di quel blocco perciò, se in un blocco annidato in un altro viene definita una variabile con un nome già usato, questa è una nuova variabile, accessibile solo all’interno di quest’ultimo. Il programma seguente mostra tale situazione. Attenzione quindi ai nomi delle variabili e a dove sono posizionate!

file: visib.c#include <stdio.h> int i = 1; /* i definita al livello di file */

int main() {

printf("%d\n", i); /* stampa 1 */

{ int i = 2, j = 3; /* i e j definite a livello di blocco */ printf("%d\n%d\n", i, j); /* stampa 2, 3 */

{ int i = 0; /* i ridefinita in un blocco interno */

/* le definizioni precedenti di i sono nascoste */ printf("%d\n%d\n", i, j); /* stampa 0, 3 */ }

printf("%d\n", i); /* stampa 2 */

}

printf("%d\n", i); /* stampa 1 */

return 0;

}

PotenzaOgni funzione “vede” le variabili che appartengono al suo ambiente locale cioè quelle dichiarate nella sua testata e nella sua parte dichiarativa e, quando rende il controllo al programma chiamante (nella maggior parte dei casi il main), può “ritornare” un valore mediante l’istruzione return(..). Perciò, se la funzione è di tipo algebrico e calcola un risultato dipendente da una serie di variabili esterne, queste ultime sono generalmente passate come valori alla funzione che ottiene la soluzione e la ritorna.La funzione potenza calcola la potenza (intera) di un numero attraverso un ciclo for:

file: potenza.c/* potenza di un numero */

13

#include<stdio.h>

float potenza(float base, int espon){ float ris; if(espon < 0) { espon = -espon;

base = 1.0 / base; }

ris = 1.0;

for(; espon > 0; espon--) ris = ris * base; return(ris);}

void main() { float base; int espon;

printf("\nfornisci base (un numero negativo termina il programma): "); scanf("%f", &base);

while(base > 0) { printf("\nfornisci esponente (numero intero): "); scanf("%d", &espon); printf("\nrisultato : %f", potenza(base,espon)); printf("\nfornisci base (un numero negativo termina il programma): "); scanf("%f", &base);

}}

Calcolo delle radici di un’equazione di 2° gradoEccone ora una funzione nota: calcolo delle radici di un’equazione di 2° grado noti i coefficienti. Le radici sono generalmente 2 e la funzione è di tipo void, non ritorna alcun valore al programma chiamante ma stampa direttamente i risultati.

file: equaz2do.c#include<stdio.h>#include<math.h>

void EquazioneSecondoGrado(double a, double b, double c) {

double x1,x2,Disc;

if (a==0) printf("\n errore: equazione di primo grado"); else { Disc=b*b-4*a*c; if (Disc < 0)

printf("\n errore: radice complessa "); else {

x1 = (-b+sqrt(Disc)) / (2.0*a); x2 = (-b-sqrt(Disc)) / (2.0*a);

printf("\n x1 = %g", x1); printf("\n x2 = %g", x2); }

14

}

}

void main() { double A, B, C;

printf("\nvalore di A, B e C: \n"); scanf("%lf %lf %lf", &A, &B, &C); EquazioneSecondoGrado(A, B, C);}

Scambio dei valori di due variabili (ver. 1)Un’operazione che viene eseguita frequentemente (necessaria ad esempio quando si esegue l’ordinamento di un insieme di elementi) è quella di effettuarne uno scambio fra due valori. Dal momento che non esiste un’istruzione elementare che operi uno scambio, bisogna eseguirlo in tre passi appoggiandosi a una variabile intermedia. Se lo scambio viene fatto da una funzione, perché il risultato sia permanente, questa deve operare nello spazio in cui sono definite le variabili, perciò deve accedere alle variabili mediante “puntatori”.La prima soluzione presentata mostra tale tecnica, si noti anche che non essendo definito nel linguaggio il dato “numero complesso”, questo viene definito dall’utente come tipo derivato (il numero complesso è una coppia ordinata di reali).

file: scambia.h /* definizione del tipo dato numero complesso */typedef struct { double realp, imgp; } complex;

/* funzioni di scambio fra due variabili (una funzione per tipo dato) */

void scambiach(char *pt1, char *pt2) { char tmp; tmp = *pt1; *pt1 = *pt2; *pt2 = tmp; }

void scambiain(int *pt1, int *pt2) { int tmp; tmp = *pt1; *pt1 = *pt2; *pt2 = tmp; }

void scambiafl(float *pt1, float *pt2) { float tmp; tmp = *pt1; *pt1 = *pt2; *pt2 = tmp; }

void scambiadb(double *pt1, double *pt2) { double tmp; tmp = *pt1; *pt1 = *pt2; *pt2 = tmp;

15

}

void scambiacx(complex *pt1, complex *pt2) { complex tmp; tmp = *pt1; *pt1 = *pt2; *pt2 = tmp; }

file: scambia.c/* programma di prova della funzione scambia */#include<stdio.h>#include"scambia.h"

void main() { int unoi = 1, duei = 2; char ac = 'a', bc = 'b'; float fla = 1.0100, flb = 2.0200; double dba = 10.0030, dbb = 23.9950; complex cx1, cx2; cx1.realp = 1.2; cx1.imgp = 2.1; cx2.realp = 91.2; cx2.imgp = 92.1;

printf("\n uno: %i due: %i ", unoi, duei); scambiain(&unoi,&duei); printf("\n uno: %i due: %i ", unoi, duei);

printf("\n a: %c b: %c ", ac, bc); scambiach(&ac,&bc); printf("\n a: %c b: %c ", ac, bc);

printf("\n fla: %f flb: %f ", fla, flb); scambiafl(&fla,&flb); printf("\n fla: %f flb: %f ", fla, flb);

printf("\n dba: %lf dbb: %lf ", dba, dbb); scambiadb(&dba,&dbb); printf("\n dba: %lf dbb: %lf ", dba, dbb);

printf("\n cx1: %lf %lf cx2: %lf %lf", cx1.realp, cx1.imgp, cx2.realp, cx2.imgp); scambiacx(&cx1,&cx2); printf("\n cx1: %lf %lf cx2: %lf %lf", cx1.realp, cx1.imgp, cx2.realp, cx2.imgp);}

Output della esecuzione di scambia: uno: 1 due: 2 uno: 2 due: 1 a: a b: b a: b b: a fla: 1.010000 flb: 2.020000 fla: 2.020000 flb: 1.010000 dba: 10.003000 dbb: 23.995000 dba: 23.995000 dbb: 10.003000 cx1: 1.200000 2.100000 cx2: 91.200000 92.100000 cx1: 91.200000 92.100000 cx2: 1.200000 2.100000

16

Scambio dei valori di due variabili (ver. 2)Se si vuole costruire una funzione di scambio che operi su diversi tipi di dato bisogna passare ad essa anche il tipo di dato interessato, in questo caso i puntatori passati devono essere modificati attraverso l’operatore di “casting”. I puntatori infatti sono puntatori a un particolare tipo di dato. Ecco allora la rielaborazione del programma precedente, in cui il primo parametro passato alla funzione è un carattere che viene interpretato come il tipo del dato su cui operare. In questa implementazione viene usato il costrutto di controllo switch - case.

file: scambiab.c /* programma di prova della funzione scambia */#include<stdio.h>

/* definizione del tipo numero complesso */typedef struct { double realp, imgp; } complex;

/* funzione di scambio fra due variabili */void scambia(char tipo, void *pt1, void *pt2) { char tmpch; int tmpin; double tmpfl; complex tmpcx; switch (tipo) { case 'c': tmpch = * (char *)pt1; * (char *)pt1 = * (char *)pt2; * (char *)pt2 = tmpch; break; case 'i': tmpin = * (int *)pt1; * (int *)pt1 = * (int *)pt2; * (int *)pt2 = tmpin; break; case 'f': tmpfl = * (double *)pt1; * (double *)pt1 = * (double *)pt2; * (double *)pt2 = tmpfl; break; case 'x': tmpcx = * (complex *)pt1; * (complex *)pt1 = * (complex *)pt2; * (complex *)pt2 = tmpcx; break;

default: puts("tipo sconosciuto"); }}

void main() { int unoi = 111, duei = 222; double unof = 10.10002, duef = 20.20001; char ac = 'Y', bc = 'Z'; void *pt1, *pt2; complex cx1, cx2; cx1.realp = 1.2; cx1.imgp = 9.3; cx2.realp = 8.2; cx2.imgp = 8.3;

17

printf("\n uno: %i due: %i ", unoi, duei); pt1 = &unoi; pt2 = &duei; scambia('i',pt1,pt2); printf("\n uno: %i due: %i ", unoi, duei);

printf("\n a: %c b: %c ", ac, bc); pt1 = &ac; pt2 = &bc; scambia('c',pt1,pt2); printf("\n a: %c b: %c ", ac, bc);

printf("\n f1: %lf f2: %lf ", unof, duef); pt1 = &unof; pt2 = &duef; scambia('f',pt1,pt2); printf("\n f1: %lf f2: %lf ", unof, duef);

printf("\n cx1: %lf %lf cx2: %lf %lf", cx1.realp, cx1.imgp, cx2.realp, cx2.imgp); pt1 = &cx1; pt2 = &cx2; scambia('x',pt1,pt2); printf("\n cx1: %lf %lf cx2: %lf %lf", cx1.realp, cx1.imgp, cx2.realp, cx2.imgp);

}

Output della esecuzione di scambia: uno: 111 due: 222 uno: 222 due: 111 a: Y b: Z a: Z b: Y f1: 10.100020 f2: 20.200010 f1: 20.200010 f2: 10.100020 cx1: 1.200000 9.300000 cx2: 8.200000 8.300000 cx1: 8.200000 8.300000 cx2: 1.200000 9.300000

Dati strutturati

RicorsivitàMolti algoritmi possono essere risolti in modo ricorsivo. Secondo questo paradigma il problema di partenza può essere risolto attraverso la soluzione del problema stesso su un sottoinsieme dei dati e combinando i risultati ottenuti. L’algoritmo richiama allora se stesso per una esecuzione interna alla precedente, finché non si verifichi una condizione di arresto.Vengono ora riportati alcuni algoritmi codificati sia in modalità iterativa sia ricorsiva così che il confronto sia più facile, più oltre si affronteranno in modo analogo problemi che implicano strutture dinamiche che sono ricorsive anche nella loro stessa definizione.

Massimo Comun DivisoreIl Massimo Comun Divisore fra due numeri si può ottenere, secondo il geniale algoritmo di Euclide, osservando che il MCD(n,m) = MCD(n-m,m), dove n > m o ancora MCD(n,m) = MCD(m, n%m) dove n%m è il resto della divisione n/m.

file: MCDiv.c/*************************************************************** Massimo Comun Divisore fra due numeri interi **** algoritmo di Euclide: **

18

** il MCD fra due numeri e' il MCD fra il minore dei due **** e la loro differenza ** *************************************************************/

#include<stdio.h>

/* codifica ricorsiva */int MCDric(int a, int b){ int differenza, minore; if(a == b) return (b); else { differenza = a>b ? a-b : b-a; minore = a>b ? b : a; return (MCDric(differenza,minore)); };

}

/* codifica iterativa */int MCDite(int a, int b){ while (a != b) { if (a > b)

a = a - b; else

b = b - a; } return (b);

}

void main (){ int x, y; printf("introdurre due numeri interi\n"); scanf("%d %d", &x, &y); printf("Il Massimo Comun Divisore fra %d e %d e' %d\n", x, y, MCDric(x,y)); printf("Il Massimo Comun Divisore fra %d e %d e' %d\n", x, y, MCDite(x,y));}

altra forma della funzione MCDite:int MCDite(int a, int b){ while ((a != 0) && (b != 0)) { if (a > b)

a = a % b; else

b = b % a; } return ((a>b) ? a : b);

}

altra forma della funzione MCDric:int MCDric(int a, int b){ return (b ? MCDric(b, a % b) : a);}

19

Media ricorsivaAnche la media può essere ottenuta ricorsivamente osservando che:

file: mediar.c#include <stdio.h>float Media(float elementi[], int num_elementi)/* funzione di calcolo della media in modo ricorsivo** bisogna fornire l'indirizzo del vettore che contiene i valori** e la sua lunghezza */ { float med,med1; if(num_elementi == 1) med=*elementi; else {

med1=Media(elementi + 1, num_elementi - 1);med=med1 + ((*elementi - med1) / num_elementi);

} return med; }

void main() { int cont, num_elem; float media, elementi[50]; printf("inserisci il numero di elementi dei quali vuoi fare la media: "); scanf("\n%d", &num_elem); for(cont=0; cont<num_elem; cont++) { printf("Inserisci numero: \n");

scanf("%f",&elementi[cont]); }

media = Media(elementi, num_elem); printf ("\nLa media e`: %f", media); }

Polinomio Per un polinomio di grado n nella variabile x di coefficienti ci, vale la seguente eguaglianza:

codificata nella funzione ricorsiva Poli, come appare qui di seguito. file: poli.c/* calcolo ricorsivo di un polinomio */ #include <stdio.h>

#define MAX_SZ 10

/* i parametri passati sono: il valore della variabile x, il vettore

20

degli n+1 coefficienti del polinomio, il suo grado n */ float Poli(float x, float * c, int n) { float Poli_val = 0.0; if (n >= 0) Poli_val = *c + x * Poli(x, c + 1, n - 1); return (Poli_val);}

void main () { float coeff[MAX_SZ], polinomio, x; int i, n, cont;

printf("\nInserisci grado del polinomio\n"); cont = scanf("%d", &n); /* lettura grado = lunghezza */

while(cont == 1){ printf("\nInserisci i %i coefficienti\n", n + 1);

for(i = 0; i < n + 1; i++) scanf(" %f", &coeff[i]);

printf("\nInserisci il valore x: "); scanf(" %f",&x); polinomio = Poli(x,coeff,n);

printf("\n valore: %f",polinomio); printf("\nInserisci grado del vettore\n"); cont = scanf("%d", &n); /* lettura grado = lunghezza */ }}

Algoritmi vari

Ricerca binariaL’algoritmo ricerca un dato in un insieme ordinato, consiste nel posizionarsi al centro della sequenza e individuare in quale delle due metà si trova eventualmente il valore cercato poi si prosegue in modo analogo nella nuova metà, fino al successo o all’esaurimento dei dati. Se N è il numero degli elementi, il numero di ricerche è allora proporzionale a log2(N).La funzione ricbin ricerca un numero intero x nella porzione del vettore v compresa fra gli indici i e j. Essa ritorna al programma chiamante 1 se la ricerca ha avuto successo, 0 in caso contrario. Non è difficile riscriverla in modo ricorsivo.

file: binr2.c#include <stdio.h>#define N 10int ricbin(int x, int v[ ], int i, int j) { int k;

if (i > j) return (0);

do { k = (i + j) / 2; if (x < v[k])

j = k - 1; else

21

i = k + 1; } while ((i <= j) && (v[k] != x)); return (x == v[k]);} int main(void){ int vect[N], i, sx = 0, dx = 9, n, x; printf("introdurre una sequenza ordinata di %d numeri\n", N); for (n = 0; n < N ; n++ ) { scanf("%d", &x); vect[n] = x; } /* endfor */ printf("introdurre il numero da cercare \n"); scanf("%d", &x); i = ricbin(x,vect,sx,dx); if (i != 0) printf("trovato %d\n", x); else printf("%d non trovato\n", x); return (0);}

Operazioni diverse su strighe di caratteriLa funzione inverti inverte l’ordine dei caratteri in una stringa e ritorna la sua lunghezza, esistono innumerevoli modi per ottenere questo risultato, la funzione usa la tecnica di copiare la stringa in un’area temporanea e poi ricopiare un carattere alla volta da questa nella posizione finale. Si noti l’uso dell’operatore prefisso –-i nella funzione.

file: strinv.c#include<stdio.h>#define MAX_LN 30int main() { char parola[MAX_LN]; int lung; int inverti(char parola[]);

printf("\ninserisci la parola: "); scanf("%s", parola); lung = inverti(parola); printf("\n %s lung: %d", parola, lung);

return 0;}

int inverti(char parola[]) { char alorap[MAX_LN]; int l, i = 0; while(parola[i] != '\0' && i < MAX_LN) { alorap[i] = parola[i]; i++; } l = --i; while(i >= 0) { parola[l - i] = alorap[i]; i--; }

return (l + 1);} La funzione ConsumaDoppi riceve in input il puntatore a una stringa di caratteri ed elimina i caratteri contigui ripetuti. Nella prima versione viene usata un’area temporanea in cui si costruisce

22

il risultato finale, ricopiato poi nella stringa di partenza. Più oltre viene riportata una versione più compatta dell’algoritmo (codificata in due modi equivalenti) in cui non vengono usate variabili intermedie ma la stringa è ricopiata su se stessa, un carattere alla volta, utilizzando una coppia di indici diversi.

file:string0.c#include<stdio.h>#include<stdlib.h>

void ConsumaDoppi(char *Str) { int i, j = 0; char Strtmp[30]; for(i = 0; Str[j] != '\0'; i++) { Strtmp[i] = Str[j]; j++; while(Strtmp[i] == Str[j])

j++; } Strtmp[i] = '\0'; for(i = 0; Strtmp[i] != '\0'; i++) Str[i] = Strtmp[i]; Str[i] = '\0';}

void main() { char stringa[30];

scanf("%s", stringa); printf("\n%s", stringa);

ConsumaDoppi(stringa); printf("\n%s ", stringa);}

versione 2 (sola funzione)void ConsumaDoppi(char *Str) { int i, j = 0; for(i = 0; Str[i] != '\0'; i++) { Str[i] = Str[j++]; while(Str[i] == Str[j])

j++; }} versione 2b (sola funzione variazione)void ConsumaDoppi(char *Str) { char *punt = Str; for(; *Str != '\0';) { *Str = *punt++; while(*Str == *punt)

punt++; Str++; }}

23

Il programma conta1 legge un file di testo e conta i digit numerici e quelli alfabetici. Si noti che i caratteri sono “numeri” interi perciò non ci si deve meravigliare se valgono gli operatori aritmetici e di confronto.

file: conta1.c #include <stdio.h>/*conta i caratteri alfabetici e numerici di un testo*/void main(){

int c, i, altri = 0, spazi = 0;int ndigit[10];

int nalfab[26];for (i = 0; i < 10; i++)

ndigit[i] = 0;for (i = 0; i < 26; i++)

nalfab[i] = 0;while ((c = getchar()) != EOF)

if (c >= '0' && c <= '9') ++ndigit[c - '0'];else if(c == ' ') ++spazi;

else if((c >= 'A') && (c <= 'Z')) ++nalfab[c - 'A']; else if((c >= 'a') && (c <= 'z')) ++nalfab[c - 'a'];

else ++altri;printf("\nnumeri\n");for (i = 0; i < 10; ++i)

printf(" %3d", i);printf("\n"); for (i = 0; i < 10; ++i)

printf(" %3d", ndigit[i]);printf("\nlettere\n");for (i = 0; i < 26; ++i)

printf(" %3c", 'A' + i);printf("\n");for (i = 0; i < 26; ++i)

printf(" %3d", nalfab[i]);printf("\n spazi = %d, altri = %d", spazi, altri);

}

Output della esecuzione di:conta1 < conta1.c (il programma legge la codifica contenuta nel file “conta1.c”)

numeri 0 1 2 3 4 5 6 7 8 9 16 4 4 4 0 0 4 0 0 1lettere A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 30 6 19 13 21 26 5 3 70 0 0 17 3 34 11 13 0 25 10 30 4 1 1 0 0 6 spazi = 193, altri = 313

24

Strutture dinamicheL’introduzione di una struttura dinamica permette una maggiore flessibilità nell’uso della memoria che può essere “allocata” e liberata in funzione della necessità.

ListeUna lista è composta da una successione di elementi, quindi perché possa essere percorsa interamente almeno in una direzione, bisogna che ogni elemento contenga l’indirizzo di quello successivo. La definizione dell’elemento di lista è ricorsiva: contiene il puntatore a un dato dello stesso tipo. Ogni lista deve avere un inizio e una fine, l’ultimo elemento si distingue per il fatto che l’indirizzo del prossimo elemento è la costante NULL (= fine lista); il primo elemento viene invece raggiunto attraverso un puntatore, che si usa chiamare testa della lista, ed è da considerarsi parte integrante della lista stessa. Una funzione progettata per gestire una lista deve sempre ricevere come parametro il puntatore ad essa. Se la funzione può modificare il puntatore perché, per esempio, inserisce in testa un nuovo elemento, è necessario che riceva come parametro un doppio puntatore. Infatti con questa tecnica la nostra funzione è in grado di modificare la testa della lista anche se si trova nell’area di memoria del programma chiamante. Il programma listai che è composto dal file .h che contiene la definizione dell’elemento più semplice che si possa pensare, composto da un dato intero e da un puntatore e qualche esempio di funzione di gestione della lista. Di alcune di queste funzioni vengono presentate implementazioni diverse. Si osservi che, come già notato, le funzioni che leggono la lista ma la lasciano inalterata (ad esempio quelle di stampa) possono ricevere in input il puntatore alla lista, quelle che ne modificano la struttura hanno invece come parametro in ingresso il puntatore al puntatore alla lista.Le funzioni sono molto semplici, si è evitato di allocare e rilasciare la memoria perciò nel main (file .c), - da usarsi per esperimenti - gli elementi sono già predefiniti staticamente. In qualche caso la versione ricorsiva di una funzione è quella più immediata e naturale. Si confronti, per esempio, la codifica delle funzioni di stampa e si osservi come sia possibile, nella versione ricorsiva, cambiare l’ordine di stampa semplicemente invertendo l’ordine di due istruzioni. Non sarebbe altrettanto facile in quella iterativa.

file: listai.h/* definizione dell'elemento di lista di interi */typedef struct EL { int Info; struct EL *next; } ElmLista, *Lista;

/* stampa lista (iterativa) in ordine diretto */void StampaLista(Lista l) { while (l != NULL) {

printf("%i\n",l->Info);l = l->next;}

}

/* stampa lista (ricorsiva) in ordine diretto */void StampaDiretta(Lista l) { if(l) { printf("%i\n", l->Info); StampaDiretta(l->next); }}

/* stampa lista (ricorsiva) in ordine inverso */void StampaInversa(Lista l) {

25

if(l) { StampaInversa(l->next); printf("%i\n",l->Info); }}

/* conteggio (iterativo) del numero di elementi di una lista */ int LungListaI(Lista l){ int lung = 0; while(l) { lung++; l = l->next; } return (lung);}

/* conteggio (ricorsivo) del numero di elementi di una lista */ int LungListaR(Lista l) { int lung = 0; if (l != NULL) { lung = 1 + LungListaR(l->next); } return (lung);}

/* inserimento in testa */void InserisciInTesta(Lista *lp, ElmLista *elp) { elp->next = *lp; *lp = elp;}

/* inserimento in coda (iterativo) */void InserisciInCoda(Lista *lp, ElmLista *elp) { ElmLista *elementoCorrente; elementoCorrente = *lp; if (*lp == NULL) *lp = elp; /* caso di lista vuota */ else {

while (elementoCorrente->next != NULL) { elementoCorrente = elementoCorrente->next; } elementoCorrente->next = elp; } elp->next = NULL;}

/* inserimento in coda (ricorsivo) */void InserisciInCodaR(Lista *lp, ElmLista *elp) {

if (*lp == NULL) { *lp = elp; /* fine della lista */ elp->next = NULL; } else {

InserisciInCodaR(&(*lp)->next, elp); }

}

/* inserimento in ordine (si suppone la lista in ordine crescente) */

26

void InserisciInOrdine(Lista *lp, ElmLista *elp) { ElmLista *elementoCorrente, *elementoPrecedente; elementoCorrente = *lp; elementoPrecedente = NULL; while (elementoCorrente != NULL && elementoCorrente->Info < elp->Info) {

elementoPrecedente = elementoCorrente;elementoCorrente = elementoCorrente->next;}

elp->next = elementoCorrente; if (elementoPrecedente != NULL)

elementoPrecedente->next = elp; /* caso di lista non vuota */ else *lp = elp;}

/* il primo elemento (se esiste) viene tolto e ritornato il puntatore */ ElmLista *TogliDaTesta(Lista *lp) {ElmLista *elementoCorrente; elementoCorrente = *lp; if (elementoCorrente != NULL) *lp = elementoCorrente->next; return elementoCorrente;}

file: listai.c#include <stdio.h>#include "listai.h"

void main() { ElmLista Elm1, Elm2, Elm3, Elm4, Elm5, Elm6, Elm0, *PElm; Lista Lista1;

Lista1 = &Elm1; Elm1.Info = 1; Elm1.next = &Elm2; Elm2.Info = 2; Elm2.next = &Elm3; Elm3.Info = 3; Elm3.next = &Elm5; Elm5.Info = 5; Elm5.next = NULL;

Elm4.Info = 4; Elm6.Info = 6; Elm0.Info = 0;

StampaLista(Lista1); printf("\n"); InserisciInOrdine(&Lista1,&Elm4); InserisciInOrdine(&Lista1,&Elm6); InserisciInOrdine(&Lista1,&Elm0); StampaLista(Lista1); printf("\n"); StampaInversa(Lista1); printf("\n"); /* printf("\n %i \n ",(*TogliDaTesta(&Lista1)).Info); printf("\n"); StampaLista(Lista1); printf("\n");

27

printf("\n %i \n ",TogliDaTesta(&Lista1)->Info); printf("\n"); StampaLista(Lista1);

InserisciInCoda(&Lista1,&Elm4); StampaLista(Lista1); printf("\n"); InserisciInCodaR(&Lista1,&Elm0); StampaLista(Lista1); printf("\n");

printf("\n %i ",LungListaI(Lista1)); printf("\n %i ",LungListaR(Lista1)); printf("\n %i ",LungListaI(NULL)); printf("\n %i ",LungListaR(NULL));

StampaDiretta(Lista1); printf("\n"); StampaInversa(Lista1); printf("\n");*/

}

Output della esecuzione di listai:1235

0123456

6543210

Pile e code (strutturate come lista)I programmi che seguono, pila e coda (entrambi composti da file .h e .c) non sono altro che la versione del problema affrontato in precedenza mediante vettori nell’esercizio pilacoda, ora risolto su strutture dinamiche. Gli elementi sono, al solito, interi. Le funzioni di inserimento e eliminazione si incaricano di richiedere e liberare la memoria. Invece di utilizzare la tecnica di passare alle funzioni il doppio puntatore, viene passato quello semplice ma la funzione ritorna il nuovo puntatore al programma chiamante.Si noti come la struttura della lista della “coda” sia ciclica, l’ultimo elemento inserito contiene l’indirizzo del primo (che sarà anche il primo da togliere). Con un solo puntatore si raggiungono

28

perciò entrambi gli elementi interessati alla operazione e il numero di istruzioni eseguite è indipendente dalla lunghezza della coda, analogamente al caso della pila. In questo modo però bisogna distinguere fra loro i tre casi: in cui non ci siano elementi accodati, ce ne sia uno solo e ce ne siano due o più.

file: pila.htypedef struct _elPila{ int Info; struct _elPila *prossimo;} elPila, *Pila;

Pila Inserisci(Pila p, int el){ elPila *nuovoElemento;

/* richiedo memoria per nuovo elemento*/ nuovoElemento = (elPila *) malloc(sizeof(elPila));

if (nuovoElemento == NULL) return (NULL); /* copio contenuto informativo nel nuovo elemento */

nuovoElemento->Info = el; nuovoElemento->prossimo = p; p = nuovoElemento; return(p);}

Pila Togli(Pila p, int *el){ Pila punt; if (p == NULL) return (NULL); *el = p->Info; punt = p->prossimo; free(p); return (punt);}

void StampaPila(Pila p){ if (p == NULL) {

printf("la pila non ha elementi\n");return;

}

while (p != NULL) {

printf("%i\n", p->Info); p = p->prossimo; }}

file: pila.c#include <stdio.h>#include <stdlib.h>#include "pila.h"

29

void main(){

Pila p = NULL; int el; int scelta = -1;

while(scelta != 0) { printf("\n 0 per uscire, 1 per inserire, 2 per togliere, 3 per visualizzare\n"); scanf("%d", &scelta);

switch(scelta) {

case 1: printf("inserire un elemento: "); scanf("%d", &el); p = Inserisci(p, el); if (p == NULL) printf("inserimento non riuscito"); break;

case 2: p = Togli(p, &el); if (p != NULL) printf("%i ",el); break;

case 3: StampaPila(p); break; } } }

file: coda.htypedef struct _elCoda{ int Info; struct _elCoda *prossimo;} elCoda, *Coda;

Coda Inserisci(Coda pc, int el){ elCoda *nuovoElemento;

/* richiedo memoria per nuovo elemento*/ nuovoElemento = (elCoda *) malloc(sizeof(elCoda));

if (nuovoElemento == NULL) return (NULL); /* copio contenuto informativo nel nuovo elemento */

nuovoElemento->Info = el; /* se Coda vuota */ if (pc == NULL) nuovoElemento->prossimo = nuovoElemento; else { /* se esistono elementi */ nuovoElemento->prossimo = pc->prossimo; pc->prossimo = nuovoElemento; } return(nuovoElemento);

30

}

Coda Togli(Coda pc, int *el){ Coda punt; if (pc == NULL) return (NULL); punt = pc->prossimo; if (pc->prossimo == pc) { printf("%i ", pc->Info); free(punt); return (NULL); } *el = punt->Info; pc->prossimo = punt->prossimo; free(punt); return (pc);}

void StampaCoda(Coda pc){ Coda punt; if (pc == NULL) {

printf("la pila non ha elementi\n");return;

} punt = pc; do {

punt = punt->prossimo;printf("%i\n", punt->Info);

} while (punt != pc);}

file: coda.c#include <stdio.h>#include <stdlib.h>#include "pila.h"

void main(){

Pila p = NULL; int el; int scelta = -1;

while(scelta != 0) { printf("\n 0 per uscire, 1 per inserire, 2 per togliere, 3 per visualizzare\n"); scanf("%d", &scelta);

switch(scelta) {

case 1: printf("inserire un elemento: "); scanf("%d", &el); p = Inserisci(p, el); if (p == NULL) printf("inserimento non riuscito"); break;

case 2:

31

p = Togli(p, &el); if (p != NULL) printf("%i ",el); break;

case 3: StampaPila(p); break; } } }

AlberiDopo la lista la struttura dinamica più semplice è l’albero binario, struttura gerarchica in cui ogni elemento può avere ha due “figli”, sinistro e destro, a partire dalla radice fino alle foglie (che terminano il ramo, non avendo più figli. Un albero binario può essere visitato in modi diversi. L’esempio che segue (file albero2.c) mostra la costruzione (funzione: addtree) di un albero di stringhe (elemento dell’albero: Treenode), la sua visita e stampa in ordine alfabetico (funzione: treeprint) e la stampa della struttura (funzione: StampaAlbero).Le funzioni fin qui elencate sono ricorsive, oltre a queste nel programma ne sono codificate altre di servizio che servono per copiare le stringhe e allocare le aree di memoria necessarie. Essendo state codificate dopo il modulo main, devono essere dichiarate prima del loro uso.Viene poi mostrato un esempio di esecuzione del programma con come input la prima terzina del Purgatorio di Dante (input in carattere corsivo).Per aggiungere un nuovo elemento si parte dalla radice muovendosi a sinistra o a destra in funzione del fatto che la parola si trovi in ordine alfabetico prima o dopo della radice, Se abbiamo raggiunto la fine del ramo, il nuovo elemento viene aggiunto come foglia in quella posizione; in caso contrario l’elemento incontrato è la radice del sottoalbero dal quale si riparte con lo stesso procedimento.Per percorrere in ordine alfabetico l’albero così costruito bisogna raggiungere la foglia più a sinistra e seguirlo a ritroso stampando l’elemento radice di ogni sottoalbero dopo gli elementi del ramo sinistro e prima di quelli del destro. Come sempre il modo migliore per capire l’algoritmo è quello di operare su un caso pratico studiando la “traccia” del programma. Infine, per comprendere meglio la stampa della struttura dell’albero costruito, occorre ruotare di 90 gradi in senso orario il foglio con l’output, allora si leggerà agevolmente che:

per è la radice dell’albero,correr e vele sono i figli della radice di sinistra e di destra rispettivamente,

acque e migliori sono figli di correr,vele ha solo il figlio di sinistra (se’),

acque ha i figli: a e alza,ecc.

file: albero2.c /* esempio di gestione albero binario */#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>

#define MAXWORD 30typedef struct tnode *Treeptr;typedef struct tnode { /* nodo dell'albero */

32

char *word; /* puntatore al testo */ int count; /* numero di occorrenze */ Treeptr left, right; /* figli di sinistra e di destra */ } Treenode;

char *strdupz(char *);Treeptr addtree(Treeptr, char *);void treeprint(Treeptr);Treeptr talloc(void);void StampaAlbero(Treeptr, int);

/* costruisce albero dinamico inserendo parole */int main(void){ Treenode *root; char word[MAXWORD]; char *fine = "END";

root = NULL; printf("\ninserisci una parola alla volta <END termina la sequenza>\n"); scanf("%s", word); while(*word != *fine) {

root = addtree(root, word);scanf("%s", word);

} printf("\n ALBERO ORDINATO\n"); treeprint(root); printf("\n"); printf("\n STRUTTURA DELL'ALBERO\n"); printf("\n"); StampaAlbero(root, 1); return 0;}

/* aggiunge un nodo con w, a livello di *p o sotto */Treenode *addtree(Treenode *p, char *w){ int cond; if (p == NULL ) /* nuova parola */ {

p = talloc(); /* crea un nuovo nodo */p->word = strdupz(w);

p->count = 1;p->left = p->right = NULL;

}

else if ((cond = strcmp(w, p->word)) == 0)p->count++; /* parola ripetuta */

else if (cond < 0) /* minore: sottoalbero sinistro */p->left = addtree(p->left, w);

else /* maggiore: sottoalbero destro */p->right = addtree(p->right, w);

return p;} /* visita e stampa dell'albero p in ordine simmetrico */void treeprint(struct tnode *p){ if (p != NULL) {

33

treeprint (p->left);printf("%s (%d)\n", p->word, p->count);

treeprint(p->right); }}

/* stampa la forma e il contenuto dell'albero */void StampaAlbero(Treenode *p, int l){ int i; if (p != NULL) {

StampaAlbero(p->right, l + 1);for (i = 0; i < l; i++) printf(" ");printf("%s\n",p->word);StampaAlbero(p->left, l + 1);

}}

/* crea un tnode */Treenode *talloc(void){ return (Treeptr)malloc(sizeof(Treenode));}

/* crea una copia della stringa letta s */char *strdupz(char *s){ char *p; p = (char *)malloc(strlen(s) + 1); if (p != NULL) strcpy(p, s); return p;}

Esempio di output della esecuzione di albero2:

inserisci una parola alla volta <END termina la sequenza>

per correr migliori acque alza le veleormai la navicella del mio ingegnoche lascia dietro a se' mar si' crudeleEND ALBERO ORDINATOa (1)acque (1)alza (1)che (1)correr (1)crudele (1)del (1)dietro (1)ingegno (1)la (1)lascia (1)le (1)mar (1)migliori (1)mio (1)navicella (1)

34

ormai (1)per (1)se' (1)si' (1)vele (1)

STRUTTURA DELL'ALBERO

vele si' se' per ormai navicella mio migliori mar le lascia la ingegno dietro del crudele correr che alza acque a

Input Output

Esempio di scrittura, lettura e aggiornamento di un fileI “record” contenuti nel file “prova.txt” hanno lunghezza fissa pari a 20 byte, se si prova perciò a visualizzare con un “editor” il file costruito, in coda ad ogni parola appaiono una serie di caratteri sporchi non stampabili fino al completamento dei 20 byte. Il problema non si pone se si stampano le stringhe con un formato, per esempio con l’istruzione printf, in questo caso infatti il carattere ‘\0’ segnala la fine della stringa. Il programma operio vuole illustrare le istruzioni di I/O, in particolare: fopen, fclose, fwrite, fread, ftell, fseek. Le ultime due servono rispettivamente a memorizzare e a posizionare l’indirizzo di lettura/scrittura nel file. file: operio.c/* il programma richiede la successione di parole con cui viene popolato il file prova.txt. L'elenco viene terminato quando viene inserito il carattere '#' a inserimento ultimato vengono richieste due parole, la prima viene cercata nel file e, se trovata, sostituita con la seconda */ #include<stdio.h>#include<string.h>#define LUNG 20

void main() { char filename[] = "prova.txt"; char parola[LUNG], parolaDaTrovare[LUNG], parolaNuova[LUNG]; int n; long pos = 0L;

35

FILE *fp;

if ((fp = fopen(filename, "w")) == NULL) exit (-1); printf("inserisci parola\n"); scanf(" %s", parola); while (parola[0] != '#') { fwrite (parola, sizeof(parola),1,fp); printf("inserisci parola\n"); scanf("%s", parola); } fclose(fp); if ((fp = fopen(filename, "r+")) == NULL) exit (-1); printf("\ninserisci la parola da sostituire e la parola nuova\n"); scanf("%s %s", parolaDaTrovare, parolaNuova); for (;;) { n = fread(parola, sizeof(parola),1,fp); if (n == 0) {

printf("parola non trovata\n"); exit(-1); }

if (strcmp(parola,parolaDaTrovare) == 0) break;

} pos = ftell(fp); pos = pos - sizeof(parola); fseek(fp,pos,0); fwrite(parolaNuova,sizeof(parola),1,fp); fclose(fp);}

36