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= dove CodaLivelli è il dominio di interesse e Elem è il dominio degli elementi che formano le code;

F= .

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 del 121j96b l'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 <iostream.h>

typedef int TipoElem;

struct item

struct coda

class CodaLivelli

private:

int num_livelli;

coda* inizio;

void Distruggi(item* pt);

item* Copia(item* pt);

// File codalivelli.cpp

#include "codalivelli.h"

#include <assert.h> // per assert() usata dall'operatore "="

CodaLivelli::CodaLivelli(int n)

CodaLivelli::CodaLivelli(const CodaLivelli& cl)

CodaLivelli& CodaLivelli::operator=(const CodaLivelli& cl)

return *this;

CodaLivelli::~CodaLivelli()

void CodaLivelli::Distruggi(item* pt)

item* CodaLivelli::Copia(item* pt)

void CodaLivelli::OutCoda()

void CodaLivelli::InCoda(int l,TipoElem elem)

else

++(inizio[l].num_elem);

TipoElem CodaLivelli::Primo()

bool CodaLivelli::EstVuota()

ostream& operator<<(ostream& os,CodaLivelli& cl)

os << endl;

return os;

ANALISI DEL COSTO TEMPORALE DELLE FUNZIONI DELLA CLASSE CODALIVELLI

Si vuole determinare la complessità computazionale dei metodi costituenti la classe; si indichi a tal fine con "nl" il numero dei livelli della coda in esame e con "n" il numero medio di elementi presenti nel generico livello.

Come prima cosa si analizzano i costi delle funzioni Copia e Distruggi di cui si riportano di seguito i codici:

item* CodaLivelli::Copia(item* pt)

void CodaLivelli::Distruggi(item* pt)

Entrambe le procedure sono di tipo ricorsivo; ad ogni chiamata si ha un numero di attivazioni di tali funzioni pari alla cardinalità del generico livello della classe, dunque pari a n;

ogni attivazione richiede l'esecuzione di un numero di istruzioni indipendente dalla dimensione dell'input.

Le due procedure hanno dunque entrambe complessità computazionale O(n).

A questo punto è possibile analizzare tutte le funzioni che definiscono il TDA CodaLivelli, gli operatori di inserimento e di assegnamento, i costruttori e distruttori della classe; per ognuna di tali funzioni si determinano il numero di volte che vengono eseguite le singole istruzioni componenti i codici (frequenza) ed il loro costo unitario; da tali informazioni si determina infine la complessità computazionale.

• Costruttore (realizza la funzione Crea del TDA CodaLivelli)

CodaLivelli::CodaLivelli(int n)

}

Costo costruttore: O(nl).

• Costruttore di copia

CodaLivelli::CodaLivelli(const CodaLivelli& cl)

}

Costo costruttore di copia: O(n*nl).

• Distruttore

CodaLivelli::~CodaLivelli()

Costo distruttore: O(n*nl).

• OutCoda

void CodaLivelli::OutCoda()

}

La funzione OutCoda ha costo dipendente fortemente dalla particolare istanza dell'input. Il caso peggiore si ha quando l'elemento da eliminare è presente nel livello zero (tutti i livelli superiori hanno num_elem=0); per una tale configurazione è possibile fare la seguente tabella:

Costo OutCoda(): O(nl) nel caso peggiore.

Primo

TipoElem CodaLivelli::Primo()

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)

else

++(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()

Costo EstVuota(): O(nl) nel caso peggiore.

Operatore =

CodaLivelli& CodaLivelli::operator=(const CodaLivelli& cl)

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:

Costo operatore =: O(nl*n).

Operatore <<

ostream& operator<<(ostream& os,CodaLivelli& cl)

os << endl;

return os;

Costo operatore <<: O(n*nl).

// ORDINAMENTO VETTORE

/* Scrivere una funzione che ordina un vettore di m locazioni i cui elementi

sono degli interi compresi tra 0 e v-1 (eventualmente con ripetizione).

Si utilizzi una variabile di tipo CodaLivelli con v livelli.

Calcolare la complessità della funzione. */

#include <iostream.h>

#include "codalivelli.h"

main()

//memorizzazione del vettore nella coda

CodaLivelli cl(max+1);

for (int i = 0; i < dim; i++) cl.InCoda(vett[i],vett[i]);

//stampa della coda associata al vettore

cout << "La CodaLivelli associata al vettore è la seguente" << endl;

cout << endl;

cout << cl;

cout << endl;

//ordinamento del vettore

int indice = dim-1;

for (int i = max; i >= 0; i--)

}

