Estructura de Datos

Implementación. Programación. Computación. Clase vector. Listas. Lenguajes de programación. Módulos. Interfaces. Archivos usados. Entrada y salida

  • Enviado por: KarolJ
  • Idioma: castellano
  • País: Costa Rica Costa Rica
  • 9 páginas
publicidad

Universidad de Costa Rica


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

Programación II
CI-1201

Manual de Uso
Tarea Programada # 2
Clase vector implementada con base en la clase lista

 

DOCUMENTACIÓN EXTERNA

 

Autora:

Carnet:

Grupo: 03

Profesor:

Marzo, 2004

 

1.Introducción

Para un programador, es sumamente importante poder manejar datos de una manera

ágil, ya que la mayoría de los programas que se implementan contienen diferentes tipos

de datos, y a veces se hace difícil porder manipularlos.

El lenguaje de programación C++ permite a los programadores utilizar una clase,

de la biblioteca estándar, llamada vector. Un vector puede definirse para almacernar

cualquier tipo de dato (int, bool, float, entre otros), esta clase hace un uso extenso de

operadores sobrecargados, y con ella se pueden crear clases robustas que nos ayudan

a manejar conjuntos de datos, de manera que podamos ordenarlos, llamarlos mediante

subíndices, entre otras cosas que facilita su manipulación.

Por otra parte, una lista es una estructura de datos dinámica que crece y se reduce

durante la ejecución. Esta estructura es una colección de elementos de datos, los cuales

están alineados en una fila, y se pueden quitar y poner elementos en cualquier lugar de

la lista. Estos elementos son conocidos como nodos. Con una lista también es posible

manipular fácilmente distintos tipos de datos.

Con base en una clase lista, es posible implementar correcta y satisfactoriamente una

clase vector. Es esto lo que se pretende con en el desarrollo de este trabajo.

'Estructuras de datos'
Esta documentación es posible encontrarla en la siguiente dirección electrónica:

2. Descripción del problema a resolver

f

Trabajo a realizar:

Esta tarea es individual. El objetivo de esta tarea programada es que usted diseñe e

implemente una clase completa, junto con sus programas de prueba.

Uno de los problemas que el lenguaje C++ tiene es que no permite usar vectores y matrices de tamaño variable, pues las dimensiones de todos los arreglos deben ser definidos en tiempo de compilación. Para remediar esta carencia, C++ le ofrece al programador la posibilidad de usar sobrecarga de operadores para simular el uso de vectores sobre estructuras de datos más sofisticadas, como la lista.

Su trabajo consiste en especificar e implementar la clase "vector" que permita administrar un vector de tamaño variable aunque para el programador cliente parezca un arreglo.

class vector {

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

void Eliminar_Final (size_t); // Eliminar elementos al Final

void Eliminar_Principio(size_t); // Eliminar elementos al principio

T & operator[] (size_t); // V[i]

size_t Capacidad() const;

size_t Dimension() const;

}; // vector


En la clase vector lo más importante es el método e "vector::operator[]()" que se encarga de retornar una referencia al i-ésimo componente del vector. Los otros métodos sirven para hacer que crezca o disminuya de tamaño el vector.

Para mostrar que su vector funciona, use la función "rand()" para generar varias secuencias de al menos 1,000,000 de números y luego aplíqueles el algoritmo "qsort()" para ordenarlos.

3. Planteamiento del problema

Para lograr la implementación de la clase vector, es necesario primero estudiar y entender

el funcionamiento de la clase lista ya implementada.

'Estructuras de datos'
Primer documento: ADH_list.cpp

Tabla #1.

Describe los métodos más relevantes de la clase ADH_list en el documento ADH_list.cpp

Nombre del método

Resultado

void ADH_list:: k_slice (int k)

Traslada al principio de la lista sus últimos K

valores, pero sin copiarlos, medinate cirugía de

punteros.

void ADH_list:: push_front(const T& v)

Agrega el valor al principio de la lista "*this".

