Compressione di file

Materie:	Appunti
Categoria:	Informatica
Download:	43
Data:	31.10.2000
Numero di pagine:	6
Formato di file:	.doc (Microsoft Word)

Cosa e’ una Coda ad N livelli.
Una Coda ad N livelli è una Coda in cui ad ogni elemento è associato un valore intero compreso tra 0 ed N-1, denominato livello dell’elemento.
A più elementi può essere associato lo stesso livello.
La gestione degli elementi della Coda ad N livelli avviene secondo una tecnica denominata FIFO (first in-first out) propria delle code semplici ma particolarizzata dal fatto che un elemento di livello i viene comunque estratto prima di un elemento di livello j se j < i, indipendentemente dall’ordine di inserimento nella coda; il primo elemento ad uscire e’ dunque il primo ad essere entrato tra quelli al livello più alto.
Il TDA Coda ad N livelli e’ adatto per modellare centri servizi con clienti a priorità diversa; la condivisione della CPU in sistemi multiprogrammati gestiti in time_sharing e l’arbitraggio dei bus per la gestione delle periferiche di un sistema di calcolo sono tipici esempi che possono essere modellati con una Coda ad N livelli.
Il TDA CodaLivelli è definito dai seguenti insiemi:
D={ CodaLivelli, Elem, Int, Bool } dove CodaLivelli è il dominio di interesse e Elem è il dominio degli elementi che formano le code;
F={ CreaCoda(), NumLivelli(), InCoda(), OutCoda(), Primo(), Lunghezza(), EstVuota() } .
Le funzioni definite in F operano sui domini di D e hanno i seguenti significati:
• CreaCoda ( Int nl ) → CodaLivelli
La funzione crea una coda ad nl livelli vuota.
• NumLivelli( CodaLivelli cl ) → Int
La funzione restituisce il numero di livelli di cl.
• InCoda ( CodaLivelli cl, Elem e, Int l ) → CodaLivelli
La coda cl viene modificata inserendo l’elemento e al livello l.
• OutCoda ( CodaLivelli cl ) → CodaLivelli
La coda cl viene modificata estraendo il primo elemento del livello più alto.
• Primo ( CodaLivelli cl ) → Elem
La funzione restituisce il primo elemento della coda cl al livello più alto.
• Lunghezza ( CodaLivelli cl, int l ) → Int
La funzione restituisce il numero di elementi di cl presenti al livelli l.
• EstVuota ( CodaLivelli cl ) → Bool
La funzione restituisce true se la coda cl è vuota, false altrimenti.
Descrizione del progetto
Il progetto presentato consiste nella realizzazione di tre diverse implementazioni della classe CodaLivelli e nell’utilizzo di una di queste per l’ordinamento di un vettore di interi.
Per la realizzazione dell’implementazione di base, da cui, con opportune modifiche, sono state ricavate le altre due, si è utilizzato un vettore ad N posizioni allocato dinamicamente; ogni componente del vettore è una struct coda contenete la sequenza degli elementi del generico livello .
Al fine di una corretta gestione delle operazioni di inserimento e cancellazione, per ogni coda semplice, viene definito sia il puntatore al primo elemento entrato che il puntatore all’ultimo; viene inoltre introdotta una variabile contatore che memorizza il numero di elementi presenti.
Questi tre campi definiscono la struct coda.
Ogni elemento è rappresentato con un record a due campi, uno contenente l’informazione vera e propria ad esso associata, l’altro contenente un puntatore all’elemento successivo della coda.
Per quanto riguarda la classe CodaLivelli, essa comprende, oltre a tutte le funzioni che definiscono il TDA e alle funzioni “proprie” di una classe, quali costruttore, costruttore di copia e distruttore, due campi; uno per l’allocazione dinamica del vettore di code (inizio) e uno che conserva il numero di livelli della codalivelli in esame (num_livelli).
Si mostra qui di seguito uno schema della struttura dati utilizzata per l’implementazione di base della classe CodaLivelli.
La realizzazione del progetto consiste dunque in:
• Presentazione dell’implementazione di base della classe CodaLivelli.
(file codalivelli.h e codalivelli.cpp)
• Scrittura di una funzione che ordina un vettore di m locazioni i cui elementi sono degli interi compresi tra 0 e v-1 (eventualmente con ripetizioni), utilizzando una variabile di tipo CodaLivelli con v livelli e calcolo della complessità computazionale.
(file ordinamento_vett.cpp)
• Riprogettazione della classe aggiungendo un campo che memorizza il numero totale di elementi della CodaLivelli modificando le funzioni della classe stessa in modo che tale campo venga gestito correttamente.
(file codalivelli2.h, codalivelli2.cpp e prova_codalivelli2.cpp)
• Riprogettazione della classe CodaLivelli in modo che utilizzi un vettore di oggetti di tipo Coda per la sua rappresentazione.
(file coda+codaliv.h, coda+codaliv.cpp e prova_coda+codalivelli.cpp)

