Algoritmos M2
Algoritmos M2
Algoritmos M2
Eficiencia y eficacia:
Esta es una estructura lineal restrictiva de tipo LIFO (last in first out), esto indica que el último
elemento que ingresó a la pila debe ser el primero en salir.
Características:
Implementación:
Una estructura de datos de tipo pila puede ser implementada a nivel de software en forma
estática o dinámica. Para una implementación estática, que define un tamaño al momento de
la creación de la estructura, utilizaremos un vector y para una implementación dinámica
utilizaremos una lista enlazada.
Operaciones:
Uno de los casos más usados en informática de una pila es el de querer verificar si una
determinada sentencia o instrucción está equilibrada en cuanto a número de paréntesis,
corchetes o llaves de apertura y cierre. Cuando se escribe código de programación si no existe
equilibrio entre signos de apertura y cierre ni siquiera debería procesarse la sentencia. Para dar
solución a este problema, vamos a utilizar una estructura de pila donde vamos a ir analizando
una sentencia para verificar si es equilibrada o no en símbolos de paréntesis, recorriendo todos
sus caracteres desde el inicio hasta el final. Iremos construyendo nuestra pila apilando un
símbolo cada vez que detectemos un símbolo de apertura y desapilando de ella cuando
detectemos un símbolo de cierre. También utilizaremos la clase Stack provista por Java y
confeccionaremos el método verificarParentesis (string cadena) que nos retornará un boolean,
indicando si dada una cadena, esta está equilibrada y correcta en paréntesis o no. Para hacerlo,
usaremos tres métodos propios de la clase pila:
El método verificarParentesis (string cadena) crea una pila vacía y recorre la cadena enviada
como parámetro. Además, ante un paréntesis de apertura lo apila. Por otra parte, ante un
paréntesis de cierre, si la pila tiene elementos, desapila uno de ellos y, si la pila está vacía, apila
el paréntesis de cierre y corta la ejecución del programa.
Características:
Solución problemas:
Clases:
Una lista lineal simplemente enlazada es una estructura de datos dinámica compuesta por
nodos enlazados linealmente, es decir, cada nodo contiene datos y una referencia al siguiente
elemento de la lista. Podemos explicar una lista como un conjunto de elementos que se
enlazan uno con otro, donde ese enlace se denomina referencia. Cuando la lista se crea, estará
vacía y no contendrá ningún elemento, con lo cual la lista tendrá una referencia a un valor nulo
(null). Cuando se agrega un nodo a la lista (A), se crea el nodo con el valor determinado y se
modifican sus referencias. Cuando se agrega un nuevo nodo a la lista (B), se crea el nodo con el
valor determinado y se modifican sus referencias. Si la inserción se hace como primer
elemento de la lista, la referencia al elemento siguiente de B será A.
Podemos definir a las listas enlazadas simples como las que contienen una única referencia a
un elemento “siguiente”, es decir que cada nodo de la lista tendrá sus datos y una sola
referencia o puntero. Uno de los problemas que posee esta estructura es que no es factible
acceder a un elemento anterior. Una lista doblemente enlazada es una muy buena opción para
dar solución al problema planteado. En ella cada nodo, además del valor, consta de dos
referencias o punteros: uno al nodo siguiente y otro al nodo anterior. Además, por otra parte,
se mantienen siempre un puntero al primer elemento de la lista y otro al final, de forma de
poder recorrerla en ambos sentidos. Para resolver este problema empleando listas doblemente
enlazadas, utilizaremos las siguientes clases:
Nodo
Lista: clase que define la estructura de lista compuesta por nodos doblemente
enlazados.
Analizando el método agregarAlFinal (char valor), Si la lista está vacía, se agrega dicho
elemento y se actualizan las referencias de inicio y fin de la lista, pero, en caso contrario, el
nuevo elemento debe insertarse al final de la lista, lo que se hace con tres instrucciones
directas:
Se puede definir a los árboles binarios de dos maneras. Por un lado, se puede decir que son
árboles en los que sus nodos tienen hasta dos hijos o se puede conceptualizar a un árbol
binario como un conjunto finito, fijo o variable de nodos, donde el nodo raíz consta de dos sub-
árboles binarios. Según la definición recursiva de árboles, podemos definir un árbol binario
como un conjunto de nodos y ramas, en el que existe un nodo raíz y dos sub-árboles binarios
conectados a la raíz.
Existe un tipo de árbol binario particular, llamado árbol binario de búsqueda, que se caracteriza
por presentar una raíz que posee un valor mayor que el de su hijo izquierdo y menor o igual
que el de su hijo derecho. Esto nos permite afirmar que cualquier nodo del árbol ubicado del
lado izquierdo de este será menor que la raíz y, de la misma manera, cualquier nodo del árbol
ubicado del lado derecho de éste será mayor o igual. Si se tiene un árbol con estas
características, localizar un valor será una tarea mucho más sencilla, en comparación con otras
estructuras. En general, las operaciones que se pueden necesitar en un árbol de búsqueda
binaria son:
Buscar un elemento.
Agregar un nuevo elemento.
Eliminar un elemento.
Recorrer el árbol.
Código:
El método agregarValor (Integer valor) hace la comparación con el valor del nodo (inicialmente
con la raíz): si es menor y el subárbol izquierdo posee valores, se llama nuevamente al método,
pero en el subárbol izquierdo. En el caso de que el valor pasado como parámetro sea mayor al
del nodo, se procede de la misma forma, pero con el subárbol derecho. Luego se definen tres
métodos de impresión por pantalla de valores, que se encargan de recorrer el árbol en
profundidad de tres formas diferentes: