Ordenamientos-VTJE

Vista previa del material en texto

Centro Universitario de Ciencias
Exactas e Ingenierías
Ingeniería informática
SEMINARIO DE SOLUCIÓN DE PROBLEMAS DE ESTRUCTURAS DE DATOS I
Nombre del Alumno:
Valenciano Tadeo Jeremy Esau
Búsquedas
Ejercicio Ordenamientos
Declaración de la clase Persona
Empezaremos con la declaración de una clase llamada Person esta clase será la
encargada de definir los atributos y métodos con los que contara nuestros objetos,
esta clase contara con los atributos, nombre, apellido materno, apellido paterno,
ocupación y dirección. Estos atributos serán de tipo string y finamente el atributo
edad que será de tipo int.
Por otra parte, los getters se encargaran de obtener y retornar los datos que el
objeto tenga, además contara de otros métodos como lo son imprimir. El método
imprimir se encargara de concatenar todos los atributos del objeto y los retornara.
A cada método setter se le pasara por referencia los valores que el usuario ingrese,
estos se deben mantener de manera constante debido a que no se modificara su
valor a lo largo de la ejecución del método.
Los constructores que contara esta clase será uno parametrizado y uno sin
parámetros.
1
Después encontraremos la respectiva sobrecarga de operadores, estos se
encargarán de modificar el comportamiento de dichos operadores para poder
manipular los objetos de la manera que se desea. Por ejemplo en esta práctica sé
2
solicito ordenar de manera alfabética los objetos de tipo Persona dentro de nuestra
Lista, la comparación de atributos dentro de nuestros objetos con ayuda de la
sobrecarga de operadores va a ser muy útil.
Implementación de la clase Persona
Método CopyAll, Constructor Por referencia y método Imprimir.
El método copyAll recibirá por referencia un objeto de tipo persona y se encargará de
asignar los valores del objeto Persona actual a dicho objeto que recibió por referencia.
Se le asignará cada uno de sus atributos, este método será de ayuda para la
sobrecarga del operador de asignación =.
3
Este método imprimir es el encargado de concatenar y retornar todos los atributos
en un solo string, con ayuda de to_string convertiremos los datos de tipos int a
string para poder concatenarlos de manera adecuada. Al final del método retornará
dicho string para poder imprimirlo.
Setters de la clase Persona.
La clase Persona contará con los métodos setters, estos métodos serán los
encargados de asignar los valores que el usuario ingrese a dicho objeto, estos
deben de ser pasados por referencia y deben ser constantes, debido a que se
mandara el valor directo y este no debe ser modificado a lo largo de la ejecución del
4
método.
Getters de la clase Persona.
Los métodos que incluirá son los getters que se encargaran de retornar los valores
con lo que cuentan cada atributo de la clase. Estos deben de ser del mismo tipo de
dato que los atributos de la clase.
5
Sobrecarga de los operadores en la clase Persona
La sobrecarga de cada uno de los operadores como lo son (==, <,>,<=,>=) nos
ayudaran para determinar el ordenamiento por medio de la concatenación de los
atributos: nombre, apellido materno y apellido paterno. Al final de cada sobrecarga se
retornarán todos los valores en un solo string.
6
Declaración de la Lista.
La lista contará con un tamaño definido por la variable ARRAYSIZE que tendrá un
valor de hasta 100 elementos. Los principales métodos de la lista son el copyAll que se
encargara de recibir una lista por referencia para después copiar cada uno de los
elementos a otra lista.
El método swapData será el encargado de intercambiar dos valores, este método
será de gran utilidad para los ordenamientos.
Contaremos con un Arreglo de objetos de tipo Persona, este arreglo contará con el
atributo último, este es el más importante debido a que sin el sería un simple arreglo.
Métodos de la Lista
Dicha clase también tendrá métodos como:
● Llena
● Vacía
● Insertar
● Eliminar
● obtener primera posición
● obtener última posición
7
● Recuperar
● imprimir
● eliminar lista
Dentro de nuestra clase también contaremos de una sobrecarga de operadores de
asignación, la cual nos ayudara a modificar el comportamiento de nuestros objetos
de tipo lista.
Declaración de métodos de búsqueda y ordenamiento.
● Búsqueda lineal:
La búsqueda lineal o la búsqueda secuencial es un método para encontrar un
valor objetivo dentro de una lista. Esta comprueba secuencialmente cada
elemento de la lista para el valor objetivo hasta que es encontrado o hasta que
todos los elementos hayan sido comparados.
● Búsqueda Binaria:
La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en
una lista ordenada de elementos. Funciona al dividir repetidamente a la mitad la
porción de la lista que podría contener al elemento, hasta reducir las ubicaciones
posibles a solo una.
● Método de la Burbuja:
Funciona revisando cada elemento de la lista que va a ser ordenada con el
siguiente, intercambiándolos de posición si están en el orden equivocado. Es
necesario verificar varias veces toda la lista hasta que no se necesiten más
intercambios, lo cual significa que la lista está ordenada.
● Método de la Burbuja mejorada:
El algoritmo burbuja se puede mejorar si existe un indicador que registre si se
han producido intercambios en la pasada. Si no se han producido cambios, la
lista está ordenada y se terminarán las comparaciones.
● Método Shell:
8
El método de ordenamiento Shell consiste en dividir el arreglo (o la lista de
elementos) en intervalos (o bloques) de varios elementos para organizarlos
después por medio del ordenamiento de inserción directa. El proceso se repite,
pero con intervalos cada vez más pequeños, de tal manera que al final, el
ordenamiento se haga en un intervalo de una sola posición.
● Método Insert Sort:
El algoritmo recibe un arreglo o lista de objetos comparables y retorna el mismo
ordenado, para esto realiza un ciclo comenzando desde la segunda posición y
terminando en N (última posición), entonces toma cada elemento del arreglo[i] y
lo inserta en su lugar correspondiente de la secuencia previamente ordenada
arreglo[1...i-1]. Y de esta manera elemento a elemento vamos ordenando el
arreglo.
● Método Quick sort:
QuickSort es un algoritmo con la filosofía divide y vencerás. Escoge un elemento
como pivote y divide la lista dada alrededor del pivote escogido.
El objetivo de las particiones es, dado un array y un elemento x del array como
pivote, poner x en su posición correcta en el array ordenado y poner todos los
elementos más pequeños (menores que x) antes de x, y poner todos los
elementos mayores (mayores que x) después de x. Todo esto debería hacerse
en tiempo lineal.
9
10
Función main.
Dentro de nuestra función main solo encontraremos la declaración de un objeto de
tipo menú, debido a que toda la implementación del menú se encuentra dentro de
dicho objeto. Con ayuda de un bucle while y la función evaluateMenu evaluaremos
nuestro menú. Esto ayuda a tener más organizado nuestra función main.
Explicación implementación de la clase Menu.
Declaración de variables auxiliares y delegación del constructor.
Declararemos unas variables auxiliares de tipo int,float,String y Persona. Debido a
que estas serán utilizadas al hacer uso de los métodos setters.
Delegaremos las variables cont y j en los constructores para asignarles valores al
momento de crear el objeto menú, Además de pasar por referencia los atributos de
dicha clase.
11
Método capturar Datos
Este método es el encargado de capturar los datos que el usuario ingrese a nuestro
objeto llamado myPerson, con ayuda de las variables previamente declaradas y de
los setters llenaremos los atributos de dicho objeto.
12
Método mostrar datos.
Este método es el encargado de mostrar en una lista los datos de tipo Persona
registrados, con ayuda de un bucle while imprimirá los nombres de cada uno de los
objetos registrados, hasta que la lista este vacia.
Método Ordenar Datos
Este método es el encargado de preguntar al usuario como desea ordenar los datosque se encuentran en la lista, los métodos de ordenamiento que se implementaron
fueron: bubbleSort, betterbubbleSort, Shell, Insert y QuickSort.
Con ayuda de un switch y la variable auxiliar se le preguntará al usuario que método
de ordenamiento desea aplicar a la lista de objetos.
13
Método Editar Persona
Este método imprime los Nombres de las Personas que se encuentran en la lista
con ayuda del método showData, después pregunta al usuario que posición desea
editar.
Con ayuda del método retrieveData implementado en la lista, se recupera la
posición ingresada por el usuario para posteriormente eliminarla de la lista. Se
imprimirá la Información de la Persona con el método toString implementado en la
clase Person.
14
Seleccionar el atributo del Objeto Persona a modificar.
Después de recuperar el elemento de lista, se le preguntará al usuario que atributo
desea modificar con ayuda de un switch. Posteriormente, con ayuda de los setters
se le asignarán a los atributos los valores que el usuario ingreso.
Después de editar los atributos que el usuario selecciono, se añadirá el objeto a la
Lista, en consecuencia la variable ordenado pasara a falso debido a que el estado
de ordenamiento de la lista se desconoce.
15
Método eliminar, mostrar lista y mostrar menú.
Este método será el encargado de eliminar un elemento de nuestra lista, primero
mostrará el nombre de las Personas registradas en nuestra lista con ayuda del
método showData, Posteriormente se le pedirá al usuario que ingrese la posición
del elemento que desea eliminar. Después se hará uso del método delete data
implementado en la lista.
El método ShowList solo es el encargado de imprimir toda la información de la
lista, se hace empleo del método toString pero implementado en la lista para imprimir
la lista.
Finalmente, nuestro método show menú mostrara las opciones de nuestro menú
principal, este capturara un char que será retornado para después utilizarlo en el
método evaluar menu, que será el encargado de definir el curso del programa.
16
17
Método Buscar Dato.
Búsqueda Lineal.
Este método no necesita que los elementos se encuentren previamente
ordenados, se le pedirá al usuario que ingrese el nombre completo de la Persona a
buscar. Se hará uso de una variable auxiliar para hacer uso del método
linearFindData. En caso de que se encuentre alguna coincidencia, se recuperara el
elemento e imprimirá con el método toString del objeto.
Búsqueda Binaria.
Este método primero verificará que los datos se encuentren ordenados
correctamente con la variable de tipo bool llamada ordenado, en caso de que se
encuentren desordenados los datos imprimirá que se deben ordenar primero.
18
En caso contrario se le pedirá al usuario que ingrese el nombre completo de la
Persona a buscar. Se hará uso de una variable auxiliar para hacer uso del método
binaryFindData. En caso de que se encuentre alguna coincidencia, se recuperara el
elemento e imprimirá con el método toString del objeto.
19