Per quanto riguarda la definizione della classe Coda, è stata mantenuta la stessa struttura dati definita in precedenza (configurazione a tre campi), e sono state realizzate le funzioni proprie del TDA Coda che vengono qui di seguito riportate con i relativi significati:
• Crea ()→ Coda
La funzione crea una coda vuota.
• GetFirst (Coda c) → Elem
La funzione restituisce il primo elemento della coda c.
• Tail (Coda c) → Coda
La Coda c viene modificata estraendo il primo elemento.
• PutIn ( Coda c, elem e ) → Coda
La Coda c viene modificata inserendo l’elemento e.
• IsEmpty ( Coda c ) → Bool
La funzione restituisce true se la coda c è vuota, false altrimenti.
Le funzioni della classe CodaLivelli sono state quindi ridefinite tramite le funzioni della classe Coda.
In tutte le realizzazioni presentate la funzione CreaCoda viene espletata attraverso il costruttore della classe.
Si riportano di seguito i vari codici del progetto.
// Implementazione di base
// File codalivelli.h
#include
typedef int TipoElem;
struct item
{ TipoElem val;
item* next;
};
struct coda
{ int num_elem;
item* front;
item* back;
};
class CodaLivelli
{ friend ostream& operatornext = pt;
inizio[l].back = pt;
}
++(inizio[l].num_elem);
}
TipoElem CodaLivelli::Primo()
{ for (int i = num_livelli-1; i >= 0; i--)
if (inizio[i].num_elem > 0)
return inizio[i].front->val;
return –1;
}
bool CodaLivelli::EstVuota()
{ for (int i = 0; i< num_livelli; i++)
if (inizio[i].num_elem != 0)
return false;
return true;
}
ostream& operator=0;i--)
if (inizio[i].num_elem>0)
return inizio[i].front->val;
}

Analizzando il codice si possono fare considerazioni analoghe a quelle fatte per la funzione OutCoda e quindi il costo computazionale è pari a O(nl).

• InCoda
void CodaLivelli::InCoda(int i,TipoElem elem)
{ item* pt=new item;
pt->val=elem;
pt->next=NULL;
if (inizio[i].front==NULL)
{ //la coda al livello i è vuota
inizio[i].front=pt;
inizio[i].back=pt;
}
else
{ //esiste almeno un elemento al livello i
inizio[i].back->next=pt;
inizio[i].back=pt;
}
++(inizio[i].num_elem);
}
Come si evince dal codice, il numero di istruzioni attivate nell’esecuzione della funzione è indipendente dalle dimensioni dell’input ( numero dei livelli e numero di elementi per livello ) e dunque la InCoda ha complessità computazionale O(1).

• EstVuota
bool CodaLivelli::EstVuota()
1{ for (int i=0;inext;
}
return *this;
}
Si prendono in considerazione le sole parti dominanti della procedura, individuate nelle linee di codice 1 e 2; per esse è possibile fare la seguente tabella:

Linea codice
1
2
Frequenza
nl
nl
Costo unitario
O(n)
O(n)

Costo operatore =: O(nl*n).

Operatore val = pt->val;
aux->next = Copia(pt->next);
return aux;
}
}
void CodaLivelli::OutCoda()
{ for (int i = num_livelli-1; i >= 0; i--)
if (inizio[i].num_elem != 0)
{ item *pt = inizio[i].front;
inizio[i].front = inizio[i].front->next;
delete pt;
--(inizio[i].num_elem);
--(tot_elem);
return;
}
}
void CodaLivelli::InCoda(int l,TipoElem elem)
{ item* pt = new item;
pt->val = elem;
pt->next = NULL;
if (inizio[l].front == NULL)
{ //la coda al livello i e' vuota
inizio[l].front = pt;
inizio[l].back = pt;
}
else
{ //esiste almeno un elemento al livello i
inizio[l].back->next = pt;
inizio[l].back = pt;
}
++(inizio[l].num_elem);
++(tot_elem);
}
TipoElem CodaLivelli::Primo()
{ for (int i = num_livelli-1; i >= 0; i--)
if (inizio[i].num_elem > 0)
return inizio[i].front->val;
return –1; // valore convenzionale
}
bool CodaLivelli::EstVuota()
{ if (tot_elem == 0) return true;
return false;
}
ostream& operator