Download Estructura de Datos y Programación TRABAJO PRÁCTICO Nº 2

 FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 2
Fecha:08/05/2012
Tema: Listas simple encadenadas. Manejo de pilas y colas dinámicas
Objetivos: Que los alumnos logren
 Capacidad para usar, en forma eficiente los diagramas UML básicos.
 Habilidad para identificar las distintas estructuras de datos dinámicas, tales como listas, pilas
y colas, utilizando P.O.O. y capacidad para seleccionar la más adecuada a la resolución del
problema.
 Capacidad para verificar la solución de algoritmos desarrollados usando POO
 Capacidad para usar, en forma eficiente, los distintos métodos de clasificación
 Destreza en el uso del entorno de desarrollo Netbeans y el lenguaje de programación Java.
 Capacidad para implementar correctamente las soluciones algorítmicas, en lenguaje de
programación Java
Fecha de presentación: Cuatro semanas a partir de la entrega del práctico.
Consideraciones generales:
 Este trabajo práctico debe realizarse en forma individual.
 La presentación implicará la entrega del material abrochado, o en una carpeta, contando con los
siguientes ítems:
o Carátula. Identificación completa del trabajo práctico con todos los datos del alumno y la
asignatura, año, carrera, etc.
o Desarrollo del práctico con hojas numeradas e identificadas, que deberá incluir:
o Los algoritmos deben estar completamente desarrollados, de manera prolija, e
incluyendo las descripciones necesarias para su mejor seguimiento (identificación,
variables utlizadas y sus funciones, etc.), cumpliendo las indicaciones relativas a la
diagramación estructurada y modular.
o Documentar suficientemente el código, agregando al principio los datos del alumno,
breve descripción del programa y métodos que implementa
o El Código de las aplicaciones solicitadas deberá enviarse al correo de la materia
[email protected]. El nombre del código deberá estar conformado de acuerdo
al siguiente esquema:
 carrera_ ApellidoNomdelAlumno_NumPrac_NumEjerc.
