Appunti Programmazione 2

//ARRAY

//Visualizzare gli elementi di un array

-​ CASO BASE

se la posizione (indice) del vettore è maggiore o uguale alla

dimensione massima del vettore, interrompe la funzione con return

-​ CASO RICORSIVO

richiama la funzione sulla posizione (indice) successiva del vettore

void stampa_array(int vet[],int p,int len){

​ //caso base

​ if(p>=len){

​ ​ return;

​ }

​ printf("[%d]:%d\n",p,vett[p]);

​

​ //caso ricorsivo

​ return stampa_array(vett,p+1,len);

} 110

//Sommare gli elementi di un array

-​ CASO BASE

se la posizione (indice) del vettore è maggiore o uguale della

dimensione del vettore, restituisce 0

-​ CASO RICORSIVO

richiama la funzione sulla posizione (indice) successiva del vettore

int array_somma_v1(int vett[],int p, int len){

​ //caso base

​ if(p>=len){

​ ​ return 0;

​ }

​ //caso ricorsivo

​ return (vett[p]+array_somma_v1(vett,p+1,len));

}

void array_somma_v2(int vett[],int p,int len, int *s){

​ //caso base

​ if(p>=len){

​ ​ return;

​ }

​ //caso ricorsivo

​ *s=*s+vett[p];

​ return array_somma_v2(vett,p+1,len,s);

} 111

//Cercare un valore nell’array

-​ CASO BASE

se la posizione (indice) del vettore è maggiore o uguale della

dimensione del vettore restituisce -1

-​ CASO RICORSIVO

richiama la funzione sulla posizione(indice) successiva del vettore

int array_cerca(int vett[],inp p,int len,int x){

​ //caso base

​ if(p>=len){

​ ​ return -1;

​ }

​ //caso ricorsivo

​ if(vett[p]==x)

​ ​ return p;

​ else

​ ​ return array_cerca(vett,p+1,len,x);

} 112

//Cercare il massimo nell’array

-​ CASO BASE

se la posizione (indice) del vettore è maggiore o uguale a 0 della

dimensione del vettore restituisce -1

-​ CASO RICORSIVO

richiama la funzione sulla posizione (indice) successiva del vettore

void array_max(int vet[],int p,int len, int *r){

​ //caso base

​ if(p>=len){

​ ​ return -1;

​ }

​ //caso ricorsivo

​ if(p==0){ //primo elemento come campione

​ *r=vett[0];

​ }

​ else{

​ ​ if(vett[p]>*r){

​ ​ ​ *r=vett[p];

​ ​ }

​ }

​ return array_max(vett,p+1,len,r);

} 113

//Visualizzare una stringa

-​ CASO BASE

se il carattere è ‘\0’ , interrompe la ricorsione con un return

-​ CASO RICORSIVO

richiama la funzione sulla posizione (indice) successiva della

stringa

void stampa_stringa(char *s){

​ //caso base

​ //*s accede al contenuto puntato da s

​ if(*s=='\0'){

​ ​ return;

​ }

​ //*s contiene l'indirizzo di memoria puntato

​ printf("Carattere puntato:%p->valore:%c(%d)\n", s,*s,*s);

​

​ //caso ricorsivo

​ //s+1 sposta il puntatore all'elemento successivo della stringa

​ return stampa_stringa(s+1);

} 114

//Lunghezza di una stringa

-​ CASO BASE

se il carattere corrente è ‘\0’ restituisce 0

-​ CASO RICORSIVO

richiama la funzione sulla posizione(indice) successiva della

stringa

int stringa_len(char *s){

​ //caso base

​ //*s accede al contenuto puntato da s

​ if(*s=='\0'){

​ ​ return 0;

​ }

​ //caso ricorsivo

​ //s+1 sposta il puntatore all'elemento successivo della stringa

​ return 1+stringa_len(s+1);

} 115

//Contare maiuscole e minuscole presenti in una

stringa

-​ CASO BASE

se il carattere corrente è ‘\0’ interrompe la ricorsione con return

