Desarrollo de programación C++. Patrones

Patrones de lista. Patrones de función

  • Enviado por: María Gabriela Rodríguez
  • Idioma: castellano
  • País: España España
  • 13 páginas
publicidad
publicidad

PATRONES

Un patrón de clase especifica como construir clases individuales, del mismo modo en que una clase especifica como se construyen los objetos individuales. Definición de una pila de elementos de tipo arbitrario :

template <class T> class pila {

T* v;

T* p;

int tam;

public:

pila(int t) { v = p = new T[tam = t] ; }

~pila() { delete[] v; }

void meter(T a) { *p++ = a; }

T sacar() { return *--p; }

int tamaño() const { return p-v; }

};

  • template <class T> especifica que se está declarando un patrón, T será el tipo de clase pila que se especificará

  • el alcance de T llega hasta el final de la declaración que empieza en template <class T>

  • template <class T> dice que T es un nombre de tipo no el nombre de una clase

Ejemplo de definiciones de clases pila de distintos tipos :

pila <char> pc(100); // pila de caracteres

pila < int> pi (50) ; // pila de enteros

pila <figura *> paf (100) ; // pila de punteros a figura

pila <punto > pp(1000) ; // pila de puntos

Las funciones del patrón que definimos anteriormente estaban en línea, pero no necesariamente tiene que ser así, por ejemplo :

template <class T> class pila {

T* v;

T* p;

int tam;

public:

pila(int t);

~pila();

void meter(T a);

T sacar();

int tamaño() const;

};

Para este caso las funciones miembros del patrón pila se deben definir e incluir en algún lado, en tales casos las funciones que se definen deben tener como parámetro el tipo del que se trate la clase, por ejemplo :

template < class T> void pila<T>::meter(T a)

{

*p++ = a;

}

template < class T> void pila<T>::pila(int t)

{

v = p = new T[tam = t];

}

Como se puede observar en las definiciones anteriores, la declaraciones de las funciones miembros anteriores solo difieren en la sintaxis del nombre de la clase y en que se debe agregar el prefijo template < class T>.

Para diseñar patrones se debe tratar de usar lo menos posible al información global. El motivo es que un patrón se utilizará para generar clases y funciones basadas en tipos y contextos desconocidos por lo tanto debe ser independiente del contexto.

Patrones de lista

Vamos a ver un ejemplo de implementación de una lista vinculada utilizando el recurso de patrón.

template<class TYPE>

struct Snode {

TYPE info; // información del nodo

Snode<TYPE>* next; // puntero al próximo nodo de

// lista

Snode(const TYPE &x);

void insertafter(Snode<TYPE>* n);

Snodeb<TYPE> * Rmvnext;

};

Ahora inicializamos el constructor :

template<class TYPE> Snode<TYPE>::Snode(const TYPE &x) : info(x)

{

next =0; // esto se hace para tener punteros

// Null en el final de la lista

}

template <class TYPE> void Snode<TYPE>:: InsertAfter(Snode<TYPE> *n)

// insertar el nodo n después de este (this)

{

n->next = next; // n->next = this->next

next = n // this-> next = n

}

Supongamos ahora que queremos trabajar con una lista de caracteres :

