Salve a tutti, non riesco a capire questi errori di compilazione a cosa siano dovuti:
"Dizionario.h: No such file or directory.
Coda.h: No such file or directory
AlberoBinarioDi Ricerca.h: No such file or directory "
[ CODE]
/************************************************** ****************************\
*
* File: AlberoBinarioDiRicerca.cpp
\************************************************* *****************************/
#ifndef DIZIONARIO_H
#define DIZIONARIO_H
namespace asd {
/*
Figura 3.1 e Figura 6.1
Il tipo di dato Dizionario.
*/
template<class Elem, class Chiave>
class Dizionario
{
/* dati:
un insieme S di coppie (elem,chiave) */
public: // operazioni
virtual ~Dizionario() {}
// void* insert(Elem& e, Chiave& k);
// void delete_(void*);
// Elem search(Chiave& k) const;
};
} // namespace asd
#endif /* _DIZIONARIO_H */
////////////////////////////////////////////////////////////////////////////
#ifndef CODA_H
#define CODA_H
#include <list>
namespace asd {
/*
Figura 3.7
Il tipo di dato Coda.
*/
template<class Elem>
class Coda
{
private:
std::list<Elem> S;
public:
Coda() {}
~Coda() {};
bool isEmpty() const;
void enqueue(const Elem& e);
Elem dequeue();
Elem first() const;
};
/* PUBLIC */
/*
Restituisce true se S e' vuota, e false altrimenti.
*/
template<class Elem>
bool Coda<Elem>::isEmpty() const
{
return S.empty();
}
/*
Aggiunge e come ultimo elemento di S.
*/
template<class Elem>
void Coda<Elem>::enqueue(const Elem& e)
{
S.push_back(e);
}
/*
Toglie da S il primo elemento e lo restituisce.
*/
template<class Elem>
Elem Coda<Elem>::dequeue()
{
Elem e = S.front();
S.pop_front();
return e;
}
/*
Restituisce il primo elemento di S (senza toglierlo da S).
*/
template<class Elem>
Elem Coda<Elem>::first() const
{
return S.front();
}
} // namespace asd
#endif /* _CODA_H */
//////////////////////////////////////////////////////////////
#ifndef ALBEROBINARIODIRICERCA_H
#define ALBEROBINARIODIRICERCA_H
#include <iostream>
#include "Dizionario.h"
#include "Coda.h"
#include <vector>
namespace asd {
template<class Elem, class Chiave>
class AlberoBinarioDiRicerca;
template<class Elem, class Chiave>
class AlberoAVL;
template<class Elem, class Chiave>
class AlberoSplay;
/*
Nodo di un albero binario di ricerca,
implementato con una rappresentazione collegata basata su puntatori ai figli.
*/
template<class Elem, class Chiave>
class nodo_ricerca
{
protected:
Elem elem;
Chiave chiave;
nodo_ricerca* padre;
nodo_ricerca* figlio_sin;
nodo_ricerca* figlio_des;
public:
nodo_ricerca(Elem elem_ = Elem(), Chiave chiave_ = Chiave(),
nodo_ricerca* padre_ = 0,
nodo_ricerca* figlio_sin_ = 0,
nodo_ricerca* figlio_des_ = 0)
: elem(elem_)
, chiave(chiave_)
, padre(padre_)
, figlio_sin(figlio_sin_)
, figlio_des(figlio_des_)
{}
nodo_ricerca(const nodo_ricerca& n)
: elem(n.elem)
, chiave(n.chiave)
, padre(n.padre)
, figlio_sin(n.figlio_sin)
, figlio_des(n.figlio_des)
{}
~nodo_ricerca()
{}
inline Chiave getChiave() const { return chiave; }
inline Elem getElem() const { return elem; }
friend class AlberoBinarioDiRicerca<Elem, Chiave>;
friend class AlberoAVL<Elem, Chiave>;
friend class AlberoSplay<Elem, Chiave>;
};
/*
Figura 6.3
Realizzazione di un dizionario mediante un albero binario di ricerca,
implementato con una rappresentazione collegata basata su puntatori ai figli.
*/
template<class Elem, class Chiave>
class AlberoBinarioDiRicerca
: public Dizionario<Elem, Chiave>
{
protected: // dati
nodo_ricerca<Elem, Chiave>* radice;
unsigned itemsCount;
public: // operazioni
AlberoBinarioDiRicerca(nodo_ricerca<Elem, Chiave>* radice_ = 0);
AlberoBinarioDiRicerca(const std::vector< std:air<Elem, Chiave> >& vec);
AlberoBinarioDiRicerca(const AlberoBinarioDiRicerca<Elem, Chiave>& t);
~AlberoBinarioDiRicerca();
Elem search(const Chiave& k) const;
nodo_ricerca<Elem, Chiave>* insert(const Elem& e, const Chiave& k);
void delete_(nodo_ricerca<Elem, Chiave>* u);
unsigned getItemsCount() const;
bool isEmpty() const;
void stampa () const;
protected: // procedure interne
nodo_ricerca<Elem, Chiave>* max(nodo_ricerca<Elem, Chiave>* u);
nodo_ricerca<Elem, Chiave>* pred(nodo_ricerca<Elem, Chiave>* u);
void distruggiSottoalbero(nodo_ricerca<Elem, Chiave>* v);
private:
typedef typename std::vector< std:air<Elem, Chiave> >::const_iterator vec_iterator;
};
/* PUBLIC */
/*
Costruttore di default.
*/
template<class Elem, class Chiave>
AlberoBinarioDiRicerca<Elem, Chiave>::AlberoBinarioDiRicerca(nodo_ricerca<Elem, Chiave>* radice_)
: radice(radice_)
, itemsCount(0)
{}
/*
Costruttore per la creazione di un nuovo albero binario di ricerca non vuoto.
*/
template<class Elem, class Chiave>
AlberoBinarioDiRicerca<Elem, Chiave>::AlberoBinarioDiRicerca(const std::vector< std:air<Elem, Chiave> >& vec)
: radice(0)
, itemsCount(0)
{
for (vec_iterator it = vec.begin(); it != vec.end(); ++it) {
insert((*it).first, (*it).second);
}
}
/*
Costruttore di copia.
*/
template<class Elem, class Chiave>
AlberoBinarioDiRicerca<Elem, Chiave>::AlberoBinarioDiRicerca(const AlberoBinarioDiRicerca<Elem, Chiave>& t)
: radice(t)
{}
/*
Distruttore.
*/
template<class Elem, class Chiave>
AlberoBinarioDiRicerca<Elem, Chiave>::~AlberoBinarioDiRicerca()
{
distruggiSottoalbero(radice);
}
/*
Figura 6.4
Ricerca dell'elemento associato a una data chiave.
*/
template<class Elem, class Chiave>
Elem AlberoBinarioDiRicerca<Elem, Chiave>::search(const Chiave& k) const
{
nodo_ricerca<Elem, Chiave>* v = radice;
while (v != 0) {
if (k == v->chiave) return v->elem;
else if (k < v->chiave) v = v->figlio_sin;
else v = v->figlio_des;
}
return 0;
}
/*
Inserimento di un elemento e di una chiave ad esso associata.
Restituisce un puntatore al nodo inserito.
*/
template<class Elem, class Chiave>
nodo_ricerca<Elem, Chiave>* AlberoBinarioDiRicerca<Elem, Chiave>::insert(const Elem& e,
const Chiave& k)
{
/* Passo 1. Cerca il nodo v che diventera' genitore del nuovo nodo. */
nodo_ricerca<Elem, Chiave>* v = radice;
while (v != 0) {
if (k < v->chiave) {
if (v->figlio_sin == 0) break;
v = v->figlio_sin;
}
else /* if (k >= v->chiave) */ {
if (v->figlio_des == 0) break;
v = v->figlio_des;
}
}
/* Passo 2. Crea un nuovo nodo u con elemento e e chiave k
ed appendilo come figlio sinistro o destro di v
rispettando la proprieta' di ricerca. */
nodo_ricerca<Elem, Chiave>* u = new nodo_ricerca<Elem, Chiave>(e, k, v);
if (v == 0) radice = u;
else {
if (k < v->chiave) v->figlio_sin = u;
else /* if (k >= v->chiave) */ v->figlio_des = u;
}
return u;
}
/*
Cancellazione di un elemento dato un nodo.
*/
template<class Elem, class Chiave>
void AlberoBinarioDiRicerca<Elem, Chiave>::delete_(nodo_ricerca<Elem, Chiave>* u)
{
if (u->figlio_sin == 0 && u->figlio_des == 0) { /* u e' una foglia */
if (u->padre) {
if ((u->padre)->figlio_sin == u) (u->padre)->figlio_sin = 0;
else /*if ((u->padre)->figlio_des == u)*/ (u->padre)->figlio_des = 0;
}
delete u;
}
else if (u->figlio_sin == 0 || u->figlio_des == 0) { /* u ha un unico figlio */
nodo_ricerca<Elem, Chiave>* v; /* sia v l'unico figlio di u */
if (u->figlio_sin != 0) v = u->figlio_sin;
else /*if (u->figlio_des != 0)*/ v = u->figlio_des;
nodo_ricerca<Elem, Chiave>* w = u->padre; /* sia w il padre di u */
if (u == radice) radice = v;
else {
v->padre = u->padre;
if (w->figlio_sin == u) w->figlio_sin = v;
else /*if (w->figlio_des == u)*/ w->figlio_des = v;
delete u;
}
}
else { /* u ha due figli */
nodo_ricerca<Elem, Chiave>* v = pred(u); /* sia v il predecessore di u */
u->chiave = v->chiave;
u->elem = v->elem;
if ((v->padre)->figlio_sin == v) (v->padre)->figlio_sin = 0;
else /*if ((v->padre)->figlio_des == v)*/ (v->padre)->figlio_des = 0;
v->padre = 0;
delete v;
}
}
/*
Restituisce il numero di elementi dell'albero binario di ricerca
*/
template<class Elem, class Chiave>
unsigned AlberoBinarioDiRicerca<Elem, Chiave>::getItemsCount() const
{
return itemsCount;
}
/*
Verifica in tempo costante se un albero di ricerca e' vuoto.
*/
template<class Elem, class Chiave>
bool AlberoBinarioDiRicerca<Elem, Chiave>::isEmpty() const
{
return (radice == 0);
}
/*
Stampa l'albero binario di ricerca, effettuando una visita BFS.
*/
template<class Elem, class Chiave>
void AlberoBinarioDiRicerca<Elem, Chiave>::stampa() const
{
nodo_ricerca<Elem, Chiave>* u;
Coda<nodo_ricerca<Elem, Chiave>*> C;
C.enqueue(radice);
while (!C.isEmpty()) {
u = C.dequeue();
if (u != 0) {
std::cout << u->chiave;
if (u->padre) std::cout << "(->" << (u->padre)->chiave << ")";
std::cout << " ";
C.enqueue(u->figlio_sin);
C.enqueue(u->figlio_des);
}
}
}
/* PROTECTED */
template<class Elem, class Chiave>
nodo_ricerca<Elem, Chiave>* AlberoBinarioDiRicerca<Elem, Chiave>::max(nodo_ricerca<Elem, Chiave>* u)
{
nodo_ricerca<Elem, Chiave>* v = u;
while (v->figlio_des != 0) {
v = v->figlio_des;
}
return v;
}
template<class Elem, class Chiave>
nodo_ricerca<Elem, Chiave>* AlberoBinarioDiRicerca<Elem, Chiave>:red(nodo_ricerca<Elem, Chiave>* u)
{
if (u->figlio_sin != 0) {
return max(u->figlio_sin);
}
while (u->padre != 0 && u == (u->padre)->figlio_sin) {
u = u->padre;
}
return u->padre;
}
template<class Elem, class Chiave>
void AlberoBinarioDiRicerca<Elem, Chiave>::distruggiSottoalbero(nodo_ricerca<Elem, Chiave>* v)
{
if (v) {
distruggiSottoalbero(v->figlio_sin);
distruggiSottoalbero(v->figlio_des);
delete v;
}
}
} // namespace asd
#endif /* _ALBEROBINARIODIRICERCA_H */
/////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
#include "AlberoBinarioDiRicerca.h"
using std::cout;
using std::endl;
using std::vector;
using asd::AlberoBinarioDiRicerca;
using asd::nodo_ricerca;
template<class Elem, class Chiave>
void stampa(nodo_ricerca<Elem, Chiave>* v)
{
cout << v->getChiave() << " ";
}
int main()
{
cout << "\nSto creando l'ALBERO BINARIO DI RICERCA di figura 6.2(a)\n"
<< " \n"
<< " 49 \n"
<< " / \\ \n"
<< " 22 82 \n"
<< " / / \\ \n"
<< " 17 57 88 \n"
<< " \\ \\ \n"
<< " 20 94 \n"
<< " / \n"
<< " 91 \n"
<< " \n";
AlberoBinarioDiRicerca<char*, int> albero;
vector< nodo_ricerca<char*, int>* > v1(6);
/* INSERT */
v1[0] = albero.insert("quarantanove", 49);
v1[1] = albero.insert("ventidue", 22);
v1[2] = albero.insert("ottantadue", 82);
v1[3] = albero.insert("diciassette", 17);
v1[4] = albero.insert("cinquantasette", 57);
v1[5] = albero.insert("ottantotto", 88);
v1[6] = albero.insert("venti", 20);
v1[7] = albero.insert("novantaquattro", 94);
v1[8] = albero.insert("novantuno", 91);
cout << "\nALBERO BINARIO DI RICERCA\n";
cout << "visitaBFS: ";
albero.stampa();
cout << endl;
/* SEARCH */
cout << "\nL'elemento con chiave '57' e': " << albero.search(57) << endl;
/* DELETE */
cout << "\nSto rimuovendo il seguente nodo: (" << v1[2]->getElem() << ", " << v1[2]->getChiave() << ")\n";
albero.delete_( v1[2] );
cout << "\nALBERO BINARIO DI RICERCA\n";
cout << "visitaBFS: ";
albero.stampa();
cout << endl;
cout << " \n"
<< " 49 \n"
<< " / \\ \n"
<< " 22 57 \n"
<< " / \\ \n"
<< " 17 88 \n"
<< " \\ \\ \n"
<< " 20 94 \n"
<< " / \n"
<< " 91 \n"
<< " \n";
cout << endl;
system("PAUSE");
return 0;
}
[/ CODE]
Un' altra domanda: Se separo le classi AlberoBinarioDi Ricerca, Dizionario e Coda dal main in file separati, quando vado poi a chiedere al compilatore di compilare il file.cpp sembra non trovare i file header (nonostante nel main inserisca gli "include"), cosa sbaglio?
Grazie a presto
Rispondi quotando
