Strutture Dati: Realizzazioni C++ - Algoritmi e Strutture Dati - Lista, Pila, Coda, Insieme, Albero, Grafo

INDICE

INTRODUZIONE

Essendo la classe Nodo uguale per tutte le strutture dati verrà illustrata qui di seguito una sola volta così da evitare ripetizioni.

Nome: Nodo.h

Autore: Trullo Raffaella

Descrizione: Classe che implementa il nodo della lista sequenziale

#include <string>

#ifndef NODO_H

#define NODO_H

using namespace std;

typedef struct tipoelem;

class Nodo ;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* Nodo.cpp */

#include <string>

#include <iostream>

#include <cstdlib>

#include "Nodo.h"

using namespace std;

Nodo::Nodo();

Nodo::Nodo(tipoelem a);

Nodo::~Nodo();

tipoelem Nodo::getEtichetta();

void Nodo::setEtichetta(tipoelem a)

void Nodo::insEtichetta(tipoelem &a);

void Nodo::stampaEtichetta(tipoelem a);

//restituisce 0 se sono uguali, 1 se a > b, -1 se a < b

int Nodo::confrontoEtichetta(string a, string b);

int Nodo::confrontoEtichetta(int a, int b)

return ris;

bool Nodo::confrontoNodi(tipoelem a, tipoelem b)   

return ris;

ustrata qui per tutte le strutture dati tazioni delle liste: mente solo ad un ristretto sottoinsieme di elementi() 1. LISTA

Una lista è una sequenza di elementi di un certo tipo e si indica con la seguente notazione:

L=<a1,a2,a3,.,an>.

È una struttura a dimensione variabile 959h74j alla quale si può accedere direttamente solo ad un ristretto sottoinsieme di elementi (di solito il primo o l'ultimo). Per accedere ad un generico elemento bisogna scandire sequenzialmente gli elementi della lista.

La lunghezza di L è pari ad n e ogni elemento è caratterizzato da una posizione in L, indicata con pos(i), e da un valore a(i).

Di seguito saranno illustrate tre diverse implementazioni delle liste: sequenziale, con puntatori e con cursori.

1.1 LISTA SEQUENZIALE

La lista viene rappresentata attraverso un vettore di dimensione prefissata. Poiché il numero di elementi che compongono la lista può variare, si usa una variabile primo per indicare l'indice del primo elemento della lista e una variabile lunghezza che indica il numero di elementi presenti nella lista.

Nome: ListaSeq.h

Autore: Trullo Raffaella

Descrizione: Classe che implementa la lista sequenziale

#ifndef LISTASEQ_H

#define LISTASEQ_H

#include "Nodo.h"

#define MAXLUNG 100

#define NIL -1

typedef int posizione;

class ListaSeq;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* ListaSeq.cpp */

#include <iostream>

#include <cstdlib>

#include "ListaSeq.h"

ListaSeq::ListaSeq();

ListaSeq::~ListaSeq();

void ListaSeq::creaLista();

bool ListaSeq::listaVuota();

posizione ListaSeq::primoLista();

posizione ListaSeq::predLista(posizione p);

posizione ListaSeq::succLista(posizione p);

bool ListaSeq::fineLista(posizione p);

bool ListaSeq::insLista(tipoelem a, posizione p) else

lista[temp].setEtichetta(a);

} else

lista[p].setEtichetta(a);

}

lunghezza++;

return true;

} else return false; // lista piena

bool ListaSeq::cancLista(posizione p)

lunghezza--;

return true;

} else return false; // posizione non valida o lista vuota

bool ListaSeq::scriviLista(tipoelem a, posizione p) else return false;

bool ListaSeq::leggiLista(tipoelem &a, posizione p) else return false;

posizione ListaSeq::pos(int p)

Nel programma principale sono implementate le procedure e le funzioni che permettono l'inserimento degli elementi nella lista (in maniera ordinata e non), la stampa, la ricerca, l' epurazione, la cancellazione dei doppioni, l'inversione degli elementi e la fusione di due liste ordinate.

/* main.cpp */

#include "ListaSeq.h"

#include <cstdlib>

#include <iostream>

using namespace std;

void inserisciLista(ListaSeq &l) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << endl << "Hai inserito " << i << " elementi" << endl;

void stampaLista(ListaSeq l)

cout << endl;

} else cout << "Lista vuota" << endl;

bool ricercaLista(ListaSeq l, tipoelem a, int &i)

trovato = true;

}

else

p = l.succLista(p);

}

}

return trovato;

bool invertiLista(ListaSeq l, ListaSeq &m)

l.leggiLista(a, p); //primo elemento di l

m.insLista(a, NIL);

return true;

} else return false;

ListaSeq epuraLista(tipoelem a, ListaSeq l)

p = l.succLista(p);

}

return m;

bool doppioniLista(ListaSeq l, ListaSeq &m)

return true;

} else return false;

//verrà richiamata sempre quando l NON è vuota

posizione recuperaPos(tipoelem a, ListaSeq l)

return p;

void inserisciListaOrd(ListaSeq &l) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << endl;

cout << "Hai inserito " << i << " elementi" << endl;

//le liste devono essere ordinate

bool fondiLista(ListaSeq l, ListaSeq m, ListaSeq &n) else

n.insLista(c, NIL);

}

}

while(!l.fineLista(p))

while(!m.fineLista(q))

if (n.listaVuota())

return true;

else return false;

int main(int argc, char *argv[])

else

cout << endl << "Inversione della lista L:" << endl << "L: ";

invertiLista(l, n);

stampaLista(n);

n.creaLista();

cout << endl << "Eliminazione dei doppioni della lista L" << endl << "L: ";

doppioniLista(l, n);

stampaLista(n);

l.creaLista();

m.creaLista();

n.creaLista();

cout << endl << "Inserimento ordinato della lista L:" << endl << endl;

inserisciListaOrd(l);

stampaLista(l);

cout << endl << "Inserimento ordinato della lista M:" << endl << endl;

inserisciListaOrd(m);

fondiLista(l, m, n);

cout << endl << "Fusione delle due liste in un'unica lista N" << endl << "N: ";

stampaLista(n);

cout << endl;

system("PAUSE");

return 0;

1.2 LISTA CON PUNTATORI

Mediante l'utilizzo dei puntatori è possibile effettuare diverse implementazioni della lista. Tutte permettono di non limitare il numero di elementi che è possibile inserire. Qui di seguito verrà illustrata l'implementazione monodirezionale senza sentinella di una lista mediante puntatori. Per gli elementi della lista si utilizza un record contenente un campo etichetta e un campo puntatore all'elemento successivo chiamato appunto successivo. Il primo elemento della lista verrà puntato dalla variabile primo

Nome: NodoPtr.h

Autori: Raffaella Trullo

Descrizione: Classe che implementa il nodo della lista con puntatore

#ifndef NODOPTR_H

#define NODOPTR_H

#include "Nodo.h"

class NodoPtr; // dichiarazione anticipata

typedef NodoPtr *posizione; //necessita della dichiarazione anticipata

class NodoPtr: public Nodo;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoPtr.cpp */

#include <iostream>

#include <cstdlib>

#include "NodoPtr.h"

NodoPtr::NodoPtr(): Nodo();

NodoPtr::NodoPtr(tipoelem a): Nodo(a);

NodoPtr::NodoPtr(tipoelem a, posizione p): Nodo(a);

NodoPtr::~NodoPtr();

posizione NodoPtr::getSuccessivo();

void NodoPtr::setSuccessivo(posizione p);

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: ListaPtr.h

Autori: Raffaella Trullo

Descrizione: Classe che implementa la lista con puntatore

#ifndef LISTAPTR_H

#define LISTAPTR_H

#include "NodoPtr.h"

class ListaPtr;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* ListaPtr.cpp */

#include <iostream>

#include <cstdlib>

#include "ListaPtr.h"

ListaPtr::ListaPtr();

ListaPtr::~ListaPtr()

void ListaPtr::creaLista();

bool ListaPtr::listaVuota();

posizione ListaPtr::primoLista();

posizione ListaPtr::predLista(posizione p) else

return q;

}

posizione ListaPtr::succLista(posizione p);

bool ListaPtr::fineLista(posizione p);

void ListaPtr::insLista(tipoelem a, posizione p)

bool ListaPtr::cancLista(posizione p) else return false;

bool ListaPtr::scriviLista(tipoelem a, posizione p) else return false;

bool ListaPtr::leggiLista(tipoelem &a, posizione p) else return false;

posizione ListaPtr::pos(int n)

return p;

Nel programma principale sono implementate le procedure e le funzioni che permettono l'inserimento degli elementi nella lista (in maniera ordinata e non), la stampa, la ricerca, l' epurazione, la cancellazione dei doppioni, l'inversione degli elementi e la fusione di due liste ordinate.

#include <cstdlib>

#include <iostream>

#include "ListaPtr.h"

using namespace std;

void inserisciLista(ListaPtr &l) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << "Hai inserito " << i << " elementi" << endl;

void stampaLista(ListaPtr &l)

cout << endl;

} else cout << "Lista vuota" << endl;

bool ricercaLista(ListaPtr &l, tipoelem a, posizione &p, int &i)

trovato = true;

}

else

p = l.succLista(p);

}

}

return trovato;

bool invertiLista(ListaPtr &l, ListaPtr &m)

l.leggiLista(a, p); //primo elemento di l

m.insLista(a, NULL);

return true;

} else return false;

bool epuraLista(tipoelem a, ListaPtr &l, ListaPtr &m)

epura = true;

}

return epura;

bool doppioniLista(ListaPtr &l, ListaPtr &m)

return true;

} else return false;

posizione recuperaPos(tipoelem a, ListaPtr &l)

return p;

void inserisciListaOrd(ListaPtr &l) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << "Hai inserito " << i << " elementi" << endl;

bool fondiLista(ListaPtr &l, ListaPtr &m, ListaPtr &n) else

n.insLista(c, NULL);

}

}

while(!l.fineLista(p))

while(!m.fineLista(q))

if (n.listaVuota())

return true;

else return false;

int main(int argc, char *argv[])

else

cout << endl << "Inversione della lista M:" << endl << "M: ";

invertiLista(m, n);

stampaLista(n);

m = n;

n.creaLista();

cout << endl << "Eliminazione dei doppioni della lista M" << endl << "M: ";

doppioniLista(m, n);

stampaLista(n);

l.creaLista();

m.creaLista();

n.creaLista();

cout << endl << "Inserimento ordinato della lista L:" << endl << endl;

inserisciListaOrd(l);

cout << endl << "Inserimento ordinato della lista M:" << endl << endl;

inserisciListaOrd(m);

fondiLista(l, m, n);

cout << endl << "Fusione delle due liste in un'unica lista N" << endl << "N: ";

stampaLista(n);

cout << endl;

system("PAUSE");

return 0;

1.3 LISTA CON CURSORE

Un cursore è una variabile intera il cui valore è interpretato come un indice di un vettore e permette di simulare il funzionamento di un puntatore. Per questo motivo, nella implementazione della lista verrà utilizzato un vettore, chiamato spazio, il quale conterrà i riferimenti a tutte le celle libere nelle quali possono essere inseriti i nuovi elementi. Il vettore spazio è implementato come un array di record i cui campi contengono l'etichetta del nodo della lista e l'indice dell'elemento successivo. Vengono utilizzate tre variabili: primo che contiene l'indice del vettore spazio in cui è memorizzato il primo elemento della lista, primoVuoto che contiene l'indice del vettore spazio contenente la prima cella della lista libera ed infine la variabile lunghezza che indica il numero di elementi presenti nella lista.

Nome: NodoCur.h

Autori: Raffaella Trullo

Descrizione: Classe che implementa il nodo della lista con cursore

#include "Nodo.h"

#define NIL -1

