Fondamenti di programmazione - Algoritmi

LISTA SEQUENZIALE

struct list{

float*buffer;

int size;

int head;

int tail;

}; 1. Inizializzazione:

void init(struct list*ptr,int dimension){

ptr->size=dimension;

ptr->head=0;

ptr->tail=0;

ptr->buffer=(float*)malloc(sizeof(float)*dimension);

}

2. Inserimento in coda:

boolean suf_insert(struct list*ptr,float value){

boolean success=FALSE;

if ( (ptr->head) != (ptr->tail+1)%(ptr->size) ){ //controllo lista non piena

ptr->buffer[ptr->tail]=value; //inserisce in tail

ptr->tail=(ptr->tail+1)%(ptr->size); //incrementa tail

success=TRUE;

}

return success;

}

3. Inserimento in testa:

boolean pre_insert(struct list*ptr,float value){

boolean success=FALSE;

if( (ptr->head) != (ptr->tail+1)%(ptr->size) ){//controllo lista non piena

ptr->head=((ptr->head)+(ptr->size-1))%(ptr->size); //decrementa head

ptr->buffer[ptr->head]=value; //inserisce in head

success=TRUE;

}

return succsess;

}

4. Cancellazione in testa:

boolean pre_delete(struct list*ptr,float*value){

boolean success=FALSE;

if (ptr->head != ptr->tail){ //controllo lista non vuota

*value=ptr->buffer[ptr->head]; //assegna a value il valore in head

ptr->head=(ptr->head+1)%(ptr->size); //incrementa head

success=TRUE;

}

return success;

}

5. Visita di stampa:

void visit(struct list*ptr);

int position;

for (position=(ptr->head); position != (ptr->tail); (position+1)%(ptr->size)){

//scorre indice position da head a tail-1

printf(“%f”,ptr->buffer[position]); //stampa elemento in posizione position

}

}

6. Ricerca:

boolean search(struct list*ptr,float value){

boolean found=FALSE; //inizializza found

int position=(ptr->head); //inizializza position

while ( position != (ptr->tail) && found==FALSE){ //finché position non arriva

alla fine e found è falso itera

if (is_equal(ptr->buffer[position],value)) found=TRUE; //confronto

else position=position+1%(ptr->size); //incrementa position se non

} trova elemento

return found;

}

LISTA COLLEGATA CON PUNTATORI

struct list{

float value;

struct list*next_ptr;

}; 1) Inizializzazione:

void init(struct list**ptrptr){ //la lista vuota è composta da un puntatore a NULL

*ptrptr=NULL;

}

2) Inserimento in testa: //non fallisce a meno di memoria insufficiente

void pre_insert(struct list**ptrptr,float value){

struct list*tmp;

tmp=*ptrptr; //assegna a tmp indirizzo prossimo elemento

*ptrptr=(struct list*)malloc(size of(struct list)); //alloca nuovo elemento

(*ptrptr)->value=value; //assegna valore

(*ptrptr)->next_ptr=tmp; //assegna al puntatore del nuovo elemento

} l'indirizzo del prossimo elemento

3) Inserimento in coda: //non fallisce a meno di memoria insufficiente

void suf_insert(struct list**ptrptr,float value){

while( *ptrptr != NULL ){ //avanza ptrptr finché non punta a NULL

ptrptr=&((*ptrptr)->next_ptr); //infatti associa a ptrptr l'indirizzo di next_ptr

}

pre_insert(ptrptr,value);

}

4) Ricerca:

boolean search(strcut list*ptr,float value,struct list**target_ptr){

boolen found=FALSE; //inizializza found a FALSE

while(ptr != NULL && found==FALSE){ //itera fino a fine lista o elemento trovato

if(is_equal(ptr->value,value)){ //confronto

found=TRUE; //imposta found a TRUE se trova elemento

*target_ptr=ptr; //target_ptr punta all'elemento

} contenente il valore cercato

else ptr=ptr->next_ptr; //altrimenti scorre ptr

}

return found;

}