-​ CASO RICORSIVO

richiama la funzione sulla posizione (indice) successiva della

stringa e aumenta i contatori

void stringa_mi_ma(char *s,int *mi,int *ma){

​ //caso base

​ //*s accede al contenuto puntato da s

​ if(*s=='\0'){

​ ​ return;

​ }

​ //caso ricorsivo

​

​ //maiuscole

​ if(isupper(*s)){

​ ​ *ma=*ma+1;

​ }

​

​ //minuscole

​ if(islower(*s)){

​ ​ *mi=*mi+1;

​ }

​

​ return stringa_mi_ma(s+1,mi,ma);

} 116

//Trasformare una stringa

-​ CASO BASE

se il carattere corrente è ‘\0’ interrompe la ricorsione con un return

-​ CASO RICORSIVO

richiama la funzione sulla posizione (indice) successiva della

stringa

void stringa_maiuscole(char *s){

​ //caso base

​ //*s accede al contenuto puntato da s

​ if(*s=='\0'){

​ ​ return;

​ }

​ //caso ricorsivo

​ if(islower(*s){

​ ​ *s=toupper(*s);

​ }

​ //s+1 sposta il puntatore all'elemento successivo della stringa

​ stringa_maiuscole(s+1);

}

//VERSIONE CON ARRAY

void stringa_maiuscole(char s[],int p){

​ //caso base

​ if(s[p]=='\0'){

​ ​ return;

​ }

​ //caso ricorsivo

​ if(islower(s[p]){

​ ​ s[p]=toupper(s[p]);

​ }

​ //p+1 sposta il puntatore all'elemento successivo della

stringa

​ stringa_maiuscole(s,p+1);

} 117

//Algoritmi ricorsivi sulle liste

//Creare una lista

Node * lista_crea(int n){

​ Node *headptr;

​

​ //caso base

​ if(n==0){

​ ​ return NULL;

​ }

​ else{//caso ricorsivo

​ headptr=(Node *)malloc(sizeof(Node));

​ if(headPtr==NULL) //verificare che sia stata allocata la partizione di

memoria

​ return NULL;

​ int num=ran()%(MAXRAND - MINRAND+1)+MINRAND;

​ //genera numeri casuali tra MINRAND e MAXRAND

​ headPtr->data=num;

​ headPtr->next=lista_crea(n-1);

​ return heardPtr;

​ }

}

//Visualizzare una lista

void lista_visualizza(Lista *headPtr,int p){

​ //caso base

​ if(headPtr==NULL){

​ ​ return;

​ }

​ else{//caso ricorsivo

​ printf("Nodo [%d]: %d\n",p,headPtr->data);

​ return lista_visualizza(headPtr->nextPtr,p+1);

​ }

} 118

//Contare gli elementi di una lista

int lista_conta_v1(Node *headPtr){

​ //caso base

​ if(headPtr==NULL){

​ ​ return 0;

​ }

​ else{

​ ​ return 1+lista_conta_v1(headptr->next);

​ }

}

//Versione con contatore per riferimento

void lista_conta_v2(Node *headPtr,int *c){

​ //caso base

​ if(headPtr==NULL){

​ ​ return;

​ }

​ else{

​ ​ *c=*c+1;

​ ​ return lista_conta_v2(headPtr->next);

​ }

} 119

//Sommare gli elementi di una lista

int lista_somma_v1(Node *headPtr){

​ //caso base

​ if(headPtr==NULL){

​ ​ return 0;

​ }

​ else{//caso ricorsivo

​ return headPtr->data+lista_somma_v1(headPtr->next);

​ }

}

//con puntatore

voit lista_somma_v2{Node *headPtr,int *s){

​ //caso base

​ if(headPtr==NULL){

​ ​ return;

​ }

​ else{//caso ricorsivo

​ *s=*s+lista_somma_v2(headptr->next,s);

​ }

}

//Cancellare una lista

void lista_cancella(Lista *headPtr){

​ //caso base

​ if(headPtr==NULL){

​ ​ return;

​ }

​ //caso ricorsivo

​ lista_cancella(headPtr->nextPtr);

​ free(headPtr);

} 120

//Ricercare un elemento all’interno della lista

int lista_cerca(Lista *headPtr,int x,int *p){

​ //caso base

if(headPtr==NULL){

​ *p=-1;

​ return 0; //falso

}

if(headPtr->data==x){

​ return 1;//vero

}

//caso ricrosivo

*(p)++;//*p=*p+1

return lista_cerca(headPtr->nextPtr,x,p);

}

//Cancellare un elemento da una lista

//p posizione del nodo corrente

//k posizione del nodo che si desidera cancellare

Lista *lista_cancella_nodo(Lista *headPtr,int p, int k){

​ //se la lista è vuota

​ if(headPtr==NULL){

​ ​ return NULL;

​ }

headPtr->nextPtr=lista_cancella_nodo(headPtr->nextPtr,p+1,k);

​ if(p==k){

​ ​ lista *newPtr=headPtr->nextPtr;

​ ​ free(headPtr);

​ ​ return newPtr;

​ }

​

​ ​ return headPtr;

} 121

//Visualizzare una lista al contrario

void lista_contrario(Node *headPtr){

​ //caso base

​ if(headPtr==NULL){

​ ​ printf("NULL\n");

​ ​ return;

​ }

​ //caso ricorsivo

​ lista_contrario(headPtr->next);

​ printf("Nodo:%d\n",headPtr->data);

}

//Makefile

//Per compilare più file è necessario il comando:

gcc file1.c file2.c……fileN.c-Wpedantic-Wextra

//Per ogni nuova compilazione bisogna lanciare lo stesso comando,

solitamente si sfrutta la history del terminale per ritrovare il comando

lanciato ed eseguirlo nuovamente

//Ogni volta che si modifica un singolo file, è necessario ricompilare tutte

le sorgenti , ciò in progetti di grandi dimensioni può rappresentare una

perdita di tempo

//Tutto ciò è risolvibile attraverso Makefiles

//Makefile: Esempio

Makefile

build:main.c file1.c

gcc -o hellomake main.c file1.c 122

//Salvando questo codice in un file chiamato Makefile o makefile e

invocando il comando make verrà eseguito il primo target incontrato nel

file (in questo caso build)

//Makefile:Esempio 2

Makefile

CC=gcc

CFLAGS=-Werror -Wpedantic -Wextra

build:main.o file.o

$(CC) -o hellomake main.o file1.o $(CFLAGS)

//Le due costanti speciali CC e CFLAGS consentono di specificare a

make il compilatore da usare (gcc) e i flags da includere nella

compilazione

//Indicando i file oggetto(“.o”) il compilatore sa che deve compilare (solo

se necessario) i rispettivi file .c

Recall compilazione:

sorgente->file oggetto->linking 123

//Makefile:Esempio 3

//Nell’esempio 2 se si dovesse fare un cambiamento in un header file

(header.h) da cui dipendono i sorgenti, il compilatore non se ne

accorgerebbe

è possibile specificare questa dipendenza attraverso la macro DEPS

Makefile

CC=gcc

CFLAGS=-Werror -Wpedantic -Wextra

DEPS

%.o: %.c $(DEPS)

$(CC) -c -o $@ $< $(CFLAGS)

build: main.o file1.o

$(CC) -o hellomake main.o file1.o $(CFLAGS)

//La regola aggiunta indica che per generare ogni file oggetto (%.o)

bisogna compilare il rispettivo sorgente (%.c) insieme alla lista delle

dipendenze (header): per fare questo viene invocato il compilatore

$(CC), usando -c per generare il file oggetto

//$@ indica il nome finale da utilizzare (corrisponderà al nome della

sorgente + .o)

//$< indica di includere i file DEPS nella compilazione 124

//Makefile:Esempio 4

//La compilazione produrrà il file eseguibile finale, ma anche molti file

oggetto