LA NECESIDAD DE LAS ESTRUCTURAS DE DATOS

A pesar de la gran potencia de las computadoras actuales, la eficiencia de los programas sigue siendo una de las características más importantes a considerar. Los problemas complejos que procesan las computadoras cada vez más obligan, sobre todo, a pensar en su eficiencia dado el elevado tamaño que suelen alcanzar. Hoy, más que nunca, los profesionales deben formarse en técnicas de construcción de programas eficientes.

En sentido general, una estructura de datos es cualquier representación de datos y sus operaciones asociadas. Bajo esta óptica, cualquier representación de datos, incluso un número entero o un número de coma flotante almacenado en la computadora, es una sencilla estructura de datos.

En un sentido más específico, una estructura de datos es una organización o estructuración de una colección de elementos dato. Así, una lista ordenada de enteros almacenados en un array es un ejemplo de dicha estructuración.

Las estructuras de datos pueden estar anidadas: se puede tener una estructura de datos que conste de otras. Por ejemplo:

La mayoría de los lenguajes de programación soporta diferentes estructuras de datos. Además, esos mismos lenguajes suelen permitir a los programadores crear sus propias nuevas estructuras de datos con el objetivo fundamental de resolver del modo más eficiente posible una aplicación.

Será necesario que la elección de una estructura de datos adecuada requiera también la posibilidad de poder realizar operaciones sobre dichas estructuras. La elección de la estructura de datos adecuada redundará en una mayor eficiencia del programa y, sobre todo, en una mejor resolución del problema en cuestión. Una elección inadecuada de la estructura de datos puede conducir a programas lentos, largos y poco eficientes.

Una solución se denomina eficiente si resuelve el problema dentro de las restricciones de recursos requeridas. Restricciones de recursos pueden ser el espacio total disponible para almacenarlos datos (considerando la memoria principal independiente de las restricciones de espacio de discos, fijos, CD, DVD, flash...) o el tiempo permitido para ejecutar cada subtarea. Se suele decir que una solución es eficiente cuando requiere menos recursos que las alternativas conocidas.

El costo de una solución es la cantidad de recursos que la solución consume. Normalmente, el coste se mide en término de recursos clave, especialmente el tiempo.

Etapas en la selección de una estructura de datos

Los pasos a seguir para seleccionar una estructura de datos que resuelva un problema son:

1. Analizar el problema para determinar las restricciones de recursos que debe cumplir cada posible solución.

2. Determinar las operaciones básicas que se deben soportar y cuantificar las restricciones de recursos para cada una. Ejemplos de operaciones básicas son la inserción de un dato en la estructura de datos, suprimir un dato de la estructura o encontrar un dato determinado en dicha estructura.

3. Seleccionar la estructura de datos que cumple mejor los requisitos o requerimientos.

Este método de tres etapas para la selección de una estructura de datos es una aproximación centrada en los datos. Primero se diseñan los datos y las operaciones que se realizan sobre ellos, a continuación viene la representación de esos datos y, por último, viene la implementación de esa representación.

Las restricciones de recursos sobre ciertas operaciones clave, como búsqueda, inserción de registros de datos y eliminación de registros de datos, normalmente conducen el proceso de selección de las estructuras de datos.

Algunas consideraciones importantes para la elección de la estructura de datos adecuada son:

• ¿Todos los datos se insertan en la estructura de datos al principio o se entremezclan con otras operaciones?

• ¿Se pueden eliminar los datos?

• ¿Los datos se procesan en un orden bien definido o se permite el acceso aleatorio?

Clases y objetos

INTRODUCCIÓN

La modularización de un programa utiliza la noción de tipo abstracto de dato (TAD) siempre

que sea posible. Si el lenguaje de programación soporta los tipos que desea el usuario y el

conjunto de operaciones sobre cada tipo, se obtiene un nuevo tipo de dato denominado TAD.

Una clase es un tipo de dato que contiene código (métodos) y datos. Una clase permite

encapsular todo el código y los datos necesarios para gestionar un tipo específico de un elemento

de programa, tal como una ventana en la pantalla, un dispositivo conectado a una computadora,

una figura de un programa de dibujo o una tarea realizada por una computadora. En el

capítulo se aprenderá a crear (definir y especificar) y utilizar clases individuales.

CLASES Y OBJETOS

Las tecnologías orientadas a objetos combinan la descripción de los elementos en un entorno

de proceso de datos con las acciones ejecutadas por esos elementos. Las clases y los objetos

como instancias o ejemplares de ellas, son los elementos clave sobre los que se articula la

orientación a objetos.

¿Qué son objetos?

En el mundo real, las personas identifican los objetos como cosas que pueden ser percibidas

por los cinco sentidos. Los objetos tienen propiedades específicas, tales como posición, tamaño,

color, forma, textura, etc., que definen su estado. Los objetos también tienen ciertos comportamientos

que los hacen diferentes de otros objetos.