typedef int posizione;

class NodoCur: public Nodo;

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
/* NodoCur.cpp */

#include <string>

#include <iostream>

#include <cstdlib>

#include "NodoCur.h"

NodoCur::NodoCur(): Nodo();

NodoCur::NodoCur(tipoelem a): Nodo(a);

NodoCur::NodoCur(tipoelem a, posizione p): Nodo(a);

NodoCur::~NodoCur();

posizione NodoCur::getSuccessivo();

void NodoCur::setSuccessivo(posizione p);

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: ListaCur.h

Autori: Raffaella Trullo

Descrizione: Classe che implementa la lista con cursore

#ifndef LISTACUR_H

#define LISTACUR_H

#include "NodoCur.h"

#define MAXLUNG 100

class ListaCur;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* ListaCur.cpp */

#include <iostream>

#include <cstdlib>

#include "ListaCur.h"

ListaCur::ListaCur();

ListaCur::~ListaCur();

void ListaCur::creaLista()

spazio[MAXLUNG-1].setSuccessivo(NIL);

bool ListaCur::listaVuota();

posizione ListaCur::primoLista();

posizione ListaCur::predLista(posizione p);

posizione ListaCur::succLista(posizione p);

bool ListaCur::fineLista(posizione p);

bool ListaCur::insLista(tipoelem a, posizione p) else

lunghezza++;

return true;

} else return false; // inserimento fallito (lista piena)

bool ListaCur::cancLista(posizione p)

spostaNodo(p, primoVuoto);

lunghezza--;

return true;

} else return false; // posizione non valida o lista vuota

bool ListaCur::scriviLista(tipoelem a, posizione p) else return false;

bool ListaCur::leggiLista(tipoelem &a, posizione p) else return false;

void ListaCur::spostaNodo(posizione &da, posizione &a);

posizione ListaCur::pos(int n)

}

return p;

Nel programma principale sono implementate le procedure e le funzioni che permettono l'inserimento degli elementi nella lista (in maniera ordinata e non), la stampa, la ricerca, l' epurazione, la cancellazione dei doppioni, l'inversione degli elementi e la fusione di due liste ordinate.

main.cpp */

#include <cstdlib>

#include <iostream>

#include "ListaCur.h"

using namespace std;

void inserisciLista(ListaCur &l) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << "Hai inserito " << i << " elementi" << endl;

void stampaLista(ListaCur l)

cout << endl;

} else cout << "Lista vuota" << endl;

bool ricercaLista(ListaCur l, tipoelem a, int &i)

trovato = true;

}

else

p = l.succLista(p);

}

}

return trovato;

bool invertiLista(ListaCur l, ListaCur &m)

l.leggiLista(a, p); //primo elemento di l

m.insLista(a, NIL);

return true;

} else return false;

// toglie dalla lista quei nodi che hanno (nel nostro caso) il cognome più

// 'grande' di quello passato in input

ListaCur epuraLista(tipoelem a, ListaCur l)

return m;

bool doppioniLista(ListaCur l, ListaCur &m)

return true;

} else return false;

posizione recuperaPos(tipoelem a, ListaCur l)

return p;

void inserisciListaOrd(ListaCur &l) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << "Hai inserito " << i << " elementi" << endl;

bool fondiLista(ListaCur l, ListaCur m, ListaCur &n) else

n.insLista(c, NIL);

}

}

while(!l.fineLista(p))

while(!m.fineLista(q))

if (n.listaVuota())

return true;

else return false;

int main(int argc, char *argv[])

else

cout << endl << "Inversione della lista L:" << endl << endl << "L: ";

invertiLista(l, n);

stampaLista(n);

n.creaLista();

cout << endl << "Eliminazione dei doppioni della lista L" << endl << "L: ";

doppioniLista(l, n);

stampaLista(n);

l.creaLista();

m.creaLista();

n.creaLista();

cout << endl << "Inserimento ordinato della lista L:" << endl << endl;

inserisciListaOrd(l);

cout << endl << "Inserimento ordinato della lista M:" << endl << endl;

inserisciListaOrd(m);

fondiLista(l, m, n);

cout << endl << "Fusione delle due liste in un'unica lista N" << endl << "N: ";

stampaLista(n);

cout << endl;

system("PAUSE");

return 0;

PILA

Una Pila è una sequenza di elementi di un certo tipo in cui è possibile aggiungere o togliere elementi soltanto da un estremo della sequenza detto testa. Una pila può essere vista come un caso particolare di lista in cui l'ultimo elemento inserito è anche il primo ad essere rimosso secondo il meccanismo LIFO ("Last In First Out"). In particolare non è possibile accedere ad alcun elemento che non sia quello in testa. Qui di seguito saranno illustrate due implementazioni per la pila: con vettore e con puntatori.

PILA CON VETTORE

La realizzazione con vettore della pila consiste nel memorizzare gli n elementi della pila, in ordine inverso, nelle prime n posizioni di un vettore di MAXLUNG elementi, mantenendo un cursore testa contenente l'indice in cui memorizzare il prossimo elemento. La pila vuota è individuata dal valore 0 contenuto nel cursore, la pila piena dal valore MAXLUNG.

Nome: PilaVet.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa la pila con vettore

#ifndef PILAVET_H

#define PILAVET_H

#include "Nodo.h"

#define MAXLUNG 100

class PilaVet ;

#endif

/* PilaVet.cpp */

#include <iostream>

#include <cstdlib>

#include "PilaVet.h"

PilaVet::PilaVet();

PilaVet::~PilaVet();

void PilaVet::creaPila();

bool PilaVet::pilaVuota();

bool PilaVet::leggiPila(tipoelem &a) else return false; // pila vuota

bool PilaVet::inPila(tipoelem a) else return false; // pila piena

bool PilaVet::fuoriPila() else return false; // pila vuota

Il programma principale permetterà di popolare una pila, stamparla, cercare un elemento, epurarla (eliminando tutti i valori maggiori di uno dato da tastiera), invertirla ed eliminare i doppioni.

#include <cstdlib>

#include <iostream>

#include "PilaVet.h"

using namespace std;

void inserisciPila(PilaVet &p) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << "Hai inserito " << i << " elementi" << endl;

}

bool invertiPila(PilaVet p, PilaVet &q)

return true;

} else return false;

bool stampaPila(PilaVet p)

cout << endl;

return true;

} else return false;

bool epuraPila(tipoelem a, PilaVet p, PilaVet &q)

invertiPila(r, q);

return true;

} else return false;

bool ricercaPila(tipoelem a, PilaVet p, int &i)

}

}

return trovato;

bool doppioniPila(PilaVet p, PilaVet &q)

invertiPila(r, q);

return true;

} else return false;

int main(int argc, char *argv[])

else

cout << endl << "Epurazione della pila P:" << endl << "Parametro di epurazione: " << endl;

Nodo::insEtichetta(a);

cout << endl;

epuraPila(a, p, q);

cout << "Q: ";

stampaPila(q);

q.creaPila();

cout << endl << "Inversione della pila P:" << endl <<"Q: ";

invertiPila(p, q);

stampaPila(q);

q.creaPila();

cout << endl << "Eliminazione dei doppioni dalla pila P:" << endl << "Q: ";

doppioniPila(p, q);

stampaPila(q);

cout << endl;

system("PAUSE");

return 0;

PILA CON PUNTATORI

L'implementazione della pila con un vettore comporta una limitazione per quanto riguarda il numero di elementi che è possibile inserire, essendo il vettore una struttura a dimensione fissa. Questa limitazione è superata utilizzando la struttura con puntatore. Una variabile testa punterà al top dello stack, e ogni elemento della pila punterà al suo successivo.

Nome: NodoPtr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il nodo della pila con puntatore

#ifndef NODOPTR_H

#define NODOPTR_H

#include "Nodo.h"

class NodoPtr;    // dichiarazione anticipata

typedef NodoPtr *posizione;     //necessita della dichiarazione anticipata

class NodoPtr: public Nodo;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoPtr.cpp */

#include <iostream>

#include <cstdlib>

#include "NodoPtr.h"

NodoPtr::NodoPtr(): Nodo();

NodoPtr::NodoPtr(tipoelem a): Nodo(a);

NodoPtr::NodoPtr(tipoelem a, posizione p): Nodo(a);

NodoPtr::~NodoPtr();

posizione NodoPtr::getSuccessivo();

void NodoPtr::setSuccessivo(posizione p);

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: PilaPtr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa la pila con puntatore

#ifndef PILAPTR_H

#define PILAPTR_H

#include "NodoPtr.h"

class PilaPtr ;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* PilaPtr.cpp */

#include <iostream>

#include <cstdlib>

#include "PilaPtr.h"

PilaPtr::PilaPtr();

PilaPtr::~PilaPtr()

void PilaPtr::creaPila();

bool PilaPtr::pilaVuota();

bool PilaPtr::leggiPila(tipoelem &a) else return false;

void PilaPtr::inPila(tipoelem a);

void PilaPtr::fuoriPila();

Il programma principale permetterà di popolare una pila, stamparla, cercare un elemento, epurarla (eliminando tutti i valori maggiori di uno dato da tastiera), invertirla ed eliminare i doppioni.

#include <cstdlib>

#include <iostream>

#include "PilaPtr.h"

using namespace std;

void inserisciPila(PilaPtr &p) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << "Hai inserito " << i << " elementi" << endl;

bool copiaPila(PilaPtr &p, PilaPtr &q)

while (!r.pilaVuota())

return true;

} else return false;

bool invertiPila(PilaPtr &p, PilaPtr &q)

//copiaPila(r, p);

return true;

} else return false;

bool stampaPila(PilaPtr &p)

cout << endl;

//copiaPila(q, p);

return true;

} else return false;

bool epuraPila(tipoelem a, PilaPtr &p, PilaPtr &q)

//copiaPila(r, p);

invertiPila(s, q);

return true;

} else return false;

bool ricercaPila(tipoelem a, PilaPtr &p, int &i)

else

}

}

return trovato;

bool doppioniPila(PilaPtr &p, PilaPtr &q)

invertiPila(s, q);

return true;

} else return false;

int main(int argc, char *argv[])

else

cout << endl << "Epurazione della pila P:" << endl << "Parametro di epurazione: " << endl;

Nodo::insEtichetta(a);

epuraPila(a, p, q);

cout << "Q: ";

stampaPila(q);

q.creaPila();

cout << endl << "Inversione della pila P:" << endl <<"Q: ";

invertiPila(p, q);

stampaPila(q);

q.creaPila();

cout << endl << "Eliminazione dei doppioni dalla pila P:" << endl << "Q: ";

doppioniPila(p, q);

stampaPila(q);

cout << endl;

system("PAUSE");

return 0;

3. CODE

Una coda è una sequenza di elementi di un certo tipo, in cui è possibile aggiungere elementi ad un estremo (il fondo) e togliere elementi dall'altro estremo (la testa) secondo il meccanismo di accessi detto "FIFO" ("First In First Out"). Può essere considerata come una particolare lista in cui il primo elemento inserito è anche il primo ad essere rimosso e non è possibile accedere ad alcun elemento che non sia quello in testa o quello in fondo. Analogamente a quanto fatto per la pila, qui di seguito saranno mostrate le implementazioni con vettore e con puntatore.

CODA CON VETTORE CIRCOLARE

Il vettore circolare è inteso come un array di MAXLUNG elementi (0.MAXLUNG-1) in cui l'elemento di indice 0 è considerato come successore di quello con indice MAXLUNG-1. La coda è contenuta in n posizioni consecutive del vettore, e i suoi elementi estremi sono individuati da due cursori che puntano rispettivamente alla testa e al fondo della coda.

Nome: CodaVet.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa la coda con vettore circolare

#ifndef CODAVET_H

#define CODAVET_H

#include "Nodocoda.h"