cout<<"Il vettore ordinato è il seguente:" << endl;

delete []vett;

cout << "Premere un tasto per tornare al codice del programma";

int temp; cin>>temp;

ANALISI DEL COSTO TEMPORALE DEL CODICE ORDINAMENTO VETTORE

Si riporta il codice "ORDINAMENTO VETTORE":

#include <iostream.h>

#include <conio.h>

#include "codalivelli.h"

main()

//memorizzazione del vettore nella coda

CodaLivelli cl(max+1); // Attivazione del costruttore di CodaLivelli

for (int i = 0; i < dim; i++)

cl.InCoda(vett[i],vett[i]);

//stampa della coda associata al vettore

cout << "La CodaLivelli associata al vettore è la seguente" << endl;

cout << endl;

cout << cl;

cout << endl;

//ordinamento del vettore

int indice = dim-1;

for (int i = max; i >= 0; i--)

}

cout << "Il vettore ordinato è il seguente:" << endl;

delete []vett;

cout << "Premere un tasto per tornare al codice del programma";

int temp; cin >> temp;

Si prendono in considerazione le sole parti dominanti del programma; in relazione ad esse è possibile fare la seguente tabella:

Analizzando i costi delle diverse linee del programma, si vede come la complessità computazionale del codice proposto per l'ordinamento del vettore sia O(n*nl²).

E' possibile ovviamente proporre altri algoritmi con costi minori sia in termini di tempo sia che di occupazione di memoria.

Ai fini della risoluzione del problema posto infatti risultano inutili sia l'allocazione dinamica di memoria ad ogni inserimento di un elemento al generico livello i ottenuta con la funzione InCoda() ( infatti il campo info di un elemento al livello i ha proprio valore i), sia la deallocazione della stessa memoria (attraverso la OutCoda()) al momento dell'ordinamento del vettore, ovvero al momento dello svuotamento dalla coda stessa.

Una soluzione alternativa a quella proposta consiste quindi in un incremento di inizia[i].num_elem ogni volta che una componente del vettore di valore i deve essere caricato in coda (senza l'allocazione di memoria dinamica) e ad un suo decremento quando tale valore viene estratto dalla coda in fase di ordinamento del vettore.

Per una tale scelta, la porzione di codice per l'ordinamento del vettore potrebbe dunque essere la seguente:

int indice = 0;

for (i = 0; i < nl; i++)

};

Il costo sarebbe dunque O(n*nl).

L'algoritmo proposto, sebbene molto costoso, enfatizza tuttavia le caratteristiche della CodaLivelli nonché le funzionalità dei suoi metodi e dunque per tali motivi è stato preferito ad altri che, pur essendo più economici, nascondono tali caratteristiche.

/* File codalivelli2.h

E' stato aggiunto il campo tot_elem */

#include <iostream.h>

typedef int TipoElem;

struct item

struct coda

class CodaLivelli

private:

int num_livelli;

coda* inizio;

void Distruggi(item* pt);

item* Copia(item* pt);

int tot_elem;

