Docente: Giuseppe Scollo
Università di Catania, sede di Comiso (RG)
Facoltà di Scienze Matematiche, Fisiche e Naturali
Corso di Studi in Informatica applicata, AA 2006-7
dalle definizioni degli ADT pila e coda emerge che essi differiscono solo per la disciplina di accesso, in particolare per la regola di rimozione di elementi dalla sequenza
ciò conduce al concetto di coda generalizzata:
coda casuale (ingl. random queue):
le operazioni delle code LIFO e FIFO sono eseguite in tempo costante, sia nelle implementazioni con array che in quelle con liste
altri tipi di code generalizzate: coda doppia, code con priorità, tabelle di simboli, ...
per un qualsiasi tipo di coda generalizzata è possibile distinguere diversi sottotipi in base alla gestione di elementi duplicati
negli ADT visti sinora (code LIFO, FIFO, random), non era specificata alcuna gestione dei duplicati
in molti casi è preferibile includere nella specifica dell'ADT una disciplina di gestione dei duplicati:
per implementare tali discipline occorre in ogni caso la funzionalità di ricerca di una chiave fra quelle degli elementi in coda, per il riconoscimento dei duplicati
se il tipo della chiave è int,
una realizzazione rapida e semplice di questa funzionalità si ottiene
con un cast
degli elementi al tipo della chiave, purché il tipo degli elementi ne sia
una derivazione
p[k] == 1 sse un elemento di chiave k è presente in coda
si realizza in tal caso una disciplina di gestione dei duplicati mediante elementi indice
assumendo un cast di Elem a
int che restituisca un intero < maxN,
l'implementazione della pila con array può essere così modificata,
per prevenire l'inserimento di duplicati secondo la disciplina
ignora il nuovo
strutture dati private ndstack-private.h:
Elem *s; // puntatore alla struttura dati su cui si implementa la pila
bool *d; // puntatore all'array di controllo della presenza di duplicati
int N; // numero di elementi nella pila + 1
// (ordinale del prossimo elemento da aggiungere alla pila)
implementazione delle operazioni ndstack.c++ :
#include "ndstack.h"
template <typename Elem>
Stack<Elem>::Stack(int maxN)
{ s = new Elem[maxN]; d = new bool[maxN]; N = 0;
for (int i = 0; i < maxN; i++) d[i] = 0; }
template <typename Elem>
bool Stack<Elem>::empty() const { return N == 0; }
template <typename Elem>
void Stack<Elem>::push(Elem elem)
{ if (d[elem]) return; s[N++] = elem; d[elem] = 1; }
template <typename Elem>
Elem Stack<Elem>::pop() { d[s[--N]] = 0; return s[N]; }
come si è accennato a proposito della ridefinizione di operatori, quando si definisce un nuovo tipo di dato è conveniente poterlo trattare allo stesso modo dei tipi di dati predefiniti
float a un ADT dei numeri complessi, ma non tutti quegli operatori
hanno senso su qualsiasi ADT
seppur vaga, la definizione rende intuitivamente l'idea, lasciando al programmatore il compito di individuare gli operatori predefiniti dei quali è appropriata la ridefinizione per un nuovo ADT
se l'ADT implementato da una classe è accessibile solo per il tramite
dell'interfaccia,
e se non ha puntatori fra i suoi dati membro,
allora è un ADT di prima categoria
se la classe che implementa un ADT ha puntatori fra i suoi dati membro, perché l'ADT sia di prima categoria occorre ridefinire opportunamente:
l'interfaccia dell'ADT coda FIFO di I categoria è un'estensione di quella vista nella lezione precedente con costruttore di copia, operatore di assegnamento e distruttore
template <typename Elem>
class Queue {
public:
Queue(); // costruttore (capacità illimitata)
Queue(int); // costruttore (parametro: capacità)
Queue(const Queue&); // costruttore di copia
Queue& operator=(const Queue&); // overloading dell'assegnamento
~Queue(); // distruttore
bool empty() const; // query: true sse la pila è vuota
void put(Elem); // inserimento di un elemento
Elem get(); // rimozione di un elemento (restituito)
private:
#include "queue-private.h" // membri dipendenti dall'implementazione
};
possiamo estendere la già vista implementazione della coda FIFO mediante lista, a un ADT di prima categoria che implementa la precedente interfaccia, se aggiungiamo alle definizioni già date (non replicate qui) le seguenti, rispettivamente nella parte privata e, in quella pubblica, per costruttore di copia, operatore di assegnamento e distruttore:
nel file queue-private.h:
void deletelist()
{ for plink t = head; t != 0; head = t) { t = head->next; delete head; } }
nel file queue.c++:
template <typename Elem> Queue<Elem>::Queue(const Queue& q) { head = 0; *this = q; }
template <typename Elem> Queue<Elem>& Queue<Elem>::operator=(const Queue<Elem>& q)
{ if (this == &q) return *this;
deletelist(); plink t = q.head;
while (t != 0) { put(t->elem); t = t->next; }
return *this;
}
template <typename Elem> Queue<Elem>::~Queue() { deletelist(); }
il programma simula l'accodamento di N richieste di servizio in un sistema casuale di M code FIFO
per il funzionamento corretto del programma è necessario che l'ADT sia di prima categoria
SimQueues.c++:
#include <iostream>
#include <cstdlib>
#include "queue.h"
using namespace std;
static const int M = 4;
int main(int argc, char* argv[])
{ int N = atoi(argv[1]);
Queue<int> queues[M];
for (int i = 0; i < N; i++, cout << endl)
{ int in = rand() % M, out = rand() % M;
queues[in].put(i); cout << i << " in ";
if ( !queues[out].empty() ) cout << queues[out].get() << " out";
cout << endl;
for (int k = 0; k < M; k++, cout << endl)
{ Queue<int> q = queues[k]; cout << k << ": ";
while ( !q.empty() ) cout << q.get() << " ";
} } }
la compilazione separata di implementazione e client della coda FIFO testè viste non segnala alcun problema, tuttavia il linking riserva una sgradevole sorpresa:
$ c++ -o bin/SimQueues queue.o SimQueues.o SimQueues.o: In function `main': SimQueues.c++:(.text+0xb3): undefined reference to `Queue<int>::Queue()' SimQueues.c++:(.text+0x16b): undefined reference to `Queue<int>::put(int)' [...]
ciò accade perché la compilazione separata dell'implementazione del template non genera automaticamente le istanze delle definizioni dei template di funzione richieste dal client
soluzione: aggiungere la compilazione (separata) di dichiarazioni di istanziazione di template, SimQueueTFI.c++:
#include "queue.c++" template Queue<int>::Queue(); template void Queue<int>::put(int); [...]
o, più semplicemente, per tutte le funzioni dell'istanza del template di classe, SimQueueTCI.c++:
#include "queue.c++" template class Queue<int>::Queue;
quando si sviluppano più client e/o più implementazioni di uno stesso ADT, è utile predisporre la costruzione di ciascun programma dalla corrispondente combinazione di client e implementazioni
una possibile organizzazione, per lo sviluppo basato su un certo ADT, ne colloca i moduli come segue:
clients/ : sorgenti dei client e rispettivi file di dichiarazioni
di istanziazione di template
include/ : interfacce, con strutture dati private in include/concrete/
adt_x/ : sorgenti dell'implementazione
x dell'ADT
build/ : procedure di costruzione e moduli oggetto
bin/ : programmi eseguibili
interfacce e implementazioni possono essere rese visibili, nelle directory dove servono a tempo di compilazione, mediante link simbolici, magari creati dinamicamente dalle procedure di costruzione
ecco ad es. una shell per la costruzione del programma di simulazione del
sistema di code, assumendo l'esistenza di link a include/queue.h in
clients/ e in
queue_l/, qui con link queue-private.h a
include/concrete/lista.h, e della directory build/simqueues_l/ :
cd ../clients ln -s ../include/concrete/lista.h queue-private.h ln -s ../queue_l/queue.c++ . cd ../build/simqueues_l c++ -c ../../clients/SimQueues.c++ ../../clients/SimQueueTCI.c++ ../../queue_l/queue.c++ c++ -o ../../bin/SimQueues_l *.o rm ../../clients/queue-private.h ../../clients/queue.c++
dimentica il vecchio (accodando il nuovo in ordine di arrivo)
ignora il nuovo