void ADH_list:: push_back(const T& v)

Agrega el valor al final de la lista "*this".

void ADH_list:: pop_front()

Elimina el valor del principio de la lista. Requiere

que la lista *this no esté vacía.

void ADH_list:: pop_back()

Elimina el valor del final de la lista. Requiere que

la lista *this no esté vacía.

ADH_list:: ~ADH_list()

Es el destructor. Elimina todos los nodos de la lista.

ADH_list::nodo*ADH_list::last_node() const

Retorna el puntero al último nodo de la lista.

ADH_list&ADH_list::operator=(const ADH_list)&LO

Hace L = LO.

void ADH_list::swap(ADH_list & L)

Intercambia *this <==> L.

void ADH_list::move(ADH_list & LO)

Traslada el valor de L a *this.

void printList (const ADH_list & L)

Graba en "count" el valor contenido en "L".

En este documento se hace uso del #include "ADH_list.h", es decir, "incluye" el


'Estructuras de datos'
Segundo documento: ADH_list.h

En ADH_list hay varios datos relevantes:

En este documento se declara class ADH_list; es decir, se declara la lista ADH_list.

También se declara el primer nodo de la lista mediante la instrucción class nodo;. Se define

friend class ADH_list; lo cual quiere decir que la clase nodo tiene derecho a acceder a los

miembros no públicos de la clase ADH_list, y accede al método printList (const ADEH_list &);.

Declara como miembros privados a T _val; (Tipo valor), y nodo * next; (siguiente nodo). Declara

también los siguientes métodos, entre otros:

1. iterator ();

2. InOut

3. push_front los métodos numerados del 1 al 6 tienen el mismo

4. push_back resultado que en ADH_list.cpp.

5. pop_front

6. pop_back

7. bool empty() const;

8. iterator first () const; el cual denota al primer valor de la lista.

9. iterator last () const; el cual denota al último valor de la lista.

10.inline ADH_list::iterator ADH_list::first () const

El cual obtiene una copia del primer valor de la lista.

11.inline ADH_list::iterator ADH_list::last () const

El cual obtiene una copia del último valor de la lista.

Se declaran otros métodos inline.

La lista maneja datos de tipo int (enteros) mediante los métodos e instrucciones nombradas

anteriormente. En base a esto se debe implementar la clase vector, la cual debe poder realizar

las mismas funciones de la clase lista.


4. Definición de módulos e interfaces

El vector va a tener una capacidad de n elementos, todos de tipo T, mediante los diversos

módulos el programados cliente será capaz de manipular estos elementos como si estuviera

trabajando en un arreglo (la lista).

Hay cuatro módulos relevantes que son:

1. Agregar_Final

2.Agregar_Principio

3.Eliminar_Final

4.Eliminar_principio

Estos módulos permiten la variabilidad del tamaño del vector durante la ejecución.

Hay un módulo muy importante, que es el cual permite referenciar el i-ésimo elemento del

vector, es decir, nos permite manipular cualquier elemento del vector, ya sea el primero, el

último o el i elemento del vector; éste es el llamado operator[ ].

Esta relación es la invariante de la clase.

Ilustraciones:


5. Análisis de la implementación

En el archivo principal del programa "vec_vec.cpp":

Hay dos constructores, primero el constructor de la clase y segundo, el constructor por

defecto de vector. Hay un destructor, el cual "mata" a los elementos del vector que ya han sido

eliminados, así libera memoria.

También hay métodos que permiten agregar elementos al principio o al final del vector, y

eliminar elementos del principio o del final del vector, hay un método operator[ ], que refiere

al elemento v[i] del vector, éste método recorre el vector y cuenta los elementos, hasta llegar

al i elemento y retorna la posición de dicho elemento.

El archivo "Tdef.h" define el dato tipo T como long.

El programa ha sido compilado en el compilador Borland C++, si el programador cliente lo

desea, puede usar el Visual C++.

Esto es, en resumen, lo que hace la implementación correcta del vector.

