Estructura de datos

Páginas: 6 (1498 palabras) Publicado: 2 de octubre de 2010
Teoría de la Programación [TP]

Estructuras de Datos para los Algoritmos
Juan Ramón Pérez Pérez

Curso 03-04

Teoría de la programación (TP) Estructuras de Datos

1

Necesidad de las estructuras de datos
• Los algoritmos requieren una representación apropiada de los datos para lograr ser eficientes. • Esta representación junto con las operaciones permitidas se llama estructura dedatos.

Curso 03-04

Teoría de la programación (TP) Estructuras de Datos

2

Matrices, pilas y colas
• Matriz (array), estructura de datos que consta de un número fijo de elementos del mismo tipo.
– Vectores, matrices unidimensionales.

• Pila, LIFO (Last In Fisrt Out) estructura de datos en la cual el acceso está limitado al elemento más recientemente insertado. • Cola, FIFO (First InFirst Out) permite acceder al elemento más antiguo.
Curso 03-04 Teoría de la programación (TP) Estructuras de Datos 3

1

Arrays en Java
• Se definen y utilizan con el operador de indexación corchetes [ ] • Es un objeto más su identificador es una referencia. • Arrays dinámicos, cuando llamamos al constructor decidimos el tamaño. • length, miembro intrínseco, sólo se puede consultar, indicacuántos elementos hay en el array. • Siempre se controlan los rangos.
Curso 03-04 Teoría de la programación (TP) Estructuras de Datos 4

Arrays multidimensionales en Java
– Declaración: int [][] – Construcción: int [][] matriz= new int [3][4]; – Acceso: matriz[2][0] – Devolver un array: String[][] conjuntoCadenas()

Curso 03-04

Teoría de la programación (TP) Estructuras de Datos

5Operaciones con arrays
• java.util.Arrays, clase que implementa un conjunto de métodos estáticos que permiten realizar operaciones con arrays:
– – – – – equals(), compara la igualdad de dos arrays. fill(), rellena un array con un valor. sort(), ordena un array. binarySearch(), busca un dato en un array ordenado. asList(), convierte el array en un contenedor tipo lista de Java.

•System.arraycopy(), copia datos de un array en otro, realiza copia superficial.
Curso 03-04 Teoría de la programación (TP) Estructuras de Datos 6

2

Diseño de la ordenación de arrays
• Problema de escribir código de ordenación genérico: debemos llevar a cabo comparaciones basadas en el tipo del objeto. • Podemos escribir código de ordenación para cada tipo no se puede reutilizar. • Algoritmo de ordenacióncoches:
[…] if (coche1.cilindrada() > coche2.cilindrada()) […]

• Algoritmo de ordenación aviones:

[…] if (avion1.verPasajeros() > avion2.verPasajeros()) […]
Curso 03-04 Teoría de la programación (TP) Estructuras de Datos 7

Diseño de la ordenación de arrays
• Podemos “separar los elementos que cambian de los que permanecen igual”, el algoritmo general de ordenación permanece igual, loque cambia es la forma de comparar los objetos. • La parte del código que varía la encapsulamos en la propia clase. • Algoritmo de ordenación genérico:
[…] if (Comparable1.comparar(Comparable2)>0) […]
Curso 03-04 Teoría de la programación (TP) Estructuras de Datos 8

Comparación para la ordenación
• Primera forma de proporcionar esto:
– La clase a ordenar debe implementar la interfazjava.lang.Comparable. – Interfaz con un único método compareTo()

• Segunda forma:

Ejemplo CompType.java

– Si tenemos que ordenar una clase que no implementa comparable o no debemos emplear este tipo de comparación. – Crear una clase separada que implementa la interfaz Comparator. – Se debe implementar el método compare()
Curso 03-04 Teoría de la programación (TP) Estructuras de Datos EjemploReverse.java 9

3

Operaciones con pilas
• void push(Object x)
– Inserta un nuevo elemento en la pila, si no está llena

• Object pop()
– Devuelve y borra el elemento más recientemente insertado.

• Object top()
– Devuelve el elemento más recientemente insertado.

• boolean estaVacia()
– Comprueba si la pila está vacía.

• void vaciar()
– Vacía la pila.
Interfaz Pila.java Curso...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Estructura de Datos
  • Estructura De Datos
  • Estructura de datos
  • Estructura de datos
  • Estructura de datos
  • Estructuras de datos
  • Estructura de Datos
  • estructura de datos

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS