Riassunto esame Informatica, prof. Carnevali, libro consigliato Fondamenti di programmazione, Vicario: programmazione in C

LISTE

E' una successione di valori di un tipo.Solitamente codifica due informazioni: il valore degli elementi e la

relazione di ordine fra i valori stessi. Due liste differiscono sia per i valori che comprendono, sia per la

posizione con cui quiesti vengono disposti.Sulle liste possono verificarsi 5 operazione:

-INSERIMENTO: aggiunge un nuovo elemento alla lista, può avvenire in testa,in coda o in pos.specifica

-CANCELLAZIONE: rimuove un elemento, può avvenire in capo,in coda o in posizione specifica.

-VISITA: applica un trattamento comune a tutti gli elementi della lista(es.stampa,somma dei valori...)

-RICERCA: determin a se la lista contiene un elemento specifico.

-INIZIALIZZAZIONE:serve a dichiarare un elemento invariante,utile per l'elaborazione del programma.

RAPPRESENTAZIONE IN FORMA SEQUENZIALE:

Gli elementi sono roppresentati su un array e il loro ordine è codificato implicitamente dal suo indice.

Tale rappresentazione può essere realizzata codificando i valori su un array associato a una variabile

che indica il numero degli elementi rappresentati.Rende molto pratiche le operazioni in coda ma

risultano difficili quelle in testa ..Anche la ricerca e la visita sono semplici.

Si crea un array circolare di N posizioni in memoria,contrassegnato da tre variabili:

Size: è la dimensione dell'array N

head: è il numero della posizione in cui è stata inserito il primo valore

Tail: è il numero del primo indirizzo libero dopo l'ultima vaiabile inserita.

Se Head=Tail --> La lista è vuota.

Se (Tail+1) % size =1 --> La lista è piena.L'ultima locazione resta sempre libera per distinguere il caso

in cui l'array è pieno da quello in cui è vuoto.

OPERAZIONI:

.INSERIMENTO IN CODA:

inserisce il valore nella locazione indicata da Tail e aumenta Tail di 1(secondo l'aritmetica degli indirizzi.

INSERIMENTO IN TESTA: Controlla che il buffer non sia pieno, decrementa di uno l'indirizzo di head e

inserisce il valore nel nuovo indirizzo(head deve sempre contenere un valore, tail non lo contiene mai).

CANCELLAZIONE IN CODA: Decrementa di 1 il valore di Tail ed elimina il valore della variabile

allocata dopo il decremento dell'indirizzo.

Il programma di una lista in foma sequenziale si crea su un array lineare i cui indici e dimensione sono

indicati dai puntatori a Head,Tail e Size.

La Dichiarazione e definizione di una lista si può compilare con questi passaggi:

-inclusione di librerie stdio.h e stdlib.h e definizione del tipo Booleano

-dichiarazione del dato strutturato "lista"

struct stack { int size; int TOS; float*buffer;}

-funzione INIT: Alloca il buffer su cui memorizzare i valori della lista e dichiara l'invariante(numero

massimo di elementi N),Se head=tail->Lista vuota,altrimento head è l'indice di testa e tail quello di coda

void init(struct list*ptr,int size) // riceve in ingresso il puntatore alla struttura e la sua dimensione.

{ptr->buffer=(float*)malloc(size*sizeof(float)); //alloca il buffer

ptr->size=size; ptr->head=0; ptr->tail=0;} // inizializza tail e head a 0,attribuisce size a ptr->size

-Boolean tail_insert(struct list*ptr, float value) è l'inserimento in coda.inserisce il valore nell'indirizzo

in coda e aumenta l'indirizzo di 1(secondo l'aritmetica degli indirizzi

// la guardia distingue il caso comune dall'eccezione.

{ if ((ptr->tail+1)%(ptr->size)!=ptr->head){ //se tail+1/size!= head

ptr->buffer[ptr->tail]=value //alloca il valore nella locazione indicata da tail nel buffer

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

return TRUE;}

else return FALSE;}

Per incrementare e decrementare si una l'espressione ptr->tail=(ptr->tail+1)%ptr->size perché, a

differenza di ptr->tail++,comprende anche il caso eccezionale head=0.

Si usano i puntatori al posto delle variabili per ridurre il numero di paramentri copiati sullo stack.

-Boolean head_insert(struct list*ptr,,float value) è l'inserimento in testa.controlla che il buffer sia

vuoto,decrementa head di un indirizzo e inserisce il valore nel nuovo indirizzo.

// la guardia distingue il caso comune dall'eccezione.

{ if ((ptr->tail+1)%ptr->size!=ptr->head){ //controlla che buffer non sia pieno

ptr->head=(ptr->head+ptr->size-1)%ptr->size //decrementa di un indirizzo la head

ptr->buffer[ptr->head]=value;} // inserisce il valore nel nuovo indirizzo di head

return TRUE;

else return FALSE ;}

void visit(struct list*ptr) è la visita di stampa. Riceve il puntatore alla struttura,stampa l'elemento e

incrementa il puntatore finchè non ha stampato tutti gli elementi della lista.

{ int position; // seleziona la locazione,controlla che non sia tail e inrementa la locazione

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

printf("%f",ptr->buffer[position]); } //stampa a video ogni valore visitato.

-Boolean search(struct list*ptr, float value) è la funzione di ricerca, riceve un value acquisito da

tastiera nella main () e restituisce TRUE se è nella lista,altrimenti rrestituisce FALSE.