#define MAXLUNG 100

#define NIL -1

class CodaVet ;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* CodaVet.cpp */

#include "CodaVet.h"

#include <iostream>

#include <cstdlib>

CodaVet::CodaVet();

CodaVet::~CodaVet();

void CodaVet::creaCoda();

bool CodaVet::codaVuota();

bool CodaVet::leggiCoda(tipoelem &a)

else return false; // coda vuota

bool CodaVet::inCoda(tipoelem a) else return false; // coda piena

bool CodaVet::fuoriCoda() else return false; // coda vuota

Il programma principale permetterà di popolare una coda, stamparla, cercare un elemento, epurarla (eliminando tutti i valori maggiori di uno dato da tastiera), invertirla ed eliminare i doppioni.

#include <cstdlib>

#include <iostream>

#include "CodaVet.h"

#include "PilaVet.h"

using namespace std;

void inserisciCoda(CodaVet &q) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

}

cout << "Hai inserito " << i << " elementi" << endl;

}

bool stampaCoda(CodaVet q)

cout << endl;

return true;

} else return false;

bool invertiCoda(CodaVet q, CodaVet &r)

while (!p.pilaVuota())

return true;

} else return false;

bool epuraCoda(tipoelem a, CodaVet q, CodaVet &r)

return true;

} else return false;

bool ricercaCoda(tipoelem a, CodaVet q, int &i)

}

}

return trovato;

bool doppioniCoda(CodaVet q, CodaVet &r)

return true;

} else return false;

int main(int argc, char *argv[])

else

cout << endl << "Epurazione della coda Q:" << endl << "Parametro di epurazione: " << endl;

Nodocoda::insEtichetta(a);

epuraCoda(a, q, r);

cout << "R: ";

stampaCoda(r);

r.creaCoda();

cout << endl << "Inversione della coda Q:" << endl <<"R: ";

invertiCoda(q, r);

stampaCoda(r);

r.creaCoda();

cout << endl << "Eliminazione dei doppioni dalla coda R:" << endl << "R: ";

doppioniCoda(q, r);

stampaCoda(r);

cout << endl;

system("PAUSE");

return 0;

CODA CON PUNTATORI

Come per la realizzazione della pila, si utilizza una struttura dinamica per ovviare al problema del dimensionamento, che tiene traccia, traverso due puntatori, testa e fondo, del primo e dell'ultimo elemento della stessa.

Nome: NodoPtr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il nodo della coda con puntatore

#ifndef NODOPTR_H

#define NODOPTR_H

#include "Nodo.h"

class NodoPtr;    // dichiarazione anticipata

typedef NodoPtr *posizione;     //necessita della dichiarazione anticipata

class NodoPtr: public Nodo;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoPtr.cpp */

#include <iostream>

#include <cstdlib>

#include "NodoPtr.h"

NodoPtr::NodoPtr(): Nodo();

NodoPtr::NodoPtr(tipoelem a): Nodo(a);

NodoPtr::NodoPtr(tipoelem a, posizione p): Nodo(a);

NodoPtr::~NodoPtr();

posizione NodoPtr::getSuccessivo();

void NodoPtr::setSuccessivo(posizione p);

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: CodaPtr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa la coda con puntatore

#include "NodoPtr.h"

#ifndef CODAPTR_H

#define CODAPTR_H

class CodaPtr ;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* CodaPtr.cpp */

#include "CodaPtr.h"

#include <iostream>

#include <cstdlib>

CodaPtr::CodaPtr();

CodaPtr::~CodaPtr()

void CodaPtr::creaCoda();

bool CodaPtr::codaVuota();

bool CodaPtr::leggiCoda(tipoelem &a) else return false;

void CodaPtr::inCoda(tipoelem a)

else

testa = fondo = q;

bool CodaPtr::fuoriCoda() else return false;

Il programma principale permetterà di popolare una coda, stamparla, cercare un elemento, epurarla (eliminando tutti i valori maggiori di uno dato da tastiera), invertirla ed eliminare i doppioni.

#include "CodaPtr.h"

#include "PilaPtr.h"

#include <cstdlib>

#include <iostream>

using namespace std;

void inserisciCoda(CodaPtr &q) while (!((risp == 'S') || (risp == 's') || (risp == 'N') ||

(risp == 'n')));

}

cout << "Hai inserito " << i << " elementi" << endl;

bool copiaCoda(CodaPtr &q, CodaPtr &r)

while (!s.codaVuota())

return true;

} else return false;

bool stampaCoda(CodaPtr &q)

cout << endl;

return true;

} else return false;

bool invertiCoda(CodaPtr &q, CodaPtr &r)

while (!p.pilaVuota())

return true;

} else return false;

bool epuraCoda(tipoelem a, CodaPtr &q, CodaPtr &r)

return true;

} else return false;

bool ricercaCoda(tipoelem a, CodaPtr &q, int &i)

}

}

return trovato;

bool doppioniCoda(CodaPtr &q, CodaPtr &r)

return true;

} else return false;

int main(int argc, char *argv[])

else

cout << endl << "Epurazione della coda Q:" << endl << "Parametro di epurazione: " << endl;

Nodo::insEtichetta(a);

epuraCoda(a, q, r);

cout << "R: ";

stampaCoda(r);

r.creaCoda();

cout << endl << "Inversione della coda Q:" << endl <<"R: ";

invertiCoda(q, r);

stampaCoda(r);

r.creaCoda();

cout << endl << "Eliminazione dei doppioni dalla coda R:" << endl << "R: ";

doppioniCoda(q, r);

stampaCoda(r);

cout << endl;

system("PAUSE");

return 0;

4. INSIEMI

Un insieme è una collezione di elementi distinti (detti anche componenti o membri) dello stesso tipo. A differenza delle liste gli elementi non sono caratterizzati da una posizione né possono apparire più di una volta. L'insieme è una struttura matematica e può essere descritto o elencandone tutti gli elementi (definizione estensionale) oppure stabilendo una proprietà che ne caratterizzi gli elementi (definizione intensionale). Il numero di elementi che compongono un insieme A è detto cardinalità e si indica con |A|. di seguito saranno mostrate le implementazioni con un vettore booleano (solo per elementi di tipo intero), e con una lista non ordinata.

4.1 INSIEME CON VETTORE BOOLEANO

L'insieme A i cui elementi sono interi compresi tra 1 e N è rappresentato mediante un vettore booleano di N elementi, in cui il k-esimo elemento è true se k A ed è false se k A. In questo modo è estremamente semplice l'implementazione degli operatori, in quanto l'accesso agli elementi è diretto.

Nome: InsiemeBool.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa l'insieme con vettore di booleani

#ifndef INSIEMEBOOL_H

#define INSIEMEBOOL_H

#define MAXLUNG 100

typedef int tipoelem;

class InsiemeBool;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* InsiemeBool.cpp */

#include <iostream>

#include <cstdlib>

#include "InsiemeBool.h"

InsiemeBool::InsiemeBool()

InsiemeBool::~InsiemeBool()

void InsiemeBool::creaInsieme()

bool InsiemeBool::insiemeVuoto()

return !flag;

bool InsiemeBool::appartiene(tipoelem a)

void InsiemeBool::inserisci(tipoelem a)

void InsiemeBool::cancella(tipoelem a)

InsiemeBool InsiemeBool::unione(InsiemeBool a)

return c;

InsiemeBool InsiemeBool::intersezione(InsiemeBool a)

return c;

InsiemeBool InsiemeBool::differenza(InsiemeBool a)

return c;

Il programma principale permetterà di popolare due insiemi e di effettuare su di essi le operazioni di unione, intersezione e differenza, con stampa a video dei risultati.

#include <cstdlib>

#include <iostream>

#include "InsiemeBool.h"

using namespace std;

void inserisciInsieme(InsiemeBool &i) while (!((a >= 0) && (a <= MAXLUNG)));

if (!i.appartiene(a))

i.inserisci(a);

else

do while (!((risp == 's') || (risp == 'S') || (risp == 'n') || (risp == 'N')));

}

cout << "Hai inserito " << index << " elementi" << endl;

void stampaInsieme(InsiemeBool &i)

cout << "}" << endl;

int main(int argc, char *argv[])

4.2 INSIEME CON LISTE NON ORDINATE

Un altro modo per realizzare un insieme è attraverso l'uso di una lista non ordinata. Ciò ci permette di svincolare dalle limitazioni sul tipo degli elementi e sulla occupazione di memoria. Gli elementi della lista sono quelli dell'insieme con la sola imposizione che gli elementi non siano ripetuti.

Nome: NodoPtr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il nodo dell'insieme con lista non ordinata

#ifndef NODOPTR_H

#define NODOPTR_H

#include "Nodo.h"

class NodoPtr; // dichiarazione anticipata

typedef NodoPtr *posizione; //necessita della dichiarazione anticipata

class NodoPtr: public Nodo;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoPtr.cpp */

#include "NodoPtr.h"

#include <iostream>

#include <cstdlib>

NodoPtr::NodoPtr(): Nodo();

NodoPtr::NodoPtr(tipoelem a): Nodo(a);

NodoPtr::NodoPtr(tipoelem a, posizione p): Nodo(a);

NodoPtr::~NodoPtr();

posizione NodoPtr::getSuccessivo();

void NodoPtr::setSuccessivo(posizione p);

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: InsiemePtrN.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa l'insieme con lista non ordinata

#ifndef INSIEMEPTRN_H

#define INSIEMEPTRN_H

#include "NodoPtr.h"

class InsiemePtrN

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* InsiemePtrN.cpp */

#include "InsiemePtrN.h"

#include <iostream>

#include <cstdlib>

using namespace std;

InsiemePtrN::InsiemePtrN();

InsiemePtrN::~InsiemePtrN()

void InsiemePtrN::creaInsieme();

bool InsiemePtrN::insiemeVuoto();

bool InsiemePtrN::appartiene(tipoelem a)

return flag;

bool InsiemePtrN::inserisci(tipoelem a) else return false;

bool InsiemePtrN::cancella(tipoelem a)

if(p==insieme) else

q->setSuccessivo(p->getSuccessivo());

delete p;

return true;

} else return false;

InsiemePtrN &InsiemePtrN::unione(InsiemePtrN &set)

c->inserisci(a);

p = p->getSuccessivo();

p = b.getInsieme();

while (p != NULL)

return *c;

InsiemePtrN &InsiemePtrN::intersezione(InsiemePtrN &set)

p = b.getInsieme();

while (p != NULL)

return *c;

InsiemePtrN &InsiemePtrN::differenza(InsiemePtrN &set)

p = p->getSuccessivo();

}

return *c;

InsiemePtrN &InsiemePtrN::operator=(InsiemePtrN &i)

p = i.getInsieme();

while (p!=NULL)

return *this;

posizione InsiemePtrN::getInsieme();

Il programma principale permetterà di popolare due insiemi e di effettuare su di essi le operazioni di unione, intersezione e differenza, con stampa a video dei risultati.

#include "InsiemePtrN.h"

#include <cstdlib>

#include <iostream>

using namespace std;

void inserisciInsieme(InsiemePtrN &i)

do while (!((risp == 's') || (risp == 'S') || (risp == 'n') || (risp == 'N')));

}

cout << "Hai inserito " << index << " elementi" << endl;

void stampaInsieme(InsiemePtrN &i)

cout << " }" << endl;

int main(int argc, char *argv[])

5. DIZIONARI

Il dizionario è un caso particolare di insieme, in cui è possibile verificare l'appartenenza di un elemento, cancellare un elemento e inserire un nuovo elemento. Gli elementi del dizionario sono generalmente tipi strutturati ai quali si accede per mezzo di un riferimento al contenuto stesso dell'elemento o a un campo chiave. Gli elementi assumono la forma di una coppia costituita da una chiave e un attributo. La caratteristica della chiave è che è legata alla particolare applicazione (ad esempio per la gestione di un magazzino la chiave può essere il codice del prodotto), mentre l'attributo rappresenta l'informazione associata alla chiave (ad esempio la descrizione del prodotto). Qui di seguito riporto la realizzazione con hash aperto con liste di trabocco.