Booch1, define un objeto como "algo que tiene un estado, un comportamiento y una identidad".

Supongamos una máquina de una fábrica. El estado de la máquina puede estar funcionando/

parada ("on/of"), su potencia, velocidad máxima, velocidad actual, temperatura, etc.

Su comportamiento puede incluir acciones para arrancar y parar la máquina, obtener su temperatura,

activar o desactivar otras máquinas, condiciones de señal de error o cambiar la velocidad.

Su identidad se basa en el hecho de que cada instancia de una máquina es única, tal vez

identificada por un número de serie. Las características que se eligen para enfatizar en el estado

y el comportamiento se apoyarán en cómo un objeto máquina se utilizará en una aplicación.

En un diseño de un programa orientado a objetos, se crea una abstracción (un modelo simplificado)

de la máquina basado en las propiedades y comportamiento que son útiles en el

tiempo.

Martin/Odell definen un objeto como "cualquier cosa, real o abstracta, en la que se almacenan

datos y aquellos métodos (operaciones) que manipulan los datos".

Un mensaje es una instrucción que se envía a un objeto y que cuando se recibe ejecuta sus

acciones. Un mensaje incluye un identificador que contiene la acción que ha de ejecutar el

objeto junto con los datos que necesita el objeto para realizar su trabajo. Los mensajes, por

consiguiente, forman una ventana del objeto al mundo exterior.

El usuario de un objeto se comunica con el objeto mediante su interfaz, un conjunto de

operaciones definidas por la clase del objeto de modo que sean todas visibles al programa. Una interfaz se puede considerar como una vista simplificada de un objeto. Por ejemplo, un dispositivo

electrónico tal como una máquina de fax tiene una interfaz de usuario bien definida; esa

interfaz incluye el mecanismo de avance del papel, botones de marcado, receptor y el botón

"enviar". El usuario no tiene que conocer cómo está construida la máquina internamente, el

protocolo de comunicaciones u otros detalles.

¿Qué son clases?

En términos prácticos, una clase es un tipo definido por el usuario. Las clases son los bloques

de construcción fundamentales de los programas orientados a objetos. Booch denomina a una

clase como "un conjunto de objetos que comparten una estructura y comportamiento comunes".

Una clase contiene la especificación de los datos que describen un objeto junto con la descripción

de las acciones que un objeto conoce cómo ha de ejecutar. Estas acciones se conocen

como servicios o métodos. Una clase incluye también todos los datos necesarios para describir

los objetos creados a partir de la clase. Estos datos se conocen como atributos, variables o

variables instancia. El término atributo se utiliza en análisis y diseño orientado a objetos y el

término variable instancia se suele utilizar en programas orientados a objetos.

Método cadena, este contiene una llamada al BufferedReader con la finalidad de poder capturar desde el teclado y como retorno será una cadena de tipo String

Sin embargo, una mejor manera de trabajar este método, es mediante la siguientes mejora, como se muestra en la imagen, la finalidad, es dar tratamiento a los errores, de manera que uno sea el que tiene el control, por tal motivo, se quito la protección throws IOException, y se manejo de manera interna, ahora este cambio tan significativo, me permite manejar el error mediante el uso de try  -  catch, lo que esta dentro de try es la instrucción de captura del teclado y lo que esta dentro del catch es para lanzar el error.

A continuación el método sobre cargado llamado entero, este método recibe y retorna un entero

La mejora en el siguiente código, del método sobrecargado tiene sus ventajas y desventajas, no se podrá dar la sobre carga, ya que no recibirá ninguna tipo de dato, lo que hará que no se permita la sobrecarga del método, sin embargo puedo manejar mucho mejor el error, si notas hay un ciclo do - while, que estará allí repitiéndose mientras sigamos haciendo una mala captura, ya sea de dedo, o intencionalmente capture un dato de tipo flotante es decir, con decimales.

Clase Captura mejorado

A continuación se muestra en el siguiente vídeo la mejora completa de la clase Captura, ya que esta clase se pasará por herencia a la clase Biblioteca

Clase grabada de la sesión en Zoom

Declaración de un arreglo

Los arrays se usan normalmente para agrupar objetos del mismo tipo. Permiten hacer referencia al grupo de objetos a través de un nombre común.

Es posible declarar arrays de cualquier tipo, ya sea tipos primitivos o de clases.:

char[ ] s; //tipo de dato primitivo

Point[ ] p; //donde Point es una clase

Al declarar arrays con los corchetes a la izquierda, éstos se aplicarán todas las variables situadas a la derecha de los corchetes.

En el lenguaje Java, un array es un objeto incluso cuando está compuesto de tipos primitivos y, como en el caso de otros tipos de clases, la declaración no crea objetos en sí. Por al contrario , la declaración de un array crea una referencia que puede utilizarse para hacer referencia a un array. La memoria utilizada por los elementos del array se asigna de forma dinámica mediante una sentencia new o mediante un inicializador del array.

Los arrays se declaran escribiendo corchetes después del nombre de la variable:

