Site hosted by Angelfire.com: Build your free website today!

Universidad de Costa Rica

Escuela de Ciencias de la
Computación e Informática

Cuarta Tarea Programada:
Inserción y Borrado en Lista

CI-1201 Programación II

 

Profesor
Adolfo Di Mare

 

Estudiantes:
Eileen Rodríguez D. A34418
Katia Montoya M.    A43493

 

Grupo 002
II Ciclo 2005

 

 

 

 

Tabla de Contenidos

 

Tabla de Contenidos...................................................................................................... . 2

Introducción...............................................................................................................3

Descripción Problema a Resolver...............................................................................4

    Planteo............................................................................................................................4

Objetivos.......................................................................................................................4

Requerimientos......................................................................................................... 5

Abstracción................................................................................................................6

Especificación de la clase..............................................................................6

Operaciones y métodos..........................................................................................6

Eficiencia.....................................................................................................................8

Especificación del programa......................................................................... 8

Arquitectura del Programa.............................................................................. 9

Implementación.............................................................................................................. 10

Modelo de la Clase............................................................................................. 10

    Invariante de la Clase……………………………………………………………………………………………13

Arquitectura Interna del Programa........................................................ 14

Compilador Usado.................................................................................................. 14

¿Cómo compilar el programa?....................................................................... 14

Guía del uso del programa.......................................................................................... 15

Datos de prueba del programa................................................................................... 15

Formato de los Datos de Prueba...................................................................15

Entradas Vs Salidas Esperadas del Programa................................. 16

Código Fuente............................................................................................................16

Bibliografía....................................................................................................................... 31

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Introducción

 

            Uno de los principales objetivos dentro de la temática del curso y de ésta tarea programada principalmente, consiste en el hecho de programarla usando especificación e implementación de una clase.

            La Especificación puede verse como un contrato en el que están definidos todos los servicios que la implementación del módulo es capaz de dar. Muchos autores consideran que una especificación correcta debe estar escrita en un lenguaje formal, matemático. Pero otros sólo requieren de la especificación un alto rigor, con estas tres cualidades:

  • Completa: debe decirse todo lo que hay que decir.
  • Correcta: debe omitirse lo que no hay que decir.
  • No ambigua

En pocas palabras, en la especificación no debe sobrar ni faltar nada. Debe estar toda la información esencial para implementar un módulo, y también para usarlo. Además, es conveniente que la especificación sea clara y sencilla de entender, de forma que para usarla el programador no requiera hacer un esfuerzo intelectual más grande de lo necesario.

            Por otro lado, se tiene que la implementación de una clase es un grupo de instrucciones imperativas a ser ejecutadas por el computador, escritas en uno o más lenguajes de programación. Cada implementación es una de las muchas posibles formas de escribir el código de un programa. Cuando se ha usado abstracción como técnica de diseño, cada implementación debe corresponder a alguna especificación pues a partir de la abstracción se llegar a la implementación.

 Mientras con la especificación se define qué hace el programa, en la implementación queda escrito cómo se hace. Por eso, después de que ha sido definida la especificación, en general existen muchas posibles implementaciones diferentes que cumplen con la especificación. Optimizar una implementación significa mejorar el código para escoger una implementación que sea más eficiente.

Tomando como modelo lo anteriormente escrito, se implementará y especificará  un programa que consista en  insertar y borrar los elementos de una lista.

 

            Es posible acceder al programa en sí, desde las direcciones de Internet:

_     http://www.angelfire.com/freak3/a34418

_     http://www.angelfire.com/moon2/a43493

 

Descripción Problema a Resolver

Ø      Planteo:

La implementación de un programa que cuente con la capacidad de llevar a cabo la inserción y el borrado de los elementos de una lista, mediante el entendimiento de nuevos elementos programables como lo son los punteros, y la definición de una lista en sí, la cual cuenta con nodos unidos entre sí, y punteros que señalan a estos. De tal manera, se presente el problema de la implementación del programa, y se tratará de llegar a su ejecución mediante la capacidad de eficiencia o no que llegue a presentar el programa.

 

Ø      Objetivo principal:

-          Realizar el programa utilizando  especificación e  implementación de una clase.

 

Ø      Objetivos Generales:

-          Entender el proceso de la utilización de punteros

-          Comprender la elaboración del programa, mediante la vista del código

-          Desarrollar habilidad y facilidad a la hora de la compilación

-          Manejo más rápido mediante un editor de texto de C++, como por ejemplo el Visual Studio 6.0

-          Obtener la solución al problema, la ejecución del  insertado y borrado de la lista

-          Entender el concepto de una lista y su implementación sencilla

Ø      Requerimientos:

-          Compilador C++, ya sea el de Visual Studio 6.0, el Visual Studio.Net  o el Borland C++.

-          Para la ejecución, obviamente se necesita el código fuente (más adelante se presentará).

-          Para mayor entendimiento o claridad, el archivo doxygen, en el cual se muestra más detalladamente la implementación del programa.

