ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
CONTENIDO
1. Diagrama de unidades de aprendizaje
2. Diagrama de clases
3. Ordenamiento y búsqueda
4. Recursividad
5. Listas Simples
6. Listas Dobles
7. Arboles binarios de búsqueda
8. Guías de laboratorio
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
DIAGRAMA DE UNIDADES DE APRENDIZAJE
DIAGRAMA DE
CLASES
RELACIONES ENTRE
CLASES
ORDENAMIENTO
Y BUSQUEDA
RECURSIVIDAD
LISTAS SIMPLES LISTAS DOBLES ARBOLES BINARIOS
DE BUSQUEDA
DIAGRAMA DE
CLASES
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 01
DIAGRAMA DE CLASES
Jerarquía de clases, Relacion entre clases, Relación entre métodos
Jerarquía de clases: La interrelación de clases a través de la herencia determina la construcción de una jerarquía de clases. ●La herencia es la propiedad que permite construir clases a partir de la existencia de otras clases. ●El objetivo principal de la herencia es la reutilización, es decir utilizar un código anteriormente desarrollado. ●Las super-clases o clases base o clases padre se derivan en sub-clases o clases derivadas o clases hijas compartiendo características y comportamiento.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 1 de jerarquía de clases
Ejemplo 2 de jerarquía de clases
Figura
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Relación entre clases ●Generalización/Especialización: Establecen la relación Es-Un. Se utiliza para establecer relación de herencia. Ejemplo:
Perro es-un Mamífero. Circulo es-una Figura. Avión de pasajeros es-un Avión.
●Asociación: Establecen la relación Tiene-Un. se utiliza cuando tenemos un objeto como atributo de una clase. Ejemplo:
Auto tiene-un Motor. Persona tiene-un Dni.
●Agregación/Composición: cuando en una clase se tiene una o varias colecciones de objetos. Ejemplo:
ColeccionAutos tiene un arreglo de objetos de la clase Auto.
●Dependencia: Establecen relación con clases que tienen servicios comunes o métodos estáticos. Por ejemplo, para realizar un cálculo de potencia se establece una relación de dependencia con la clase Mathy su método pow().
Diagrama de clases En este diagrama se puede visualizar la relación entre clases y la jerarquía de clases correspondiente. Ejemplo 1: Dibuje el diagrama de clases e indique la relación entre clases, considerando lo siguiente: Clase PantallaPrincipal hereda de la clase Pantalla Clase ManejadorPrincipal hereda de la clase Manejador Clase Principal tiene un objeto PantallaPrincipal Clase Principal tiene un objeto ManejadorPrincipal
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 2: Dibuje el diagrama de clases e indique la relación entre clases considerando lo siguiente: Clase Empleado hereda de la clase Persona Clase Cliente hereda de la clase Persona Clase Directivo hereda de la clase Empleado Clase Empresa tiene varios empleados Clase Empresa tiene varios clientes Ejemplo 3: Diseñe el diagrama de clases e indique la relación entre clases, para administrar una colección de objetos de tipo Vehiculo considerando lo siguiente: Clase Automovil hereda de la clase Vehiculo Clase Camion hereda de la clase Vehiculo Clase ColeccionVehiculos tiene varios vehículos Clase ColeccionVehiculos tiene un objeto tipo ArrayList Clase PanelVehiculos tiene un objeto tipo ColeccionVehiculos Clase Principal tiene un objeto tipo PanelVehiculos. Ejemplo 4: Dibuje el diagrama de clases e indique la relación entre clases considerando lo siguiente: Clase TV hereda de la clase Producto Clase TVH hereda a la clase TV Clase ArregloTVH tiene un objeto ArrayList Clase ArregloTVH tiene varios objetos TVH Clase ArchivoTVH hereda de la clase ArregloTVH Clase ArchivoTVH tiene los siguientes objetos: FileReader, BufferedReader, StringTokenizer, FilePrinter, PrintWriter, Clase PanelPrincipal tiene un objeto ArchivoTVH Clase Principal tiene un objeto PanelPrincipal
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 02
ORDENAMIENTO Y BUSQUEDA
En arreglos simples
ORDENAMIENTO Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. Ordenar colecciones de datos como vectores, matrices, colecciones de objetos. Nos centraremos en los métodos más populares, analizando la cantidad de comparaciones que suceden, el tiempo que demora y revisando el código, escrito en Java, de cada algoritmo.
METODOS ITERATIVOS Estos metodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado. Dentro de los Algoritmos iterativos encontramos:
– Burbuja – Inserción – Selección – Shellsort
METODOS RECURSIVOS Estos metodos son aún más complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos. Mediante llamadas recursivas a si mismas, es posible que el tiempo de ejecución y de ordenación sea más óptimo. Dento de los algoritmos recursivos encontramos:
– Ordenamiento por Mezclas (merge sort) – Ordenamiento Rápido (quick sort)
Dentro de cada método, inclusive, existen variantes. Es decir, variaciones que han mejorado el algoritmo original.
BURBUJA El metodo de la burbuja es uno de los más simples, es tan facil como comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor a otro, entonces los intercambia de posición. Por ejemplo, imaginemos que tenemos el siguiente vector: 5, 6, 1, 0, 3 Lo que haria una burbuja simple, seria comenzar comparando los valores de izquierda a derecha, de dos en dos. Si es mayor o menor (dependiendo si el orden es ascendente o descendente) se intercambian de posicion. Repite este proceso n-1 veces, con lo que se asegura que la lista terminara ordenada.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Código java: int temp;
for(int i = 0; i < limite; i++){
for(int j = 0; j < limite-1; j++){
if(vector[j] > vector[j+1]){
temp = vector[j];
vector[j] = vector[j+1];
vector[j+1] = temp;
}
}
}
Haga el seguimiento para ordenar el siguiente vector: 5, 6, 1, 0, 3 limite=5. Se harán las comparaciones de izquierda a derecha, 5 veces. Primera vez: i=0 5 con 6, queda : 5,6,1,0,3 6 con 1, intercambia: 5,1,6,0,3 6 con 0, intercambia: 5,1,0,6,3 6 con 3, intercambia: 5,1,0,6,3 Segunda vez: i=1 5 con 1, intercambia: 1,5,0,6,3 5 con 0, intercambia: 1,0,5,6,3 5 con 6, queda : 1,0,5,6,3 6 con 3, intercambia: 1,0,5,3,6 Tercera vez: i=2 1 con 0, intercambia: 0,1,5,3,6 1 con 5, queda : 0,1,5,3,6 5 con 3, intercambia: 0,1,3,5,6 5 con 6, queda : 0,1,3,5,6 Cuarta vez: i=3 0 con 1, queda : 0,1,3,5,6 1 con 3, queda : 0,1,3,5,6 3 con 5, queda : 0,1,3,5,6 5 con 6, queda : 0,1,3,5,6 Quinta vez: i=4 0 con 1, queda : 0,1,3,5,6 1 con 3, queda : 0,1,3,5,6 3 con 5, queda : 0,1,3,5,6 5 con 6, queda : 0,1,3,5,6
Quedó ordenado con 20 comparaciones!. (n x (n-1)) Haga el seguimiento para ordenar el siguiente vector: 21, 14, 19, 27, 4, 16, 0.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
BURBUJA OPTIMIZADA El hecho de que los elementos que estan detrás del que se esta comparando, ya estan ordenados, las comparaciones serian aun menos y el metodo seria aún más efectivo. Si tenemos una lista de 10 elementos y estamos analizando el quinto elemento, que sentido tiene que el quinto se compare con el primero, el segundo o el tercero, si supuestamente, ya estan ordenados? Entonces optimizamos más aún el algoritmo, quedando nuestra version final del algoritmo optimizado de la siguiente manera: Código java:
int temp;
for (int i=0 ; i<limite - 1; i++)
for (int j=i+1; j<limite; j++)
if (vector[i] > vector[j]){
temp = vector[i];
vector[i] = vector[j];
vector[j] = temp;
}
Haga el seguimiento para ordenar el siguiente vector: 5, 6, 1, 0, 3 limite=5 Primera vez: i=0, compara posición 0 con las demas 5 con 6, queda : 5,6,1,0,3 5 con 1, intercambia : 1,6,5,0,3 1 con 0, intercambia : 0,6,5,1,3 0 con 3, queda : 0,6,5,1,3 Segunda vez: i=1, compara posición 1 con las demás 6 con 5, intercambia : 0,5,6,1,3 5 con 1, intercambia : 0,1,6,5,3 1 con 3, queda : 0,1,6,5,3 Tercera vez: i=2, compara posición 2 con las demás 6 con 5, intercambia : 0,1,5,6,3 5 con 3, intercambia : 0,1,3,6,5 Cuarta vez: i=3, compara posición 3 con las demás 6 con 5, intercambia : 0,1,3,5,6 Quedó ordenado en 10 comparaciones! (n x (n-1)/2) Haga el seguimiento para ordenar el siguiente vector: 21, 14, 19, 27, 4, 16, 0.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Analizar la siguiente Variante:
boolean hayCambios = true;
int temp;
for (int i = 0; hayCambios ; i++) {
hayCambios = false;
for (int j = 0; j < limite - 1; j++) {
if (vector[j] > vector[j + 1]) {
temp = vector[i];
vector[i] = vector[j];
vector[j] = temp;
hayCambios = true;
}
}
}
INSERCION: El bucle principal de la ordenacion por inserción va examinando sucesivamente todos los elementos del vector desde el segundo hasta el n-ésimo, e inserta cada uno en el lugar adecuado entre sus predecesores dentro del vector.
Código java:
int i, temp, j;
for (i = 1; i < vector.length; i++){
temp = vector[i];
j = i - 1;
while (j >= 0 && vector[j] > temp){
vector[j + 1] = vector[j];
j--;
}
vector[j + 1] = temp;
}
Haga el seguimiento para ordenar el siguiente vector: 5, 6, 1, 0, 3 vector.length = 5 Primera vez: i=1, compara la posición 1 hacia atraz 6 con 5, queda : 5,6,1,0,3 Segunda vez: i=2, compara la posición 2 hacia atraz 1 con 6, con 5, traslada : 1,5,6,0,3 Tercera vez: i=3, compara la posición 3 hacia atraz 0 con 6, con 5, con 1, traslada: 0,1,5,6,3 Cuarta vez: i= 4, compara la posición 4 hacia atraz 3 con 6, con 5, traslada: 0,1,3,5,6 Quedó ordenado en 4 pasos, 8 comparaciones!
Haga el seguimiento para ordenar el siguiente vector: 21, 14, 19, 27, 4, 16, 0.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SELECCION: La ordenacion por selección funciona seleccionando el menor elemento del vector y llevandolo al principio; a continuacion selecciona el siguiente menor y lo pone en la segunda posicion del vector y asi sucesivamente.
Código java:
int i, j, k, p, buffer, limit = vector.length-1;
for(k = 0; k < limit; k++){
p = k;
for(i = k+1; i <= limit; i++)
if(vector[i] < vector[p]) p = i;
if(p != k){
buffer = vector[p];
vector[p] = vector[k];
vector[k] = buffer;
}
}
Haga el seguimiento para ordenar el siguiente vector: 5, 6, 1, 0, 3 limit = 4
primera vez: k=0, encuentra el menor a partir de la posición 0 y lo coloca en la posición
0, intercambiando.
0 lo coloca en la posición 0, intercambia : 0,6,1,5,3
Segunda vez: k=1, encuentra el menor a partir de la posición 1 y lo coloca en la
posición 1, intercambiando.
1 lo coloca en la posición 1, intercambia : 0,1,6,5,3
Tercera vez: k=2, encuentra el menor a partir de la posición 2 y lo coloca en la
posición 2, intercambiando.
3 lo coloca en la posición 2, intercambia : 0,1,3,5,6
Cuarfa vez: k=3, encuentra el menor a partir de la posición 3 y lo coloca en la posición
3, intercambiando.
5 lo coloca en la posición 3, sin intercambio : 0,1,3,5,6
Quedó ordenado en 4 pasos, 10 comparaciones!
Haga el seguimiento para ordenar el siguiente vector: 21, 14, 19, 27, 4, 16, 0.
SHELL SORT:
Tarea para usted.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
COMPARACION DE TIEMPOS Se han ordenado una cantidad determinada de elementos aleatorios en una lista mediante distintos metodos de ordenamiento y se ha registrado el tiempo de ejecución en segundos:
Como podemos analizar, el algoritmo que se va demorando cada vez mas tiempo es el de la burbuja, luego de selección y tercero el insercion. Los algoritmos que los siguen son el Shell y el de ordenacion por mezcla, pero el más optimo es el “Rapido” o quick sort.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
BUSQUEDA:
Puede aplicar su método de búsqueda secuencial.
int busquedaSecuencial( int key ){
for(int i=0, i<n, i++){
if(vector[i]==key)
return i;
}
return -1;
}
Sin embargo, cuando el vector está ordenado, el método de búsqueda puede mejorar
en tiempo, de la siguiente manera:
int busquedaSecuencial( int key){
int i = 0;
while(i<n && vector[i]<key){
i++;
}
if(i<n && vector[i]==key)
return i;
else
return-1;
}
También se puede aplicar la búsqueda binaria cuando se tiene un vector ordenado, de
la siguiente manera:
int busquedaBinaria (int key ){
int inicio = 0 ;
int fin =n-1;
while( inicio <= fin ){
int mitad =(inicio + fin) / 2;
if( vector[mitad] < key )
inicio = mitad + 1;
else if( vector[mitad] > key )
fin = mitad –1;
else
return mitad;
}
return -1;
}
Proponga un vector ordenado con números enteros y haga el seguimiento de cada
uno de los métodos de búsqueda.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 03
ORDENAMIENTO Y BUSQUEDA
En arreglos de objetos
Ahora vamos a adecuar los algoritmos de ordenamiento vistos en la clase anterior para ordenar colecciones de objetos. Para ello, considere la clase Producto con los siguientes atributos: código(cadena), descripción(cadena), precio(real). Diseñe la clase ColeccionProductos que tenga como atributo un objeto de la clase ArrayList y considere los siguientes métodos de administración: adiciona(), obtiene(), tamaño(), actualiza(). Finalmente diseñe la clase ColeccionProductosEnOrden que herede a la clase ColeccionProductos y agregue los siguientes métodos de ordenamiento: burbujaOptimizada(), inserción(), selección().
El método burbuja optimizada tendría el siguiente código para ordenar, en forma
ascendente, por código:
Producto temp;
for (int i=0 ; i<tamaño() - 1; i++)
for (int j=i+1; j<tamaño(); j++)
if (obtiene(i).getCodigo().compareTo(
obtiene(j).getCodigo())>0 ){
temp = new
Producto(obtiene(i).getCodigo(),
obtiene(i).getDescripcion(),
obtiene(i).getPrecio());
actualiza(i,obtiene(j));
actualiza(j,temp);
}
El método inserción tendría el siguiente código para ordenar, en forma ascendente,
por descripcion:
int i, j;
Producto temp;
for (i = 1; i < tamaño(); i++){
temp = new Producto(obtiene(i).getCodigo(),
obtiene(i).getDescripcion(),
obtiene(i).getPrecio());
j = i - 1;
while (j >= 0 &&
obtiene(j).getDescripcion().compareTo(
temp.getDescripcion()) > 0){
actualiza(j + 1,obtiene(j));
j--;
}
actualiza(j + 1,temp);
}
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Haga el código para ordenar por precio, en forma ascendente, con el método
Selección.
BUSQUEDA:
Puede aplicar su método de búsqueda secuencial con clave entera:
int busquedaSecuencial( int key ){
for(int i=0, i<tamaño(), i++){
if(obtiene(i).getDato()==key)
return i;
}
return -1;
}
Sin embargo, cuando el vector está ordenado, el método de búsqueda puede mejorar
en tiempo, de la siguiente manera:
int busquedaSecuencial( int key){
int i = 0;
while(i<tamaño() && obtiene(i).getDato()<key){
i++;
}
if(i<tamaño() && obtiene(i).getDato()==key)
return i;
else
return-1;
}
También se puede aplicar la búsqueda binaria cuando se tiene un vector ordenado,
de la siguiente manera:
int busquedaBinaria (int key ){
int inicio = 0 ;
int fin =tamaño()-1;
while( inicio <= fin ){
int mitad <-(inicio + fin) / 2;
if( obtiene(mitad).getDato() < key )
inicio = mitad + 1;
else
if(obtiene(mitad).getDato() > key )
fin = mitad –1;
else
return mitad;
}
return -1;
}
Adecúe los métodos de búsqueda presentados para que sean utilizados con el arreglo
de objetos de Productos. Elija el código de producto como clave de búsqueda.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 04
EVALUACION
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 05
RECURSIVIDAD
En métodos sin retorno
Ideas principales
Una función recursiva es aquella que se llama a sí misma.
La recursividad es una alternativa a la repetición o iteración.
La recursividad es un concepto fundamental en matemáticas y en computación.
Es una alternativa diferente para implementar estructuras de repetición (ciclos).
Los módulos se hacen llamadas recursivas.
Imágenes recursivas
Ejemplo Matrushka
• La Matrushka es una artesanía tradicional rusa. Es una muñeca de madera que
contiene otra muñeca más pequeña dentro de sí. Esta muñeca, también
contiene otra muñeca dentro. Y así, una dentro de otra.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Método Recursivo
Definición de un método recursivo
• La característica principal de la recursividad es que siempre existe un medio de
salir de la definición (caso base o salida), y la segunda condición (llamado
recursivo) es propiamente donde se llama a sí misma.
• Caso base:
– Es el caso más simple de una función recursiva, y simplemente
representa la salida del método recursivo.
• Caso recursivo:
– Relaciona el resultado del algoritmo con resultados de casos más
simples. Dado que cada caso de problema se ve similar al problema
original, el método llama una copia nueva de si misma, para que
empiece a trabajar sobre el problema más pequeño y esto se conoce
como una llamada recursiva y también se llama el paso de recursión.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 1: Desarrolle un método recursivo que muestre los n primeros múltiplos de 5
en forma descendente.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 2: Desarrolle un método recursivo que muestre los n primeros múltiplos de 5
en forma ascendente. Ejm. N=3, rpta: 5,10,15
void serie (int num){
if(num>1)
serie(num-1);
imprime(num*5+” ”);
}
Llamada del método: serie(3).
Dibuje la secuencia de ejecución y determine el resultado.
Ejemplo 3: Desarrolle un método recursivo que muestre las cifras invertidas de un
número entero.
void cifrasInvertidas (int num){
if(num>0){
imprime(num%10+”,”);
cifrasInvertidas(num/10);
}
}
Llamada del método: cifrasInvertidas(3245).
Dibuje la secuencia de ejecución y determine el resultado.
Ejemplo 4: Desarrolle un método recursivo que muestre los n primeros números
naturales consecutivos en forma descendente. Ejm. N=5, rpta: 5,4,3,2,1
void consecutivosDescendentes (int n){
if(n>0){
imprime(n+”,”);
consecutivosDescendentes(num-1);
}
}
Llamada del método: consecutivosDescendentes(5).
Dibuje la secuencia de ejecución y determine el resultado.
Ejemplo 5: Desarrolle un método recursivo que muestre los n primeros números
naturales consecutivos en forma ascendente. Ejm. N=5, rpta: 1,2,3,4,5
Ejemplo 6: Desarrolle un método recursivo que muestre los números consecutivos
descendentes hasta 0 y luego los números consecutivos ascendentes hasta el número
dado como parámetro. Ejm. N=5, rpta: 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 7: Desarrolle un método recursivo que muestre el contenido de un vector de
enteros
Ejemplo 8: Desarrolle un método recursivo que muestre el contenido invertido de un
vector de enteros
Ejemplo 9: Desarrolle un método recursivo que realice la búsqueda binaria en un
vector de enteros.
Ejemplo 10: Implemente el método recursivo de búsqueda en la clase
ColeccionProductosEnOrden.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 06
RECURSIVIDAD
En métodos con retorno
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 1: Desarrolle un método recursivo que retorne la suma de los n primeros
números naturales.
Ejemplo 2: Desarrolle un método recursivo que retorne el factorial de un número
entero no negativo: considere que:
n! = n * (n-1) * (n-2) * … *2 *1
n! = n(n-1)!
Ahora de manera recursiva se puede definir el factorial como:
int factorial(int n) {
if(n!=0)
return n*factorial(n-1) ;
else
return 1;
}
0 si )!1(*
0 si 1!
nnn
nn
CASO BASE
CASO RECURSIVO
Es importante determinar un caso BASE, es decir, un punto en el cual existe
una condición por la cual no se requiere volver a llamar a la misma función,
sino que devuelve un resultado.
Hace el llamado recursivo al
mismo método
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Llamada: int f = factorial(5);
Ejemplo 3: Desarrolle un método recursivo que calcule el producto de dos
números enteros. El producto de dos números se calcula también como una
suma de la siguiente manera:
Producto(a,b) = a + a + a + a + a + ….. + a (b veces)
public int producto (int a, int b){
if(b==1)
return a;
else
return a+producto(a,b-1);
}
Llamada: int p = producto(3,5);
Dibuje la secuencia de ejecución y determine el resultado.
Agregue lo necesario para considerar la posibilidad de que el producto sea 0.
5! 5*4! 4*3! 3*2! 2*1! 1*0!
Caso BASE devuelve 1
5! 5*4! 4*3! 3*2! 2*1! 1*0!
0!=1
Devuelve 1!=1
Devuelve 2!=2
Devuelve 3!=6
Devuelve 4!=24
Devuelve 5!=120
5!=120
1 si )1,(
1 si ),(
bbaproductoa
babaproducto
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 4: Desarrolle un método recursivo que retorne la potencia entera de un
número real
Ejemplo 5: Desarrolle un método recursivo que retorne el máximo común
divisor (MCD) de dos números enteros.
Ejemplo 6: desarrolle un método recursivo que retorne la suma de los números
contenidos en un vector de enteros.
Ejemplo 7: desarrolle un método recursivo que retorne el menor valor de los
números contenidos en un vector.
0.
;01)1( nsiXX
nsiX
n
n
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 07
EVALUACION
Y
EXPOSICION DEL TRABAJO DE INVESTIGACION I
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 08
EVALUACION INTEGRAL
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 09
LISTAS SIMPLES
Tipo pila
APUNTADORES
●Apuntador (puntero) es una variable capaz de almacenar una dirección de
memoria (apunta a).
●En Java y en cualquier otro lenguaje, todos los objetos son apuntadores porque
almacenan una dirección de memoria donde se guardan sus respectivos
atributos.
Liberación de Memoria
●Para liberar la memoria asignada a un apuntador, Java utiliza la técnica de
garbage collection que consiste en liberar la memoria de los objetos cuando
éstos mueren (salen de su ámbito)
●Liberar la memoria significa que el espacio ocupado por los atributos de algún
objeto se vuelve disponible.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Lista Enlazada
●Representación secuencial en la cual el orden lógico y físico no necesariamente
es el mismo.
●El orden lógico se representa de tal forma que cada elemento apunta al
siguiente (los elementos se encuentran enlazados).
●El orden físico est{ representado por las posiciones físicas que ocupa la lista
enlazada en memoria.
●La unidad de una lista enlazada es el Nodo el cual es una clase.
●La clase Nodo, tiene dos atributos básicos:
Información : objeto que guarda los datos correspondientes a sus
atributos, como código, apellidos, nombres, etc.
Siguiente : objeto apuntador al siguiente nodo, es un objeto del
mismo tipo de la clase Nodo.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ventajas:
●Consumo de memoria a requerimiento. No hay desperdicio de memoria como
en los arreglos.
●Insersión y Eliminación eficientes. A diferencia de estas operaciones en
arreglos donde se consume más tiempo de proceso.
Desventajas:
●Requiere de espacio de memoria extra para los apuntadores.
●Búsqueda ineficiente y lenta: para llegar al n-ésimo elemento hay que pasar
por los n-1 anteriores.
LISTA ENLAZADA TIPO PILA
Operación de Insersión tipo LIFO: Last In, First Out
Esta operación hace que el último nodo ingresado sea el primero de la lista.
Instrucciones de insersión:
Nodo nuevo = new Nodo(info);
nuevo.setSiguiente(inicio);
inicio = nuevo;
/ inicio
Dibuje la secuencia de instrucciones
y verifique el comportamiento de
insersión en una pila.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Operación de eliminación en una pila
Esta operación hace que sea eliminado (sacado) al primero de la lista.
Instrucciones de eliminación:
if(inicio != null){
Nodo aux=inicio.getSiguiente();
inicio = aux;
}
Instrucciones de búsqueda:
Nodo aux=inicio;
while(aux!=null){
if(aux.getInfo().getDato() == key)
return aux;
else
aux = aux.getSiguiente();
}
Ejercicio 1
Considere la clase Empleado con los siguientes atributos: código(cadena),
nombre(cadena), sueldo(real).
Diseñe la clase NodoEmpleado con los siguientes atributos: un objeto info de tipo
Empleado y un objeto siguiente de tipo NodoEmpleado.
Diseñe la clase PilaEmpleados con los siguientes atributos: un objeto inicio de tipo
NodoEmpleado, un contador de empleados tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelEmpleados con el siguiente atributo: un objeto pe de tipo
PilaEmpleados y con la siguiente interface gráfica:
Dibuje la secuencia de
instrucciones y verifique el
comportamiento de eliminación
en una pila.
Dibuje la secuencia de
instrucciones y verifique el
comportamiento de búsqueda.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Programe la acción de los botones. Diseñe la clase Principal (Frame) y haga
funcionar su aplicación.
Ejercicio 2
Considere la clase Producto con los siguientes atributos: código(cadena),
nombre(cadena), precio(real), origen(cadena).
Diseñe la clase NodoProducto con los siguientes atributos: un objeto info de tipo
Producto y un objeto siguiente de tipo NodoProducto.
Diseñe la clase PilaProductos con los siguientes atributos: un objeto inicio de tipo
NodoProducto, un contador de productos tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelProductos con el siguiente atributo: un objeto pe de tipo
PilaProductos con la interface gráfica correspondiente
Ejercicio 3
Considere la clase Frase con los siguientes atributos: texto(cadena)
Diseñe la clase NodoFrase con los siguientes atributos: un objeto info de tipo Frase y
un objeto siguiente de tipo NodoFrase.
Diseñe la clase PilaFrases con los siguientes atributos: un objeto inicio de tipo
NodoFrase, un contador de frases tipo entero. También considere los siguientes
métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelFrases con el siguiente atributo: un objeto pe de tipo PilaFrases
con la interface gráfica correspondiente.
Agrega Elimina Busca Lista
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 4
Diseñe la clase Entero con los siguientes atributos: numero(entero)
Diseñe la clase NodoEntero con los siguientes atributos: un objeto info de tipo Entero
y un objeto siguiente de tipo NodoEntero.
Diseñe la clase PilaEnteros con los siguientes atributos: un objeto inicio de tipo
NodoEntero, un contador de números tipo entero. Tambien considere los siguientes
métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelEnteros con el siguiente atributo: un objeto de tipo PilaEnteros
con la interface gráfica correspondiente.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 10
LISTAS SIMPLES
Tipo cola
LISTA ENLAZADA TIPO COLA
Operación de Insersión tipo FIFO: First In, First Out
Esta operación hace que el primer nodo ingresado sea el primero de la lista.
Instrucciones de insersión:
Nodo temp = new Nodo( info );
if(inicio==null)
inicio=temp;
else{
Nodo aux = inicio;
while(aux.getSiguiente()!=null)
aux = aux.getSiguiente();
aux.setSiguiente(temp);
}
Dibuje la secuencia de
instrucciones y verifique el
comportamiento de insersión en
una cola.
1 2 3 4
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Operación de eliminación en una cola
Esta operación hace que sea eliminado (sacado) al primero de la lista.
Instrucciones de eliminación:
if(inicio != null){
Nodo aux=inicio.getSiguiente();
inicio = aux;
}
Instrucciones de búsqueda:
Nodo busca(key){
Nodo aux=inicio;
while(aux!=null){
if(aux.getInfo().getDato() == key)
return aux;
else
aux = aux.getSiguiente();
}
return null;
}
Nota: este método debe recibir la key que quiere buscar y debe retornar el
puntero del nodeo donde fue encontrado o null en caso que no sea encontrado
LISTA ENLAZADA SIMPLE
Considera operaciones de insersión diversas: al inicio, al final, después de.
Para la operación de eliminación considera como parámetro un nodo.
Dibuje la secuencia de instrucciones
y verifique el comportamiento de
eliminación en una cola.
Dibuje la secuencia de
instrucciones y verifique el
comportamiento de búsqueda.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 1
Considere la clase Empleado con los siguientes atributos: código(cadena),
nombre(cadena), sueldo(real).
Diseñe la clase NodoEmpleado con los siguientes atributos: un objeto info de tipo
Empleado y un objeto siguiente de tipo NodoEmpleado.
Diseñe la clase ColaEmpleados con los siguientes atributos: un objeto inicio de tipo
NodoEmpleado, un contador de empleados tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelEmpleados con el siguiente atributo: un objeto pe de tipo
ColaEmpleados y con la siguiente interface gráfica:
Programe la acción de los botones. Diseñe la clase Principal (Frame) y haga
funcionar su aplicación.
Ejercicio 2
Considere la clase Producto con los siguientes atributos: código(cadena),
nombre(cadena), precio(real), origen(cadena).
Diseñe la clase NodoProducto con los siguientes atributos: un objeto info de tipo
Producto y un objeto siguiente de tipo NodoProducto.
Diseñe la clase ColaProductos con los siguientes atributos: un objeto inicio de tipo
NodoProducto, un contador de productos tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelProductos con el siguiente atributo: un objeto pe de tipo
ColaProductos con la interface gráfica correspondiente
Agrega Elimina Busca Lista
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 3
Diseñe en un nuevo proyecto la administración de una LISTA SIMPLE DE
EMPLEADOS que permita realizar los procesos de la siguiente interface gráfica:
Ejercicio 4
Diseñe en un nuevo proyecto un Frame con las siguientes opciones de menú:
Listas Empleados Salir
Tipo pila no
Tipo cola si
Simple
Al elegir una opción de listas muestre la funcionalidad de la lista correspondiente.
Busca Modifica Elimina Al Inicio Al Final Lista
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 11
EVALUACION
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 12
LISTAS DOBLES
●La unidad de una lista enlazada es el Nodo el cual es una clase.
●La clase Nodo, tiene tres atributos básicos:
Información : objeto que guarda los datos correspondientes a sus
atributos, como código, apellidos, nombres, etc.
Siguiente : objeto apuntador al siguiente nodo, es un objeto del
mismo tipo de la clase Nodo.
Anterior : objeto apuntador al anterior nodo, es un objeto del
mismo tipo de la clase Nodo.
Representación gráfica:
Lista vacía:
Inicio = null
null
null
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Operación de Inserción:
Operación de Eliminación:
Al inicio:
if(aux.ant==null){
aux.sig.ant=null;
inicio=aux.sig;
conta--;
}
null
null null
null
null null
null null
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Al final:
if(aux.sig==null){
aux.ant.sig=null;
conta--;
}
Al medio:
aux.ant.sig = aux.sig;
aux.sig.ant = aux.ant;
conta--;
Operación de Recorrido: de izquierda a derecha y de derecha a izquierda.
Ventajas:
●Al identificar a un nodo, automáticamente se identifica el anterior y el
siguiente.
●El recorrido se puede realizar en ambos sentidos.
Desventajas:
●Requiere de espacio de memoria extra para el apuntador del anterior.
●Las operaciones de inserción y eliminación requieren mayor cuidado que las
listas simples.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 1
Considere la clase Empleado con los siguientes atributos: código(cadena),
nombre(cadena), sueldo(real).
Diseñe la clase NodoEmpleado con los siguientes atributos: un objeto info de tipo
Empleado, un objeto siguiente de tipo NodoEmpleado y un objeto anterior de tipo
NodoEmpleado.
Diseñe la clase ListaDobleEmpleados con los siguientes atributos: un objeto inicio de
tipo NodoEmpleado, un contador de empleados tipo entero. También considere los
siguientes métodos de administración: agregaAlFinal(), agregaAlInicio(), elimina(),
busca(), getN().
Diseñe la clase PanelEmpleados con el siguiente atributo: un objeto lde de tipo
ListaDobleEmpleados y con la siguiente interface gráfica:
Programe la acción de los botones. Diseñe la clase Principal (Frame) y haga
funcionar su aplicación.
Ejercicio 2
Considere la clase Producto con los siguientes atributos: código(cadena),
nombre(cadena), precio(real), origen(cadena).
Diseñe la clase NodoProducto con los siguientes atributos: un objeto info de tipo
Producto, un objeto siguiente de tipo NodoProducto y un objeto anterior de tipo
NodoProducto.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase ListaDobleProductos con los siguientes atributos: un objeto inicio de
tipo NodoProducto, un contador de productos tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca(), getN()
Diseñe la clase PanelProductos con el siguiente atributo: un objeto ldp de tipo
ListaDobleProductos con la interface gráfica correspondiente
Ejercicio 3
Diseñe la clase ListaDobleEmpleadosA que herede a la clase
ListaDobleEmpleados y considere los métodos necesarios para guardar la
información en un archivo de texto.
Haga los cambios necesarios en la clase Principal (Frame) y ejecute su aplicación.
Ejercicio 4
Diseñe la clase ListaDobleProductosA que herede a la clase ListaDobleProductos
y considere los métodos necesarios para guardar la información en un archivo de
texto.
Haga los cambios necesarios en la clase Principal (Frame) y ejecute su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 13
LISTAS DOBLES
Clase LinkedList
LinkedList, al igual que ArrayList es una implementación de la interface List. Esta
clase provee métodos para obtener (get), remover (remove) e insertar elementos al
principio(addFirst), al final(addLast), después de algún nodo (add), antes de algún
nodo(add). Estas operaciones permiten a las listas doblemente enlazadas sean
utilizadas como pila, cola o como listas generales.
Métodos más frecuentes:
addFirst(<objeto-info>): agrega un nuevo nodo con el objeto info al inicio de la
lista.
addLast (<objeto-info>): agrega un nuevo nodo con el objeto info al final de la
lista.
add(<posicion>, objeto): agrega un nuevo nodo en la posición entera indicada
removeFirst (): elimina el nodo del inicio de la lista.
removeLast(): elimina el nodo del final de la lista.
remove(<posición>): elimina el nodo de la posición indicada
remove(<objeto-info>): elimina el nodo que contiene al objeto indicado
size(): retorna la cantidad de nodos de la lista.
clear(): elimina todos los nodos de la lista.
indexOf(<objeto-info>): retorna el número de nodo correspondiente al objeto
indicado.
Ejercicio 1
Considere la clase Empleado con los siguientes atributos: código(cadena),
nombre(cadena), sueldo(real).
Diseñe la clase ListaDobleEmpleados con los siguientes atributos: un objeto lista de
tipo LinkedList. También considere los siguientes métodos de administración:
agregaAlInicio, agregaAlFinal(), elimina(), busca(), getNodos().
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase PanelEmpleados con el siguiente atributo: un objeto lde de tipo
ListaDobleEmpleados y con la siguiente interface gráfica:
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Programe la acción de los botones.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase Principal (Frame) y haga funcionar su aplicación.
Ejercicio 2
Considere la clase Producto con los siguientes atributos: código(cadena),
nombre(cadena), precio(real), origen(cadena).
Diseñe la clase ListaDobleProductos con los siguientes atributos: un objeto lista de
tipo LinkedList. También considere los siguientes métodos de administración:
agregaAlInicio, agregaAlFinal(), elimina(), busca(), getN().
Diseñe la clase PanelProductos con el siguiente atributo: un objeto ldp de tipo
ListaDobleProductos con la interface gráfica correspondiente
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 14
ARBOLES BINARIOS DE BUSQUEDA
Arbol:
Un árbol impone una estructura jerárquica sobre una colección de objetos. Ejemplos:
árboles genealógicos, organigramas, etc.
Arbol: es una colección de elementos llamados nodos, uno de los cuales se distingue
como raíz, junto con una relación (de “paternidad”) que impone una estructura
jerárquica sobre los nodos.
Cada nodo puede tener varios hijos.
Aplicaciones:
Analizar circuitos eléctricos.
Representar la estructura de fórmulas matemáticas.
Organizar la información
Representar la estructura sintáctica de un programa en los compiladores.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 1:
Arbol binario:
Cada nodo tiene máximo 2 hijos.
Cada nodo tiene información y dos apuntadores, subárboles conocidos como subárbol
izquierdo y subárbol derecho.
Ejemplo 1:
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 2:
Recorridos de un árbol binario:
Pre Orden : Raiz, Izquierda, Derecha (RID)
Entre Orden : Izquierda, Raiz, Derecha (IRD)
Post Orden : Izquierda, Derecha, Raiz (IDR)
Ejemplo 1: Haga los tres recorridos del siguiente árbol:
Arbol binario de búsqueda:
Agiliza los procesos de búsqueda, inserción, eliminación
Valores menores a la izquierda de la raíz, valores mayores a la derecha de la raíz.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejemplo 1:
Observaciones:
En un arreglo es posible localizar datos eficientemente si los mismos están ordenados,
pero las operaciones de inserción y eliminación resultan costosas.
En las listas, las operaciones de inserción y eliminación se pueden llevar a cabo con
facilidad, pero la búsqueda es una operación costosa.
En un árbol binario de búsqueda, las operaciones de búsqueda, inserción y eliminación
se pueden llevara a cabo con facilidad.
Ejercicio 1:
Construya un árbol binario de búsqueda con los siguientes valores y luego escriba el recorrido
pre-orden, en-orden, post-orden:
121, 87, 34, 12, 54, 76, 100, 28, 99, 115, 16, 66.
Ejercicio 2:
Construya un árbol binario de búsqueda con los siguientes nombres y luego escriba el
recorrido pre-orden, en-orden, post-orden:
joaquin, jaime, jessica, jeremias, jesus, julio, jose, juan, Javier, juan, jonas, josefina.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 3:
Construya un árbol binario de búsqueda con las siguientes claves y luego escriba el recorrido
pre-orden, en-orden, post-orden:
K034, k210, k056, k110, k072, k210, k087, k005, k029, k108, k025, k140.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 15
EVALUACION
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 16
EXPOSICION DEL TRABAJO DE INVESTIGACION II
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 17
EVALUACION INTEGRAL
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 01
GUIA DE LABORATORIO 1
Polimorfismo con colecciones
Ejercicio 1
Cree un proyecto nuevo de nombre P01E01. Cree un paquete nuevo de nombre
vehiculos. Diseñe una clase de nombre Vehiculo con los siguientes atributos
privados: placa (cadena), marca (cadena), pasajeros (entero), precio (real).
implemente el constructor y todos los métodos accesores(get,set) de los atributos de
la clase.
Considere un método abstracto de nombre clase() que retorne el nombre de la clase.
Considere un método no abstracto de nombre info() que retorne la información de un
vehículo separando sus campos por un tabulador.
Diseñe otra clase de nombre Automovil que herede a la clase Vehiculo con los
siguientes atributos:
implemente el constructor y todos los métodos accesores(get,set) de los atributos de la clase.
Desarrolle el método abstracto clase() para que retorne el nombre de la clase.
Desarrolle el método no abstracto info() aplicando refinamiento para que considere
sus propios atributos adicionales a la información del vehículo.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe otra clase de nombre Camion que herede la clase Vehiculo con los siguientes
atributos:
implemente el constructor y todos los métodos accesores(get,set) de los atributos de la clase.
Desarrolle el método abstracto clase() para que retorne el nombre de la clase.
Desarrolle el método no abstracto info() aplicando refinamiento para que considere
sus propios atributos adicionales a la información del vehículo.
Diseñe otra clase de nombre ColeccionVehiculos que tenga como atributo un objeto
de la clase ArrayList e implemente los métodos de administración.
Diseñe otra clase de nombre PanelPrincipal que tenga una vista similar a la siguiente:
Programe la acción de los botones, Diseñe la clase Principal y ejecute su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 02
GUIA DE LABORATORIO 2
Ordenamiento y búsqueda
En arreglos simples
Ejercicio 1:
Cree un proyecto de nombre P02E01, un paquete de nombre p02e01 y diseñe la clase
OrdenarVector con los siguientes atributos:
Arreglo de enteros de tamaño 1000.
Considere los siguientes métodos:
llenaVector(), genera números enteros aleatorios pertencientes al rango 0 a 1000 y
los guarda en el arreglo.
ordenBurbuja(), ordena el arreglo mediante el método burbuja.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
ordenBurbujaOptimizada(), ordena el arreglo mediante el método burbuja
Optimizada.
ordenInsersion(), ordena el arreglo mediante el método de inserción
ordenSeleccion(), ordena el arreglo mediante el método de selección
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
contenido(), retorna en un string el contenido del arreglo en forma tabulada.
Diseñe la clase PanelPrincipal con 5 botones y programe cada uno de ellos invocando
al contenido para verificar el proceso.
Diseñe la clase Principal de tipo Frame donde coloca el panel anterior y hace funcionar
su programa.
Ejercicio 2
En base al ejercicio 1 haga que el tamaño del arreglo sea dinámico y se ingrese desde
la interfaz gráfica de usuario (panel principal).
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 3
En base al ejercicio 1 haga las modificaciones necesarias para saber la cantidad de
iteraciones que realiza cada método de ordenamiento y agrege un botón en su panel
para saber la cantidad de iteraciones que realiza cada método con el mismo
contenido.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 03
GUIA DE LABORATORIO 3
Ordenamiento y búsqueda
En arreglos de objetos
Ejercicio 1:
Cree un proyecto de nombre P03E01, un paquete de nombre p03e01 y diseñe la clase
Producto con los siguientes atributos: código(cadena), descripción(cadena),
precio(real). Luego diseñe la clase ColeccionProductos con los siguientes atributos:
Objeto de tipo ArrayList particularizada para la clase <Producto> con sus métodos de
administración: adiciona(), obtiene(), tamaño(), actualiza().
Luego diseñe la clase ColeccionProductosEnOrden que hereda a la clase
ColeccionProductos
Agrege los siguientes métodos:
ordenBurbujaOptimizada(), ordena el arreglo de productos, en orden ascendente,
por código mediante el método burbuja Optimizada
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
ordenInsersion(), ordena el arreglo de productos, en orden ascendente, por
descripción mediante el método de inserción
ordenSeleccion(), ordena el arreglo de productos, en orden descendente, por precio
mediante el método de selección
contenido(), retorna en un string el contenido del arreglo de productos en forma
tabulada.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase PanelPrincipal con 5 botones y programe cada uno de ellos invocando
al contenido para verificar el proceso.
Diseñe la clase Principal de tipo Frame donde coloca el panel anterior y hace funcionar
su programa.
Ejercicio 2: En base al ejercicio 1 haga las modificaciones necesarias para que la
forma del ordenamiento se elija desde la interfaz gráfica de usuario.
Ejercicio 3
En base al ejercicio 2 haga las modificaciones necesarias para que el ordenamiento se
realice con el método Shell.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 04
EVALUACION
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 05
GUIA DE LABORATORIO 5
Recursividad sin retorno
Ejercicio 1
Diseñe una clase Numeros con los siguientes métodos recursivos de ámbito static:
Que muestre los n primeros múltiplos de 5 en forma ascendente. Ejm. N=3, rpta: 5 10
15
Que muestre las cifras invertidas de un número entero.
Que muestre los n primeros números naturales consecutivos en forma descendente.
Ejm. N=5, rpta: 5-4-3-2-1
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Luego diseñe la interfaz gráfica de usuario con los botones necesarios para invocar a
los métodos recursivos.
Ejercicio 2
Herede a la clase del ejercicio 1 y desarrolle los siguientes métodos recursivos
adicionales:
a) Que muestre los n primeros números naturales consecutivos en forma ascendente.
Ejm. N=5, rpta: 1,2,3,4,5
b) que muestre los números consecutivos descendentes hasta 0 y luego los números
consecutivos ascendentes hasta el número dado como parámetro. Ejm. N=5, rpta: 5,
4, 3, 2, 1, 0, 1, 2, 3, 4, 5
Luego diseñe la interfaz gráfica de usuario con los botones necesarios para invocar a
los métodos recursivos.
Ejercicio 3
Diseñe una clase AEnteros con los siguientes métodos recursivos:
a) que llene un vector con 30 numeros aleatorios enteros de 2 cifras.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
b) que muestre el contenido de un vector de enteros
c) que muestre el contenido invertido de un vector de enteros
d) que realice la búsqueda binaria en un vector de enteros.
Diseñe un panel para el ingreso de datos de cada método, el área de salida y los
botones de proceso.
Diseñe un frame que soporte al panel y ejecute su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 06
GUIA DE LABORATORIO 6
Recursividad con retorno
Ejercicio 1
Diseñe una clase Numeros con los siguientes métodos de ámbito static:
Diseñe un panel para el ingreso de datos de cada método, el área de salida y los
botones de proceso.
Diseñe un frame que soporte al panel y ejecute su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 2
Herede la clase del ejercicio 1 y desarrolle los siguientes métodos recursivos
adicionales:
a) que retorne la suma de los n primeros números naturales.
b) que retorne el máximo común divisor (MCD) de dos números enteros.
c) que retorne el cociente entero de la división de 2 numeros enteros aplicando el
método de restas sucesivas.
Ejercicio 3
Diseñe una clase AEnteros que tenga como atributo un objeto de tipo ArrayList y
considere los siguientes métodos recursivos:
a) que llene el arreglo con números aleatorios de 2 cifras.
b) que retorne todo el contenido del arreglo
c) que retorne solo los números pares contenidos en el arreglo
d) que muestre solo los números impares contenidos en el arreglo.
e) que retorne la suma de los números contenidos en un vector de enteros.
f) que retorne el menor valor de los números contenidos en un vector.
Diseñe en un panel la interfaz gráfica necesaria con un botón para cada método.
Diseñe un frame que contenga al panel y ejecute su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 07
EVALUACION
Y
EXPOSICIÓN DE TRABAJO DE INVESTIGACION I
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 08
EVALUACION INTEGRAL
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 09
GUIA DE LABORATORIO 09
Listas simples: tipo pila
Ejercicio 1
Considere la clase Empleado con los siguientes atributos: código(cadena),
nombre(cadena), sueldo(real).
Diseñe la clase NodoEmpleado con los siguientes atributos: un objeto info de tipo
Empleado y un objeto siguiente de tipo NodoEmpleado.
Diseñe la clase PilaEmpleados con los siguientes atributos: un objeto inicio de tipo
NodoEmpleado, un contador de empleados tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca()
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase PanelEmpleados con el siguiente atributo: un objeto pe de tipo
PilaEmpleados y con la siguiente interface gráfica:
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Programe la acción de los botones. Diseñe la clase Principal (Frame) y haga funcionar
su aplicación.
Ejercicio 2
Considere la clase Producto con los siguientes atributos: código(cadena),
nombre(cadena), precio(real), origen(cadena).
Diseñe la clase NodoProducto con los siguientes atributos: un objeto info de tipo
Producto y un objeto siguiente de tipo NodoProducto.
Diseñe la clase PilaProductos con los siguientes atributos: un objeto inicio de tipo
NodoProducto, un contador de productos tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelProductos con el siguiente atributo: un objeto pe de tipo
PilaProductos con la interface gráfica correspondiente
Ejemplo 3
Considere la clase Frase con los siguientes atributos: texto(cadena)
Diseñe la clase NodoFrase con los siguientes atributos: un objeto info de tipo Frase y
un objeto siguiente de tipo NodoFrase.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase PilaFrases con los siguientes atributos: un objeto inicio de tipo
NodoFrase, un contador de frases tipo entero. También considere los siguientes
métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelFrases con el siguiente atributo: un objeto pe de tipo PilaFrases
con la interface gráfica correspondiente.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 10
GUIA DE LABORATORIO 10
Listas simples: tipo cola
Ejercicio 1
Considere la clase Empleado con los siguientes atributos: código(cadena),
nombre(cadena), sueldo(real).
Diseñe la clase NodoEmpleado con los siguientes atributos: un objeto info de tipo
Empleado y un objeto siguiente de tipo NodoEmpleado.
Diseñe la clase ColaEmpleados con los siguientes atributos: un objeto inicio de tipo
NodoEmpleado, un contador de empleados tipo entero.
También considere los siguientes métodos de administración: agrega(), elimina(),
busca()
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase PanelEmpleados con el siguiente atributo: un objeto pe de tipo
ColaEmpleados y con la siguiente interface gráfica:
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Programe la acción de los botones. Diseñe la clase Principal (Frame) y haga
funcionar su aplicación.
Ejercicio 2
Considere la clase Producto con los siguientes atributos: código(cadena),
nombre(cadena), precio(real), origen(cadena).
Diseñe la clase NodoProducto con los siguientes atributos: un objeto info de tipo
Producto y un objeto siguiente de tipo NodoProducto.
Diseñe la clase ColaProductos con los siguientes atributos: un objeto inicio de tipo
NodoProducto, un contador de productos tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca()
Diseñe la clase PanelProductos con el siguiente atributo: un objeto pe de tipo
ColaProductos con la interface gráfica correspondiente
Ejercicio 3
Diseñe en un nuevo proyecto la administración de una LISTA SIMPLE DE
EMPLEADOS que permita realizar los procesos de la siguiente interface gráfica:
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 4
Diseñe en un nuevo proyecto un Frame con las siguientes opciones de menú:
Listas Empleados Salir
Tipo pila no
Tipo cola si
Simple
Al elegir una opción de listas muestre la funcionalidad de la lista correspondiente.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 11
EVALUACION
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 12
GUIA DE LABORATORIO 12
Listas dobles
Ejercicio 1
Considere la clase Empleado con los siguientes atributos: código(cadena),
nombre(cadena), sueldo(real).
Diseñe la clase NodoEmpleado con los siguientes atributos: un objeto info de tipo
Empleado, un objeto siguiente de tipo NodoEmpleado y un objeto anterior de tipo
NodoEmpleado.
Diseñe la clase ListaDobleEmpleados con los siguientes atributos: un objeto inicio de
tipo NodoEmpleado, un contador de empleados tipo entero.
También considere los siguientes métodos de administración: agregaAlFinal(),
agregaAlInicio(), elimina(), busca(), getN().
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase PanelEmpleados con el siguiente atributo: un objeto lde de tipo
ListaDobleEmpleados y con la siguiente interface gráfica:
Programe la acción de los botones. Diseñe la clase Principal (Frame) y haga
funcionar su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 2
Diseñe la clase ListaDobleEmpleadosA que herede a la clase
ListaDobleEmpleados y considere los métodos necesarios para guardar la
información en un archivo de texto.
Haga los cambios necesarios en la clase Principal (Frame) y ejecute su aplicación.
Ejercicio 3
Considere la clase Producto con los siguientes atributos: código(cadena),
nombre(cadena), precio(real), origen(cadena).
Diseñe la clase NodoProducto con los siguientes atributos: un objeto info de tipo
Producto, un objeto siguiente de tipo NodoProducto y un objeto anterior de tipo
NodoProducto.
Diseñe la clase ListaDobleProductos con los siguientes atributos: un objeto inicio de
tipo NodoProducto, un contador de productos tipo entero. También considere los
siguientes métodos de administración: agrega(), elimina(), busca(), getN()
Diseñe la clase PanelProductos con el siguiente atributo: un objeto ldp de tipo
ListaDobleProductos con la interface gráfica correspondiente
Ejercicio 4
Diseñe la clase ListaDobleProductosA que herede a la clase ListaDobleProductos
y considere los métodos necesarios para guardar la información en un archivo de
texto.
Haga los cambios necesarios en la clase Principal (Frame) y ejecute su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 13
GUIA DE LABORATORIO 13
Listas dobles: clase LinkedList
Ejercicio 1
Considere la clase Empleado con los siguientes atributos: código(cadena),
nombre(cadena), sueldo(real).
Diseñe la clase ListaDobleEmpleados con los siguientes atributos: un objeto lista de
tipo LinkedList.
También considere los siguientes métodos de administración: agregaAlInicio,
agregaAlFinal(), elimina(), busca(), getN().
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Diseñe la clase PanelEmpleados con el siguiente atributo: un objeto lde de tipo
ListaDobleEmpleados y con la siguiente interface gráfica:
Programe la acción de los botones. Diseñe la clase Principal (Frame) y haga
funcionar su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 2
Considere la clase Producto con los siguientes atributos: código(cadena),
nombre(cadena), precio(real), origen(cadena).
Diseñe la clase ListaDobleProductos con los siguientes atributos: un objeto lista de
tipo LinkedList. También considere los siguientes métodos de administración:
agregaAlInicio, agregaAlFinal(), elimina(), busca(), getN().
Diseñe la clase PanelProductos con el siguiente atributo: un objeto ldp de tipo
ListaDobleProductos con la interface gráfica correspondiente
Ejercicio 3
Diseñe la clase ListaDobleEmpleadosA que herede a la clase
ListaDobleEmpleados y considere los métodos necesarios para guardar la
información en un archivo de texto.
Haga los cambios necesarios en el panel para que programe los botones Agrega
Despues De, Agrega Antes De.
Haga los cambios necesarios en la clase Principal (Frame) y ejecute su aplicación.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
Ejercicio 4
Diseñe la clase ListaDobleProductosA que herede a la clase ListaDobleProductos
y considere los métodos necesarios para guardar la información en un archivo de
texto.
Haga los cambios necesarios en el panel para que programe los botones Agrega
Despues De, Agrega Antes De.
Haga los cambios necesarios en la clase Principal (Frame) y ejecute su aplicación.
Ejercicio 5:
Diseñe un programa que, a través de un menú de opciones, se pueda implementar el
funcionamiento de la lista doble de empleados y la lista doble de productos.
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 14
GUIA DE LABORATORIO 14
Arboles binarios de búsqueda
Ejercicio 1:
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 15
ASESORIA PROYECTO
ESTRUCTURA DE DATOS
FACULTAD DE CIENCIAS E INGENIERIA DPTO ACADEMICO DE INGENIERIA DE SISTEMAS E INFORMATICA
SEMANA 16
EXPOSICION DE TRABAJOS
Top Related