/* File codalivelli2.cpp

#include "codalivelli2.h"

#include <assert.h> // per assert() usata dall'operatore "="

CodaLivelli::CodaLivelli(int n)

CodaLivelli::CodaLivelli(const CodaLivelli& cl)

CodaLivelli& CodaLivelli::operator=(const CodaLivelli& cl)

return *this;

CodaLivelli::~CodaLivelli()

void CodaLivelli::Distruggi(item* pt)

item* CodaLivelli::Copia(item* pt)

void CodaLivelli::OutCoda()

void CodaLivelli::InCoda(int l,TipoElem elem)

else

++(inizio[l].num_elem);

++(tot_elem);

TipoElem CodaLivelli::Primo()

bool CodaLivelli::EstVuota()

ostream& operator<<(ostream& os,CodaLivelli& cl)

os << endl;

}

return os;

}

// file prova codalivelli2

#include<iostream.h>

#include "codalivelli2.h"

main()

cout << endl;

}

cout <<"La coda inserita e' la seguente:" << endl << endl;

cout << a << endl;

char risposta='s';

while (risposta=='s')

a.InCoda(l,e);

cout << "La coda modificata è la seguente" << endl << a;

break;

case 2:

cout<< "Il primo elemento della coda è " << a.Primo();

cout << endl;

break;

case 3:

a.OutCoda();

cout << "E' stato cancellato il primo elemento" << endl;

cout << "La coda modificata è la seguente" << endl << a;

break;

case 4:

bool test;

test = a.EstVuota();

if (test) cout << "La coda è vuota";

else cout << "La coda è non vuota";

break;

case 5:

case 6:

default:

cout << "Errore! Inserire un numero compreso tra 1 e 6" << endl;

}

cout << endl;

cout << "Vuoi apportare altre modifiche? (s-n) ";

cin >> risposta;

}

else cout <<"Errore! Il numero dei livelli deve essere > 0!" << endl;

return 0;

ANALISI DEL COSTO TEMPORALE

L'aggiunta del campo tot_elem, e la conseguente modifica delle funzioni della classe per un suo corretto utilizzo, non modifica la complessità computazionale delle funzioni stesse.

Il vantaggio derivato dall'aver introdotto questo nuovo campo si può riscontrare nella sola funzione EstVuota(); in precedenza infatti il test sulla coda veniva effettuato con un controllo ciclico sul numero degli elementi di ciascun livello, mentre ora si esegue un controllo diretto sul nuovo campo introdotto, determinando così un notevole risparmio in termini di tempo di esecuzione; si è passati infatti da un costo O(nl) a un costo pari a O(1).

//File coda+codaliv.h

#include <iostream.h>

typedef int TipoElem;

struct elem

//Dichiarazione della classe Coda

class Coda ;

//Dichiarazione della classe CodaLivelli

class CodaLivelli

//File coda+codalivelli.cpp

#include <assert.h>

#include "coda+codalivelli.h"

// Funzioni della classe Coda

//Il costruttore della classe Coda realizza la funzione Crea() del TDA Coda.

Coda::Coda()

//Costruttore di copia

Coda::Coda(const Coda& c)

else last = NULL;

//Distruttre

Coda::~Coda()

ostream& operator<<(ostream& os,Coda& c)

os << endl;

return os;

Coda& Coda::operator=(const Coda& c)

bool Coda::IsEmpty()

void Coda::PutIn(TipoElem i)

num_elem++;

void Coda::Tail()

else

num_elem--;

}

TipoElem Coda::GetFirst()

elem* Coda:: Copia(elem* pt)

void Coda::Distruggi(elem* pt)

//Funzioni della classe CodaLivelli

/*Il costruttore della classe CodaLivelli realizza la funzione Crea() del

TDA CodaLivelli*/

CodaLivelli::CodaLivelli(int n)

//Distruttore

CodaLivelli::~CodaLivelli()

//Costruttore di copia

CodaLivelli::CodaLivelli(const CodaLivelli& cl)

void CodaLivelli::InCoda(int l,TipoElem i)

TipoElem CodaLivelli::Primo()

return -1; // valore convenzionale

void CodaLivelli::OutCoda()

bool CodaLivelli::EstVuota()

ostream& operator<<(ostream& os,CodaLivelli& cl)

return os;

CodaLivelli& CodaLivelli::operator=(const CodaLivelli& cl)

return *this;

}

// file prova coda+codalivelli

#include<iostream.h>

#include "coda+codalivelli.h"

main()

cout << endl;

}

cout <<"La coda inserita e' la seguente:" << endl << endl;

cout << a << endl;

char risposta='s';

while (risposta=='s')

a.InCoda(l,e);

cout << "La coda modificata e' la seguente" << endl << a;

break;

case 2:

cout<< "Il primo elemento della coda e' " << a.Primo();

cout << endl;

break;

case 3:

a.OutCoda();

cout << "E' stato cancellato il primo elemento dalla funzione OutCoda()" << endl;

cout << "La coda modificata e' la seguente" << endl << a;

break;

case 4:

bool test;

test = a.EstVuota();

if (test) cout << "La coda e' vuota" << endl;

else cout << "La coda e' non vuota" << endl;

break;

case 5:

case 6:

default:

cout << "Errore! Inserire un numero compreso tra 1 e 6" << endl;

}

