PDA

Visualizza la versione completa : C++ funzioni virtuali non pure


pietrol83
06-12-2011, 10:18
ciao a tutti, sempre sulle liste, poichè creando la classe lista con le funzioni virtuali pure ho avuto problemi di compilazione, ho deciso di renderle non pure. diciamo che va un po' meglio però mi da un errore sulle funzioni virtuali. posto la classe lista (con la relativa classe derivata) e il test della lista.

lista.h


#include <iostream>
#include <stdlib.h>

using namespace std;

template<class posizione, class tipoelem>
class lista
{
public:
virtual void crealista();
virtual bool listavuota();
virtual posizione primolista();
virtual bool finelista(posizione);
virtual posizione succlista(posizione);
virtual posizione predlista(posizione);
virtual tipoelem leggilista(posizione);
virtual void scrivilista(posizione, tipoelem);
virtual void inslista(posizione, tipoelem);
virtual void canclista(posizione);

void stampalista();
void fondiordinate(lista &, lista &);
void epurazione();
void naturalmergesort();
private:
void distribuisci(lista &, lista &);
void copiacatena(posizione, lista &, posizione, lista &);
void copia(posizione, lista &, posizione, lista &, bool *);
void merge(lista &, lista &, lista &, int *);
void fondicatena(posizione, lista &, posizione, lista &, posizione, lista &);

};

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::stampalista()
{
posizione p = primolista();
while(!finelista(p))
{
cout << leggilista(p) << "\n";
p = succlista(p);
}
cout << "\n";
}


template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::fondiordinate(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B)
{
posizione pa = A.primolista();
posizione pb = B.primolista();
posizione pc = primolista();

tipoelem elem1 = A.leggilista(pa);
tipoelem elem2 = B.leggilista(pb);
while(!A.finelista(pa) && !B.finelista(pb))
{
if(elem1 <= elem2)
{
inslista(pc, elem1);
pa = A.succlista(pa);
}
else
{
inslista(pc, elem2);
pb = B.succlista(pb);
}
elem1 = A.leggilista(pa);
elem2 = B.leggilista(pb);
}
while(!A.finelista(pa))
{
inslista(pc, elem1);
pa = A.succlista(pa);
elem1 = A.leggilista(pa);
}
while(!B.finelista(pb))
{
inslista(pc, elem2);
pb = B.succlista(pb);
elem2 = B.leggilista(pb);
}
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::epurazione()
{
posizione p = primolista();
posizione q;
posizione t;
while(!finelista(p))
{
q = succlista(p);
while(!finelista(q))
{
if(leggilista(p) == leggilista(q))
{
t = succlista(q);
canclista(q);
q = t;
}
else
q = succlista(q);
}
p = succlista(p);
}
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::naturalmergesort()
{
int numerocatene;
lista<posizione, tipoelem> A, B, L;
do
{
A.crealista();
B.crealista();
distribuisci(A, B);
numerocatene = 0;
crealista();
merge(A, B, L, &numerocatene);
}while(numerocatene != 1);
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::distribuisci(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B)
{
posizione p = primolista();
posizione pa = A.primolista();
posizione pb = B.primolista();
do
{
copiacatena(p, *this, pa, A);
if(!finelista(p))
copiacatena(p, *this, pb, B);
}while(!finelista(p));
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::copiacatena(posizione p, lista<posizione, tipoelem> &L, posizione pa, lista<posizione, tipoelem> &A)
{
bool finecatena = false;
do
copia(p, L, pa, A, &finecatena);
while(!finecatena);
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::copia(posizione p, lista<posizione, tipoelem> &L, posizione pa, lista<posizione, tipoelem> &A, bool *finecatena)
{
bool esito = *finecatena;
finecatena = &esito;
tipoelem elemento = leggilista(p);
A.inslista(pa, elemento);
p = succlista(p);
pa = succlista(pa);
if(finelista(p))
esito = true;
else
esito = (elemento > leggilista(p));
finecatena = &esito;
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::merge(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B, lista<posizione, tipoelem> &L, int *numcatene)
{
posizione p = primolista();
posizione pa = A.primolista();
posizione pb = B.primolista();

while(!A.finelista(pa) && !B.finelista(pb))
{
fondicatena(pa, A, pb, B, p, L);
numcatene++;
}
while(!A.finelista(pa))
{
copiacatena(pa, A, p, L);
numcatene++;
}
while(!B.finelista(pb))
{
copiacatena(pb, B, p, L);
numcatene++;
}
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::fondicatena(posizione pa, lista<posizione, tipoelem> &A, posizione pb, lista<posizione, tipoelem> &B, posizione p, lista<posizione, tipoelem> &L)
{
bool finecatena = false;
do
{
if(A.leggilista(pa) < B.leggilista(pb))
{
copia(pa, A, p, *this, &finecatena);
if(finecatena)
copiacatena(pb, B, p, *this);
}
else
{
copia(pb, B, p, *this, &finecatena);
if(finecatena)
copiacatena(pa, A, p, *this);
}
}while(finecatena);
}


listap.h


#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include "lista.h"
#include "nodop.h"

using namespace std;

template<class tipoelem>
class listap : public lista<nodop<tipoelem> *, tipoelem>
{
public:
typedef nodop<tipoelem> *posizione;
listap(); //costruttore di default
void crealista(); //crea la lista vuota
bool listavuota(); //stabilisce se la lista è vuota o meno
posizione primolista(); //restituisce la posizione del primo elemento della lista
bool finelista(posizione); //stabilisce se il nodo è l'ultimo della lista
tipoelem leggilista(posizione); //restituisce l'elemento della posizione specificata
posizione succlista(posizione); //restituisce la posizione del nodo successivo
posizione predlista(posizione); //restituisce la posizione del nodo precedente
void scrivilista(posizione, tipoelem);//scrive l'elemtno nel nodo specificato dalla posizione
void inslista(posizione, tipoelem); //inserisce un nodo e scrive l'elemento nella posizione specificata
void canclista(posizione); //elimina il nodo nella posizione specificata
private:
nodop<tipoelem> cella; //nodo della lista (nodo sentinella)
};

template<class tipoelem>
listap<tipoelem>::listap()
{
crealista(); //il costruttore invoca il metodo crealista
}

template<class tipoelem>
void listap<tipoelem>::crealista()
{
cella.setprec(&cella);
cella.setsuc(&cella);
cella.setelem(0);
}

template<class tipoelem>
bool listap<tipoelem>::listavuota()
{
return((cella.getprec() == &cella) && (cella.getsuc() == &cella));
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::primolista()
{
return(cella.getsuc());
}

template<class tipoelem>
bool listap<tipoelem>::finelista(typename listap<tipoelem>::posizione pos)
{
return(pos == &cella);
}

template<class tipoelem>
tipoelem listap<tipoelem>::leggilista(typename listap<tipoelem>::posizione pos)
{
return(pos->getelem());
}

template<class tipoelem>
void listap<tipoelem>::scrivilista(typename listap<tipoelem>::posizione pos, tipoelem elem)
{
pos->setelem(elem);
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::succlista(typename listap<tipoelem>::posizione pos)
{
return(pos->getsuc());
}

template<class tipoelem>
typename listap<tipoelem>::posizione listap<tipoelem>::predlista(typename listap<tipoelem>::posizione pos)
{
return(pos->getprec());
}

template<class tipoelem>
void listap<tipoelem>::inslista(typename listap<tipoelem>::posizione pos, tipoelem elem)
{
posizione temp = new nodop<tipoelem>;

temp->setprec(pos->getprec());
temp->setsuc(pos);
(pos->getprec())->setsuc(temp);
pos->setprec(temp);
temp->setelem(elem);
pos = temp;
}

template<class tipoelem>
void listap<tipoelem>::canclista(typename listap<tipoelem>::posizione pos)
{
posizione temp = pos;
(pos->getsuc())->setprec(pos->getprec());
(pos->getprec())->setsuc(pos->getsuc());
pos = pos->getsuc();
delete temp;
}


testlista.cpp


#include "listap.h"
#include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{
listap<int> list, list2, list3, list4;
listap<int>::posizione pos = list.primolista();
listap<int>::posizione pos2 = list2.primolista();
listap<int>::posizione pos4 = list4.primolista();
int k;

for(int i = 0; i < 10; i++)
{
list.inslista(pos, (100 - (i * 10)));
pos = list.primolista();
}

for(int i = 0; i < 10; i++)
{
list2.inslista(pos2, (50 - (i * 5)));
pos2 = list2.primolista();
}

list.stampalista();
list2.stampalista();

cout << "\n\n";

list3.fondiordinate(list, list2);
list3.stampalista();
cout << "\n\n";
list3.epurazione();
list3.stampalista();

cout << "\n\n";
for(int i = 0; i < 10; i++)
{
cin >> k;
list4.inslista(pos4, k);
pos2 = list2.primolista();
}
list4.stampalista();
list4.naturalmergesort();
cout << "\n\n";
list4.stampalista();

system("pause");
return 0;
}


l'errore è il seguente:

[Linker error] undefined reference to `lista<nodop<int>*, int>::scrivilista(nodop<int>*, int)'


in pratica mi dà una lista di quell'errore per ogni metodo virtuale. cosa c'è che non va?
eppure i metodi virtuali vengono implementati nella classe derivata!!!

shodan
06-12-2011, 12:36
Originariamente inviato da pietrol83
eppure i metodi virtuali vengono implementati nella classe derivata!!!

Se i metodi di lista non sono virtuali puri sei obbligato a fornirne comunque un'implementazione. Questo perché non è obbligatorio ridefinire tale funzione in una classe derivata, come succederebbe se il metodo fosse virtuale puro.

In pratica togliendo i metodi virtuali puri non freghi il compilatore.

pietrol83
06-12-2011, 12:58
ma io inizialmente ho provato con i metodi virtuali puri però poi non mi è stato possibile implementare i metodi private di cui si serve il metodo naturalmergesort() perchè non è possibile istanziare oggietti della classe lista, il che è normale perchè una classe astratta non può essere istanziata. come posso risolvere il problema?

pietrol83
06-12-2011, 13:08
ora ho provato a rendere i metodi di lista come virtuali puri e a utilizzare i riferimenti a lista anzichè istanziare gli oggetti lista. il test viene compilato ma va in crash.

ho apportato le seguenti modifiche nel file lista.h (le modifiche sono segnate in rosso).

lista.h


#include <iostream>
#include <stdlib.h>

using namespace std;

template<class posizione, class tipoelem>
class lista
{
public:
virtual void crealista() = 0;
virtual bool listavuota() = 0;
virtual posizione primolista() = 0;
virtual bool finelista(posizione) = 0;
virtual posizione succlista(posizione) = 0;
virtual posizione predlista(posizione) = 0;
virtual tipoelem leggilista(posizione) = 0;
virtual void scrivilista(posizione, tipoelem) = 0;
virtual void inslista(posizione, tipoelem) = 0;
virtual void canclista(posizione) = 0;

void stampalista();
void fondiordinate(lista &, lista &);
void epurazione();
void naturalmergesort();
private:
void distribuisci(lista &, lista &);
void copiacatena(posizione, lista &, posizione, lista &);
void copia(posizione, lista &, posizione, lista &, bool *);
void merge(lista &, lista &, lista &, int *);
void fondicatena(posizione, lista &, posizione, lista &, posizione, lista &);

};

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::stampalista()
{
posizione p = primolista();
while(!finelista(p))
{
cout << leggilista(p) << "\n";
p = succlista(p);
}
cout << "\n";
}


template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::fondiordinate(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B)
{
posizione pa = A.primolista();
posizione pb = B.primolista();
posizione pc = primolista();

tipoelem elem1 = A.leggilista(pa);
tipoelem elem2 = B.leggilista(pb);
while(!A.finelista(pa) && !B.finelista(pb))
{
if(elem1 <= elem2)
{
inslista(pc, elem1);
pa = A.succlista(pa);
}
else
{
inslista(pc, elem2);
pb = B.succlista(pb);
}
elem1 = A.leggilista(pa);
elem2 = B.leggilista(pb);
}
while(!A.finelista(pa))
{
inslista(pc, elem1);
pa = A.succlista(pa);
elem1 = A.leggilista(pa);
}
while(!B.finelista(pb))
{
inslista(pc, elem2);
pb = B.succlista(pb);
elem2 = B.leggilista(pb);
}
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::epurazione()
{
posizione p = primolista();
posizione q;
posizione t;
while(!finelista(p))
{
q = succlista(p);
while(!finelista(q))
{
if(leggilista(p) == leggilista(q))
{
t = succlista(q);
canclista(q);
q = t;
}
else
q = succlista(q);
}
p = succlista(p);
}
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::naturalmergesort()
{
int numerocatene;
lista<posizione, tipoelem> *A, *B, *L;
do
{
A->crealista();
B->crealista();
distribuisci(*A, *B);
numerocatene = 0;
crealista();
merge(*A, *B, *L, &numerocatene);
}while(numerocatene != 1);
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::distribuisci(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B)
{
posizione p = primolista();
posizione pa = A.primolista();
posizione pb = B.primolista();
do
{
copiacatena(p, *this, pa, A);
if(!finelista(p))
copiacatena(p, *this, pb, B);
}while(!finelista(p));
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::copiacatena(posizione p, lista<posizione, tipoelem> &L, posizione pa, lista<posizione, tipoelem> &A)
{
bool finecatena = false;
do
copia(p, L, pa, A, &finecatena);
while(!finecatena);
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::copia(posizione p, lista<posizione, tipoelem> &L, posizione pa, lista<posizione, tipoelem> &A, bool *finecatena)
{
bool esito = *finecatena;
finecatena = &esito;
tipoelem elemento = leggilista(p);
A.inslista(pa, elemento);
p = succlista(p);
pa = succlista(pa);
if(finelista(p))
esito = true;
else
esito = (elemento > leggilista(p));
finecatena = &esito;
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::merge(lista<posizione, tipoelem> &A, lista<posizione, tipoelem> &B, lista<posizione, tipoelem> &L, int *numcatene)
{
posizione p = primolista();
posizione pa = A.primolista();
posizione pb = B.primolista();

while(!A.finelista(pa) && !B.finelista(pb))
{
fondicatena(pa, A, pb, B, p, L);
numcatene++;
}
while(!A.finelista(pa))
{
copiacatena(pa, A, p, L);
numcatene++;
}
while(!B.finelista(pb))
{
copiacatena(pb, B, p, L);
numcatene++;
}
}

template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::fondicatena(posizione pa, lista<posizione, tipoelem> &A, posizione pb, lista<posizione, tipoelem> &B, posizione p, lista<posizione, tipoelem> &L)
{
bool finecatena = false;
do
{
if(A.leggilista(pa) < B.leggilista(pb))
{
copia(pa, A, p, *this, &finecatena);
if(finecatena)
copiacatena(pb, B, p, *this);
}
else
{
copia(pb, B, p, *this, &finecatena);
if(finecatena)
copiacatena(pa, A, p, *this);
}
}while(finecatena);
}

shodan
06-12-2011, 17:41
Originariamente inviato da pietrol83
...però poi non mi è stato possibile implementare i metodi private di cui si serve il metodo naturalmergesort() perchè non è possibile istanziare oggetti della classe lista...

Basta cambiare modificatore: protected invece di private. Non vedo il problema.

Per le righe in rosso del metodo mergesort.
Ti sei accorto di usare pointer che puntano alla luna invece che a una istanza dinamica di lista?
(Che comunque non puoi avere visto che lista ha metodi puri?)

Cambiando il modificatore d'accesso e derivando la classe come avevi fatto prima avrai:


template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::naturalmergesort()
{
int numerocatene;
lista<posizione, tipoelem> *A, *B, *L;

A = new listap<quel che è> ;
B = new listap<quel che è> ;
L = new listap<quel che è> ;

do
{
A->crealista();
B->crealista();
distribuisci(*A, *B);
numerocatene = 0;
crealista();
merge(*A, *B, *L, &numerocatene);
}while(numerocatene != 1);

// eventuali delete di A, B, L

}

pietrol83
07-12-2011, 00:44
non posso mettere new listap<quel che è> perchè dalla classe base ereditano tre tipi di lista: con puntatori, vettori e cursori.
come posso fare??

per quanto riguarda i pointer, non ho capito a cosa ti riferisci...

oregon
07-12-2011, 10:13
Originariamente inviato da pietrol83
per quanto riguarda i pointer, non ho capito a cosa ti riferisci...

Al fatto che usi dei puntatori come

lista<posizione, tipoelem> *A, *B, *L;

direttamente così

A->crealista();

senza avere fatto la new per istanziare l'oggetto.

pietrol83
07-12-2011, 10:19
ho fatto:
A = new lista<posizione, tipoelem>
e la stessa cosa per B e L. questo è l'errore:

114 C:\Dev-Cpp\esercizi\Lista\lista.h cannot allocate an object of type `lista<nodop<int>*, int>'

mi è stato consigliato di fare:
A = new listap<quello che è> ma nn posso farlo poichè dalla classe lista.h ereditano altri due tipi di liste, con vettore e con cursori, le quali ereditano anche il metodo naturalmergesort.

shodan
07-12-2011, 13:02
Originariamente inviato da pietrol83
ho fatto:
A = new lista<posizione, tipoelem>
e la stessa cosa per B e L. questo è l'errore:

114 C:\Dev-Cpp\esercizi\Lista\lista.h cannot allocate an object of type `lista<nodop<int>*, int>'

Come annunciato prima:


(Che comunque non puoi avere visto che lista ha metodi puri.)




mi è stato consigliato di fare:

Non è un consiglio: è un obbligo del compilatore.



le quali ereditano anche il metodo naturalmergesort.

Se non devi lavorare con la lista corrente sarebbe meglio che naturalMergeSort non fosse una funzione membro (imho). In ogni caso dovresti cambiare prototipo in:


::naturalmergesort(lista<posizione, tipoelem>& A, lista<posizione, tipoelem>& B, lista<posizione, tipoelem>& L)

dove A,B,L saranno classi concrete (derivate da lista).
Invocando solo i metodi polimorfici di quelle classi all'interno di naturalMergeSort(), non importerà più come sia implementata la loro struttura dati interna (cursori, vettori, altro), ma solo l'interfaccia esportata.



template<class posizione, class tipoelem>
void lista<posizione, tipoelem>::naturalmergesort(
lista<posizione, tipoelem>& A,
lista<posizione, tipoelem>& B,
lista<posizione, tipoelem>& L,
) {
int numerocatene;
do
{
A.crealista();
B.crealista();
distribuisci(A, B);
numerocatene = 0;
crealista();
merge(A, B, L, &numerocatene);
}while(numerocatene != 1);
}

pietrol83
08-12-2011, 09:38
ok proverò a fare così, ma in questo modo devo istanziare due lista in più nel main. A e B dovrebbero servire per raccogliere le catene di L.

Loading