{Boolean found; int position; //introduce le variabili found(conferma ritrovamento valore) e position

position=ptr->head; found=FALSE; //assegna a position la locazione di head e stabilisce found FALSE

while(found==false,&& position!=ptr->tail) //finche non trova il valore e non si raggiunge la tail

{ if (ptr->buffer[position]==value) // se trova il valore restituisce found== TRUE

found==TRUE;

else position=(position+1)%ptr->size; } //se non lo trova incrementa l'indirizzo.

return found; /7 se il valore è stato trovato found è TRUE altrimenti è FALSE.

RAPPRESENTAZIONE CON ARRAYS E INDICI:

Memorizza i valori su un buffer ma ne virtualizza l'ordine di sequanza.Il buffer è un array di dati

strutturati (records), ognuno dei quali contiene un valore e l'indice del record interno al buffer che

contiene il successivo valore della lista. L'ultimo elemento come indice successivo presenta un dato

illegale,solitamente la dimensione stessa del buffer. I recors liberi sono collegati fra sè attraverso

indici,per rendere più facile il collocamento di un altro valore. Records liberi e records occupati non

sono collegati anche se appartengono allo stesso buffer.

ESEMPIO: Si rappresenta adesso una lista {10,20,50} con 2 elementi liberi:

-DEFINIZIONE DEI DATI STRUTTURATI: icludo librerie e definisco Boolean

struct record{ // Serve a definire tutti i record che contengono numero e indirizzo succesivo

float value; int next)};

struct list{

int first;

int free;

int size;

int struct record*buffer;

I records occupati sono concatenati a partire dall'indirizzo del record che contiene il 1° valore della lista

-void(struct list*ptr, int size) alloca il buffer,assegna a first il valore illegale,assegna a free il primo

l'indirizzo del 1° record. I VALORI NON SONO ANCORA STATI ASSEGNATI! OGNI RECORD E'

LIBERO! OGNI RECORD CONTIENE L'INDIRIZZO DEL SUCCESSIVO!

{ int count;

ptr->buffer=(struct record*)malloc(size*sizeof(struct record)); // definisce il buffer

ptr->size=size; // assegna la dimensione della lista

ptr->first=ptr->size; // assegna a first il valore illegale (non ci sono dati memorizzati)

ptr->free=0; // assegna a first l'indirizzo del primo record libero.(è 0 perchè sono tutti liberi)

for(count=0;count<ptr->size;count++) //inizializza count a 0,per ogni volta che count è minore di size

ptr->buffer[count].next=count+1; } // l'area next di record viene incrementata di 1,si incrementa

count,si passa al record successivo e si assegna all'area next il valore del precedente+1.

Void visit(struct list*ptr) riceve in entrata il puntatore alla struttra "lista",effettua la visita e stampa i

valori

{ //QUESTA FUNZIONE DEVE EESSERE USATA DOPO CHE SONO STATI INSERITI

int position; // I VALORI. ALLORA FIRST CONTERRA' IL PRIMO VALORE DELLA LISTA.

position=ptr->first; //assegna a position il valore della prima locazione record.Il valore di first sembra

while(position!=ptr->size) //errato ma è corretto perchè successivamente first sarà la 1°loc.con valore.

{ printf("%f",ptr->buffer[position].value); //stampa a video il valore contenuto in tale locazione

position=ptr->buffer[position].next;};} // position assume il valore della locazione in cui è

contenuto il valore successivo della lista. Questa assegnazione sembra senza senso, ma lo avrà a fine

prrogramma.

Boolean search(struct list*ptr,float value) è la ricerca di un elemento. E' simile alla precedente.

{ int position; Boolean found;

position=ptr->first; found==FALSE;

while(found==FALSE && position!=ptr->size)

if(ptr->buffer[position].value==value)

found==TRUE;

else position=ptr->buffer[position].next;

Boolean pre_insert(struct list*ptr,float value) corrisponde all'inserimento in testa.se la lista degli

elementi liberi(tutte le caselle che non contengono valore,ovvero quelle che sono state definite per

collegamento alla prima,che è quella puntata da ptr->free) libera non è vuota(nel senso che esistono

elementi liberi). Sgancia il primo elemento (ptr->free), lo aggangia in testa alla lista dei valori utili(quelli

puntati da ptr->first) e ci memorizza il valore.

{

int moved; if (ptr->free!=ptr->size){ // if stabilisce la condizione ordinaria di disponibilità di memoria

moved=ptr->free; // moved assume il valore della posizione della prima locazione libera

ptr->free=((ptr->buffer[ptr->free].next; //ptr->free viene assegnato alla posizione successiva

ptr->buffer[moved].value=value; // assegna il valore alla locazione "moved"(ex-locazione di free)

ptr->buffer[moved].next=ptr->first; //assegna l'indirizzo della locazione successiva all'area [move].next

ptr->first=moved; return TRUE;} //assegna a first la locazione del primo record contenente valore.

else return FALSE;}

-Boolean suf_insert(struct list*ptr,, float value) è l'inserimento in coda. Se la lista degli elementi liberi

non è vuota,sgancia il primo elemento e lo inserisce in coda alla lista degli elementi utili. Copia il valore

acquisito su questo elemento e attribuisce il valore illegale(size) al campo .next

{

int moved;

int*position_ptr;

if(ptr->free!=ptr->size){

moved=ptr->free; //moved codifica la prima locazione libera

ptr->free=((ptr->buffer)[ptr->free]).next; //ptr->free ora codifica la posizione successiva rispetto a prima

position_ptr=&ptr->first; //position_ptr assume il valore dell'INDIRIZZO del 1° valore

while (*position_ptr!=ptr->size){ //ripete finchè *position_ptr non ha puntato tutte le locazioni

position_ptr=&(ptr->