Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1101
II Semestre 2000
[<=] [home] [<>] [\/] [=>]
CI-1101 Programación I

Tarea #9 [solución]

La clase Vector redimensionable

// vector.h   (C) 2000  ci1101@anubis.ecci.ucr.ac.cr

#ifndef  _vector_h
#define  _vector_h

#include <cstddef> // size_t

typedef long T;  // tipo de valor almacenado en la vector

class vector {
/*  resultado
    Esta clase permite usar vectores a los que se les puede agregar
    nuevas entradas, tanto al principio como al final.
*/
public:
    enum { Vdim  = 40,    // Cantidad de Patas
           VPdim = 30 };  // dimensión de la "pata"
private:
    class Pata {  // usada para implementar "vector"
        friend class vector;
    public:
        T _v[VPdim];     // pedazo del vector, de longitud fija VPdim
    private:
        Pata() {} // evita usar la clase fuera de vector
    }; // Pata

public:
    vector(size_t n);  // Contructor
    vector();          // Contructor por defecto (de vector)
    ~vector();         // Destructor

    void  Agregar_Final    (size_t); // Agregar elementos al Final
    void  Agregar_Principio(size_t); // Agregar elementos al principio

    T &    operator[]  (size_t);     // V[i]
    size_t Capacidad() { return Vdim * VPdim; }
    size_t Dimension();

private:
    size_t _izq_primero; // tamaño del bloque libre a la izquierda
    size_t _der_ultimo;  // tamaño del bloque libre a la derecha
    size_t _der;
    Pata * _vp[Vdim]; // vector de punteros hacia las partes ("patas")
}; // vector

#endif //_vector_h

// EOF: vector.h
Figura 1

      Los vectores del lenguaje C++ son muy úiles, pero tienen el defecto de son de tamaño fijo. Por eso, en esta tarea usted implementará un vector que puede cambiar de tamaño. Para trabajar, use la clase vector cuya declaración aparece en la Figura 1.

// vector.cpp (C) 2000  ci1101@anubis.ecci.ucr.ac.cr

#include "vector.h"
/*  requiere
    El tipo de valor almacenado en el vector es "T", por lo que
    para usar la clase el programador usuario debe definirlo
    cambiando el "typedef" que se encuentra al principio del
    archivo de encabezado "vector.h". */

/*  implementación
        _izq_primero-----+
                         |
    _vp:[*]--->[?][?][?][*][*][*][*]
        [*]--->[*][*][*][*][*][*][*]
     V  [*]--->[*][*][*][*][*][*][*]
     d  [*]--->[*][*][*][*][*][*][*]
     i  [*]--->[*][*][?][?][?][?][?] <--- _der
     m  [.]        |  VPdim
        [.]        |
                   +---_der_ultimo

    El vector completo está formado por varias partes (en el diagrama
    "[?][?][?][*][*][*][*]"), de tipo "vector::Pata", que contiene
    cada una la misma cantidad "VPdim" de valores. Estas partes o
    "patas" del vector se obtienen dinámicamente, conforme el
    programador usuario agrega nuevos valores al vector al invocar
    los métodos vector::Agregar_Final() y vector::Agregar_Principio().

    En el vector de punteros "_vp[]" hay "Vdim" punteros hacia un
    máximo de "Vdim" patas del vector. Por eso, la capacidad máxima
    del vector es "VPdim*Vdim". El campo "_der" indica cuántas partes
    o "patas" tiene el vector; es un índice para el vector "_vp[]".

    Los campos "_izq_primero" y "_der_ultimo" son índice que indican,
    para la primera y última de las partes del vector, cuántos campos
    están vacíos (en el diagrama "[?][?][?]").
    - En el caso de la primera parte, "_izq_primero" indica que los
      campos que están vaciós son:
         _vp[0]->_v[0] ===> _vp[0]->_v[_izq_primero-1]

    - En el caso de la última pata, "_der_ultimo" indica que los
      campos que están vaciós son:
         _vp[_der]->_v[_der_ultimo] ===> _vp[_der]->_v[VPdim]

    - Todos los campos intermedios ("[*][*][*][*][*][*][*]" en el
      diagrama) contienen los valores almacenados en el vector.

    Para encontrar el sitio (índice) en que está almacenado uno
    de los elementos del vector, hay que localizar primero en qué
    pata se encuentra, y luego, dentro de la pata, en qué entrada
    está el valor.
*/

vector::vector(size_t n) { // Contructor
/*  resultado
    Inicializa el vector "*this" para que su dimensión sea "n".‡
    - Si "n" excede la capacidad máxima de un vector, la
      dimensión del vector se ajusta para que sea la de la
      capacidad máxima.
*/
    if (n > Capacidad()) { // ajusta hasta a la capacidad máxima
        n = Capacidad();
    }

    // calcula la cantidad de patas para el vector
    _izq_primero = 0;
    _der         = (n / VPdim) + 1;
    _der_ultimo  = (n % VPdim);

    size_t i;
    // crea las "_der" patas
    for (i = 0; i<_der; ++i) {
        _vp[i] = new vector::Pata;
        // pone ceros en cada parte del vector
        for (size_t j = 0; j<VPdim; ++j) {
            _vp[i]->_v[j] = 0;
        }
    }

    // pone punteros nulos en todo el resto de _vp[]
    for (i = _der; i<Vdim; ++i) {
        _vp[i] = 0;
    }
}

vector::~vector() { // Destructor
    // basta destruir las "_der" patas de _vp[]
    for (size_t i = 0; i<_der; ++i) {
        delete _vp[i]; // destruye cada vector::Pata
    }
}

// EOF: vector.cpp
Figura 2

      Estructure su vector de longitud variable usando pedazos, más pequeños, de longitud fija. Luego haga un programa de prueba para verificar que su vector puede crecer y encogerse. Una vez que termine la implementación, envíe su trabajo a los asistentes del curso por correo electrónico.

Envío de tareas por correo electrónico

[mailto:]Andrés Arias y Tomás Rodríguez

 

Tiempo de entrega: 3 Días
Modalidad: Individual

Soluciones

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2000
Derechos de autor reservados © 2000
[home] <> [/\]