Índex
Miguel A. Almarza
Departament d'Informàtica
IES Mare de Deu de la Merce
       

 
Capítol 7

Funcions i classes genèriques.

  1. Funcions genèriques.
  2. Classes genèriques.
  3. Una Pila amb plantilles de classes.
    1. Definició de pila.
    2. Implementació de la classe genèrica o plantilla de pila.
    3. Ús de la classe Pila
      1. Ús de la classe Pila amb nobres enters
      2. Ús de la classe Pila amb estructures
      3. Ús de la classe Pila amb objectes
  4. Exercicis.

7.1. Funcions genèriques.

Les funcions genèriques són funcions en les que la seva declaració inclou un tipus genèric de dades pel que fa als paràmetres rebuts i al paràmetre tornat per la funció.

La concrecció d'aquest tipus de dades es fa en el moment de fer la crida a aquesta funció amb uns tipus de dades determinats.

Segons veiem a l'exemple següent la funció Canvia està declarada en la forma següent:

template <class tipus> Canvia(tipus &x, tipus &y)

i al llarg del seu codi es fa referència al tipus genèric de dades am la paraula tipus.

Quan fem la crida de la funció,

int i=3, j=5;
Canvia(i,j); 		             float x1=3.2, y1=8.1;
Canvia(x1,y1);

el compilador crea la funció adient als tipus de dades amb els que cridem la funció.

Funció genèrica Canvia.
Rep dades d'un tipus indeterminats.		 Funció genèrica Menor
Rep i torna dades d'un tipus indeterminats.		 
#include <iostream.h>

template <class tipus> Canvia(tipus &x, tipus &y)
{
    tipus z;
    z = x;
    x = y;
    y = z;
}

main()
{
    int i=3, j=5;
    Canvia(i,j);
    cout << "i=" << i << endl;
    cout << "j=" << j << endl;

    float x1=3.2, y1=8.1;
    Canvia(x1,y1);
    cout << "x1=" << x1 << endl;
    cout << "y1=" << y1 << endl;
}

#include <iostream.h>

template <class Tipus>
Tipus Menor(Tipus x, Tipus y)
{
    return (x < y ? x : y);
}

main()
{
    cout << Menor(3,1) << endl;
    cout << Menor(3.23,18.1) << endl;
}


Funció genèrica Canvia.
Aplicada a objectes de tipus Complex.		 Funció genèrica Suma.
Rep dos tipus de dades indetermitats. 
class Complex
{
    float a,b;
public:
  ...............................
};

template <class tipus> Canvia(tipus &x, tipus &y)
{
    tipus z;
    z = x;
    x = y;
    y = z;
}

main()
{
    clrscr();
    Complex z1(2,2), z2(3,5);

    Canvia(z1,z2);

    cout << "z1=" << z1 << endl;
    cout << "z2=" << z2 << endl;
}

#include <iostream.h>

template <class Tipus1, class Tipus2>
Tipus2 Suma(Tipus1 x, Tipus2 y)
{
    return x + y;
}

main()
{
    int i=5, j=8;
    cout << Suma(i,j) << endl;

    int x=5; float y=13.45;
    cout << Suma(x,y) << endl;
}


Queda clar aquestes funcions genèriques són en realitat plantilles per a funcions. Quan posem template estem indicant al compilador que té una plantilla per a una funció.

En el lloc del codi on fem la crida el compilador defineix la funció descrita en la plantilla segons els tipus concrets de dades que li posem en la crida. És aquesta funció la que el compilador inclou en el codi.

7.2. Classes genèriques.

Les classes genèriques o plantilles de classes son classes en les que podem donar un tipus de dades genèric, sense especificar, i que es concretarà quan farem la declaració d'un objecte d'aquesta classes.

La forma general de la declaració d'una classe d'aquest tipus és:

template <class TipusDada> class NomClasse

on TipusDada és el nom de la dada genèrica que hem d'utilitzar al llarg del codi de la classe per referir-nos a aquest tipus de dada.

Per declarar un objecte d'aquesta classe hem de fer us d'una sintaxi com la següent:

NomClase<Tipus concret de dada> NomObjecte

on Tipus concret de dada és un tipus vàlid de C++ des de les dades simples com int i float, fins a estructures o classes.

Examinem l'exemple següent:

Declarem i escrivim una plantilla de classe anomenada Vector. Després fem ús d'aquesta plantilla per fer tres vectors diferents:

  1. Un vector de nombres enters al primer exemple.
  2. Altre vector ara d'estructures al segon exemple.
  3. Un vector d'objectes de tipus Complex al tercer exemple.
