Gerardo Casimiro Reyes Torres

“

RUBEN RIOJAS

1

Índice.Introducción......................................................................................................................................2

Tipos de datos................................................................................................................................3

Modularidad..................................................................................................................................4

Ventajas y Desventajas de la Modularidad...............................................................................4

Tipos de Módulos:.....................................................................................................................5

Usos de los TDA.............................................................................................................................7

Manejo de memoria estática........................................................................................................7

Conceptos de Arreglos...............................................................................................................8

Arreglos Unidimensionales.......................................................................................................8

Arreglos Bidimensionales..........................................................................................................9

Registros. (Estructuras)............................................................................................................10

Arreglos y Registros.................................................................................................................10

Ventajas y Desventajas............................................................................................................11

Memoria Dinámica......................................................................................................................11

Ventajas y Desventajas............................................................................................................12

Apuntadores............................................................................................................................12

2

Introducción.Normalmente el estudio de las estructura de datos supone que éstos se encuentran almacenados en memoria RAM. Un archivo constituido por decenas o más de millones de registros es demasiado grande para cargarlo en memoria RAM a fin de efectuar operaciones sobre él. Dichas operaciones implican el uso de almacenamiento secundario, y por lo tanto, ya no se está en un ambiente de acceso aleatorio. En la práctica, la mayor parte de información útil no aparece aislada en forma de datos simples, sino que lo hace de forma organizada y estructurada. Los diccionarios, guías, enciclopedias, etc., son colecciones de datos que serían inútiles se no estuvieran organizadas de acuerdo con unas determinadas reglas. Además, tener estructurada la información supone ventajas adicionales, al facilitar el acceso y el manejo de los datos. Por ello parece razonable desarrollar esa idea de la agrupación de datos, que tengan un cierto tipo de estructura y organización interna. La información que se procesa en la computadora es un conjunto de datos, que pueden ser simples o estructurados. Los datos simples son aquellos que ocupan sólo un localidad de memoria, mientras que los estructurados son un conjunto de casillas de memoria a las cuales hacemos referencia mediante un identificador único. Debido a que por lo general tenemos que tratar con conjuntos de datos y no con datos simples (enteros, reales, booleanos, etc.) que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con estructuras de datos adecuadas a cada

necesidad. La abstracción de datos es la técnica de inventar nuevos tipos de

datos que sean más adecuados y por consiguiente, facilitar la estructura del programa. Los lenguajes de programación soportan tipos de datos fundamentales o básicos (predefinidos), tales como int, char y float en los distintos tipos de lenguaje de programación que existen hoy en día. La popularización de un programa utiliza la noción 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.

3

Tipos de datos.

Un TDA es un tipo de dato definido por el programador que se puede manipular de un modo similar a los tipos de datos definidos por el sistema. Es el conjunto de valores que puede tomar durante el programa. Si se le intenta dar un valor fuera del conjunto se producirá un error.

La asignación de tipos a los datos tiene dos objetivos principales:

• Por un lado, detectar errores en las operaciones.• Por el otro, determinar cómo ejecutar estas operaciones.

Un lenguaje fuertemente tipeado1 es aquel en el que todos los datos deben de tener un tipo declarado explícitamente, y además que existen ciertas restricciones en las expresiones en cuanto a los tipos de datos que en ellas intervienen. Una ventaja de los lenguajes fuertemente tipeados es que se gasta mucho menos esfuerzo en depurar (corregir) los programas gracias a la gran cantidad de errores que detecta el compilador. Los TDA por lo general manejan memoria dinámica, esto es, la asignación dinámica de memoria es una característica que le permite al usuario crear tipos de datos y estructuras de cualquier tamaño de acuerdo a las necesidades que se tengan en el programa.

La abstracción de datos consiste en ocultar las características de un objeto y obviarlas, de manera que solamente utilizamos el nombre del objeto en nuestro programa. Al hecho de guardar todas las características y habilidades de un objeto por separado se le llama Encapsulamiento y es también un concepto importante para entender la estructuración de datos. Es frecuente que el Encapsulamiento sea usado como un sinónimo del Ocultación de información.

1 Teclear.

4

Ejemplos:

Modularidad.Se denomina Modularidad2 a la propiedad que permite subdividir una aplicación en partes más pequeñas (llamadas módulos), cada una de las cuales debe ser tan independiente como sea posible de la aplicación en sí y de las restantes partes. Estos módulos que se puedan compilar por separado, pero que tienen conexiones con otros módulos. Al igual que la encapsulación, los lenguajes soportan la Modularidad de diversas formas.