5.1 DIZIONARIO CON HASH APERTO E LISTE DI TRABOCCO

La funzione hash è una particolare funzione matematica che calcola, a partire da una generica chiave, un intero definito in un intervallo. La tecnica hash è una tecnica che si basa su una struttura dati tabellare e che utilizza appunto una funzione hash per calcolare la posizione in cui memorizzare un elemento. È possibile però che due distinte chiavi producano la stessa posizione dopo l'applicazione della funzione hash. Questi casi sono detti collisioni.

L'Hash aperto permette una buona gestione delle collisioni mediante l'utilizzo di liste di trabocco per ogni posizione del vettore. La funzione hash viene utilizzata sia per calcolare in quale posizione inserire un elemento, sia per capire in quale lista cercarlo. Nel nostro caso, il dizionario è un vettore di puntatori al primo elemento di ogni lista di trabocco.

Nome: NodoStr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il nodo della lista di stringhe

#ifndef NODOSTR_H

#define NODOSTR_H

typedef std::string tipochiave;

struct attrib;

struct rec;

typedef rec tipoelem;

class NodoStr; // dichiarazione anticipata

typedef NodoStr *posizione; //necessita della dichiarazione anticipata

class NodoStr;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoStr.h */

#include <iostream>

#include <cstdlib>

#include "NodoStr.h"

NodoStr::NodoStr();

NodoStr::NodoStr(tipoelem a);

NodoStr::NodoStr(tipoelem a, posizione p);

NodoStr::~NodoStr();

tipoelem NodoStr::getEtichetta();

void NodoStr::setEtichetta(tipoelem a)

posizione NodoStr::getSuccessivo();

void NodoStr::setSuccessivo(posizione p);

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: ListaStr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa la lista di stringhe

#ifndef LISTASTR_H

#define LISTASTR_H

#include "NodoStr.h"

class ListaStr;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* ListaStr.cpp */

#include <iostream>

#include <cstdlib>

#include "ListaStr.h"

ListaStr::ListaStr();

ListaStr::~ListaStr()

void ListaStr::creaLista();

bool ListaStr::listaVuota();

posizione ListaStr::primoLista();

posizione ListaStr::predLista(posizione p) else

return q;

}

posizione ListaStr::succLista(posizione p);

bool ListaStr::fineLista(posizione p);

void ListaStr::insLista(tipoelem a, posizione p)

bool ListaStr::cancLista(posizione p) else

primo = primo->getSuccessivo();

delete p;

return true;

} else return false;

bool ListaStr::scriviLista(tipoelem a, posizione p) else return false;

bool ListaStr::leggiLista(tipoelem &a, posizione p) else return false;

ListaStr &ListaStr::operator=(ListaStr &l)

p = l.primoLista();

tipoelem a;

while (!l.fineLista(p))

return *this;

posizione ListaStr::pos(int n)

return p;

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: Dizionario.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il dizionario (hash chiuso estendibile)

#ifndef DIZIONARIO_H

#define DIZIONARIO_H

#define M 101

#include "ListaStr.h"

class Dizionario;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* Dizionario.cpp */

#include <iostream>

#include <cstdlib>

#include <string.h>

#include "Dizionario.h"

using namespace std;

Dizionario::Dizionario()

Dizionario::~Dizionario()

}

void Dizionario::creaDizionario()

bool Dizionario::appartiene(tipochiave k)

return trovato;

bool Dizionario::inserisci(tipoelem a) else

cout << a.chiave << " presente in posizione " << h << endl;

return inserito;

bool Dizionario::cancella(tipochiave k)

p = dizionario[h].succLista(p);

}

return trovato;

bool Dizionario::recupera(tipochiave k, tipoelem &a)

return trovato;

bool Dizionario::aggiorna(tipochiave k, tipoelem a) else

dizionario[h].succLista(p);

}

return trovato;

void Dizionario::stampa()

cout << "Numero di collisioni per la chiave "<< i <<": "<< collision-1 << "\n"<<endl;

}

}

cout << "Per le chiavi non specificate non sono stati trovati elementi"<< endl;

int Dizionario::hashWord(tipochiave k)

Il programma principale permetterà di inserire parole nel dizionario, cancellarle, aggiornare un elemento già inserito, recuperarne le informazioni e stampare il dizionario.

#include <iostream>

#include <cstdlib>

#include <cstring>

#include "Dizionario.h"

using namespace std;

int main(int argc, char *argv[]) while (!((scelta > 0) && (scelta < 7)));

cout << endl;

switch (scelta) else

cout << "Parola " << a.chiave << " non trovata" << endl;

break;

case 3:

cout << "Inserisci chiave: ";

cin >> a.chiave;

if (d.appartiene(a.chiave)) else

cout << "Parola " << a.chiave << " non presente" << endl;

break;

case 4:

cout << "Inserisci chiave: ";

cin >> a.chiave;

if (d.appartiene(a.chiave)) else

cout << "Parola " << a.chiave << " non presente" << endl;

break;

case 5:

d.stampa();

break;

case 6:

cout << "bye bye..." << endl;

break;

}

system("PAUSE");

system("CLS");

} while (scelta != 6);

return 0;

6. ALBERI

L'Albero è una struttura informativa fondamentale utile per rappresentare:

• Partizioni successive di un insieme in sottoinsiemi disgiunti.
• Organizzazioni gerarchiche di dati.
• Procedimenti decisionali enumerativi.

Un'Albero è definito matematicamente con una coppia T=(N,A) dove: N è un insieme finito di nodi ed A è un insieme di coppie non ordinate tali che il numero di archi è uguale al numero di nodi meno uno (|A|=|N|-1), inoltre T è debolemente connesso, cioè, per ogni nodo u e v appartenenti ad N, se esiste un cammino tra u e v, esso è unico. L'albero, infine, è radicato, cioè esiste un nodo speciale detto radice e tutti gli altri nodi sono organizzati per livelli (livello radice = 0). Definiamo albero di ordine k un albero i cui nodi hanno al più k figli.

6.1 ALBERI BINARI

Un albero binario è un particolare albero ordinato in cui ogni nodo ha al più due figli (albero di ordine 2) e si fa distinzione tra il figlio sinistro ed il figlio destro di ogni nodo. Questa proprietà fa si che due alberi T e U aventi gli stessi nodi, gli stessi figli per ogni nodo e la stessa radice, siano distinti qualora un nodo u sia destinato come figlio sinistro di un nodo v in T e come figlio destro per il medesimo nodo in U.  Per quanto riguarda la realizzazione, qui di seguito saranno illustrate sia quella con cursori che quella con puntatori.

6.1.1 ALBERI BINARI CON CURSORI

In questa rappresentazione viene utilizzato un vettore spazio in cui ogni componente è un record avente, oltre al campo etichetta, tre indici che rappresentano la posizione del padre di quel nodo, del suo figlio sinistro e del suo figlio destro. Ovviamente, se un nodo non ha figlio sinistro o destro, verrà assegnato un valore fittizio all'indice (-1). Verrà utilizzata inoltre, una variabile primo che terrà traccia dell'indice della radice dell'albero, e di una variabile primoVuoto che invece farà riferimento al primo elemento vuoto del vettore spazio.

Nome: NodoBinCur.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il nodo dell'albero binario con cursore

#include "Nodo.h"

#ifndef NODOBINCUR_H

#define NODOBINCUR_H

#define NIL -1

typedef int nodoBin;

class NodoBinCur: public Nodo;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoBinCur.cpp */

#include "NodoBinCur.h"

#include <iostream>

#include <cstdlib>

NodoBinCur::NodoBinCur(): Nodo()

NodoBinCur::NodoBinCur(tipoelem a): Nodo(a)

NodoBinCur::NodoBinCur(tipoelem a, nodoBin s, nodoBin d, nodoBin p): Nodo(a)

NodoBinCur::~NodoBinCur()

nodoBin NodoBinCur::getSx()

nodoBin NodoBinCur::getDx()

nodoBin NodoBinCur::getDaddy()

void NodoBinCur::setSx(nodoBin s)

void NodoBinCur::setDx(nodoBin d)

void NodoBinCur::setDaddy(nodoBin p)

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: BinAlberoCur.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa l'albero binario con cursore

#ifndef BINALBEROCUR_H

#define BINALBEROCUR_H

#include "NodoBinCur.h"

#define MAXLUNG 100

class BinAlberoCur;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* BinAlberoCur.cpp */

#include "BinAlberoCur.h"

#include <iostream>

#include <cstdlib>

BinAlberoCur::BinAlberoCur()

BinAlberoCur::~BinAlberoCur()

void BinAlberoCur::creaBinAlbero()

spazio[MAXLUNG-1].setSx(NIL);

bool BinAlberoCur::binAlberoVuoto()  

nodoBin BinAlberoCur::binRadice()

nodoBin BinAlberoCur::binPadre(nodoBin p)

nodoBin BinAlberoCur::figlioSx(nodoBin p)

nodoBin BinAlberoCur::figlioDx(nodoBin p)

bool BinAlberoCur::sxVuoto(nodoBin p)

bool BinAlberoCur::dxVuoto(nodoBin p)  

bool BinAlberoCur::insBinRadice(nodoBin p) else return false;

bool BinAlberoCur::insFiglioSx(nodoBin p) else return false;

bool BinAlberoCur::insFiglioDx(nodoBin p) else return false;

void BinAlberoCur::cancSottoBinAlbero(nodoBin p)

if (!dxVuoto(p))

if (p != primo) else

} else primo = NIL;

totNodi--;

spazio[p].setSx(primoVuoto);

primoVuoto = p;

}

bool BinAlberoCur::leggiNodo(nodoBin p, tipoelem &a) else return false;

bool BinAlberoCur::scriviNodo(nodoBin p, tipoelem a) else return false;

nodoBin BinAlberoCur::pos(int n)

}

return p;

Il programma principale permetterà di popolare un albero in maniera ordinata, di stamparlo, effettuare delle visite (previsita, postvisita, invisita, visita per livelli), cercare un nodo restituendone la profondità ed eventualmente potare l'albero a partire da quel nodo.

#include "BinAlberoCur.h"

#include "CodaPtr.h"

#include <cstdlib>

#include <iostream>

using namespace std;

void riempiBinAlbero(tipoelem a, nodoBin n, BinAlberoCur &t) else riempiBinAlbero(a, t.figlioSx(n), t);

} else if (ris == 1) else riempiBinAlbero(a, t.figlioDx(n), t);

} else

} else

void stampaBinAlbero(nodoBin p, BinAlberoCur &t) else cout << "S()";

if (!t.dxVuoto(p)) else cout << "D()";

//cout << ")";

void preVisita(nodoBin p, BinAlberoCur &t)

if (!t.dxVuoto(p))

}

void postVisita(nodoBin p, BinAlberoCur &t)

if (!t.dxVuoto(p))

tipoelem a;

t.leggiNodo(p, a);

Nodo::stampaEtichetta(a);

cout << " ";

}

void inVisita(nodoBin p, BinAlberoCur &t)

tipoelem a;

t.leggiNodo(p, a);

Nodo::stampaEtichetta(a);

cout << " ";

if (!t.dxVuoto(p))

}

void ampiezzaBin(nodoBin p, BinAlberoCur &t)

if (!t.dxVuoto(p))

}

bool trovaParola(tipoelem &a, nodoBin n, BinAlberoCur &t, int &i, nodoBin &pota) else if (ris == 1) else  

} else return false;

void inserisciBinAlbero(BinAlberoCur &t)

while (!((risp == 's') || (risp == 'S') || (risp == 'N') || (risp == 'n')));

}

int main(int argc, char *argv[])

while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

if ((risp == 's') || (risp == 'S'))

} else

system("PAUSE");

return 0;

6.1.2 ALBERI BINARI CON PUNTATORI

Per la realizzazione dell'albero binario con puntatore ogni elemento sarà un record che conterrà, oltre all'etichetta del nodo, tre puntatori, padre, sx, dx, rispettivamente al padre, al figlio sinistro ed al figlio destro del nodo stesso. Quindi, attraverso un puntatore radice, sarà possibile accedere alla radice dell'albero.

Nome: NodoBinPtr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il nodo dell'albero binario con puntatore

#ifndef NODOBINPTR_H

#define NODOBINPTR_H

#include "Nodo.h"

class NodoBinPtr; // dichiarazione anticipata

typedef  NodoBinPtr *nodoBin;

class NodoBinPtr: public Nodo;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoBinPtr.cpp */

#include "NodoBinPtr.h"

#include <iostream>

NodoBinPtr::NodoBinPtr() : Nodo()

NodoBinPtr::NodoBinPtr(tipoelem a) : Nodo(a)

NodoBinPtr::NodoBinPtr(tipoelem a, nodoBin s, nodoBin d) : Nodo(a)

NodoBinPtr::~NodoBinPtr()

nodoBin NodoBinPtr::getSx()

nodoBin NodoBinPtr::getDx()

nodoBin NodoBinPtr::getPadre()

bool NodoBinPtr::setSx(nodoBin s)else return false;

bool NodoBinPtr::setDx(nodoBin d)else return false;

bool NodoBinPtr::setPadre(nodoBin ddd)else return false;

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: BinAlbero.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa l'albero binario con puntatore

#ifndef BINABERO_H

#define BINALBERO_H

#include "NodoBinPtr.h"

class BinAlbero;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* BinAlbero.cpp */

#include "BinAlbero.h"

#include <iostream>

BinAlbero::BinAlbero()

BinAlbero::~BinAlbero()

void BinAlbero::creaBinAlbero()

bool BinAlbero::binAlberoVuoto()  

nodoBin BinAlbero::binRadice()

nodoBin BinAlbero::binPadre(nodoBin p)

nodoBin BinAlbero::figlioSx(nodoBin p)

nodoBin BinAlbero::figlioDx(nodoBin p)

bool BinAlbero::sxVuoto(nodoBin p)

bool BinAlbero::dxVuoto(nodoBin p)  

bool BinAlbero::insBinRadice(nodoBin p) else return false;

bool BinAlbero::insFiglioSx(nodoBin p) else return false;

bool BinAlbero::insFiglioDx(nodoBin p) else return false;

void BinAlbero::cancSottoBinAlbero(nodoBin p) else radice = NULL;

std::cout << "Cancellato: ";

Nodo::stampaEtichetta(p->getEtichetta());

std::cout << std::endl;

delete p;

}

bool BinAlbero::leggiNodo(nodoBin p, tipoelem &a) else return false;

bool BinAlbero::scriviNodo(nodoBin p, tipoelem a) else return false;

Il programma principale permetterà di popolare un albero in maniera ordinata, di stamparlo, effettuare delle visite (previsita, postvisita, invisita, visita per livelli), cercare un nodo restituendone la profondità ed eventualmente potare l'albero a partire da quel nodo.

#include <cstdlib>

#include <iostream>

#include "BinAlbero.h"

#include "CodaPtr.h"

using namespace std;

void riempiBinAlbero(tipoelem a, nodoBin n, BinAlbero &t) else riempiBinAlbero(a, t.figlioSx(n), t);

} else if (ris == 1) else riempiBinAlbero(a, t.figlioDx(n), t);

} else

} else

void stampaBinAlbero(nodoBin p, BinAlbero &t) else cout << "()";

if (!t.dxVuoto(p)) else cout << "()";

cout << ")";

}

void preVisita(nodoBin p, BinAlbero &t)

if (!t.dxVuoto(p))

}

void postVisita(nodoBin p, BinAlbero &t)

if (!t.dxVuoto(p))

tipoelem a;

t.leggiNodo(p, a);

Nodo::stampaEtichetta(a);

cout << " ";

}

void inVisita(nodoBin p, BinAlbero &t)

tipoelem a;

t.leggiNodo(p, a);

Nodo::stampaEtichetta(a);

cout << " ";

if (!t.dxVuoto(p))

}

void ampiezzaBin(nodoBin p, BinAlbero &t)

if (!t.dxVuoto(p))

}

bool trovaParola(tipoelem &a, nodoBin n, BinAlbero &t, int &i, nodoBin &pota) else if (ris == 1) else  

} else return false;

void inserisciBinAlbero(BinAlbero &t)

while (!((risp == 's') || (risp == 'S') || (risp == 'N') || (risp == 'n')));

}

int main(int argc, char *argv[])

while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

if ((risp == 's') || (risp == 'S'))

} else

system("PAUSE");

return 0;

6.2 ALBERI N-ARI

Gli alberi n-ari sono alberi di ordine k e, a differenza degli alberi binari, ogni nodo dell'albero può avere un numero arbitrario di figli, sui quali però esistere una relazione di ordinamento, cioè si sa qual è il primo figlio e si può accedere ai successivi fratelli. Sono state prese in considerazione due realizzazioni di albero n-ario: con cursore e con puntatore.

6.2.1 ALBERI N-ARI CON CURSORI

In questa rappresentazione viene utilizzato un vettore stazio in cui ogni componente è un record avente, oltre al campo etichetta, tre indici che rappresentano la posizione del padre di quel nodo, del suo primo figlio e del suo successivo fratello. Ovviamente, se un nodo non ha figli o fratelli, verrà assegnato un valore fittizio all'indice (-1). Verrà utilizzata una variabile root che terrà traccia dell'indice della radice dell'albero, e di una variabile primoVuoto che invece farà riferimento al primo elemento vuoto del vettore spazio.

Nome: NodoNCur.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il nodo dell'albero n-ario con cursore

#ifndef NODONCUR_H

#define NODONCUR_H

#include "Nodo.h"

#define NIL -1

typedef int nodoN;    // cursore al nodo

class NodoNCur: public Nodo;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoNCur.cpp */

#include <iostream>

#include <cstdlib>

#include "NodoNCur.h"

NodoNCur::NodoNCur(): Nodo()

NodoNCur::NodoNCur(tipoelem a): Nodo(a)

NodoNCur::NodoNCur(tipoelem a, nodoN p, nodoN pf, nodoN sf): Nodo(a)

NodoNCur::~NodoNCur()

nodoN NodoNCur::getPrimoFigl()

nodoN NodoNCur::getProxFratello()

nodoN NodoNCur::getGenitore()

void NodoNCur::setPrimoFigl(nodoN n)

void NodoNCur::setProxFratello(nodoN n)

void NodoNCur::setGenitore(nodoN n)

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: NAlbero.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa l'albero n-ario con cursore

#ifndef NALBERO_H

#define NALBERO_H

#include "NodoNCur.h"

#define MAXLUNG 100

class NAlbero;

#endif // NALBERO_H

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NAlbero.cpp */

#include <iostream>

#include <cstdlib>

#include "NAlbero.h"

NAlbero::NAlbero()

NAlbero::~NAlbero()

void NAlbero::creaNAlbero()

bool NAlbero::nAlberoVuoto()

bool NAlbero::insRadice(nodoN n) else return false;

} else return false;

nodoN NAlbero::radice()

nodoN NAlbero::padre(nodoN n) else return NIL;

bool NAlbero::foglia(nodoN n)else return NIL;

nodoN NAlbero::primoFiglio(nodoN n) else return NIL;

bool NAlbero::ultimoFratello(nodoN n)else return NIL;

nodoN NAlbero::succFratello(nodoN n)else return NIL;

bool NAlbero::insPrimoSottoAlbero(nodoN n, nodoN r)else return false;

} else return false;

else return false;

bool NAlbero::insSottoAlbero(nodoN n, nodoN r)else return false;

}else return false;

else return false;

bool NAlbero::cancSottoAlbero(nodoN n)

} else

// riassegna il nodo alle risorse disponibili

spazio[n].setProxFratello(primoVuoto);

primoVuoto = n;

return true;

} else return false;

tipoelem NAlbero::leggiNodo(nodoN n)

bool NAlbero::scriviNodo(nodoN n, tipoelem a)else return false;

nodoN NAlbero::newNodo()

Il programma principale permetterà di popolare un albero, di stamparlo, effettuare delle visite (previsita, postvisita, invisita con ordine 1, visita per livelli), cercare un nodo restituendone la profondità ed eventualmente potare l'albero a partire da quel nodo.

#include <cstdlib>

#include <iostream>

#include "NAlbero.h"

#include "CodaPtr.h"

using namespace std;

void inserisciNAlbero(nodoN n, NAlbero &t) else

cout << endl;

t.scriviNodo(m, a);

inserisciNAlbero(m, t);

}

} else cout << endl;

}

void stampaNAlbero(nodoN n, NAlbero &t)

} else cout << "()";

void preVisita(nodoN n, NAlbero &t)

void postVisita(nodoN n, NAlbero &t)

void inVisita(nodoN n, NAlbero &t)

}

else

void ampiezzaN(nodoN p, NAlbero &t)

q.inCoda(x);

}

}

void cancella(tipoelem a, NAlbero &t, nodoN n, int prof) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

if ((risp == 's') || (risp == 'S')) else

cout << "Albero non potato!" << endl << "T: ";

stampaNAlbero(t.radice(), t);

bool profNodo(tipoelem a, nodoN n, int &prof, NAlbero &t, bool &cancellata)

}

}

if (trovata && !cancellata)

}

return trovata;

int main(int argc, char *argv[])

cout << endl;

system("PAUSE");

return 0;

6.2.2 ALBERI N-ARI CON PUNTATORI

Nella realizzazione dell'albero n-ario con puntatore ogni elemento dell'albero sarà un record che conterrà, oltre all'etichetta del nodo, tre puntatori, genitore, primoFigl, proxFratello, rispettivamente al padre, al primo figlio ed al successivo fratello del nodo stesso. Quindi, attraverso un puntatore root, sarà possibile accedere alla radice dell'albero.

Nome: NodoNPtr.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il nodo dell'albero n-ario con puntatore

#ifndef NODONPTR_H

#define NODONPTR_H

#include "Nodo.h"

class NodoNPtr;    //dichiarazione anticipata

typedef NodoNPtr *nodoN;

class NodoNPtr: public Nodo;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NodoNPtr.cpp */

#include <iostream>

#include <cstdlib>

#include "NodoNPtr.h"

NodoNPtr::NodoNPtr(): Nodo()

NodoNPtr::NodoNPtr(tipoelem a): Nodo(a)

NodoNPtr::NodoNPtr(tipoelem a, nodoN p, nodoN pf, nodoN sf): Nodo(a)

NodoNPtr::~NodoNPtr()

nodoN NodoNPtr::getPrimoFigl()

nodoN NodoNPtr::getProxFratello()

nodoN NodoNPtr::getGenitore()

void NodoNPtr::setPrimoFigl(nodoN n)

void NodoNPtr::setProxFratello(nodoN n)

void NodoNPtr::setGenitore(nodoN n)

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: NAlbero.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa l'albero n-ario con puntatore

#ifndef NALBERO_H

#define NALBERO_H

#include "NodoNPtr.h"

class NAlbero;

#endif // NALBERO_H

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* NAlbero.cpp */

#include <iostream>

#include <cstdlib>

#include "NAlbero.h"

NAlbero::NAlbero()

NAlbero::~NAlbero()

void NAlbero::creaNAlbero()

