Tarea #1 [solución]

La Clase Lista

      La estructura de datos más importante, sin lugar a dudas, es el arreglo o vector. De hecho, todos los lenguajes de programación permiten definir vectores. Sin embargo, no es suficiente usar únicamente vectores para escruibir programas eficientes, pues en la mayoría de los casos también es necesario usar listas.

      Las listas tienen casi todas las propiedades de los vectores, pero no permiten acceso directo a cualquiera de sus elementos, pues para llegar al i­ésimo elemento, siempre hay que que recorrer a todos los anteriores. Además, lo usual es que las listas almacenen sus valores en memoria dinámica, para lo que deben también usar punteros. Por eso las listas ocupan más espacio que un vector para almacenar la misma cantidad de datos.

      La singular ventaja de la lista sobre el vector es que puede crecer en tiempo de ejecución, por lo que sirve en todas aquellas tareas en las que el programador no puede determinar de antemano la cantidad de valores que debe almacenar en un contenedor. Con alguna frecuencia es necesario hacer arimética con números racionales, para lo que conviene contar con una claes que tenga esas operaciones.

      En esta tarea programada usted implementará el contenedor Lista en C++. Puede usar como base cualquier implementación que quiera, como por ejemplo la lista Turbo Pascal que está en este sitio:
      http://www.di-mare.com/adolfo/p/src/listc.pas
      http://www.di-mare.com/adolfo/p/src/list2.pas

class List2T {      // lista doble circular

    class node {
       T      e;    // elemento
       node * next;
       node * prev;
    }; // node

    class iterator {
        friend class List2T;
        iterator& operator++();     // ++p
        iterator  operator++(int);  // p++
        iterator& operator--();     // --p
        iterator  operator--(int);  // p--
        T& operator*();
        iterator& operator=(iterator &x);
    }; // iterator

    List2T();
    ~List2T();

    unsigned count();
    int empty()
    int valid(iterator);

    void insert( iterator where, T &e);
    void remove( iterator where );

    void push_front(T &e) { insert(begin(), e); }
    void push_back( T &e) { insert(end(),   e); }

    itr last();
    itr begin();
    itr end()   { return 0; }
    itr nth(unsigned n);

    unsigned pos(iterator i);

}; // List2T

      En la Figura 1 aparece el encabezado del objeto List2T, que es una lista que almacena valores de tipo T. Haga su implementación usando una lista circular doblemente enlazada, en donde las inserciones y borrados se hacen antes del sitio a que apunta el iterador "where". Implemente su lista de manera que sea posible insertar y borrar valores eficientemente tanto al final de la lista, como al principio.

void primes(List2T &L, unsigned n) {
/*-------------------------------*\
| Prepends to L all prime numbers |
| smaller than "n"                |
\*-------------------------------*/

    for (int i = 1; i<n; i++) {
        int j, is_prime = 1;
        for (j = 2; j<i; j++) {
            if (0 == i % j) {
               is_prime = 0;
            }
        }
        if (is_prime) {
            L.push_front(i);
        }
    }
}

void print_list(List2T &L) {
    cout << "  [";

    List2T::iterator p = L.begin();
    while (p != L.end()) {
        cout << *p << ":";
        p++;
    }
    cout << "] ";
}

      Haga la especificación de su lista de manera que los programas del la Figura 2 puedan usarse con ella. Como modelo para hacer su especificación, puede usar las de la biblioteca STL o las operaciones de contenedores definidas en:

Di Mare, Adolfo

"Reutilización de Contenedores Parametrizables con Lenguajes de Semántica Limitada", Capiítulo 5 Tesis de Doctorado, Universidad Autónoma de Centro América, 1999.
      http://www.di-mare.com/adolfo/binder/c05.htm

      Escriba tres programas C++ para probar la lista que ha implementado, usando tres tipos diferentes T. Cuídese, sin embargo, de evitar reescribir la lista completa para cada caso. Por ejemplo, puede hacer una versión de la lista para números enteros, otra para racionales, y otra para hileras. Para eso el valor de la lista es de tipo T, el que usted puede adaptar a cada caso. Es importante que para obtener una nueva lista no deba reprogramarla completa, sino que pueda obtener la nueva versión haciéndole pequeños ajustes a la vieja.

      Luego de imprimir la documentación de su programa, y entregarla en clase, envíe su trabajo al asistente del curso por correo electrónico. Para esto, haga un archivo empacado .zip cuyo nombre sea su número de carnet. Incluya en ese archivo lo siguiente:

1. Un documento en formato HTML que describa el trabajo que realizó. Incluya el nombre del compilador que usó.
2. La especificación de su lista.
3. El código fuente de sus programa de prueba.
4. Los datos de prueba para sus tres programas.

      Las cuentas de computador en la ECCI se asignan de acuerdo al número de carnet. Por ejemplo, si su carnet es el número 95-28-09, para entregar su tarea usted debe crear el archivo 952809.zip para enviarlo por correo electrónico al asistente del curso.

      Luego haga en su cuenta personal un subdirectorio llamado public_html, que es bajo el que se instalan todas sus páginas Internet. Por ejemplo, si su solución está en el archivo HTML llamado "OLP/t3sol952809.htm", entonces usted debe instalar esa página en el archivo
      public_html/OLP/t3sol952809.htm
de su cuenta. Luego, para acceder esa página Internet, debe entrar a este sitio:
      http://anubis.ecci.ucr.ac.cr/~e952809/OLP/t3sol952809.htm

      Como todas las cuentas de estudiante son la letra "e" seguida del número de carnet, para el estudiante de carnet "952809" la cuenta es "e952809". Para indicarle al servidor Internet a cuál cuenta entrar se usa el caracter "~" (Alt-126), seguido del nombre de la cuenta: "~e952809".

      Después de la fecha de entrega del programa, puede usted instalar en su cuenta personal su solución (no instale antes su solución en Internet, pues en ese caso sería usted culpable de facilitar la copia de su trabajo, y en consecuencia se haría acreedor a la sanción respectiva).

Manuel Aguilar

Tiempo de entrega: 10 días Modalidad: Individual

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2000
Derechos de autor reservados © 2000