Ventajas y Desventajas de la Modularidad.Ventajas.

• Un programa modular es fácil de mantener y modificar.• Un programa modular es más fácil de escribir y depurar (ejecutar, probar y

poner a punto).• Un programa modular es más fácil de controlar. El desglose de un problema en

módulos permite encomendar los módulos más complejos a los programadores más experimentados y los más sencillos a los programadores nóveles.

• Posibilita el uso repetitivo de las rutinas en el mismo o en diferentes programas.

2 Capacidad de un sistema que ha sido dividido en módulos cohesivos y débilmente acoplados

public class Coche {

private String matricula;

private double velocidad; // atributos privados

private double velocidadMax;

// Método constructor

public Coche(String pMatricula, double pVelMax) {

this.matricula= pMatricula;

this.velocidad = 0.0;

if (velocidadMax >= 0.0) {

this.velocidadMax = pVelMax; }

else { velocidadMax = 0.0; }

}

// Métodos de consulta

public String getMatricula() { return this.matricula; }

…

// Métodos de asignación

public void setMatricula(String pMatric) { this.matricula = pMatric; }

…

// Otros métodos

public void Acelerar(double pVel) {

this.velocidad = this.velocidad + pVel;

if (this.velocidad > this.velocidadMax) {

this.velocidad = this.velocidadMax; }

if (this.velocidad < 0.0) { this.velocidad= 0.0; }

}

…}

5

Desventajas.

• No se dispone de algoritmos formales de modularidad, por lo que a veces los programadores no tienen claras las ideas de los módulos.

• La programación modular requiere más memoria y tiempo de ejecución.

Tipos de Módulos:a) Módulos de definición.b) Módulos de servicio.c) Tipos Abstractos de Datos.d) Máquinas Abstractas de Estado.

Módulos de Definición

• Declaración de constantes y variables.• Se declaran sobre clases abstractas (abstract).• Se declaran como estáticas (static).• Definiciones de constantes (final).

Ejemplo:abstract class ConfiguracionSistema{

static boolean VersionEvaluacion;

static int diasUtilización;

static final int maxDias;

static String ubicacion;

static String paginaInicial;

}

Módulos de Servicio.

• Ofrecen un servicio.• Agrupan un conjunto de operaciones.• Las operaciones de la interfaz se declaran sobre clases no instanciables

(abstract y• final).• Las operaciones son declaradas estáticas (static).

6

Ejemplo:abstract class UtilidadesString

{

static void aMayusculas(String S)

{...}

static void eliminarBlancos(String S)

{...}

static Boolean esPrefijo (String P, String S)

{...}

private static int interna(String P, String S)

{...}

}

Máquinas Abstractas de Estado (MAE)A diferencia de los TADs, las operaciones de una MAE se efectúan sobre un único objeto (la clase), no se pueden generar diferentes objetos del mismo tipo

En Java definiremos MAEs a través de clases que cumplan los siguientes requisitos:

• No pueden admitir tener varias instancias.

• Los métodos se aplican sobre el único objeto de la clase.