5) Ricerca in lista ordinata: //ipotizza lista con valori ordinati in modo crescente

boolean ord_search(struct list*ptr,float value,struct list**target_ptr){

boolean found=FALSE;

while( ptr != NULL && found==FALSE && (ptr->value)<=value ){

if( is_equal(ptr->value,value )){

found=TRUE;

*target_ptr=ptr;

}

else ptr=ptr->next_ptr;

}

return found;

}

6) Cancellazione in testa: //fallisce per lista vuota,restituisce valore elemento eliminato

boolean consume_first(struct list**ptrptr, float*value_ptr){

boolean success=FALSE;

struct list*tmp;

if (*ptrptr != NULL){ //lista non vuota

tmp=*ptrptr; //assegna a tmp indirizzo dell'elemento da cancellare

*ptrptr=(*ptrptr)->next_ptr; //assegna a ptrptr indirizzo elemento successivo

*value_ptr=tmp->value; //assegna a value_ptr valore elemento da cancellare

free(tmp); //libera l'elemento puntato da tmp

success=TRUE;

}

return success;

}

7) Clonazione di una lista:

void clone(struct list*src_ptr,struct list**dst_ptr){

init(dst_ptr); //inizializza lista destinazione

while(src_ptr != NULL){ //itera fino alla fine della lista sorgente

suf_insert(dst_ptr, (src_ptr->value)); //inserisce elemento da src in coda a dst

dst_ptr=&((*dst_ptr)->next_ptr); //scorre dst_ptr

src_ptr=src_ptr->next_ptr; //scorre src_ptr

}

8) Visita:

void visit(struct list*ptr){

while(ptr != NULL){ //itera fino a fine lista

printf(“%f”,ptr->value); //stampa valore elemento puntato

ptr=ptr->next_ptr; //scorre ptr

}

}

9) Somma elementi lista:

void sum(struct list*ptr,float*sum){

*sum=0; //inizializza sum a 0

while(ptr!=NULL){ //itera fino a fine lista

*sum+=ptr->value; //sum= sum+(valore elemento corrente)

ptr=ptr->next_ptr; //incrementa ptr

}

}

FORME RICORSIVE

1) Visita ricorsiva:

void visit_r(struct list*ptr){

if(ptr != NULL){ //guardia (consente arresto iterazione)

printf(“%f”,ptr->value); //stampa valore elemento corrente

visit_r(ptr->next_ptr); //chiama se stessa incrementando ptr

}

}

2) Inserimento in coda ricorsivo:

void suf_insert_r(struct list**ptrptr,float value){

if(*ptrptr != NULL){ //guardia

suf_insert_r(&((*ptrptr)->next-ptr),value); //chiama se stessa incrementando ptrptr

}

else{ //arrivata all'ultimo elemento inserisce in

pre_insert(ptrptr,value); testa a lista vuota

}

}

3) Ricerca ricorsiva:

boolean search_r(struct list*ptr,float value,struct list**target){

boolean found=FALSE;

if (ptr != NULL){ //guardia

if (is_equal(ptr->value,value)){ //se valore elemento corrente=valore cercato

*target=ptr; //target punta a elemento trovato

found=TRUE; //found impostata su TRUE

}

else{

return search_r(ptr->next_ptr,value,target); //altrimenti ritorna found di se

} stessa applicata all'elemento successivo

}

else return found; //se arriva a fine lista senza trovare elemento cercato da FALSE

}

ALGORITMI DI RICERCA

1) Ricerca sequenziale:

I dati sono memorizzati in un array V in memoria. L'algoritmo confronta il valore cercato

con tutti gli elementi di V fino a trovare tale elemento.