cout << endl;

cout << "Vuoi apportare altre modifiche? (s-n) ";

cin >> risposta;

}

else cout <<"Errore! Il numero dei livelli deve essere > 0!" << endl;

return 0;

}

ANALISI DEL COSTO TEMPORALE DELLE CLASSI CODA E CODALIVELLI

Costo delle funzioni di Coda

Si procederà ora alla valutazione del costo temporale dei metodi costituenti la classe Coda.

Come si evince facilmente dai codici, tutte le funzioni che definiscono il TDA Coda, ovvero Tail(), GetFirst(), PutIn(), IsEmpty() e Create() ( quest'ultima realizzata attraverso il costruttore della classe ) hanno costi indipendenti dalle dimensioni dell'input ( numero di elementi nella coda ) e dunque hanno costo O(1).

Analizziamo con maggior dettaglio le altre funzioni della classe.

Costruttore di copia

Coda::Coda(const Coda& c)

else last = NULL;

Le parti dominanti del programma si individuano nelle linee di codice 1 e 2 ( attivazione della procedura Crea() e ciclo di scansione della coda ) .

E' facile vedere come entrambe hanno costo O(n) e dunque O(n) è il costo dell'intera funzione.

Distruttore

Coda::~Coda()

Ogni attivazione del distruttore consta nell'esecuzione per n+1 volte della funzione IsEmpty(), che ha costo O(1), e per n volte della funzione Tail() anch'essa di costo O(1).

Il Distruttore ha dunque complessità computazionale O(n).

Operatore <<

ostream& operator<<(ostream& os,Coda& c)

os << endl;

return os;

Analizzando la tabella su esposta si vede che il costo dell'operatore << è O(n).

Operatore =

Coda& Coda::operator=(const Coda& c)

Le linee 1, 2 e 3 hanno tutte costo O(n) e dunque O(n) e' il costo dell'operatore =.

Costo della CodaLivelli

Utilizzando i risultati trovati per la classe Coda, è ora possibile ricavare i costi della nuova implementazione della classe CodaLivelli.

• Costruttore

/*Il costruttore della classe CodaLivelli realizza la funzione Crea() del TDA CodaLivelli*/

CodaLivelli::CodaLivelli(int n)

Una volta allocata memoria dinamica per la CodaLivelli in esame, viene automaticamente attivato per nl volte il Costruttore di Coda che ha costo O(1).

Il costo del Costruttore di CodaLivelli è dunque O(nl).

• Distruttore

CodaLivelli::~CodaLivelli()

Considerazioni analoghe a quelle fatte per il Costruttore portano ad una complessità O(n*nl).

InCoda

void CodaLivelli::InCoda(int l,TipoElem i)

Il numero di istruzioni attivate è indipendente dall'input e dunque il costo è O(1).

EstVuota

bool CodaLivelli::EstVuota()

Considerazioni analoghe portano ad una complessità O(1).

Primo

TipoElem CodaLivelli::Primo()

else return -1; //valore convenzionale

}

Nel caso peggiore (primo elemento al livello zero) il corpo del ciclo while di cui alla linea 1 viene eseguito nl volte con costo unitario.

La linea 2 viene eseguita una sola volta anch'essa con costo unitario.

La funzione Primo() ha dunque costo O(nl).

OutCoda

void CodaLivelli::OutCoda()

}

Considerazioni analoghe a quelle fatte per Primo() portano ad una complessità computazionale O(nl).

Costruttore di copia

//Costruttore di copia

CodaLivelli::CodaLivelli(const CodaLivelli& cl)

Il ciclo for attiva nl volte l'operatore di assegnamento della classe Coda che ha costo O(n).

Il costruttore di copia ha dunque costo O(n*nl).

Operatore <<

ostream& operator<<(ostream& os,CodaLivelli& cl)

return os;

}

Viene attivato nl volte l'operatore << della classe Coda che ha costo unitario O(n).

L'operatore di estrazione della classe CodaLivelli ha dunque costo O(n*nl).

Operatore =

CodaLivelli& CodaLivelli::operator=(const CodaLivelli& cl)

Viene attivato nl volte l'operatore = della classe Coda e dunque con considerazioni analoghe a quelle fatte per l'operatore << si perviene ad un costo pari a O(n*nl).