bool NAlbero::nAlberoVuoto()

bool NAlbero::insRadice(nodoN n) else return false;

nodoN NAlbero::radice()

nodoN NAlbero::padre(nodoN n)

bool NAlbero::foglia(nodoN n)

nodoN NAlbero::primoFiglio(nodoN n)

bool NAlbero::ultimoFratello(nodoN n)

nodoN NAlbero::succFratello(nodoN n)

bool NAlbero::insPrimoSottoAlbero(nodoN n, nodoN r) else return false;

bool NAlbero::insSottoAlbero(nodoN n, nodoN r)else return false;

bool NAlbero::cancSottoAlbero(nodoN n)

else root = NULL;

delete n;

return true;

} else return false;

tipoelem NAlbero::leggiNodo(nodoN n)

bool NAlbero::scriviNodo(nodoN n, tipoelem a)else return false;

Il programma principale permetterà di popolare un albero, di stamparlo, effettuare delle visite (previsita, postvisita, invisita con ordine 1, visita per livelli), cercare un nodo restituendone la profondità ed eventualmente potare l'albero a partire da quel nodo.

#include <cstdlib>

#include <iostream>

#include "NAlbero.h"

#include "CodaPtr.h"

using namespace std;

void inserisciNAlbero(nodoN n, NAlbero &t) else

cout << endl;

inserisciNAlbero(m, t);

} else cout << endl;

}

void stampaNAlbero(nodoN n, NAlbero &t)

} else cout << "()";

void preVisita(nodoN n, NAlbero &t)

}

void postVisita(nodoN n, NAlbero &t)

}

void inVisita(nodoN n, NAlbero &t)

} else

}

void ampiezzaN(nodoN n, NAlbero &t)

q.inCoda(m);

}

}

void cancella(tipoelem a, NAlbero &t, nodoN n, int prof) while (!((risp == 'S') || (risp == 's') || (risp == 'N') || (risp == 'n')));

if ((risp == 's') || (risp == 'S')) else

cout << "Albero non potato!" << endl << "T: ";

stampaNAlbero(t.radice(), t);

bool profNodo(tipoelem a, nodoN n, int &prof, NAlbero &t, bool &cancellata)

}

}

if (trovata && !cancellata)

}

return trovata;

int main(int argc, char *argv[])

cout << endl;

system("PAUSE");

return 0;

7. GRAFI

Il grafo è una struttura dati definibile come una coppia G = <N, A> dove N è un insieme finito di nodi ed A è un insieme di coppie <u, v> detti archi. Solitamente, questi archi sono orientati, vale a dire le coppie <u, v> sono ordinate. Ovviamente, ogni grafo non orientato può essere visto come un grafo orientato, dove, per ogni arco <i, j> appartenente al primo, esistono due archi, <i, j> e <j, i> appartenenti al secondo.

Si è preso in considerazione, quattro tipi di grafo: con matrice di adiacenza, matrice di adiacenza estesa e liste di adiacenza.

7.1 GRAFI CON MATRICE DI ADIACENZA

Questa è senza dubbio la più semplice rappresentazione di un grafo. Se n sono i nodi, essa sfrutta una matrice nxn (che nel nostro programma si chiama grafo) dove, se esiste l'arco <i, j>, sarà presente un 1 nella riga i e colonna j della stessa. Questa rappresentazione però impone una limitazione sul numero di nodi.

Nome: ListaAdiacenti.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa la lista di adiacenza dei nodi

#ifndef LISTAADIACENTI_H

#define LISTAADIACENTI_H

#define NIL -1

typedef struct NodoAdiacenti *posizione;

typedef struct tipo tipoelem;

typedef int Nodo;

typedef int tipoPeso;

struct NodoAdiacenti;

class ListaAdiacenti;

#endif // LISTAADIACENTI_H

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* ListaAdiacenti.cpp */

#include <iostream>

#include <cstdlib>

#include "ListaAdiacenti.h"

using namespace std;

ListaAdiacenti::ListaAdiacenti()

ListaAdiacenti::~ListaAdiacenti()

void ListaAdiacenti::creaLista()

bool ListaAdiacenti::listaVuota()

posizione ListaAdiacenti::primoLista()

posizione ListaAdiacenti::predLista(posizione p)else

return NULL;

posizione ListaAdiacenti::succLista(posizione p)

bool ListaAdiacenti::fineLista(posizione p)

void ListaAdiacenti::insLista(Nodo a, posizione p)else

bool ListaAdiacenti::cancLista(posizione p) else

delete p;

return true;

}else return false; //ERRORE!

bool ListaAdiacenti::scriviLista(Nodo a, posizione p)else return false; //ERRORE!

bool ListaAdiacenti::leggiLista(Nodo &a, posizione p)else return false; //ERRORE!

ListaAdiacenti &ListaAdiacenti::operator=(ListaAdiacenti &l)

p = l.primoLista();

Nodo a;

while (!l.fineLista(p))

return *this;

posizione ListaAdiacenti::pos(int i)

return p;

}else

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: GrafoMatAd.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa il grafo con matrice di adiacenza

#ifndef GRAFOMATAD_H

#define GRAFOMATAD_H

#define MAXNODI 20

#include <iostream>

#include "ListaAdiacenti.h"

typedef int Nodo;

struct tipoNodi;

class GrafoMatAd;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* GrafoMatAd.cpp */

#include <iostream>

#include <cstdlib>

#include "GrafoMatAd.h"

GrafoMatAd::GrafoMatAd()

GrafoMatAd::~GrafoMatAd()

void GrafoMatAd::creaGrafo()

bool GrafoMatAd::grafoVuoto()

return vuoto;

bool GrafoMatAd::esisteNodo(Nodo i)

bool GrafoMatAd::esisteArco(Nodo i, Nodo j)

void GrafoMatAd::insNodo(Nodo i)

bool GrafoMatAd::insArco(Nodo i, Nodo j) else return false;

bool GrafoMatAd::cancNodo(Nodo i) else return false;

bool GrafoMatAd::cancArco(Nodo i, Nodo j) else return false;

void GrafoMatAd::adiacenti(Nodo i, ListaAdiacenti &l)

bool GrafoMatAd::getVisitato(Nodo i)

void GrafoMatAd::setVisitato(bool b, Nodo i)

void GrafoMatAd::azzeraVisitato()

Il programma principale permetterà di popolare un grafo, stamparlo, visitarlo (bfs e dfs), stabilire il nodo col maggior numero di archi entranti e quello col maggior numero di archi uscenti, verificare se due nodi sono connessi, stabilire se il grafo è connesso, cancellare un nodo e tutti i suoi archi.

#include <cstdlib>

#include <iostream>

#include "GrafoMatAd.h"

#include "CodaPtr.h"

using namespace std;

void insGrafo(GrafoMatAd &g) while (!((risp =='s') || (risp == 'S') || (risp == 'n') || (risp == 'N')));

risp = 's';

cout << endl;

cout << "Inserimento archi:" << endl;

cout << "----- ----- --------" << endl;

while ((risp == 's') || (risp =='S')) while (!((i >= 0) && (i < MAXNODI) && (g.esisteNodo(i))));

do while (!((j >= 0) && (j < MAXNODI) && (g.esisteNodo(j))));

if (g.esisteArco(i, j))

cout << "Arco (" << i << ", " << j << ") esistente" << endl;

else

g.insArco(i, j);

do while (!((risp =='s') || (risp == 'S') || (risp == 'n') || (risp == 'N')));

}

void stampaGrafo(GrafoMatAd &g)

void stampaLista(ListaAdiacenti &l)

void isolaNodo(Nodo n, GrafoMatAd &g)

}

void dfs(Nodo u, GrafoMatAd &g)

} else cout << "dfs non applicabile" << endl;

bool copiaCoda(CodaPtr &q, CodaPtr &r)

while (!s.codaVuota())

return true;

} else return false;

bool ricercaCoda(elemCoda a, CodaPtr &q)

}

return trovato;

void bfs(Nodo u, GrafoMatAd &g)

}

g.azzeraVisitato();

cout << endl;

} else cout << "bfs non applicabile" << endl;

bool nodiConnessi(Nodo u, Nodo z, GrafoMatAd &g)

}

g.azzeraVisitato();

} else cout << "Funzione non applicabile" << endl;

return connessi;

void maxEntranti(GrafoMatAd &g, Nodo &a, int &entranti)

}

entranti = max;

} else cout << "Grafo vuoto" << endl;

void maxUscenti(GrafoMatAd &g, Nodo &a, int &uscenti)

if(maxTemp > max)

}

uscenti = max;

} else cout << "Grafo vuoto" << endl;

bool grafoConnesso(GrafoMatAd &g)

}

}

} else

connesso = false;

return connesso;

int main(int argc, char *argv[])

while (!((i >= 0) && (i < MAXNODI) && (g.esisteNodo(i))));

cout << endl << "dfs G: ";

dfs(i, g);

g.azzeraVisitato();

cout << endl << "bfs G: ";

bfs(i, g);

maxEntranti(g, a, i);

cout<<endl<<"Il nodo con il maggior num di nodi entranti:"<<a<<" ("<< i <<")"<< endl;

maxUscenti(g, a, i);

cout << "Il nodo con il maggior numero di nodi uscenti: " <<a<< " (" << i << ")" << endl;

cout << endl << "Connessione fra due nodi:" << endl;

do while (!((i >= 0) && (i < MAXNODI) && (g.esisteNodo(i))));

do while (!((j >= 0) && (j < MAXNODI) && (g.esisteNodo(j))));

if (nodiConnessi(i, j, g))

cout << "Nodi " << i << ", " << j << " connessi" << endl;

else

cout << "Nodi " << i << ", " << j << " non connessi" << endl;

if (grafoConnesso(g))

cout << endl << "Grafo G totalmente connesso" << endl;

else

cout << endl << "Grafo G non totalmente connesso" << endl;

cout << endl << "Cancellazione di un nodo:" << endl;

do while (!((i >= 0) && (i < MAXNODI)));

if (g.esisteNodo(i)) else

cout << "Nodo " << i << "inesistente" << endl << endl;

system("PAUSE");

return 0;

7.2 GRAFO CON MATRICE DI ADIACENZA ESTESA

Il grafo con matrice di adiacenza non porta con sé particolari informazioni sui nodi del grafo. Un miglioramento della precedente realizzazione è l'utilizzo di una matrice di adiacenza estesa, dove, oltre alle informazioni sugli archi presenti, per ogni nodo è specificata una label, un mark (per indicare la presenza o assenza del nodo) e il numero di archi entranti ed uscenti da ogni nodo (archi).

Nome: ListaAdiacenti.h

Autore: Trullo Raffaella

Descrizione: Classe che implementa la lista di adiacenza dei nodi

#ifndef LISTAADIACENTI_H

#define LISTAADIACENTI_H

#define NIL -1

typedef struct NodoAdiacenti *posizione;

typedef struct tipo tipoelem;

typedef int Nodo;

typedef int tipoPeso;

struct NodoAdiacenti;

class ListaAdiacenti;

#endif // LISTAADIACENTI_H

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* ListaAdiacenti.cpp */

#include <iostream>

#include <cstdlib>

#include "ListaAdiacenti.h"

using namespace std;

ListaAdiacenti::ListaAdiacenti()

ListaAdiacenti::~ListaAdiacenti()

void ListaAdiacenti::creaLista()

bool ListaAdiacenti::listaVuota()

posizione ListaAdiacenti::primoLista()

posizione ListaAdiacenti::predLista(posizione p)else

return NULL;

posizione ListaAdiacenti::succLista(posizione p)

bool ListaAdiacenti::fineLista(posizione p)

void ListaAdiacenti::insLista(Nodo a, posizione p)else

bool ListaAdiacenti::cancLista(posizione p) else

delete p;