Conceptos teóricos
Una lista encadenada es una colección de elementos dispuestos uno detrás de otro, en la que cada
elemento se conecta con el siguiente a través de un enlace o puntero. Los elementos de la lista se
llaman nodos y están formados como mínimo por dos campos, uno para almacenar un dato de
cualquier tipo (entero, real, cadena...) y otro para el enlace o puntero (dirección del siguiente nodo).
A diferencia de la representación secuencial, el orden lógico de los elementos no necesariamente es
igual al orden físico.
Clasificación:
LSE: Lista Simple Encadenada: cada nodo tiene un único sucesor y un único predecesor (excepto el
primero y el último elemento de la lista).
LDE: Lista Doble Encadenada: cada nodo tiene dos punteros, uno a su predecesor y el otro a su
sucesor.
LCSE: Lista Circular Simple Encadenada: es una LSE donde el último elemento se encadena con el
primer elemento de la lista.
LCDE: Lista Circular Doble Encadenada: es una LDE en la que el último elemento se enlaza con el
primero y viceversa.
Para la Implementación Dinámica de listas: Se usa la asignación dinámica de memoria mediante
punteros o referencias.
Operaciones básicas
• Inicialización.
Estructuras de Datos y Programación
Trabajo Práctico N° 2
Pag:1
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 2
Fecha:08/05/2012
La primera operación a realizar con una lista encadenada es la inicialización. Esta operación constituye
una lista vacía.
public Lista() {
list = null; }
• Creación.
Pasos necesarios para crear una Lista:
1) Definir la clase Nodo.
2) Definir la clase Lista (con referencia a la cabecera).
3) Definir el método constructor Lista() que inicializa la cabecera con null (lista vacía).
• Insertar.
Para agregar elementos a la lista se debe declarar un método que implemente esta operación, en
este caso el método se lo llamaría insertar (), al que se convocará cada vez que se desee agregar un
nuevo nodo (elemento) en la lista.
El método insertar () tiene las variantes:
•
•
•
Insertar al principio de una lista encadenada insertarAntes().
Insertar en el medio de una lista encadenada InsertarMedio().
Insertar al final de una lista encadenada insertarDespues().
Insertar un nuevo elemento en la cabecera de la Lista:
Paso 1: Crear un Nodo cargando el campo dato con el nuevo elemento. La referencia del nodo
creado se asigna a nuevo (variable local).
Paso 2: Hacer que el campo ps (puntero siguiente) del nuevo nodo apunte a la cabecera de la lista
original.
Paso 3: Hacer que el puntero a la lista apunte al nuevo nodo.
• Recorrido de una lista.
La operación de imprimir los datos de una lista se conoce como recorrido. Se debe comenzar por la
cabecera de la lista y seguir con todos los elementos de la lista, imprimiendo el campo dato de todos
los nodos
public void recorrido(Lista listaDatos){
Nodo p = listaDatos.inicio(); // Devuelve el puntero al primer nodo de la lista
while (p != null){
System.out.print(" Elemento de la lista: " + p.dato);
p = p.ps;}
}
• Ejemplo de Clase Nodo.
public class Nodo {
// variables de instancia
int dato;
Nodo ps;
public Nodo(int elem){
// inicializar las variables de instancia
dato = elem;
ps = null;
}
}
• Ejemplo de Clase Lista
public class Lista {
// variables de instancia
private Nodo list;
public Lista() {
Estructuras de Datos y Programación
Trabajo Práctico N° 2
Pag:2
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 2
Fecha:08/05/2012
list = null;
}
/**
* Agrega un elemento al principio de la lista
*/
public void insertar(int elem) {
Nodo x = new Nodo(elem);
x.ps = list;
list = x;
}
* Quita el elemento que esta en la cabecera de la listas
* devuelve la dirección del nodo
*/
public Nodo quitar() {
Nodo x = list;
list = list.ps;
return x;
}
/**
* Devuelve el puntero al primer nodo de la lista
*/
public Nodo inicio() {
return list;
}
}
Resolver los siguientes problemas de tipo teórico, practico y experimental
1. Responder las siguientes preguntas y dar un ejemplo de cada concepto:
a) ¿Qué es un nodo? b) ¿Qué es un puntero? c) ¿Qué operaciones se pueden realizar con un
puntero? d) ¿Qué es una lista? e) ¿Qué operaciones se pueden realizar con una lista? f) ¿Cómo se
pasa de un nodo a otro? g) Si recorremos una lista, como identificamos al primer nodo y como al
último?
2. Lista Simple Encadenada (LSE) Defina de manera formal e informal el TAD LISTA de elementos
enteros para el siguiente enunciado determinando el método constructor y los métodos que permitan:
a. Ejercicios de Recorrido
 Recorrer la lista ListaNum e imprimir los elementos
 Imprimir la cantidad de elementos, el promedio, la cantidad de pares
 Ingresar un elemento X y buscarlo en la lista. Imprimir el mensaje “El elemento X se encuentra en
la lista”, si se encuentra el elemento, caso contrario imprimir “El elemento X no se encuentra en la
lista”.
b. Ejercicios de Inserción
 Agregar un elemento al principio de la lista
 Agregar un elemento al final de la lista.
 Agregar un elemento en el medio de la lista.
c. Ejercicios de Eliminación
 Eliminar el primer elemento de la lista.
 Eliminar el último elemento de la lista.
 Ingresar un elemento, buscarlo y eliminarlo de la lista
3. Desarrollar la clase aplicación para:
a) Generar ListaAlum: debe permitir ingresar los datos: DNI, nombre del alumno y condición (1:
regular/2: Libre)
y agregar a la lista, hasta que el operador decida no continuar, el nombre de la
lista es ListaAlum.
Estructuras de Datos y Programación
Trabajo Práctico N° 2
Pag:3
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 2
Fecha:08/05/2012
b) Eliminar Alumno: debe permitir ingresar el DNI del alumno y eliminarlo de la lista, hasta que el
operador decida no continuar.
c) Imprimir: mostrar un listado con los elementos de la lista. Debe mostrar el mensaje “Elementos de
la Lista Simple:” y mostrar los elementos de la ListaAlum.
Manejo de Listas Simples Enlazadas
1- Generar Lista de alumnos
2- Eliminar Alumno
3- Imprimir
0- Salir
Ingrese su opción:
Pila
Una pila es una estructura de datos, que consta de una serie de datos, en la cual las inserciones y
eliminaciones se hacen por un extremo, llamado tope de la pila. La estructura pila se conoce también
como estructura LIFO (last-in, first-out), que significa “ultimo elemento introducido, primero sacado”.
Consideraciones generales: Para cualquier ejercicio se debe dejar la Pila en el estado original,
siempre que éste no especifique lo contrario. 4. Defina de manera formal e informal el TAD PILA de elementos enteros para el siguiente
enunciado determinando el método constructor y los métodos que permitan:
a) Agregar un elemento a la Pila (llamarlo insertar ()),
b) Eliminar un elemento de la Pila (llamarlo quitar ()),
c) Indique si la pila esta vacía (llamarlo vacía ()) y
d) Indique si la pila esta llena (llamarlo llena ()).
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos.
5. Desarrollar los métodos que permitan cargar la pila con la expresión: a*b/(a+c) y transformarla a
su equivalente expresión en postfija ab*ac+/.
Una notación postfija coloca el operador a continuación de sus dos operandos. No son necesarios los
paréntesis para cambiar el orden de evaluación.
 Identificar clases, atributos, métodos y objetos para resolver el problema aplicando POO.
 Realizar el diagrama UML e identifique la jerarquía de clases si fuera pertinente.
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos de las clases
utilizadas.
 Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo
(IDE) Netbeans.
6. En una Pila A se guardan los trabajos prácticos de una materia. En cada momento tan sólo se
puede acceder al práctico que está situado en la parte superior del montón. Para cada práctico
se conoce la siguiente información: materia, tema, Nombre del alumno, cantidad de hojas y
estado. El campo estado tiene el valor 0: sin corregir o 1: corregido.
Se pide:
a) Colocar los prácticos corregidos en otra pila C en el mismo orden que fueron evaluados.
b) Mostrar la cantidad de prácticos sin corregir que hay en la pila A en la cual quedaran solo los
prácticos sin corregir.
 Identificar clases, atributos, métodos y objetos para resolver el problema aplicando POO.
 Realizar el diagrama UML e identifique la jerarquía de clases si fuera pertinente.
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos de las clases
utilizadas.
 Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo
(IDE) Netbeans.
Estructuras de Datos y Programación
Trabajo Práctico N° 2
Pag:4
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 2
Fecha:08/05/2012
.
Cola
Una cola es una estructura FIFO (first-in, first-out) también llamada estructura FCFS (first come, first
served). Los elementos de esta estructura se añaden por un extremo llamado final o fin (rear, tail) y
se eliminan por el otro extremo llamado frente o cabeza (front, head).
Consideraciones generales: Para cualquier ejercicio se debe dejar la Cola en el estado original,
siempre que este no especifique lo contrario.
7. Definir de manera formal e informal el TAD COLA de elementos enteros para el siguiente
enunciado determinando el método constructor y los métodos que permitan:
a) Agregar un elemento a la Cola (llamarlo Insertar(n) ),
b) Eliminar un elemento de la Cola (llamarlo Quitar() ),
c) Indique si la cola está vacía (llamarlo Vacía () ) y
d) Indique si la cola está llena (llamarlo Llena()).
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos.
8. Dada una cola de elementos enteros determinar los métodos que permitan:
a) Agregar elementos a la Cola hasta que el operador decida no continuar
b) Imprimir los elementos de la cola.
c) Eliminar elementos de la Cola hasta que el operador decida no continuar.
d) Modificar un elemento de la Cola. Si no existe mostrar un mensaje.
e) Borrar todos los elementos de la Cola.
 Identificar clases, atributos, métodos y objetos para resolver el problema aplicando POO.
 Realizar el diagrama UML e identifique la jerarquía de clases si fuera pertinente.
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos de la clase
COLA.
 Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo
(IDE) Netbeans.
9. Ordenar una cola de números enteros, mediante el método de ordenamiento de base o “radix”.
Este método está basado en los valores reales de los dígitos de acuerdo a la posición que ocupan
los números que son ordenados. Por ejemplo el número 246 en representación decimal se escribe
con un 2 en la posición de las centenas, un 4 en la posición de las decenas y un 6 en la posición
de las unidades. Asuma que se desea ordenar un arreglo que contiene números que tienen el
mismo número de dígitos colocándole 0 en la parte de adelante si es necesario.
El método de ordenamiento funciona de la siguiente manera: para cada digito se realizan las
siguientes acciones, empezando con el digito menos significativo y terminando con el más
significativo. Tome cada número en el orden en el cual aparece en el arreglo y colóquelo en una
de las 10 colas, dependiendo del valor del digito que es procesado. Luego, empezando con la
cola de los números con digito 0 y terminando con la cola de números con digito 9, retorne los
números al arreglo original en el cual fueron colocados en la cola. Al terminar con el digito más
significativo el arreglo esta ordenado. Utilice cola implementada dinámicamente.
Estructuras de Datos y Programación
Trabajo Práctico N° 2
Pag:5
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 2
Fecha:08/05/2012
Ejemplo:
232
537
2
328
291
432
521
95
537
328
291
95
Digito 1:
Cola 0
Cola 1
291
521
Cola 2
232
2
432
Cola 3
Cola 4
Cola 5
95
Cola 6
Cola 7
537
Cola 8
328
Cola 9
291
521
232 2
432
95
Digito 2:
Cola 0
2
Cola 1
Cola 2
521
328
Cola 3
232
432
291
95
537
Cola 4
Cola 5
Cola 6
Cola 7
Cola 8
Cola 9
2
Estructuras de Datos y Programación
521
328 232
432
537
Trabajo Práctico N° 2
Pag:6
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 2
Fecha:08/05/2012
Digito 3:
Cola 0
2
95
Cola 2
232
291
Cola 3
328
Cola 4
432
Cola 5
521
Cola 1
537
Cola 6
Cola 7
Cola 8
Cola 9
2
95
232 291
328
432
521
537
 Identificar clases, atributos, métodos y objetos para resolver el problema aplicando POO.
 Realizar el diagrama UML e identifique la jerarquía de clases si fuera pertinente.
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos de las clases
utilizadas.
 Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo
(IDE) Netbeans.
10. La salida a pista de las avionetas de un aeródromo esta organizada en forma de fila (lineal), Las
avionetas llegan por el extremo derecho (final) y salen por el extremo izquierdo (frente). Un piloto
puede decidir retirarse de la fila por razones técnicas, en ese caso todas las avionetas que la
preceden deben ser retiradas de la fila, retirar el aparato y colocar de nuevo las avionetas
desplazadas en el mismo orden en el que estaban. Se ingresa un carácter que indica una acción
sobre la avioneta y la matricula de la avioneta. La acción puede ser llegada (E) salida(S) y
retirada por desperfecto (R).
 Identificar clases, atributos, métodos y objetos para resolver el problema aplicando POO.
 Realizar el diagrama UML e identifique la jerarquía de clases si fuera pertinente.
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos de las clases
utilizadas.
 Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo
(IDE) Netbeans
11. Dada una lista con los datos de los clientes de una compañía de telefonía celular, los cuales
pueden aparecer repetidos en la lista, si el cliente tiene registrado más de un número telefónico.
Los nodos tiene la siguiente estructura:
NumCli
Estructuras de Datos y Programación
Apellido
NumTel
Trabajo Práctico N° 2
PS
Pag:7
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 2
Fecha:08/05/2012
La compañía para su próximo aniversario desea enviar un regalo a sus clientes, sin repetir regalos
a un mismo cliente. Los regalos se encuentran almacenados en una pila de regalos, donde cada
nodo almacena:
Num_Reg
Descripcion PS
Se desea elaborar un método, que permita generar una estructura con el cliente y su regalo
asignado para proceder a la entrega de los mismos. Si la pila de regalos resulta insuficiente informar
dicha situación con el mensaje “Regalos insuficientes”, caso contrario generar una estructura de
datos con los regalos que sobraron.
Cada nodo de la nueva estructura tiene:
Num_Cli
Num_Reg
PS
 Identificar clases, atributos, métodos y objetos para resolver el problema aplicando POO.
 Realizar el diagrama UML e identifique la jerarquía de clases si fuera pertinente.
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos de las clases
utilizadas.
 Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo
(IDE) Netbeans.
Recursos Bibliográficos
 JOYANES AGUILAR LUIS ZAHONERO MARTINEZ IGNACIO. “Estructuras de Datos en JAVA”. Mc
Graw Hill. 2008.
 JOYANES AGUILAR - ZAHONERO MARTINEZ. Programación en JAVA 2 - Algoritmos, Estructuras de
Datos y Programación orientada a objetos. Mc Graw Hill -2002.
 GOODRICH M.T. – TAMASSIA ROBERTO. Estructuras de datos y algoritmos en Java. 1º Edición
México 2002.Recursos Software
 Entorno de Desarrollo NetBeans versión 7.1
 Java 2EE.
Estructuras de Datos y Programación
Trabajo Práctico N° 2
Pag:8