6. Descripción de archivos usados

La clase vector se implementa en tres archivos, a saber:

El principal: vec_vec.cpp. En este archivo se incluye el vec_vec.h mediante

#include "vec_vec.h". A su vez, en el vec_vec.h se incluye el Tdef.h (#include "Tdef.h").

En los tres archivos se implementan los métodos necesarios para el funcionamiento del

vector de la misma manera que la lista.

Mediante un diagrama podemos observar las relaciones de las partes que interactúan en el

programa:

Tdef.h =========)>vec_vec.h

¦¦ ¦¦

vec_vec.cpp<(===¦¦

¦¦

vec_vec.obj

¦¦

VEC_VEC.exe

El archivo vec_vec.obj se crea al compilar, y el VEC_VEC.exe, es el ejecutable del proyecto

del programa.

 

7. Descripción de entradas y salidas

Se debe dar como dato de entrada, la n cantidad de elementos con que se construye el

vector, el número de tipo T que se desea manipular, ya sea agregar o eliminar, y el elemento

i de tipo T que se desea referenciar.

El resultado será una linea de elementos, los cuales son datos de tipo T, que se reordenarán

dependiendo del método que se utilice al ejecutar el programa.

Ej. n = 5

El programa, mediante la función rand() genera 5 números distintos:

3, 9, 6, 5, 45

Si uso el método Agregar_final ( 1 );

el programa me devolverá la siguiente línea de elementos:

3, 9, 6, 5, 45, 1

Así se puede notar la variación del tamaño del vector.

8. Requerimientos especiales

El programa necesita tener una capacidad n de elementos, es decir, el vector no puede estar vacío. Los datos de entrada deben ser números, no se pueden introducir literales como datos de entrada. El vector puede tener el tamaño que el programador cliente desee, incrementar el tamaño del vector cuántos elementos necesite agregar, o disminuirlo según los elementos que elimine.

Para ejecutar el programa, debe crearse un proyecto que incluya el archivo vec_vec.cpp, y en la misma carpeta en que se encuentra el vec_vec.cpp, debe estar el vec_vec.h y el Tdef.h.

9. Reconocimientos

Se reconoce la labor realizada por el profesor Adolfo Di Mare al realizar el trabajo llamado "Convenciones de programación para Pascal", ya que gracias a dicho documento se ha logrado la elaboración de este trabajo. Gracias al profesor por poner a nuestra disposición tan valiosa información.

10. Bibliografía

Deitel, Harvey M. y Deitel, Paul J., C++ Cómo Programar, Pearson educación, Cuarta edición, México, 2003.

Di Mare, Adolfo: Convenciones de Programación para Pascal, Reporte Técnico ECCI-01-88, Proyecto 326-86-053, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1988.

Di Mare, Adolfo: Reutilización de Contenedores Parametrizables con Lenguajes de Semántica Limitada, Capítulo 3: Abstracción en Pascal, 1999.

11. Glosario e índice

Implementación: grupo de instrucciones imperativas a ser ejecutadas por el computador.

Invarinate: Para almacenar en el computador los valores del ADT es necesario agregar varios campos, y escoger una o más formas de interrelación entre ellos. Esta organización de los campos del ADT constituye su "representación privada", mejor conocida por el acrónimo "Rep". a la relación que siempre deben cumplir los campos del Rep se le conoce como la invariante del tipo de datos.

Método: las rutinas que están encapsuladas en el tipo de datos que se conocen como "Procedimiento Miembro". Rutina que sirve para manipular, examinar o cambiar un dato.

Módulo: es una sección e un programa bien construida, con un fin específico, y que puede ser reutilizado.

 

Indice:

1.Introducción

2.Descripción del problema a resolver

3.Planteamiento del problema

4.Definición de módulos e interfaces

5.Análisis de la implementación

6.Descripción de archivos usados

7.Descripción de entradas y salidas

8.Requerimientos especiales

9.Reconocimientos

10.Bibliografía

11.Glosario e índice

FIN