return true;

}else return false; //ERRORE!

bool ListaAdiacenti::scriviLista(Nodo a, posizione p)else return false; //ERRORE!

bool ListaAdiacenti::leggiLista(Nodo &a, posizione p)else return false; //ERRORE!

ListaAdiacenti &ListaAdiacenti::operator=(ListaAdiacenti &l)

p = l.primoLista();

Nodo a;

while (!l.fineLista(p))

return *this;

posizione ListaAdiacenti::pos(int i)

return p;

}else

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: GrafoMatAdExt.h

Autore: Trullo Raffaella

Descrizione: Classe che implementa il grafo con matrice di adiacenza estesa

#ifndef GRAFOMATADEXT_H

#define GRAFOMATADEXT_H

#define MAXNODI 20

#include <iostream>

#include "ListaAdiacenti.h"

typedef int Nodo;

typedef structtipolabel;

struct tipoNodi;

class GrafoMatAdExt;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* GrafoMatAdExt.cpp */

#include <iostream>

#include <cstdlib>

#include "GrafoMatAdExt.h"

GrafoMatAdExt::GrafoMatAdExt()

GrafoMatAdExt::~GrafoMatAdExt()

void GrafoMatAdExt::creaGrafo()

bool GrafoMatAdExt::grafoVuoto()

return vuoto;

bool GrafoMatAdExt::esisteNodo(Nodo i)

bool GrafoMatAdExt::esisteArco(Nodo i, Nodo j)

bool GrafoMatAdExt::insNodo(Nodo i, tipolabel a) else return false;

bool GrafoMatAdExt::insArco(Nodo i, Nodo j) else return false;

bool GrafoMatAdExt::cancNodo(Nodo i) else return false;

bool GrafoMatAdExt::cancArco(Nodo i, Nodo j) else return false;

void GrafoMatAdExt::adiacenti(Nodo i, ListaAdiacenti &l)

bool GrafoMatAdExt::getVisitato(Nodo i)

void GrafoMatAdExt::setVisitato(bool b, Nodo i)

bool GrafoMatAdExt::getLabel(Nodo i, tipolabel &k) else return false;

bool GrafoMatAdExt::setLabel(Nodo i, tipolabel k) else return false;

bool GrafoMatAdExt::getArchi(Nodo i, int &a) else return false;

void GrafoMatAdExt::azzeraVisitato()

tipolabel GrafoMatAdExt::labelVuota()

Il programma principale permetterà di popolare un grafo, stamparlo, visitarlo (bfs e dfs), stabilire il nodo col maggior numero di archi entranti e quello col maggior numero di archi uscenti, verificare se due nodi sono connessi, stabilire se il grafo è connesso, cancellare un nodo e tutti i suoi archi.

#include "GrafoMatAdExt.h"

#include <cstdlib>

#include <iostream>

#include "CodaPtr.h"

using namespace std;

void insLabel(tipolabel &a);

void stampaLabel(tipolabel a);

void insGrafo(GrafoMatAdExt &g) while (!((i >= 0) && (i < MAXNODI) && (!g.esisteNodo(i))));

cout << "Inserisci label per il nodo " << i << ": ";

insLabel(k);

g.insNodo(i, k);

dowhile(!((risp =='s') || (risp == 'S') || (risp == 'n') || (risp == 'N')));

}

risp = 's';

cout << endl;

cout << "Inserimento archi:" << endl;

cout << "----- ----- --------" << endl;

while ((risp == 's') || (risp =='S')) while (!((i >= 0) && (i < MAXNODI) && (g.esisteNodo(i))));

do while (!((j >= 0) && (j < MAXNODI) && (g.esisteNodo(j))));

if (g.esisteArco(i, j))

cout << "Arco (" << i << ", " << j << ") esistente" << endl;

else

g.insArco(i, j);

dowhile(!((risp =='s') || (risp == 'S') || (risp == 'n') || (risp == 'N')));

}

void stampaGrafo(GrafoMatAdExt &g)

cout << endl << endl;

cout << "Elenco archi (A):" << endl;

cout << "----- ----- -------" << endl;

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

for (int j = 0; j < MAXNODI; j++)

if (g.esisteArco(i, j))

cout << "(" << i << ", " << j << ") ";

cout << endl;

void stampaLista(ListaAdiacenti &l)

void isolaNodo(Nodo n, GrafoMatAdExt &g)

}

// Depth - First - Search : visita in profondità (a scandaglio)

void dfs(Nodo u, GrafoMatAdExt &g)

} else cout << "dfs non applicabile" << endl;

//serve per la bfs

bool copiaCoda(CodaPtr &q, CodaPtr &r)

while (!s.codaVuota())

return true;

} else return false;

//serve per la bfs

bool ricercaCoda(elemCoda a, CodaPtr &q)

}

return trovato;

//Breadth - First - Search : visita in ampiezza (ventaglio)

void bfs(Nodo u, GrafoMatAdExt &g)

p = l.succLista(p);

}

}

cout << endl;

g.azzeraVisitato();

} else cout << "bfs non applicabile" << endl;

bool nodiConnessi(Nodo u, Nodo z, GrafoMatAdExt &g)

}

g.azzeraVisitato();

} else cout << "Funzione non applicabile" << endl;

return connessi;

void maxEntranti(GrafoMatAdExt &g, Nodo &a, int &entranti)

}

entranti = max;

} else cout << "Grafo vuoto" << endl;

void maxUscenti(GrafoMatAdExt &g, Nodo &a, int &uscenti)

if(maxTemp > max)

}

uscenti = max;

} else cout << "Grafo vuoto" << endl;

bool grafoConnesso(GrafoMatAdExt &g)

}

}

} else

connesso = false;

return connesso;

int main(int argc, char *argv[])

while (!((i >= 0) && (i < MAXNODI) && (g.esisteNodo(i))));

cout << endl << "dfs G: ";

dfs(i, g);

g.azzeraVisitato();

cout << endl << "bfs G: ";

bfs(i, g);

maxEntranti(g, a, i);

cout <<endl<<"Il nodo con il maggior num di nodi entranti: "<<a<<"("<<i<< ")" << endl;

maxUscenti(g, a, i);

cout << "Il nodo con il maggior numero di nodi uscenti: " << a << " ("<<i << ")" << endl;

cout << endl << "Connessione fra due nodi:" << endl;

do while (!((i >= 0) && (i < MAXNODI) && (g.esisteNodo(i))));

do while (!((j >= 0) && (j < MAXNODI) && (g.esisteNodo(j))));

if (nodiConnessi(i, j, g))

cout << "Nodi " << i << ", " << j << " connessi" << endl;

else

cout << "Nodi " << i << ", " << j << " non connessi" << endl;

if (grafoConnesso(g))

cout << endl << "Grafo G totalmente connesso" << endl;

else

cout << endl << "Grafo G non totalmente connesso" << endl;

cout << endl << "Cancellazione di un nodo:" << endl;

do while (!((i >= 0) && (i < MAXNODI)));

if (g.esisteNodo(i)) else

cout << "Nodo " << i << "inesistente" << endl << endl;

system("PAUSE");

return 0;

7.3 GRAFO CON LISTE DI ADIACENZA

Questa realizzazione migliora le precedenti perché viene memorizzato un vettore di puntatori alle liste di adiacenza di ogni nodo. In questa maniera, alla generica posizione i del vettore troveremo tutti i nodi adiacenti ad i; per questo, verranno memorizzati solo e soltanto gli archi effettivamente presenti nel grafo, senza spreco di memoria. Inoltre, sarà possibile memorizzare anche altre informazioni, quali ad esempio il peso dell'arco.

Nome: ListaAdiacenti.h

Autore: Trullo Raffaella

Descrizione: Classe che implementa la lista di adiacenza dei nodi

#ifndef LISTAADIACENTI_H

#define LISTAADIACENTI_H

#define NIL -1

typedef struct NodoAdiacenti *posizione;

typedef struct tipo tipoelem;

typedef int Nodo;

typedef int tipoPeso;

struct tipo;

struct NodoAdiacenti;

class ListaAdiacenti;

#endif // LISTAADIACENTI_H

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* ListaAdiacenti.cpp */

#include "ListaAdiacenti.h"

#include <iostream>

#include <cstdlib>

using namespace std;

ListaAdiacenti::ListaAdiacenti()

ListaAdiacenti::~ListaAdiacenti()

void ListaAdiacenti::creaLista()

bool ListaAdiacenti::listaVuota()

posizione ListaAdiacenti::primoLista()

posizione ListaAdiacenti::predLista(posizione p)else

return NULL;

posizione ListaAdiacenti::succLista(posizione p)

bool ListaAdiacenti::fineLista(posizione p)

void ListaAdiacenti::insLista(tipoelem a, posizione p)else

bool ListaAdiacenti::cancLista(posizione p) else

delete p;

return true;

}else return false; //ERRORE!

bool ListaAdiacenti::scriviLista(tipoelem a, posizione p)else return false; //ERRORE!

bool ListaAdiacenti::leggiLista(tipoelem &a, posizione p)else return false; //ERRORE!

ListaAdiacenti &ListaAdiacenti::operator=(ListaAdiacenti &l)

p = l.primoLista();

tipoelem a;

while (!l.fineLista(p))

return *this;

posizione ListaAdiacenti::pos(int i)

return p;

}else

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

Nome: GrafoAdiacenti.h

Autore: Trullo Raffaella

Descrizione: Classe che implementa il grafo con liste di adiacenza

#ifndef GRAFOADIACENTI_H

#define GRAFOADIACENTI_H

#define MAXNODI 20

#include <iostream>

#include "ListaAdiacenti.h"

typedef structlabel;

struct NodoGrafo;

class GrafoAdiacenti;

#endif // GRAFOADIACENTI_H

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* GrafoAdiacenti.cpp */

#include "GrafoAdiacenti.h"

#include <iostream>

#include <cstdlib>

GrafoAdiacenti::GrafoAdiacenti()

GrafoAdiacenti::~GrafoAdiacenti()

}

void GrafoAdiacenti::creaGrafo()

bool GrafoAdiacenti::grafoVuoto()

return vuoto;

bool GrafoAdiacenti::esisteNodo(Nodo n)

bool GrafoAdiacenti::esisteArco(Nodo n, Nodo m)

return trovato;

} else return false;

bool GrafoAdiacenti::insNodo(Nodo n)else return false;

bool GrafoAdiacenti::insArco(Nodo n, Nodo m) else return false; 

bool GrafoAdiacenti::cancNodo(Nodo n) else return false;

} else return false;

bool GrafoAdiacenti::cancArco(Nodo n , Nodo m)

grafo[n].adiacen.cancLista(p);

return true;

} else

return false;

void GrafoAdiacenti::adiacenti(Nodo n, ListaAdiacenti &l)

bool GrafoAdiacenti::scriviNodo(Nodo n, label l) else return false;

bool GrafoAdiacenti::leggiNodo(Nodo n, label &l) else return false;

bool GrafoAdiacenti::scriviArco(Nodo n, Nodo m, tipoPeso w) else return false;

bool GrafoAdiacenti::leggiArco(Nodo n, Nodo m, tipoPeso &w) else return false;

bool GrafoAdiacenti::getVisitato(Nodo n)

void GrafoAdiacenti::setVisitato(bool b, Nodo n)

void GrafoAdiacenti::azzeraVisitato()

GrafoAdiacenti &GrafoAdiacenti::operator=(GrafoAdiacenti &g)

}

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

}

return *this;

label GrafoAdiacenti::labelVuota()

Il programma principale permetterà di popolare un grafo, stamparlo, visitarlo (bfs e dfs), stabilire il nodo col maggior numero di archi entranti e quello col maggior numero di archi uscenti, verificare se due nodi sono connessi, stabilire se il grafo è connesso, cancellare un nodo e tutti i suoi archi.