Classe genèrica vector.1.-Vector de nombres enters. 
#include <iostream.h>

template <class TipusDades>
class Vector
{
    TipusDades * V;
    int Longitud;
public:
    Vector(int n)
    {
        V = new TipusDades[n];
        Longitud = n;
    }
    ~Vector() { delete V;};
    TipusDades & operator[](int i)
    {
        if (i >= 0 && i < Longitud) return V[i];
    }
};
main()
{
    Vector<int> v1(10);
    int i;
    for (i=0;i<10;i++) v1[i]=i;

    for (i=0;i<10;i++) cout << v1[i] << "  ";
    cout << endl;
}
2.Vector d'estructures. 
main()
{
    struct Fitxa
    {
        char Nom[45];
        char Telefon[15];
    };

    Vector<Fitxa> Agenda(10);
    cout << "Introdueix l'element 3 de l'agenda" << endl;
    cout << "Nom: "; cin >> Agenda[3].Nom;
    cout << "Telefon: "; cin >> Agenda[3].Telefon;

    cout << "Has posat a la posici¢ 3 del vector " << endl;
    cout << "Nom: " << Agenda[3].Nom << endl;
    cout << "Telefon: " << Agenda[3].Telefon << endl;
}
3.-Vector d'objectes Complex. 
class Complex
{
    float a,b;
public:
    Complex(float a=0, float b=0)
    {
        this->a=a;
        this->b=b;
    }
    friend ostream &operator<<(ostream &flux, Complex z)
    {
        flux << z.a;
        flux.setf(ios::showpos);
        flux << z.b << 'i';
        flux.unsetf(ios::showpos);
        return flux;
    }
    friend istream &operator>>(istream &flux, Complex &z)
    {
        cout << "Dades d'un complex" << endl;
        cout << "Introdueix la part real: ";
        flux >> z.a;
        cout << "Introdueix la part imagin…ria: ";
        flux >> z.b;
        return flux;
    }
}

main()
{
    Vector<Complex> v1(10);
    int i;
    for (i=0;i<5;i++)
    {
        cout << "Element i = " << i << endl;
        cin >> v1[i];
    }

    for (i=0;i<10;i++) cout << v1[i] << "  ";
    cout << endl;
}

7.3 Una Pila amb plantilles de classes.

Les estructures de dades són les millors candidates per crear plantilles de classes car d'aquesta manera no haurem de una implementació de l'estructura per a cada tipus de dades.

Així ens fixem en la pila com a exemple d'implementació d'una estructura dinàmica de dades i deixem al lector que es faci després les implementacions d'estructures que segurament ha estudiat en el curs de C.

7.3.1 Definició de pila.

Una pila és una estructura de dades que simula una situació real molt comú. Una pila de plats o una pila de cartes són els exemples més comuns.

Una  pila és una estructura de dades (Objecte en la terminologia de OOP) que es composa d'elements, anomenats nodes de la pila, del mateix tipus i que funciona de la següent manera:

  1. Tenen una funció que inicialitza la pila.
  2. Tenen una funció que ens indica si la pila està buida.
  3. Tenen una funció que permet afegir elements a la pila. En una pila només es pot afegir un element al cim de la pila.
  4. Tenen una funció que ens retorna l'element que està al cim de la pila i que el treu de la pila.
Pila de nombres enters

7.3.2 Implementació de la classe genèrica o plantilla de pila.

Classes NodoPila i Pila
Classe NodoPila
template <class TipusDada> class NodoPila
{
    TipusDada Informacio;
    NodoPila<TipusDada> * Seguent;
public:
    NodoPila() {Seguent = NULL;}
    NodoPila(TipusDada V)
    {
       Informacio=V;
       Seguent = NULL;
    }

    NodoPila<TipusDada> * DonamSeguent()
    {
       return Seguent;
    }
    void PosaSeguent(NodoPila * p){Seguent = p;}
    void ObteInformacio(TipusDada &c) {c=Informacio;}
    void PosaInformacio(TipusDada c){Informacio=c;}
};
Ja hem comentat que les piles es fan de nodes. Un node és un element d'una classe que conté una informació i un punter que apunta a un altre node de la mateixa classe.

Si volem fer un node genèric hem de posar la informació del node com a tipus genèric de dades.

