Tarea #4 [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 arímetica 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++. Como base, use la implementación en Turbo Pascal descrita en el siguiente artículo:

Di Mare, Adolfo

"El ADT Lista"; Reporte técnico ECCI-01-88; ECCI-UCR; 1988.
      http://www.di-mare.com/adolfo/p/list.htm

TYPE
  TNode = RECORD
    next: ^TNode;
    elem:  TElem;
  END;                      PLpos = ^TNode;

  TList = OBJECT
     _last: ^TNode;

    PROCEDURE InsertA  ( p: PLpos; VAR x: TElem );
    PROCEDURE DeleteA  ( p: PLpos );
  END; { TList }

      En la Figura 1 aparece el encabezado del objeto TList, que es una lista circular que almacena valores de tipo TElem. La implementación de esta clase se encuentra en este sitio Internet:
      http://www.di-mare.com/adolfo/p/src/listc.pas

      Esta lista es una lista circular, por lo que desde la lista hay un puntero al último nodo, el que a su vez apunta al primer nodo. De esta manera es posible insertar y borrar valores eficientemente tanto al final de la lista, como al principio.

      Escriba tres programas C++ para probar la lista que ha implementado. 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 TElem, 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 a los asistentes 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. El código fuente de sus programa de prueba.
3. El código ejecutable de sus programa de prueba.

      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).

Hilda Pineda y Mario Tenorio

Tiempo de entrega: 10 días Modalidad: Individual

Soluciones

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