#include "ListaAdiacenti.h"

#include "GrafoAdiacenti.h"

#include "CodaPtr.h"

#include <iostream>

#include <cstdlib>

using namespace std;

void insLabel(label &a);

void stampaLabel(label a);

void insGrafo(GrafoAdiacenti &g) while ((index < 0) || (index >= MAXNODI) || (g.esisteNodo(index)));

cout << "Inserisci etichetta: ";

insLabel(a);

g.insNodo(index);

g.scriviNodo(index, a);

do while (!((risp =='s') || (risp == 'S') || (risp == 'n') || (risp == 'N')));

risp = 's';

cout << endl;

cout << "Inserimento archi:" << endl;

cout << "----- ----- --------" << endl;

while ((risp == 's') || (risp =='S')) while (!((part >= 0) && (part < MAXNODI) && (g.esisteNodo(part))));

do while (!((arr >= 0) && (arr < MAXNODI) && (g.esisteNodo(arr))));

cout << "Inserisci peso arco (" << part << ", " << arr << "): ";

cin >> w;

if (!g.insArco(part, arr))

cout << "Arco esistente" << endl;

else

g.scriviArco(part, arr, w);

do while (!((risp =='s') || (risp == 'S') || (risp == 'n') || (risp == 'N')));

}

void stampaArchi(int i, GrafoAdiacenti &g)

void stampaGrafo(GrafoAdiacenti &g)

}

cout << endl << "Insieme archi (A): " << endl;

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

} else cout << "Grafo vuoto" << endl;

void isolaNodo(Nodo n, GrafoAdiacenti &g)

}

void dfs(Nodo u, GrafoAdiacenti &g)

} else cout << "dfs non applicabile" << endl;

bool copiaCoda(CodaPtr &q, CodaPtr &r)

while (!s.codaVuota())

return true;

} else return false;

bool ricercaCoda(elemCoda a, CodaPtr &q)

}

return trovato;

void bfs(Nodo u, GrafoAdiacenti &g)

}

g.azzeraVisitato();

cout << endl;

} else cout << "bfs non applicabile" << endl;

bool nodiConnessi(Nodo u, Nodo z, GrafoAdiacenti &g)

}

g.azzeraVisitato();

} else cout << "Funzione non applicabile" << endl;

return connessi;

void maxEntranti(GrafoAdiacenti &g, label &a, int &entranti)

}

entranti = max;

} else cout << "Grafo vuoto" << endl;

void maxUscenti(GrafoAdiacenti &g, label &a, int &uscenti)

if(maxTemp > max)

}

uscenti = max;

} else cout << "Grafo vuoto" << endl;

bool grafoConnesso(GrafoAdiacenti &g)

}

}

} else

connesso = false;

return connesso;

int main(int argc, char *argv[])

while (!((i >= 0) && (i < MAXNODI) && (g.esisteNodo(i))));

cout << endl << "dfs G: ";

dfs(i, g);

g.azzeraVisitato();

cout << endl << "bfs G: ";

bfs(i, g);

maxEntranti(g, a, i);

cout << endl << "Il nodo con il maggior numero di nodi entranti: ";

stampaLabel(a);

cout << " (" << i << ")" << endl;

maxUscenti(g, a, i);

cout << "Il nodo con il maggior numero di nodi uscenti: ";

stampaLabel(a);

cout << " (" << i << ")" << endl;

cout << endl << "Connessione fra due nodi:" << endl;

do while (!((i >= 0) && (i < MAXNODI) && (g.esisteNodo(i))));

do while (!((j >= 0) && (j < MAXNODI) && (g.esisteNodo(j))));

if (nodiConnessi(i, j, g))

cout << "Nodi " << i << ", " << j << " connessi" << endl;

else

cout << "Nodi " << i << ", " << j << " non connessi" << endl;

if (grafoConnesso(g))

cout << endl << "Grafo G totalmente connesso" << endl;

else

cout << endl << "Grafo G non totalmente connesso" << endl;

cout << endl << "Cancellazione di un nodo:" << endl;

do while (!((i >= 0) && (i < MAXNODI)));

if (g.esisteNodo(i)) else

cout << "Nodo " << i << "inesistente" << endl << endl;

system("PAUSE");

return 0;

8. CODE CON PRIORITA'

Le code con priorità sono un caso particolare di insieme, sugli elementi del quale è definita una relazione "≤" di ordinamento totale, in cui è possibile inserire un nuovo elemento o estrarre l'elemento minimo. Le operazioni ammesse sono: creazione, inserimento, estrazione dell'elemento minimo (MIN) e cancellazione di quest'ultimo. In generale, le priorità degli elementi possono intendersi come proprietà associate agli elementi stessi che, talvolta, possono avere la stessa priorità. Qui di seguito sono mostrate le realizzazioni della cda con priorità mediante l'uso di alberi binari e attraverso l'utilizzo di in Heap.

8.1 CODA CON PRIORITA' CON ALBERO BINARIO

Gli elementi di una coda con priorità possono essere memorizzati nei nodi di un albero binario avente le seguenti proprietà:

L'albero è quasi perfettamente bilanciato, ovvero:

Se k è il livello massimo delle foglie, allora l'albero ha esattamente 2^k-1 nodi di livello minore di k.

Tutte le sue foglie di livello k sono addossate a sinistra.

L'albero è parzialmente ordinato, ovvero, ogni nodo contiene un elemento della coda con priorità che è maggiore di quello del padre.

Nella realizzazione si utilizza un albero binario a puntatori i cui nodi, oltre che a contenere l'elemento (quindi la sua priorità), mantengono un puntatore al padre, al figlio destro e al figlio sinistro del nodo stesso.

Nome: prioricoda.h

Autore: Trullo Raffaella

Descrizione: Classe che implementa la coda con priorita come un albero binario a puntatori.

#ifndef PRIORICODA_H

#define PRIORICODA_H

typedef int tipoelem;

typedef bool boolean;

struct nodoBin ;

typedef struct nodoBin *nodo;

class Prioricoda;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* prioricoda.cpp */

#include "prioricoda.h"

#include <cstdlib>

#include <iostream>

void Prioricoda::creaprioricoda()

tipoelem Prioricoda::min()

void Prioricoda::inserisci(tipoelem a)

else

else

if(temp->padre->destro==temp)

else

while(temp->sinistro!=NULL)

newNodo->padre=temp;

newNodo->padre->sinistro=newNodo;

}

}

}

ultimo=newNodo;

//fase 2: aggiustamento degli elementi in base alla priorità

temp=ultimo;

if(ultimo!=P)

}

return;

void Prioricoda::cancellamin()

}

else

else

if(corrente->padre->sinistro==corrente

if(corrente->padre->destro==NULL)

else

}

else

while(corrente->destro!=NULL)

ultimo->padre->sinistro=NULL;

ultimo=corrente;

delete temp;

}

}

//fase 2: aggiustamento degli elementi in base alla priorità

temp=P;

boolean trovato=false;

nodo minore;

while(!trovato)

else

if(minore->priority < store) else

} else else

else

}

}

return;

Prioricoda::Prioricoda()

Prioricoda::~Prioricoda()

Nel programma principale sono implementate le procedure e le funzioni che permettono attraverso un esempio di utilizzo di verificare il funzionamento della coda con priorità. Si permette la creazione di un vettore non ordinato e si utilizza una coda con priorità per ordinarlo in maniera crescente, utilizzando gli operatori messi a disposizione dalla struttura dati.

#include <iostream>

#include <cstdlib>

#include "prioricoda.h"

#define N 10

using namespace std;

void pc_sort(Prioricoda &c, tipoelem vettore[])

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

void printvettore(tipoelem* vettore)

void setvettore(tipoelem* vettore)

int main(int argc, char *argv[]);

8.2 CODA CON PRIORITA' CON HEAP

Gli elementi della coda con priorità possono essere disposti in un vettore P, detto heap, che può essere interpretato come un albero binario. Ciascun nodo dell'albero corrisponde ad una posizione del vettore P che memorizza gli elementi della coda con priorità. Gli elementi sono inseriti nell'heap nell'ordine in cui si incontrano visitando l'albero per livelli crescenti ed esaminando da sinistra verso destra i nodi allo stesso livello. Allora si avrà che:

P[1] è l'elemento contenuto nella radice dell'albero.

P[2i] e P[2i+1] sono gli elementi corrispondenti al figlio sinistro e al figlio destro dell'elemento P[i].

Se l'albero contiene n elementi, allora il figlio sinistro (destro) di P[i] non esiste nell'albero se e solo se 2i>n (2i+1>n). Inoltre se il figlio sinistro (destro) di P[i] esiste, allora P[2i]>P[i] (P[2i+1]>P[i]).

Nome: Nodo.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa la coda con priorità ad Heap

#ifndef PC_HEAP_H

#define PC_HEAP_H

#define H 100     //dimensione del vettore

typedef bool boolean;

typedef int tipoelem;

typedef int pos;

class Prioricoda ;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* pc_heap.cpp */

#include <iostream>

#include <cstdlib>

#include "pc_heap.h"

using namespace std;

void Prioricoda::creaprioricoda()

tipoelem Prioricoda::min()

void Prioricoda::inserisci(tipoelem a)

else

while(corrente>1 && (P[corrente-1]<P[padre-1]))

}

void Prioricoda::cancellamin()

else

}

if(P[corrente-1]>P[figlio-1])

else

}

}

Prioricoda::Prioricoda()

Prioricoda::~Prioricoda()

Nel programma principale sono implementate le procedure e le funzioni che permettono attraverso un esempio di utilizzo di verificare il funzionamento della coda con priorità. Si permette la creazione di un vettore non ordinato e si utilizza una coda con priorità per ordinarlo in maniera crescente, utilizzando gli operatori messi a disposizione dalla struttura dati.

#include <cstdlib>

#include <iostream>

#include "pc_heap.h"

#define N 10

using namespace std;

void pc_sort(Prioricoda &c, tipoelem vettore[])

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

void printvettore(tipoelem vettore[])

void setvettore(tipoelem vettore[])

int main(int argc, char *argv[])

9. MATRICE

Qui di seguito vi propongo una implementazione per il tipo di dato Matrice (nonostante molti linguaggi di programmazione abbiano già un apposito operatore.) La matrice intesa come tabella a due dimensioni, prevede due indici per l'accesso diretto ai suoi elementi. Mette a disposizione operatori per la creazione, la stampa, l'addizione e la moltiplicazione, inoltre dispone di un operatore che verifica se la matrice è unitaria.

Nome: Matrice.h

Autore: Raffaella Trullo

Descrizione: Classe che implementa la matrice.

#include "Nodo.h"

#ifndef MATRICE_H

#define MATRICE_H

#define MAXDIM 100

class Matrice ;

#endif

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* Matrice.cpp */

#include "Matrice.h"

#include <iostream>

#include <cstdlib>

using namespace std;

Matrice::Matrice();

Matrice::Matrice(int r, int c);

Matrice::~Matrice();

void Matrice::creaMatrice(int r, int c)

}

}

bool Matrice::matriceUnitaria()

}

else

}

}

}

m_uni = ok;

}

return m_uni;

Matrice Matrice::sommaMatrici(Matrice a)

}

return s;

}

else

Matrice Matrice::prodottoMatriciale(Matrice a)

}

}

return p;

else

void Matrice::Stampa()

cout << endl;

}

void Matrice::Acquisisci()while(r<0 || r>MAXDIM);

dowhile(c<0 || c>MAXDIM);

righe = r;

colonne = c;

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

}

tipoelem Matrice::getIndice(int i, int j);

void Matrice::setIndice(int i, int j, tipoelem a);

---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

/* Main.cpp */

#include <cstdlib>

#include <iostream>

#include "Matrice.h"

using namespace std;

int main(int argc, char *argv[])