-          Alguna guía de compilación y ejecución del programa (más adelante se presentará).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Abstracción

            Especificación de las Clases

 

ADH_list.cpp:

            En esta clase se implementan los principales métodos para llevar a cabo la ejecución del programa, es decir, el insertado y el borrado de los valores que contienen cada nodo de la lista. Además se implementa y especifica la invariante, la cual se explicará mas adelante.  En resumen se dan las implementaciones para la clase.

 

Operaciones / Métodos

 

*  bool check_ok( const list & L ) { : verifica la invariante

*  void list::push_front( const T& v ) { : Agrega una copia del valor "v" al principio de la lista "*this"

*  void list::push_back(  const T& v ) { : Agrega una copia del valor  "v" al final de la lista "*this"

*  void list::pop_front() { : Elimina el valor del principio de la lista

*  void list::pop_back() { : Elimina el valor del final de la lista

*  void list::clear() {

*  list::node * last_node( const list& L) {: Retorna el puntero al último nodo de la lista

*  list::node * prev_node( const list& L, const list::node * p ) {

*  void list::swap(list& L) { : Intercambia *this <==> L

*  void list::move(list& LO) {: Traslada el valor de  "LO" a  "*this"

*  void list::insert(list::iterator p, const T& v) { : Agrega el valor v al contenedor

*  void list::remove( const T& v) { : Elimina cada uno de los valores iguales a v

*  std::ostream& operator << (std::ostream &COUT, const list& L) {: Graba el valor L en el flujo COUT.

*  std::istream& operator >> (std::istream &CIN, list& r) { : Lee el flujo de texto CIN en el valor  de r.

 

 

 

 

ADH_list.h:

             Se establecen las implementaciones para la clase “Adh_list.cpp”. La clase ADH_list.h especifica el propósito de implementar una  lista simple de nodos con puntero final nulo. Contiene varias de las operaciones más importantes de la clase std::list de la biblioteca estándar de C++. Se especifican los nodos de la clase lista.

 

Funciones / Métodos

 

*         inline bool list::empty() const {

*         inline list::iterator list::first() const { : Primer valor de la lista

*         inline list::iterator list::last() const { : Último valor de la lista

*         inline list::iterator& list::iterator::operator= ( const list::iterator& o) {: Copia

*         inline bool operator == ( const list::iterator& p,const list::iterator& q) {

*         inline bool operator != ( const list::iterator& p, const list::iterator& q) {

*         inline list::iterator( const list::iterator& o ) {

 

USE_list.cpp:

Es la clase que contiene la función principal, en ella se da salida a las instrucciones  que permiten la ejecución  e impresión de la lista.

Funciones / Métodos

*  inline void printList( const list& L ) {

*  int main() {

 

Tdef.h:

Funciones / Métodos

*   inline bool check_ok( const T ) { : Un entero  "long" siempre almacena un valor correcto

 

 

 

 

 

 

 

 

Eficiencia:

      El programa no es eficiente puesto que primeramente es una lista muy frágil.  Además los resultados que muestra no son los solicitados por el usuario, sino son los que el programador decide que aparezca en el momento de ejecutar el programa, por lo tanto, el programa no recibe ningún dato por parte del cliente o usuario; y esto lo hace ineficiente porque no cumple con las solicitudes de las otras personas; requiriéndose así, que el usuario conozca muy bien la arquitectura del programa y sepa cómo está implementado para que pueda hacerle los cambios a la lista que él desee.

 

Especificación del Programa

Este programa tiene la capacidad de llevar a cabo la inserción y el borrado de los elementos de una lista, mediante el uso de punteros.

Diagrama de la clase

                                                  NULL
                +-----+---+   +-----+---+   +-----+---+
    L.m_first-->| v_1 | *-|-->| v_2 | *-|-->| v_3 | 0 |
                +-----+---+   +-----+---+   +-----+---+
                m_val  next                      /\
                                                 ||
                                            last_node(L)

Descripción en palabras

·        Una lista es una secuencia de nodos enlazados del primero al último.

·        El último nodo tiene su campo "next" en nulo [puntero (0)].

·        Para que el valor de la lista sea correcto es necesario que cada uno de los valores almacenados en la lista sea correcto.

·        El campo "next" no se llama "m_next" porque en los libros de texto el nombre que aparece siempre es "next".

Descripción en símbolos

·        (this->m_first == 0) || (this->m_first == p ) apunta a un nodo

·        Para cada node de una lista (p->m_val es correcto && (p->next == 0 || p->next apunta a un node válido )

 

 

Arquitectura del Programa

 

 

 


Cuadro de texto: ADH_port.h

 

 

Cuadro de texto: ADH_list.cpp Cuadro de texto: ADH_list.h Cuadro de texto: USE_list.cpp

 

 

 

 

 

Cuadro de texto: ADH_list.obj Cuadro de texto: USE_list.obj

 

 

Cuadro de texto: ADH_list.exe

 

 

 

 

 

 

 

 

 

 

 

 


Implementación

 

            Modelo de la Clase

Clase ADH_list.h

·          private:

    class node {

 

·          private:

        friend std::ostream& operator<< (std::ostream &, const list& );

        friend bool check_ok( const list & L );

        friend node * prev_node( const list& L, const node * p );

        friend node * last_node( const list& L);

·          private:

        T     m_val; 

        node * next;

·          public:

    class iterator

·          public:

        iterator() : m_p(0)

        iterator( const iterator& o)

             { m_p = o.m_p;} 

        iterator& operator=( const iterator& );

        friend bool operator == ( const iterator&, const iterator& );

        friend bool operator != ( const iterator&, const iterator& );

        iterator operator++()

            { m_p = m_p -> next; return *this; }                   

        iterator operator++(int)

            { iterator q = (*this); m_p = m_p -> next; return q; }

        T& operator*()  { return   m_p -> m_val ; }

        T* operator->() { return &(m_p -> m_val); }

·          private:

        node * m_p;      

·          public:

    list() : m_first(0) { }

    list(const list& L) : m_first(0) { *this = L; }

    ~list() { clear(); }

    void clear();

 

    void push_front( const T& v );

    void push_back(  const T& v );

 

    void pop_front();

    void pop_back();

 

    bool empty() const;     

    iterator first() const; 

    iterator last()  const; 

 

    iterator begin() const { iterator p; p.m_p = m_first; return p; }

   

    iterator end  () const { iterator p; p.m_p = 0;      return p; }

 

    list& operator=(const list& LO);   

    void move(list& L);

    void swap(list& L);  

    void insert(iterator position, const T& v);

    void remove(const T& v);

 

    friend std::ostream& operator<< (std::ostream &, const list& );

    friend std::istream& operator>> (std::istream &,       list& );

 

    friend bool check_ok( const list& );

 

·          private:

    friend node * prev_node( const list& L, const node * p );

    friend node * last_node( const list& L);

 

·          private:

    node * m_first; 

 

 

Clase ADH_list.cpp

·          bool check_ok( const list & L )

·          void list::push_front( const T& v )

·          void list::push_back(  const T& v )

·          void list::pop_front()  

·          void list::pop_back()

·          void list::clear()

·          list::node * last_node( const list& L )

·          list::node * prev_node( const list& L, const list::node * p )

·          list& list::operator=(const list& LO)

·          void list::swap(list& L)

·          void list::move(list& LO)

·          void list::insert(list::iterator p, const T& v)

·          void list::remove(const T& v)

·          std::ostream& operator<< (std::ostream &COUT, const list& L)

·          std::istream& operator >> (std::istream &CIN, list& r)

 

   

 

 

Clase USE_list.cpp

·          int main() {

int a[] = { 2, 6, 4, 8 };

    const int SIZE = sizeof(a) / sizeof(a[0]);

    list LV, LO;

 

    printList( LV );

 

    LV.push_front( 1 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_front( 2 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_front( 5 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_back( 4 );     printList( LV );

    cout << ( * LV.last() );

 

    LV.push_back( 3 );     printList( LV );

    cout << ( * LV.last() );

 

 

    cout << "LV contains: ";

    printList( LV );

 

    (* LV.last() ) = 18;

    printList( LV );

 

    cout << "\nLV after sorting contains: ";

    printList( LV );

 

    cout << "\nLO contains: ";

    printList( LO );

 

    cout << "\nLV contains: ";

 

    LV.pop_front();

    LV.pop_back();  

    cout << "\nAfter pop_front and pop_back LV contains:\n";

    printList( LV );

 

    LV.swap( LO );

    cout << "\nAfter swap:\n   LV contains: ";

    printList( LV );

    cout << "\n   LO contains: ";

    printList( LO );

 

    LV.remove( 4 );

    cout << "\nAfter remove( 4 ) LV contains: ";

    printList( LV );

    cout << endl;

    return 0;

}

 

 

Invariante de la Clase

 

     Las invariantes de este programa son:

1.      La lista nula siempre tiene un valor correcto.

2.      El valor "m_val" almacenado en un nodo de la lista no contiene un valor correcto.

 Las invariantes del programa son verificadas mediante la siguiente instrucción:

                                              bool check_ok ( const list & L

            la cual:

·                     Regresa "true" si "L" contiene un valor correcto.

·                     Podría retornar "true" aún cuando "L" tenga su valor corrupto.

·                     Podría no retornar si "L" tiene su valor corrupto.

 

Arquitectura Interna

 

            Este programa consiste en la implementación y especificación de un programa con el que se pueda realizar el insertar y el borrar de una lista, se presentan dos listas, la llamada LV y la lista LO, el programa funciona mediante el llamado al compilador del editor del Visual Sutiio.NET esto mediante la implementación de un archivo llamado ADH_port que permite el uso de cualquier compilador entre el Studio 6.0 el .Net y el Borland, sin embargo el programa puede que presente problemas a la hora de compilarlo en el Visual Studio6.0, a continuación se implementa la clase ADH_list.h que permite la definición de las funciones más importantes para la realización de este programa, a esta  se unen los archivos ADH_list.cpp y USE_list.cpp la cual contiene a la función principal para la ejecución del programa. Seguidamente se da la ejecución del programa y se presentan los casos de insertado y borrado, se tienen las lista se insertacambian sus valores y se les puede agregar o eliminar valores, sin embargo, para el usuario puede resultar la realización puesto que necesitaría conocer como funciona el programa, pero se presentará más adelante en la eficiencia con que cuenta el programa.

 

Compilador Usado

·         Para la ejecución del programa fue utilizado el compilador del Visual Studio.NET C++.

 

Cómo Compilar el Programa?

            Primero que todo, se debe buscar si en su computador está instalado un compilador de C++, compatible, en nuestro caso, utilizamos el visual Studio 6.0, para verificar, haga clic en el botón inicio, váyase a archivos de programas, y búsquelo si no, es así puede estar alojado en el archivo, desarrollo, una vez encontrado, haga clic en el icono perteneciente al Visual en este caso, ya abierto el programa, y sin la necesidad de haber creado primeramente un proyecto váyase a files, dele clic en el botón open, y seleccione los archivos conjunto para poder compilarlos, claro, está es necesario tener los archivos guardados ya sea en su computador, o bien en un disquete o CD, una vez ubicados los archivos haga clic en abrir, e inmediatamente le aparecerán los archivos dentro del visual, ya sea que los vaya abriendo uno por uno, o todos a la vez. Ya hecho esto, digite control + f7 o bien al lado izquierdo dentro de la barra superior hay un icono con una flechita para abajo, esto le permitirá compilar el programa, seguidamente, digite f7, para darle build y tener listo el programa, seguidamente seleccione control + f5 y su programa se ejecutará, si no se ejecuta inmediatamente podrá ser porque necesita el proyecto, sin embargo el computador se lo hará saber, mediante una ventanita de advertencia, haga clic en sí, y eso permitirá que se cree, permitiendo la ejecución del programa.

 

Guía de Uso del Programa

 

            En el caso de que quiera bajar el programa de internet, que lo puede encontrar en www.angelfire.com/freak3/a34418 o www.angelfire.com/moon2/a43493 , en el link de tareas, haga clic si desea guardarlo o si desea abrirlo, seguidamente guárdelo en un dispositivo, abra el visual Studio, compílelo, y seguidamente ejecútelo.

 

Datos de Prueba del Programa

 

            Formato de los Datos de Prueba        

Los datos de prueba consiste en las diferentes formas en que es posible insertar o eliminar distintos tipos de datos, por ejemplo si se deseara insertar un carácter como una letra o un símbolo, el programa se caería, puesto que está implementado para la utilización de datos enteros, además si el número excediera la longitud de las entradas definidas long, pues no funcionaría y mandaría una alerta de que el número excede la capacidad de almacenamiento de un long.

 

 

 

 

 

 

Entradas vs Salidas Esperadas

 

()(1)1(2, 1)1(5, 2, 1)1(5, 2, 1, 4)4(5, 2, 1, 4, 3)3LV contains: (5, 2, 1, 4, 3)

(5, 2, 1, 4, 18)

LV after sorting contains: (5, 2, 1, 4, 18)

LV contains: (5, 2, 1, 4, 18)

LV contains:

After pop_front and pop_back LV contains:

(2, 1, 4)

After swap:

   LV contains: ()

   LO contains: (2, 1, 4)

After remove( 4 ) LO contains: (2, 1)

()

After insert( 7 ) LV contains: (7)

(7)

After insert( 50 ) LV contains: (50, 7)

(50, 7)

After insert( 40 ) LV contains: (50, 7, 40)

(50, 7, 40)

After insert( 7000 ) LV contains: (50, 7, 40, 7000)

Press any key to continue

 

                Código Fuente

/* ADH_list.cpp (C) 2005  adolfo@di-mare.com  */

 

/** \file  ADH_list.cpp

    \brief Implementaciones para la clase \c "ADH::list"

 

    \author Adolfo Di Mare <adolfo@di-mare.com>

    \date   2005

*/

 

 

#include "ADH_list.h"

 

OPEN_namespace( ADH ) // namespace ADH {

 

/** Verifica la invariante de la clase \c "list"

 

    - Regresa \c "true" si \c "L" contiene un valor correcto.

 

    - Podría retornar \c "true" aún cuando \c "L" tenga su valor corrupto.

 

    - Podría no retornar si \c "L" tiene su valor corrupto.

 

    \par Rep Diagrama de la clase

    \code

                                                  NULL

                +-----+---+   +-----+---+   +-----+---+

    L.m_first-->| v_1 | *-|-->| v_2 | *-|-->| v_3 | 0 |

                +-----+---+   +-----+---+   +-----+---+

                m_val  next                      /\

                                                 ||

                                            last_node(L)

    \endcode

 

    \par Descripción en palabras

    - Una lista es una secuencia de nodos enlazados del primero al último.

    - El último nodo tiene su campo \c "next" en nulo [puntero \c (0)].

    - Para que el valor de la lista sea correcto es necesario que

      cada uno de los valores almacenados en la lista sea correcto.

    - El campo \c "next" no se llama \c "m_next" porque en los libros

      de texto el nombre que aparece siempre es \c "next".

 

    \par Descripción en símbolos

    - (this->m_first == 0) || (this->m_first == p ) apunta a un nodo

    - Para cada node de una lista

      (p->m_val es correcto && (p->next == 0 || p->next apunta a un node válido )

 

    \pre Obliga al programador cliente a implementar la función

          \c bool check_ok( const T & );

*/

bool check_ok( const list & L ) {

    if ( L.m_first == 0 ) {

        return true; /// - Invariante: la lista nula siempre tiene un valor correcto

    }

 

    list::node * p = L.m_first;

    while ( p != 0 ) {

        if ( ! check_ok( p->m_val ) ) {

            return false; /// - Invariante: El valor \c "m_val" almacenado en un nodo de la lista no contiene un valor correcto

        }

        p = p->next;

    }

    return true;

}

 

/// Agrega una copia del valor "v" al principio de la lista "*this"

void list::push_front( const T& v ) {

    if (m_first == 0) {

        this->m_first = new node(v);

        m_first->next = 0;  // (*m_first).next = 0;

    }

    else {

        node *p;

        p = new node(v);

        p->next = m_first;  // (*p).next = (*this).m_first;

        m_first = p; // this->m_first = p;

    }

} // list::push_front()

 

/** Agrega una copia del valor \c "v" al final de la lista \c "*this"

 

    \par Complejidad

    - O ( \c size() )

*/

void list::push_back(  const T& v ) {

 

    if ( empty() ) {

        m_first = new node(v);

        m_first->next = 0;  // (*m_first).next = 0;

    }

    else {

        node * p = last_node( *this );

        p->next = new node(v);

        p->next->next = 0;

    }

} // list::push_back()

 

/** Elimina el valor del principio de la lista

 

    \pre

    \c !empty()

*/

void list::pop_front() {

    #if defined(NDEBUG)

    //  #define NDEBUG ==> Activo para obtener al versión de producción

        if ( empty() ) {

            throw (BOOOM!!!);

        }

    #endif

 

    node *p = m_first;    // recuerda adónde está el siguiente node

    m_first = m_first->next;

 

    delete p;

} //  list::pop_front()

 

/** Elimina el valor del final de la lista

 

    \pre

    \c !empty()

 

    \par Complejidad

    - O ( \c size() )

*/

void list::pop_back() {

    #if defined(NDEBUG)

        if ( empty() ) {

            throw (BOOOM!!!);

        }

    #endif

 

    // avanza hasta el final

    node *p = m_first;

    node *q = 0;    // valor anterior de "p"

    while (p->next != 0) {

        q = p;

        p = p->next;

    }

 

    if (q == 0) { // nunca se entró al ciclo while()

        // Sólo queda un node en la lista

        delete m_first; // mata al node

        m_first = 0;    // marca la lista como vacía

    }

    else {

       q->next = 0;

       delete p;

    }

} //  list::pop_back()

 

void list::clear() {

    #if 0

        while ( ! empty() ) { // No se le meta al Rep

            pop_front();      // - es "menos" eficiente

        }

    #endif

 

    #if 1

        while ( ! empty() ) {  // SI se le meta al Rep

            node *p = m_first;     // a la larga vale la pena que

            m_first = m_first->next;  // pop_front() sea inline...

            delete p;

        }

    #endif

} // list::clear()

 

/** Retorna el puntero al último nodo de la lista

 

    \pre

     <code>!L.empty()</code>

*/

list::node * last_node( const list& L/*, const list::node * p */) {

    list::node *p = L.m_first;

    while (p->next != 0) {

        p = p->next;

    }

    return p;

} // last_node()

 

/** Retorna el puntero al nodo anterior

 

    Devuelve un puntero al nodo anterior al que \c "p" apunta.

    - Retorna \c "0" si \c "p" es el primer nodo de la lista \c "L".

 

    \pre

    - \c "*p" debe ser uno de los nodos de la lista

    - <code>(p != 0) && (! empty())</code>

 

    \remark

    Aunque es correcto implementar esta función como un método,

    está implementada como función para destacar el hecho de

    que es necesaria la lista \c "L" para poder buscar el nodo

    anterior a \c "p" a partir del nodo \c "L,m_first".

 

    \remark

    Como la lista "L" está enlazada en una sóla

    dirección, para encontrar el antecesor  de un nodo es

    necesario recorrer toda la lista. Si se necesita usar

    una lista para la que el tiempo de ejecución de esta

    operación es O(1), entonces es necesario usar una

    lista doblemente enlazada.

*/

 list::node * prev_node( const list& L, const list::node * p ) {

    if (p == L.m_first) {

        return 0;

    }

 

    list::node* q;

    q  = L.m_first; // busca desde el principio de la lista

    while (q != 0) {

        if ( p == q->next ) {

            return q;

        }

        q = q->next;

    }

 

    return 0;

} // prev_node()

 

list& list::operator=(const list& LO) {

    if (&LO == this) {

        return *this; // evita autocopia

    }

 

    // borra todo

    while ( ! empty() ) {

        pop_front();

    }

 

    // copia

    node *p = LO.m_first;

    while (p != 0) {

        push_back(p->m_val);

        p = p->next;

    }

    return *this;

/*  nota

    Esta implementación es un poco lerda, pues sería más eficiente

    no devolver todos los nodos de *this, y reutilizarlos para

    almacenar ahí la copia de los valores que están en "LO".

    - Esta lista es más didáctica que eficiente...

*/

} // list::operator=()

 

/// Intercambia <code>*this <==> L</code>

void list::swap(list& L) {

    node *tmp = L.m_first;

    L.m_first = m_first;

    m_first = tmp;

}

 

/// Traslada el valor de \c "LO" a \c "*this"

void list::move(list& LO) {

    if (&LO == this) {

        return; // evita autocopia

    }

 

    // borra todo

    while ( ! empty() ) {

        pop_front();

    }

 

    m_first    = LO.m_first;    // le roba a LO todos sus valores

    LO.m_first = 0;

}

 

#include <assert.h>

 

/** Agrega el valor \c "v" al contenedor

 

    - El valor agregado queda antes de la posición \c "p" en el contenedor.

    - Si <code>p==this->end()</code> el valor queda al final de la lista.

 

    \par Complejidad

    - O ( \c size() )

*/

void list::insert(list::iterator p, const T& v) {

   

    node* q = new node(v);

    if ( m_first==0 ) { // push_front(v)

        q->next = 0;

        m_first = q;

    }

    else if ( m_first==p.m_p ) { // push_front(v)

        q->next = m_first;

        m_first = q;

    }

    else if ( p.m_p==0 ) { // push_back(v)

        node *last = last_node( *this );

        q->next    = 0;

        last->next = q;

    }

    else {

        node *prev = prev_node(*this, p.m_p);

        q->next = prev->next;

        prev->next = q;

    }

} // list::insert()

 

#include <assert.h>

 

/// Elimina cada uno de los valores iguales a "v"void list::remove( const T& v) {

      node *q = new node(v);

      node *temp = new node(v);

      q = m_first;

      temp= m_first;

      if(m_first==0){

            return;

      }

 

      if(m_first->m_val==v){

            m_first= m_first->next;

          delete (q);

      }

      else{

            q=q->next;

            while (q!=0){

                  if(q->m_val==v){

                        temp->next=q->next;

                        delete (y);

                        q=temp->next;

                  }

                  else{

                        q= q->next;

                        temp=temp->next;

                            

                  }

                 

} // list::remove()

 

/** Graba el valor de \c "L" en el flujo \c "COUT".

 

    - En particular, este es el operador que se invoca

      cuando se usa, por ejemplo, este tipo de instrucción:

      \code

      COUT << L << LO;

      \endcode

*/

std::ostream& operator << (std::ostream &COUT, const list& L) {

#if 1

    COUT << "(";

    list::node *p = L.m_first;

    while (p != 0) {

        COUT << p ->m_val;

        if (! (p->next == 0) ) { // ¿último node de la lista?

           COUT << ", ";

        }

        p = p->next;

    }

    COUT << ")";

#endif

 

#if 0

    list::iterator p;     // recorre la lista

    list::iterator endL;  // después de la lista

 

    COUT << "(";

 

    p    = L.begin();  // p.operator= ( Lista.begin() );

    endL = L.end();    // generalmente NULL==0

 

    for ( ; p != endL; ++p) {

        COUT << ( *p );

        if (p != L.last() ) {

            cout << ", ";

        }

    }

 

    COUT << ")";

#endif

 

#if 0

    COUT << "(";

    list::node *p = L.m_first;

    while (p != 0) {

        cout << p ->m_val;

        if (! (p->next == 0) ) { // ¿último node de la lista?

           cout << ", ";

        }

        p = p->next;

    }

    COUT << ")";

#endif

 

#if 0

    if ( L.empty() ) {

        COUT << "()";

    }

    else {

        list LO;

        LO = L; // Hace una copia

        COUT << "(";

        while (! LO.empty()) {

            T val = *LO.first();

            cout << "  " << val;

            LO.pop_front();

        }

        COUT << ")";

    }

#endif

 

#if 0

    COUT << "(";

    for (list LO = L; ! LO.empty(); LO.pop_front() ) {

        T val = *LO.first();

        cout << "  " << val;

    }

    COUT << ")";

#endif

 

    return COUT;

}  // operator <<

 

#include <assert.h>

 

/** Lee del flujo de texto \c "CIN" el valor de \c "r"

    \remark

    Requiere de algún buen samaritano lo implemente.

*/

std::istream& operator >> (std::istream &CIN, list& r) {

    assert( false && "operator >> (istream &, list& r) ==>NO IMPLEMENTADO");

 

    return CIN;

}  // operator >>

 

CLOSE_namespace( ADH )  // } // namespace ADH

 

// EOF: ADH_list.cpp

// USE_list.cpp (choriceado de)

 

// Fig. 20.17: fig20_17.cpp

// Testing Standard Library class list

 

/// \file USE_list.cpp Usan la lista polimórfica de Adolfo

 

 

#define  INCLUDE_iostream

#include "ADH_port.h"

 

#include "ADH_list.h"

 

USING_namespace( ADH ); // using namespace ADH;

USING_namespace( std ); // using namespace std;

 

/// Graba en \c "cout" el contenido de \c "L"

inline void printList( const list& L ) {

    cout << L;

}

 

/// Función principal en la que empieza la ejecución del programa

int main() {

    int a[] = { 2, 6, 4, 8 };

    const int SIZE = sizeof(a) / sizeof(a[0]);

    list LV, LO;

 

    printList( LV );

 

    LV.push_front( 1 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_front( 2 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_front( 5 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_back( 4 );     printList( LV );

    cout << ( * LV.last() );

 

    LV.push_back( 3 );     printList( LV );

    cout << ( * LV.last() );

 

 

    cout << "LV contains: ";

    printList( LV );

 

    (* LV.last() ) = 18;

    printList( LV );

 

//  LV.sort();

    cout << "\nLV after sorting contains: ";

    printList( LV );

 

// LV.insert( LV.begin(), 7 );

    cout << "\nLV contains: ";

    printList( LV );

 

//  LV.sort();

    cout << "\nLV contains: ";

 

    LV.pop_front();

    LV.pop_back();   // all sequence containers

    cout << "\nAfter pop_front and pop_back LV contains:\n";

    printList( LV );

 

    // method swap is available in all containers

    LV.swap( LO );

    cout << "\nAfter swap:\n   LV contains: ";

    printList( LV );

    cout << "\n   LO contains: ";

    printList( LO );

 

    LO.remove( 4 );

    cout << "\nAfter remove( 4 ) LO contains: ";

    printList( LO );

    cout << endl;

 

      LO.remove( 1 );

    cout << "\nAfter remove( 1 ) LO contains: ";

    printList( LO );

    cout << endl;

 

    printList( LO );

    LO.insert( LO.begin(), 8 );

    cout << "\nAfter insert( 8 ) LO contains: ";

    printList( LO );

    cout << endl;

 

      printList( LO );

    LO.insert( LO.end(), 20 );

    cout << "\nAfter insert( 20 ) LO contains: ";

    printList( LO );

    cout << endl;

 

      printList( LO );

    LO.insert( LO.end(), 16 );

    cout << "\nAfter insert( 16 ) LO contains: ";

    printList( LO );

    cout << endl;

 

    printList( LV );

    LV.insert( LV.begin(), 89 );

    cout << "\nAfter insert( 89 ) LV contains: ";

    printList( LV );

    cout << endl;

   

      printList( LV );

    LV.insert( LV.begin(), 50 );

    cout << "\nAfter insert( 50 ) LV contains: ";

    printList( LV );

    cout << endl;

     

      printList( LV );

    LV.insert( LV.end(), 13 );

    cout << "\nAfter insert( 13 ) LV contains: ";

    printList( LV );

    cout << endl;

     

      printList( LV );

    LV.insert( LV.end(), 9000 );

    cout << "\nAfter insert( 9000 ) LV contains: ";

    printList( LV );

    cout << endl;

   

      return 0;

}

 

// EOF: USE_list.cpp

 

/* ADH_list.h  (C) 2005  adolfo@di-mare.com  */

 

/** \file  ADH_list.h

    \brief Lista simple de nodos con puntero final nulo

 

    \author Adolfo Di Mare <adolfo@di-mare.com>

    \date   2005

*/

 

 

#ifndef ADH_list_h

#define ADH_list_h   ///< Evita la inclusión múltiple

 

#define  INCLUDE_iostream

#include "ADH_port.h"

 

#include "Tdef.h" // truco para usar pseudo-plantillas

#include <istream>

#include <ostream>

 

OPEN_namespace( ADH ) // namespace ADH {

 

/** Lista simple de nodos con puntero final nulo

 

    - Esta clase tiene varias de las operaciones más importantes

      de la clase \c "std::list" de la biblioteca estándar de C++.

 

    - Es la que usan los estudiantes de Adolfo para aprender.

*/

class list {

    public: class node;

    public:  class iterator;

    friend   class iterator;

 

public:

    /// Nodos de la clase \c "list"

    class node {

        friend class list;

        friend class iterator;

 

        node(const T& v) : m_val(v) { /* next = 0; */ } ///< Constructor para \c "v"

 

    private:

      //    friend std::istream& operator<< (std::ostream &, const list& );

        friend std::ostream& operator<< (std::ostream &, const list& );

        friend bool check_ok( const list & L );

        friend node * prev_node( const list& L, const node * p );

        friend node * last_node( const list& L);

    private:

        T     m_val;  ///< Valor almacenado en el nodo

        node * next; ///< Puntero al siguiente nodo

    };  // node

 

public:

    /// Iteradores simples hacia adelante (<em>forward</em>) para la clase \c "list"

    class iterator {

        friend class list;

    public:

        iterator() : m_p(0) { /* inicializo, como los de STL */ } ///< Constructor

 

        /// Constructor de copia

        iterator( const iterator& o)

             { m_p = o.m_p;}  // copia el Rep directo

        iterator& operator=( const iterator& ); ///< Copia

 

        friend bool operator == ( const iterator&, const iterator& );

        friend bool operator != ( const iterator&, const iterator& );

 

        iterator operator++()

            { m_p = m_p -> next; return *this; }                   ///< \c ++p

        iterator operator++(int)

            { iterator q = (*this); m_p = m_p -> next; return q; } ///< \c p++

 

        T& operator*()  { return   m_p -> m_val ; } ///< \c *p

        //T* operator->() { return &(m_p -> m_val); } ///< \c p->

 

    private:

        node * m_p;   ///< Puntero al nodo de \c "list"

    }; // list::iterator

 

public:

    list() : m_first(0) { } ///< Constructor de vector

    list(const list& L) : m_first(0) { *this = L; } ///< Constructor de copia

    ~list() { clear(); } ///< Destructor

    void clear(); ///< Elimina los valores del contenedor y lo deja vacío

 

    void push_front( const T& v );

    void push_back(  const T& v );

 

    void pop_front();

    void pop_back();

 

    bool empty() const;      ///< Retorna "true" si la lista está vacía

    iterator first() const;  ///< Denota al primer valor de la lista

    iterator last()  const;  ///< Denota al último valor de la lista

 

    /// Denota al primer valor de la lista

    iterator begin() const { iterator p; p.m_p = m_first; return p; }

    /// Denota el valor que ya está fuera del contenedor

    iterator end  () const { iterator p; p.m_p = 0;      return p; }

 

    list& operator=(const list& LO); ///< Copia ==> <code>L = LO</code>

    void move(list& L);

    void swap(list& L);   // Intercambia <code>*this <==> L</code>

 

    void insert(iterator position, const T& v);

    void remove(const T& v);

 

    friend std::ostream& operator<< (std::ostream &, const list& );

    friend std::istream& operator>> (std::istream &,       list& );

 

    friend bool check_ok( const list& );

 

private:

    friend node * prev_node( const list& L, const node * p );

    friend node * last_node( const list& L);

 

private:

    node * m_first;  ///< Puntero al primer nodo de la lista

}; // list

 

inline bool list::empty() const {

    return (m_first == 0);

 

 

/// Primer valor de la lista

}

 

inline list::iterator list::first() const {

    list::iterator p;

    p.m_p = m_first;

    return p;

} // list::first()

 

/// Denota el último valor de la lista

inline list::iterator list::last() const {

    list::iterator p;

    p.m_p = ( m_first == 0 ? 0 : last_node( *this ) );

    return p;

} // list::last()

 

/// Copia

inline list::iterator& list::iterator::operator= (

    const list::iterator& o

) {

    m_p = o.m_p; // copia el Rep directo

    return *this;

}

 

/// ¿ <code>p == q</code> ?

inline bool operator == (

    const list::iterator& p,

    const list::iterator& q

) {

    return p.m_p==q.m_p;

}

/// ¿ <code>p != q</code> ?

inline bool operator != (

    const list::iterator& p,

    const list::iterator& q

) {

    return !(p==q); // return operator == (p, q);

}

 

#if 0

        iterator( const iterator& o) // ; // constructor de copia

             { m_p = o.m_p;}  // copia el Rep directo

 

inline list::iterator( const list::iterator& o ) {

//  constructor de copia

    m_p = o.m_p; // copia el Rep directo

}

#endif

 

CLOSE_namespace( ADH ) // } // namespace ADH

 

#endif // _list_h

 

// EOF: ADH_list.h

 

 

 

 

           

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Bibliografía

*  Deitel, Harvey M. y Deitel, Paul J. Cómo programar en C++. Cuarta Edición. Editorial Prentice Hall. México 2003.

*      Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994. 
      http://www.di-mare.com/adolfo/p/list.htm
*  Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica,1994.
                  http://www.di-mare.com/adolfo/p/list.htm
*  Di Mare, Adolfo. La implementación de Rational.pas. Reporte Técnico ECCI-94-03. Proyecto 326-89-019