Snode<char> milista(`a'); //Creamos la lista milista con el primer nodo siendo a

milista.InsertAfter(new Snode<char>(`c'));

milista.InsertAfter(new Snode<char>(`b'));

Supongamos ahora otro tipo de implementación :

struct Snodeb {

Snodeb* next;

Snodeb();

void InsertAfter(Snodeb* n);

Snodeb* Rmvnext();

};

struct Shapenode : public Snodeb{

Shape info;

ShapeNode(float x=0; float y=0);

};

ShapeNode::ShapeNode( float x, float y): info(x,y) {};

struct CircleNode : public Snodeb {

Circle info;

CircleNode(float x=0 , float y=0; float r=0 );

};

CircleNode::CircleNode(float x, float y, float r) : info(x,y,t) {}

Snodeb milista;

milista.InsertAfter(new ShapeNode(1,2));

milista.IndertAfter(new CircleNode(3,4,5);

Implementación con patrón :

template<class TYPE>

class Snode : public Snodeb {

public:

TYPE info;

Snode();

Snode(const TYPE &x);

Snode<TYPE> *Next();

};

Vamos a definir la función Next() :

template <class TYPE> // Esta función está definida

// para evitar excesivos tipeos

Snode<TYPE> *Snode<TYPE>::Next()

{

return (Snode<TYPE> *)next;

}

clase ListaS : private Snodeb {

protected:

virtual void MakeEmpty();

public:

Snodeb* back

ListaS();

virtual ~ListaS();

Snodeb* Front() const;

Snodeb* Back() const;

virtual Snodeb *dupnode(const Snodeb *n) = 0;

virtual void FreeNode(Snodeb* n) = 0;

virtual void Clear();

int Copy(const ListaS &sl);

int Concatenate(const ListaS &sl);

void InsertAfter(Snodeb *a, Snodeb *b);

Snodeb *RmvNext(Snodeb *n);

Snodeb *RmvFront();

void AttachToFront(Snodeb *n);

void AttachToBack(Snodeb *n);

void Absorb(ListaS &sl);

void SplitAfter(Snodeb *n, ListaS &sl);

public:

virtual void Clear();

int IsEmpty() const;

int IsHeader(const Snodeb *n) const;

};

Las funciones virtuales FreeNode() y DupNode han sido implementadas de esa forma para poder soportar diferentes tipos de asignación de memoria, como ListaS no conoce el tipo de datos a ser almacenados en los nodos, por lo tanto no es responsable de construirlos. Observar que ListaS es una clase derivada de Snodeb y que por lo tanto representa una cabecera de una lista, como la lista se implementa de manera circular, el último nodo de la lista apunta al primero. Ahora estamos en condiciones de escribir una lista completa como patrón :

template<class TYPE>

class Slist : public ListaS {

protected:

virtual Snode<TYPE> *AllocNode(const TYPE &x);

virtual Snodeb *DupNode(const Snodeb *sn);

virtual void FreeNode(Snodeb *dn);

public:

friend class TempSlist<TYPE>;

friend class ArraySlist<TYPE>;

Slist();

Slist(const Slist<TYPE> &s);

Slist(TempSlist<TYPE> &s);

virtual ~Slist();

void operator=(const Slist<TYPE> &s);

void operator=(TempSlist<TYPE> &s);

Snode<TYPE> *Header();

const Snode<TYPE> *Header() const;

Snode<TYPE> *Front();

const Snode<TYPE> *Front() const;

Snode<TYPE> *Back();

const Snode<TYPE> *Back() const;

TYPE *FrontData();

const TYPE *FrontData() const;

TYPE *BackData();

const TYPE *BackData() const;

int Copy(const Slist<TYPE> &sl);

void InsertAfter(Snode<TYPE> *a,

Snode<TYPE>*b);

void AttachToFront(Snode<TYPE> *n);

void AttachToBack(Snode<TYPE> *n);

Snode<TYPE> *RmvNext(Snode<TYPE> *n);

Snode<TYPE> *RmvFront();

int DelNext(Snode<TYPE> *n, TYPE *x=0);

int DelFront(TYPE *x = 0);

void Absorb(Slist<TYPE> &sl);

void SplitAfter(Snode<TYPE> *n, Slist<TYPE>

&sl);

int Concatenate(const Slist<TYPE> &sl);

int operator+=(const Slist<TYPE> &sl);

friend TempSlist<TYPE> operator+(const

Slist<TYPE> &a, const Slist<TYPE> &b);

const Snode<TYPE> *

NodeBeforeMatch(const TYPE &x, const Snode<TYPE> *p=0) const;

Snode<TYPE> *AddToFront(const TYPE &x);

Snode<TYPE> *AddToBack(const TYPE &x);

Snode<TYPE> *AddAfter(const TYPE &x, Snode<TYPE> *n);

};

Patrones de función

El empleo de clases patrón implica funciones miembro patrón. Además, es posible definir patrones de función globales , es decir patrones de función que no sean miembros de ninguna clase. Un patron de función define familia de funciones de la misma manera que un patrón de clases define una familia de clases.

Supongamos el siguiente patrón de una función ordenar :

template <class T> void ordenar(Vector<T>&);

void f( Vector<int>& vi,

Vector<Cadena>& vc,

Vector<int>& vi2,

Vector<char*>& vs)

{

ordenar(vi); // ordenar vector de enteros

ordenar(vc); // ordenar vector de Cadena

ordenar(vi2); // ordenar vector de enteros del tipo 2

ordenar(vs); // ordenar vector de cadenas de

// caracteres

};

En cada llamada el tipo de argumento determina la función de ordenamiento que se va a utilizar, lo que se necesita ahora es definir el patrón de la función, por ejemplo un patron simple de la función de ordenamineto por el método de la burbuja es :

template<class T> void ordenar(Vector<T>& v)

// función de ordenamiento en orden ascendente por el

// método de la burbuja

{

unsigned n = v.tamaño();

for (int i=0; i<n-1; I++)

for(int j=n-1; i<j; j--)

if (v[j] < v[j-1]) { // intercambiar valores

T temp = v[j];

v[j] = v[j-1];

v[j-1] = temp;

}

}

En la implementación de esta función se deben prever algunos problemas que se pueden presentar, especialmente en la utilización del operador < (menor que), pues por ejemplo algunos tipos como char* no pueden emplearse con ese operador, para estos casos debemos proveer otro tipo de implementación, por ejemplo :

void ordenar(Vector<char*>& v)

{

unsigned n = v.tamaño();

for (int i=0; i<n-1; I++)

for(int j=n-1; i<j; j--)

if (strcmp(v[j], v[j-1] < 0) { // intercambiar

char* temp = v[j];

v[j] = v[j-1];

v[j-1] = temp;

}

}

Esta definición de la función especial para tipos de cadena de caracteres, que puede ser empleado siempre que se necesite dar una definición individual a una función patrón, da una gran flexibilidad para este tipo de implementaciones.

Función comparación para tipos en los que no está definido directamente la comparación la posibilidad de incluir en una función Ordenar la comparación:

template <class T, class Comp> class Ordenar

{

public :

static void ordenar (Vector<T>&);

};

La repetición de tipos de elementos es tediosa, por lo tanto esto se puede evitar poniendo typedef en el patrón de Comparador :

template<class T> class Comparador {

public:

typedef T T; // definir Comparador<T>::T

static int menorque (T& a, T& b) { return a < b}

};

la versión especial para cadena de caracteres:

class Compardor<char*> {

public:

typedef char* T;

static int menorque (T a, T b) {

return strcmp(a,b) < 0;

}

// ........

};

Ahora se puede escribir :

void f( Vector<int>& vi,

Vector<Cadena>& vc,

Vector<int>& vi2,

Vector<char*>& vs)

{

Ordenar<int, Comparador<int>>::ordenar(vi);

Ordenar<Cadena, Comparador<Cadena>>::ordenar(vc);

Ordenar<int, Comparador<int>>::ordenar(vi2);

Ordenar<char*, Comparador<char*>>::ordenar(vs);

}

template<class comp> void Ordenar::ordenar(Vector<Comp::T>& v)

{

unsigned n = v.tamaño();

for (int i=0; i<n-1; I++)

for(int j=n-1; i<j; j--)

if (Comp::menorque(v[j],v[j-1]))) {

// intercambiar los valores

Comp::T temp = v[j];

v[j] = v[j-1];

v[j-1] = temp;

}

}

Universidad Tecnológica Nacional - Santa Fe - Departamento Sistemas -

Curso : Desarrollos de Programación en C++