Igual que abans aquest tipus podrà substituir-se en el moment de la compilació, quan declarem un node, per qualsevol tipus de dades vàlid en C++, des de ints i floats fins a estructures o objectes d'altres classes.
Classe Pila
template <class TipusDada> class Pila
{
    NodoPila<TipusDada> *Principi;
public:
    Pila(){Principi=NULL;}

    Boolean Push(TipusDada c);
    Boolean Pop(TipusDada &c);

    Boolean EstaBuida()
    {
        if (Principi==NULL) return CERT;
        else return FALS;
    }
};

template <class TipusDada> 
Boolean Pila<TipusDada>::Push(TipusDada c)
{
    NodoPila<TipusDada> *p;

    p=new NodoPila<TipusDada>;
    if (p)
    {
        p->PosaInformacio(c);
        p->PosaSeguent(Principi);
        Principi=p;
        return CERT;
    }
    else return FALS;
}

template <class TipusDada> 
Boolean Pila<TipusDada>::Pop(TipusDada &c)
{
    if (Principi!=NULL)
    {
        NodoPila<TipusDada> * Auxiliar;
        Auxiliar=Principi;
        Principi->ObteInformacio(c);
        Principi = Principi->DonamSeguent();
        delete Auxiliar;

        return CERT;
    }
    else return FALS;
}
La classe genèrica Pila té, com veiem, una única dada que és un punter a node, punter que s'anomena Principi. També veiem que té les funcions següents:

Pila() És el constructor que no rep cap paràmetre ja que la seva funció és inicialitzar el punter Principi a NULL.
Push La funció que rep un objecte de la classe TipusDada. Aquesta funció busca memòria per posar aquest objecte i si troba aquesta memòria afegeix la dada a la pila.

Si té èxit retorna CERT i si no en té d'èxit retorna FALS.
Pop La funció Rep una referència a un objecte de la classe TipusDada. Si la pila no està buida (Principi != NULL) copia les dades del primer objecte a l'objecte rebut (c) i després esborra aquest objecte de la pila.

Si té èxit retorna CERT i si no en té d'èxit retorna FALS.
EstaBuida La funció EstaBuida torna CERT si la pila no té cap objecte i FALS si té algun objecte.


Nota: Al llarg d'aquest codi hem fet ús del fitxer BOOLEAN.H següent:

#ifndef _BOOLEAN_

#define _BOOLEAN_ 1
typedef int Boolean;
#define CERT 1
#define FALS 0

#endif


7.3.3 Ús de la classe Pila

La classe genèrica Pila que acabem de veure ens permet fer objectes pila de qualsevol mena de dades, des de dades simples com enters o floats a estructures u objectes.

Als tres exemples següents veiem una pila d'enters, una pila de estructures senzilles i una pila de nombres complexos (objectes).

7.3.3.1 Ús de la classe Pila amb nobres enters i floats.

Pila d'enters i pila de floats 
#include <pila.h>

main()
{
    int A;

    Pila<int> MiPila;
    MiPila.Push(23);
    MiPila.Push(12);

    MiPila.Pop(A);
    cout << A << endl;
    MiPila.Pop(A);
    cout << A << endl;

    float B;
    Pila<float> TuPila;
    TuPila.Push(15.45);
    TuPila.Push(16.01);

    TuPila.Pop(B);
    cout << B << endl;
    TuPila.Pop(B);
    cout << B << endl;
}
Segons veiem en el codi ara és molt senzill fer ús de piles en els nostres programes.

Hem declarat ara una pila de nombres enters anomenada MiPila. L'hem afegit dos nombres enters i després els hem obtingut i esborrat de la pila.

Després hem declarat una pila de nombres reals (float) i hem fet ús de la mateixa manera que amb la de nombres enters, sense haver de pensar en l'estructura interna del codi de la classe pila.

!!!! Quina meravella !!!!

No hem de reprogramar les piles per a cada tipus de dades.

7.3.3.2 Ús de la classe Pila amb estructures.

Hem declarat una estructura senzilla de DadesPersonals i declarat una pila (MiPila) d'aquest tipus de dades.

A partir d'aquest situació podem fer ús de les funcions de pila per a variables estructura d'aquest tipus de dades DadesPersonals com les variables Aux1 i Aux2.

Ja hem comentat alguna vegada que les estructures son quasi objectes en C++. Així que aquest exemple pot considerar-se un cas particular del tercer exemple on fem piles d'objectes.

Pila d'estructures 
#include <pila.h>
#include <string.h>

typedef struct DadesPersonals
{
    char Nom[45];
    char Telefon[20];
};