boolean seq_search(float*V,int N,float target){

boolean found=FALSE;

int count=0;

while(count<N && found==FALSE){ //itera fino a trovare target o a fine array

if( is_equal(V[count],target)){ //confronta elementi con target (con la

found=TRUE; precisione di macchina)

}

else count++; //se non trova target scorre l'indice

}

return found;

}

# include <float . h> (FLT_EPSILON è la precisone di macchina)

boolean is_equal(float a , float b){

float dif;

dif=a-b;

if(dif <= a*FLT_EPSILON && dif>= -a*FLT_EPSILON){

return TRUE;

}

else return FALSE;

}

2) Ricerca binaria:

I dati sono memorizzati in un array V ordinato in maniera crescente. L'algoritmo confronta

target con l'elemento in posizione mediana di V (V[N/2]): se questo è maggiore o uguale a

target, la ricerca prosegue allo stesso modo nel semivettore sinsitro, altrimenti nel destro.

Ricorsiva:

boolean binary_search(float*V,int N,float target){

boolean found=FALSE;

if (N>0){ //guardia per array vuoto

if (isequal(V[N/2],target)){ //confronta elemento mediano con target

found=TRUE;

}

else{

if (V[N/2]>target){ //se elemento mediano è maggiore di target

return binary_search(V,N/2,target); //prosegue con ricorsione a sinistra

}

else return binary_search(&V[N/2+1],(N/2)-1,target); //altrimenti prosegue

} con ricorsione a destra

return found;

}

}

Iterativa:

boolean binary_search_iter(float*V,int N,float target){

int first=0; //indice di inizio vettore o sottovettore

int length=N; //lunghezza vettore o sottovettore

boolean found=FALSE;

while (length>0 && found==FALSE){ //guardia per vettore non nullo

if ( is_equal(V[first+length/2],target) found=TRUE;//confronto con elemento

else{ mediano

if (V[first+length/2]>target){ //se elemento mediano>target

length=length/2; //itera a sinistra dimezzando lenght

}

else{

first=first+length/2+1; //altrimenti itera a destra incrementando

length=length-length/2-1; first e cambiando lenght

}

}

}

return found;

}

3) Ricerca a salti:

I dati sono memorizzati in un array V ordinato in maniera crescente. L'algoritmo confronta

target con gli elementi in posizione k*step fino a trovare un elemento maggiore di target o

la fine di V, dopodiché esamina gli elementi presenti nell'ultimo step.

boolean step_search(float*V,int N,float target,int step){

int up=0; //indice che scorre in avanti

int down; //indice che scorre indietro

boolean greater_or_equal_found=FALSE;

boolean equal_found=FALSE;

while (up<N && greater_or_equal_found == FALSE){

if (V[up]>=target) greater_or_equal_found=TRUE; //ferma up se trova

else{ elemento>=target

up+=step; //altrimenti incrementa up di uno step

if (up>N-1 && up<N-1+step) up=N-1; //se up supera lunghezza array e

} l'up precedente non è arrivato a fine array assegna a up ultima posizione

}

if (greater_or_equal_found==TRUE){ //se ha trovato elemento>=target

down=up; //assegna a down posizione di up

while( V[down]>=target && equal_found==FALSE && down>=0){

//itera finché gli elementi sono>=target o non trova target o non

arriva a inizio array

if (is_equal(V[down],target) equal_found=TRUE; //se trova target, ok..

else down--; //..altrimenti decrementa down

}

}

return equal_found;

}

4) Ricerca binaria su lista sequenziale:

La lista sequenziale è ordinata in maniera crescente.

boolean binary_search_seq_list(struct list*ptr,float target){

int first=ptr->head; //assegna all'indice first il valore di head

int length=(ptr->tail – ptr->head)%(ptr->size); //lunghezza sottovettore

boolean found=FALSE;

while (length>0 && found==FALSE){//guardia array non nullo e target non trovato

if (is_equal(ptr->buffer[(first+length/2)%ptr->size],target)){ //confronto con

fou