Ejemplo:public class Pila { // Atributos

private static final int CAPACIDAD=1000;

private static int elementos[];

private int tope; // índice de la primera posición libre

private static Pila unaPila = new Pila(); // única instancia de la clase

// Constructora

private Pila() {

elementos = new int[CAPACIDAD];

7

tope = 0;

}

// Operación de acceso

public static Pila obtPila (){

return unaPila;

}

Usos de los TDAAlgunos ejemplos de utilización de TDA en programación son:

• Conjuntos: Implementación de conjuntos con sus operaciones básicas (unión, intersección y diferencia), operaciones de inserción, borrado, búsqueda.

• Árboles Binarios de Búsqueda: Implementación de árboles de elementos, utilizados para la representación interna de datos complejos. Aunque siempre se los toma como un TDA separado son parte de la familia de los grafos.

• Pilas y Colas: Implementación de los algoritmos FIFO y LIFO.

• Grafos: Implementación de grafos; una serie de vértices unidos mediante una serie de arcos o aristas.

Manejo de memoria estática.Memoria estática es cuando no puede modificarse en tiempo de ejecución.

• Es la asignación de memoria para algunos elementos fijos del programa que es controlada por el compilador.

• Define la cantidad de memoria necesaria para un programa durante el tiempo de compilación.

• El tamaño no puede cambiar durante el tiempo de ejecución del programa.• Algunos lenguajes de programación utilizan la palabra static para especificar elementos

del programa que deben almacenarse en memoria estática.• Elementos que residen en memoria estática:

o Código del programa.o Las variables definidas en la sección principal del programa, las cuales pueden

solo cambiar su contenido no su tamaño.o Todas aquellas variables declaradas como estáticas en otras clases o módulos.

Conceptos de Arreglos.• Colección finita, homogénea y ordenada de elementos.

8

Finita: Porque todo arreglo tiene un límite.

Homogénea: Porque todos los elementos son del mismo tipo.

Ordenada: Porque se puede determinar cuál es el enésimo elemento.

• Un arreglo tiene dos partes: Componentes e índices

• Componentes : Hacen referencia a los elementos que forman el arreglo.

• Índices: Permiten referirse a los componentes del arreglo en forma individual.

Arreglos Unidimensionales.• Son los arreglos más simples y constan de un solo índice, también se llaman vectores.

• Notación: Podría ser de diferentes maneras. Por ej:

Array [0...9] de enteros: Vector

Vector: x

X hace referencia a todo el vector, mientras que x0, o x1 hace referencia los elementos en forma individual

Los arreglos se almacenan en forma adyacente, así que su representación en memoria es:

X0 ,Dirección z; X1 ,Dirección z+1; Xn ,Dirección z+n

Cada elemento del arreglo se puede procesar como si fuera una variable simple. Ej:

Índices

Componentes

ini1i0

Cn....C2C1

Índices

Componentes

x9x1x0

4....4314

9

Suma Suma + x[2]

X[2] 15

I 3

X[i] 15

X[i+2] 15

Sobre los vectores se pueden realizar las siguientes operaciones: Lectura/Escritura, Asignación, Actualización (insertar, eliminar, modificar), Ordenamiento y Búsqueda.

Arreglos Bidimensionales.• Estos arreglos constan de dos índices, también se llaman matrices.

• Notación: Podría ser de diferentes maneras. Por ej:

Array [0...2, 0...2] de enteros: Matriz

Matriz: M

Para su declaración se hace de la sig. Manera:

int [] Arreglo //Ojo esto es solo la declaración.int [] Arreglo n= new int [10]//esto es la creación del Arreglo

Registros. (Estructuras)Un registro es una colección de datos, que pueden ser de diferentes tipos. Cada uno de sus elementos se llama Campo.

Notación: Podría ser de diferentes maneras. Por ej:

10

Tipo registro: Domicilio

Entero: Calle

Entero: Numero

Cadena: Ciudad

Fin Tipo

Domicilio: dir

El acceso a los campos se hace así: variable_registro.id_campo.

Por Ej: dir.Calle, dir.Numero, dir.Ciudad.

Arreglos y Registros.Se pueden presentar las siguientes combinaciones:

I. Arreglos de Registros: Cada elemento del registro es un arreglo.

II. Registro Anidado: Por lo menos un campo del registro es de tipo registro.

III. Registro con Arreglos : Por lo menos un campo del registro es un array.

11

Ventajas y Desventajas.Ventajas.-

         Tiene una lógica fácil         Óptima para resolver problemas pequeños y  medianos    

   Desventajas.-          No se puede modificar el tamaño de  la estructura en tiempo de ejecución             No es óptima para grandes cantidades de datos          Desperdicio de memoria cuando no se ocupa la totalidad del tamaño de la estructura

Memoria Dinámica.La memoria dinámica si puede modificarse en tiempo de  ejecución, se puede aumentar o reducir el tamaño de la estructura sin ningún problema

Es la asignación y posible recuperación de memoria durante la ejecución de un programa y bajo su control.

Define el tamaño del espacio de memoria necesario para un programa en tiempo de ejecución.

El tamaño de los elementos puede cambiar durante la ejecución del programa.

Almacena todos los elementos definidos con la palabra new en un programa.

Sus variables crecen de tamaño o se reducen durante la ejecución del programa. Estas se almacenan en un espacio de memoria llamado heap; el cual se localiza en la región de memoria que está encima del stack.

Algunos lenguajes de programación permiten que el programador asigne y desasigne manualmente la memoria.

Ventajas y Desventajas.Ventajas.-

El tamaño de la estructura no interfiere en la lógica del programa

12

No desperdicia espacio de memoria Se puede modificar el tamaño de la estructura sin ninguna dificultad

Desventajas.- No se conoce con anticipación el espacio que memoria que se va ocupar

Apuntadores.Las variables contienen valores específicos, las variables apuntador contienen direcciones de memoria de otras variables.

• La variable “ptrcont” contiene la dirección de memoria de la variable “cont”

Las variables apuntador están asociadas a un tipo de dato. Por ej. Si el valor de cont es entero la variable apuntador ptrcont debe ser de tipo entero.