main()
{
    DadesPersonals Aux1, Aux2;

    Pila<DadesPersonals> MiPila;

    strcpy(Aux1.Nom,"Pep Palop Pelap");
    strcpy(Aux1.Telefon,"931234567");

    MiPila.Push(Aux1);

    MiPila.Pop(Aux2);
    cout << "Nom: " << Aux2.Nom << endl ;
    cout << "Telèfon: " << Aux2.Telefon << endl;
}


7.3.3.3 Ús de la classe Pila amb objectes.

A l'exemple següent hem fet ús d'una classe senzilla com la classe Complex, però podem fer piles de qualsevol mena d'objectes dels que disposem per programar.

Pila de nombres complexos 
#include <complex.h>
#include <pila.h>

main()
{
    Complex z;

    Pila<Complex> MiPila;
    for(int i=1;i<5;i++)
    {
        cin >> z;
        MiPila.Push(z);
    }

    while (!MiPila.EstaBuida())
    {
        MiPila.Pop(z);
        cout << z << endl;
    }
}
Segons veiem, tenim la classe de nombre complexos ja feta al tema 6.

Només incloem els arxius de capçalera de les classes complex i pila i podem fer piles de complexos.


7.4 Exercicis.

  1. Escriure les funcions Canvia i Suma. Has de provar-les amb nombres enters i amb elements de la classe complex que tens feta. Ha de funcionar expressions dels tipus Suma(z1,z2) i Suma(6,z2).


  2. Escriu la plantilla de la classe vector que ha de tenir les funcions següents:

    1. Constructors.
    2. Sobrecàrrega dels operadors = , [] , + , -.
    3. Sobrecàrrega dels operadors << i >>

    Comprova en els casos següents:

    1. vector de nombres enters
    2. vector de nombres complexos
    3. carrega en un vector tot el fitxer de DatosPersonales del Tema 6 exercici 5

  3. Les cues.

    Són altres estructures de dades semblants a les piles, que també simulen una situació real com son les cues de persones. En aquestes cues les dades s'insereixen al final de la cua i surten pel principi.

    Una  cua és una estructura de dades (Objecte en la terminologia de OOP) que es composa d'elements del mateix tipus i podem dir que funciona  de la següent manera:

    1. Tenen una funció que inicialitza la cua.
    2. Tenen una funció que ens indica si la cua està buida.
    3. Tenen una funció que permet afegir elements a la cua. En una cua només es pot afegir un element al final de la cua.
    4. Tenen una funció que ens retorna l'element que està al principi de la cua.
    5. Tenen una funció que extreu l'element que està al principi de la cua.



  1. Llistes unidireccionals.

    Són piles a les que afegim algunes funcions noves. Entre altres afegireu les funcions següents:

    Recorregut, Busca, InsereixDespres, InsereixAbans, EsborraElement, EsborraSeguent, EsborraLlista, VeurePrimerElement.

    Com que aquestes llistes són piles haureu de fer una classe que hereti de la classe pila, i així només haureu de fer les noves funcions.



  2. Llistes doblement enllaçades són les que en cada element tenen dos punters, un apunta al registre següent i l'altre al registre anterior. Aixó permet fer el recorregut de la llista en els dos sentits posibles.

    Hauràs de fer la classe amb les les funcions següents: InicialitzaLlista, InsereixALaDreta, InsereixALaEsquerra, Busca, EsborraElement i ImprimeixNomsDreta i ImprimeixNomsEsquerra.

  3. Una llista circular és una llista unidireccional en la que l'últim element de la llista apunta al primer element en lloc d'apuntar a NULL. Si observes la imatge veuràs que en realitat no existeix primer element.




    Per recórrer una llista circular hem de mantenir un punter PunterAReg que apunti a un element de la llista. Com que no té ni principi ni fi haurem de convenir que acabarem el recorregut quan el PunterAReg torni a estar en el lloc on va començar a moure's. Així si el punter està apuntant a l'element Lola i el movem (Josep, Pep, Ramon, ...) haurem d'aturar el moviment quan arribem una altra vegada a Lola.

    Hauràs de fer una classe amb les funcions següents: InicialitzaLlista, InsereixALaDreta, Busca, EsborraElement i ImprimeixLlista.

  4. En el capítol 13 dels apunts de C, al paràgraf 4, es parla de les operacions més comuns en un arbre no equilibrat.

    Apunts de C, capítol 13, paràgraf 4


    Implementa una classe genèrica d'arbre binari no equilibrat en el que has de crear com a funcions membre totes les operacions descrites en el paràgraf 4.