Página principal | Lista de namespace | Jerarquía de la clase | Lista de componentes | Lista de archivos | Miembros de las clases | Archivos de los miembros

Referencia de la Clase Lista_Ordenable

Lista ordenable simple, compuesta de nodos, que almacena números enteros Más...

Diagrama de herencias de Lista_Ordenable

Contenedor_Ordenable Lista de todos los miembros.

Tipos públicos

typedef int value_type
 Tipo de valor almacenado en el contenedor.

Métodos públicos

 Lista_Ordenable (unsigned N)
 Constructor que inserta "N" valores (aleatorios) en el contenedor.
virtual ~Lista_Ordenable ()
 Destructor.
virtual void Intercambie (int, int)
 Intercambia los valores de los elementos que están en las posiciones [i] <=> [j].
virtual bool Es_Menor (int, int) const
 Compara los elementos en las dos posiciones "i" && "j" del contenedor
  • Retorna "true" cuando el primero es menor que el segundo
  • Retorna "false" cuando el primero es mayor o igual que el segundo.

virtual void ImprimaSe () const
 Graba en "cout" todos los valores almacenados en el contendor
  • Los graba en el orden en el que se encuentran almacenados.

virtual const char * Nombre () const
 Nombre del contenedor.
virtual int Encuentra_pivote (int, int)
 devuelve 0 si el contenedor tiene claves idénticas de otra forma, devuelve el indice de la mayor de las do claves diferentes de mas a la izquierda.
virtual void Particion (int, int, int)
 divide al contenedor para que las claves menores que pivote estén a la izquierda y las claves mayores estén a la derecha
virtual void Mezclar (int, int, int)
virtual int Get_valor (int)
 devuelve el valor de la posición que ingresa como parámetro
virtual void * Get_direccion (int)
 devuelve el puntero de la posicion ingresada como parámetro
virtual int Get_posicion (void *)
 devuelve la posición dentro del contenedor de la direccion pasada como parametro se utiliza el puntero nulo para luego asinar tal puntero a cualquier otro puntero que apunte a un tipo baase arbitrario
unsigned Dimension () const
 Devuelve la cantidad de valores almacenados en el "Contenedor_Ordenable".

Atributos protegidos

int m_cantidad_de_elementos
 Cantidad de valores almacenados en el "Contenedor_Ordenable".

Métodos privados

void Agregar_Valor (value_type v)
 Agrega una copia de "v" al prinicipio de "*this".

Atributos privados

Nodo * m_cabeza
 Primer "Nodo" de la lista.

Clases

class  Nodo
 Nodos de la "Lista_Ordenable". Más...

Descripción detallada

Lista ordenable simple, compuesta de nodos, que almacena números enteros

Documentación de los 'Tipos Definidos' miembros de la clase

typedef int Contenedor_Ordenable::value_type [inherited]
 

Tipo de valor almacenado en el contenedor.

Documentación del constructor y destructor

Lista_Ordenable::Lista_Ordenable (  unsigned  N  ) 
 

Constructor que inserta "N" valores (aleatorios) en el contenedor. 

00252                                            : Contenedor_Ordenable(N) {
00253     m_cabeza = 0;
00254     this->m_cantidad_de_elementos = N;
00255 
00256     srand(time(0));
00257     for (int i = 0; i < N; ++i) {
00258         Agregar_Valor( rand() % 100 );
00259     }
00260 }

Lista_Ordenable::~Lista_Ordenable (   )  [virtual]
 

Destructor. 

00262                                   {
00263     if (m_cabeza != 0) {
00264         delete m_cabeza;
00265     }
00266 }

Documentación de las funciones miembro

void Lista_Ordenable::Agregar_Valor (  value_type  v  )  [private]
 

Agrega una copia de "v" al prinicipio de "*this". 

00280                                                 {
00281     if (m_cabeza == 0) {
00282         m_cabeza = new Nodo(v);
00283     }
00284     else {
00285         Nodo * p  = new Nodo(v);
00286         p->next   = m_cabeza;
00287         m_cabeza    = p;
00288     }
00289 }

void Lista_Ordenable::Intercambie (  int  ,
int 
)  [virtual]
 

Intercambia los valores de los elementos que están en las posiciones [i] <=> [j].

Implementa Contenedor_Ordenable.

00291                                               {
00292     Nodo * pI = m_cabeza;
00293     Nodo * pJ = m_cabeza;
00294 
00295     int k;
00296     for (k = 0; k < i; ++k) {
00297         pI = pI->next;
00298     }
00299     for (k = 0; k < j; ++k) {
00300         pJ = pJ->next;
00301     }
00302 
00303     value_type temp;
00304     temp = pJ->m_val;
00305     pJ->m_val = pI->m_val; // NO intercambia los nodos
00306     pI->m_val = temp;      // intercambia los valores
00307 }

bool Lista_Ordenable::Es_Menor (  int  ,
int 
)  const [virtual]
 

Compara los elementos en las dos posiciones "i" && "j" del contenedor

  • Retorna "true" cuando el primero es menor que el segundo
  • Retorna "false" cuando el primero es mayor o igual que el segundo.

Precondición:
(i < Dimension()) && (j < Dimension())

Implementa Contenedor_Ordenable.