char[ ] s;

Point [ ] p;

Este formato es estándar en C, C++ y Java. Su uso puede coincidir a formas complejas de declaración que pueden ser difíciles de leer.

El resultado es que puede considerar la declaración como una expresión que tiene la parte de tipos a la izquierda y el nombre de la variable a la derecha. Aquí veremos el uso de ambos formatos, pero deberá optar por uno de ellos cuando escriba su propio código. Las declaraciones nos indican el tamaño concreto del array.

 Creación de arrays 

Como en el caso de los demás objetos, los arrays pueden crearse utilizando la palabra clave new. Por ejemplo, para crear un array de un tipo primitivo (char), utilice:

s = new char[ 26];

La primera línea crea un array de 26 valores char. Después de su creación, los elementos del array se inicializan con el valor predeterminado ('\u0000' en el caso de los caracteres). Es necesario llenar el array con algún valor para que sea útil, por ejemplo:

public char[] poblarArray(){

char [ ] s;

s = new char[26];

for( int i=0; i<26; i++){

s[i] = (char) ('A'+1);

}

return s;

}

Este código genera un array en el espacio de memoria dinámica con las letras del alfabeto inglés en mayúsculas. El aspecto del array en la memoria dinámica se muestra en la siguiente figura

El subíndice que indexa los distintos elementos del array siempre empieza a partir de 0 y debe mantenerse dentro del rango de valores admitido: mayor o igual que 0 y menor igual que la longitud del array. Cualquier intento de acceder a un elemento del array fuera de estos límites provocará un error de tiempo de ejecución. 

Creación de arrays de referencia 

Es posible crear arrays de objetos. La sintaxis utilizada es la misma:

p = new Point[10];

esta línea crea un array de 10 referencia de tipo Point, pero no crea 10 objetos Point. Estos se crean por separado de la forma siguiente:

public Point[] poblarArray(){

Point [ ] p;

p = new Point[10];

for( int i=0; i<10; i++){

p[i] = new Point (i,i+1);

}

return p;

}

Este código genera un array en la memoria dinámica de forma que cada elemento del array se llena con una referencia de un objeto Point. El aspecto del array en la memoria dinámica se muestra en la siguiente figura

Arrays Multidimensionales 

Java no proporciona arrays multidimensionales de la misma forma que lo hacen otros lenguajes. Dado que es posible declarar un arrays de arrays, arrays de arrays de arrays y así sucesivamente. En el ejemplo siguiente se utiliza un array bidimensional:

Int [] [] dobDimen =new int [4] [];

dosDimen[0] = new int[5];

dosDimen[1] = new int[5];

El objeto que se crea con la primera llamada a new es un array que contiene cuatro elementos. Cada elemento es una referencia vacía (null) a un elemento de tipo array de enteros (int) y cada elemento debe inicializarse por separado para que señale a su correspondiente array.

Gracias a esta separación, es posible crear arrays de arrays no rectangulares. Es decir, existe la posibilidad de inicializar los elementos de dosDimen como sigue:

dosDimen[0] = new int [2];

dosDimen[1] = new int [4];

dosDimen[2] = new int [6];

dosDimen[3] = new int [8];

Dado que este tipo de inicialización es tediosa y el array de arrays rectangular es la forma más común de array multidimensional, existe un sistema abreviado para crear arrays bidimensionales. Por ejemplo, puede utilizarse el código siguiente para crear un array de cuatro arrays formados por cinco enteros cada uno:

Int [ ][ ] dosDimen = new int [4][5];

Uso de bucles for mejorados

Iterar sobre los elementos de un array es una tarea muy habitual. En la plataforma Java 2, Standard Edition (J2SE) se ha introducido esta mejora del bucle for para facilitar la iteración de arrays. Su uso se muestra a continuación

public void mostrarElementos( int [ ] list){

for( int element : list ){

System.out.println(element);

}

}

Esta versión del bucle puede interpretarse como: por cada elemento de la lista haz. El compilador maneja el código iteración. 

Redimensionamiento de arrays

No es posible cambiar el tamaño de los arrays una vez creados. No obstante, sí se puede utilizar la misma variable de referencia para señalar a un array completamente nuevo:

Int [ ] miArray = new int [6];

miArray=new int [10];

en este caso, el primer array en la práctica se pierde a menos que exista otra referencia a él en otro lugar.

Copia de Arrays

Copia de Arrays

El lenguaje Java proporciona un método especial en la clase System(arraycopy()) para copiar arrays. Por ejemplo, el método arraycopy() puede utilizarse como sigue:

//array original

Int [ ] miArray =;

//nuevo array más largo

Int [ ] copia = ;

//copia todos los elementos de miArray en el array copia, empezando por el índice 0

System.arraycopy(miArray, 0, copia, 0, miArray.length);

En este punto, el array copia tiene contenido siguientes: 1, 2, 3, 4, 5, 6, 4, 3, 2, 1.