00309                                                  {
00310     Nodo * pI = m_cabeza;
00311     Nodo * pJ = m_cabeza;
00312 
00313     int k;
00314     for (k = 0; k < i; ++k) {
00315         pI = pI->next;
00316     }
00317 
00318     for (k = 0; k < j; ++k) {
00319         pJ = pJ->next;
00320     }
00321     return (pI->m_val  <  pJ->m_val);
00322 }

void Lista_Ordenable::ImprimaSe (   )  const [virtual]
 

Graba en "cout" todos los valores almacenados en el contendor

  • Los graba en el orden en el que se encuentran almacenados.

Implementa Contenedor_Ordenable.

00324                                       {
00325     Nodo * p = m_cabeza;
00326     Nodo * end = 0;
00327     cout << "[";
00328     while (p != end) {
00329         cout << p ->m_val;
00330         if (p->next != end) { // ¿último nodo de la lista?
00331            cout << " ";
00332         }
00333         p = p->next;
00334     }
00335     cout << "]" << endl;
00336 }

const char * Lista_Ordenable::Nombre (   )  const [virtual]
 

Nombre del contenedor.

Implementa Contenedor_Ordenable.

00338                                           {
00339     #ifdef    __BORLANDC__
00340         // Este método no puede ser definido dentro de la clase porque
00341         // BC++ lo considera "inline", lo que impide que sea "virtual"
00342     #endif // __BORLANDC__
00343     return "Lista_Ordenable";
00344 }

int Lista_Ordenable::Encuentra_pivote (  int  ,
int 
)  [virtual]
 

devuelve 0 si el contenedor tiene claves idénticas de otra forma, devuelve el indice de la mayor de las do claves diferentes de mas a la izquierda.

Implementa Contenedor_Ordenable.

00346                                                           {
00347         value_type primera_clave = this->Get_valor(inicio);
00348         Nodo *k = this->m_cabeza->next;
00349         Nodo *m = (Nodo*) this->Get_direccion(final);
00350         while (k != m )
00351         {
00352                 // selecciona la clave mayor
00353                 if (k->m_val > primera_clave)
00354                         return this->Get_posicion(k);
00355                 else
00356                         if (k->m_val < primera_clave)
00357                                 return inicio;
00358                 k = k->next;
00359         }
00360         // nunca encontró dos claves diferentes
00361         return 0;
00362 }

void Lista_Ordenable::Particion (  int  ,
int  ,
int 
)  [virtual]
 

divide al contenedor para que las claves menores que pivote estén a la izquierda y las claves mayores estén a la derecha

Implementa Contenedor_Ordenable.

00364                                                        {
00365         int z= i;
00366         int d= j;
00367         while (z<d)
00368         {
00369                 while ((Get_valor(z)<pivote) && (z<=d))
00370                         ++z;
00371                 while ((Get_valor(d)>=pivote) && (z<=d))
00372                         --d;
00373                 if(z<=d)
00374                 {
00375                         this->Intercambie(z-1,d-1);
00376                         ++z;
00377                         --d;
00378                 }
00379         }
00380         this->Intercambie(i-1,d-1);
00381 }

void Lista_Ordenable::Mezclar (  int  i,
int  p,
int  j
)  [virtual]
 

no implementado

Implementa Contenedor_Ordenable.

00383                                               {
00385 }

int Lista_Ordenable::Get_valor (  int   )  [virtual]
 

devuelve el valor de la posición que ingresa como parámetro

Implementa Contenedor_Ordenable.

00387                                        {
00388         Nodo *p = this->m_cabeza;
00389         for(int i = 1; i<valor; ++i)
00390                 p=p->next;
00391         return p->m_val;
00392 }

void * Lista_Ordenable::Get_direccion (  int   )  [virtual]
 

devuelve el puntero de la posicion ingresada como parámetro

Implementa Contenedor_Ordenable.

00394                                              {
00395         Nodo *p = this->m_cabeza;
00396         for(int i = 1; i<valor; ++i)
00397                 p=p->next;
00398         return (Nodo*) p;
00399 }

int Lista_Ordenable::Get_posicion (  void *   )  [virtual]
 

devuelve la posición dentro del contenedor de la direccion pasada como parametro se utiliza el puntero nulo para luego asinar tal puntero a cualquier otro puntero que apunte a un tipo baase arbitrario

Implementa Contenedor_Ordenable.

00401                                               {
00402         Nodo *p = this->m_cabeza;
00403         int i= 1;
00404         bool encontrado = false;
00405         while (!encontrado){
00406                 if (puntero != p){
00407                         p=p->next;
00408                         ++i;
00409                 }
00410                 else
00411                         encontrado = true;
00412         }
00413         return i;
00414 }

unsigned Contenedor_Ordenable::Dimension (   )  const [inline, inherited]
 

Devuelve la cantidad de valores almacenados en el "Contenedor_Ordenable". 

00048 { return m_cantidad_de_elementos; }

Documentación de los datos miembro

Nodo* Lista_Ordenable::m_cabeza [private]
 

Primer "Nodo" de la lista.

int Contenedor_Ordenable::m_cantidad_de_elementos [protected, inherited]
 

Cantidad de valores almacenados en el "Contenedor_Ordenable".

La documentación para esta clase fué generada a partir del siguiente archivo:
Generado el Fri Nov 11 22:48:41 2005 para A21551 y 791572 Tarea Programada #7 por  doxygen 1.4.4
Hosted by www.Geocities.ws

1