Autor Oscar Rosas

Arboles II: El Ataque de los BST

Oscar Rosas Deja un comentario

Nota: Esta lección se lee mejor con palomitas a la mano y el código completo de BTS

*Dale click a las palomitas para ir al Código*palomitas

…Bienvenidos a a segunda parte de Árboles, es de lo más útil que nos encontraremos pero ¿Qué demonios son?

«BTS: Binary Search Tree, osea que es un árbol binario de búsqueda (ósea que esta ordenado)…Si, eso es todo, así de simple un árbol binario ordenado.Punto»

bst-2

Ejemplo de BTS

Digo que un árbol esta «ordenado» cuando tengo un nodo (lo llamamos nodoRaiz) tal que para cualquier nodo que elija se tienen que cumplirse que:

  1. El hijo izquierdo de nodoRaiz (si es que hay) debe ser menor
  2. El hijo derecho de nodoRaiz (si es que hay) debe de ser mayor.

Esta regla se debe de cumplir para TODOS los nodos del árbol.

Para verificarlo basta con que miremos de izquierda a derecha el árbol y veamos is los elementos van de menor a mayor:

bts

BTS

¿Y que vamos a buscar?

De igual manera que con los arboles normales ls BTS guardan su información en nodos, pero más bien la forma de encontrarlos va a ser por comparación, sea de números, ID o por orden alfabético o un método se te ocurra.

Operaciones

Veamos las operaciones que podemos hacer con un BST:

Búsqueda

busqueda

Ejemplo de Búsqueda

Se usa principalmente para dos operaciones derivadas:

  • Una función que se llama Existe que busca si existe un elemento.
  • Una función que se llama ObtenerElemento que regresa un objeto cuyo identificador sea igual al que pedimos.
  • Una función que se llama EliminarElemento que ..bueno, elimina un elemento (que primero hay que encontrar)

Algoritmo

  1. ¿Es el nodo donde estas ahora el que buscas?, si es así regresa el valor, sino:
  2. ¿Es menor? Ve a la rama izquierda
  3. ¿Es mayor? Ve a la rama derecha
  4. ¿Es una hoja? …No existe

Insertar Elemento

Aquí lo primero es preguntarnos si nuestro árbol va a permitir elementos duplicados, sino también (recomendable) hay que tener eso en cuenta.

Recuerda, siempre se inserta en las hojas.

insertar.gif

Insertar

Algoritmo

  1. Si esta vacío va a la raíz
  2. Si donde estamos es igual al elemento a añadir hay que ver que onda con los duplicados
  3. Si es menor que el elemento actual recursivamente inserta en la rama derecha
  4. Si es mayor que el elemento actual recursivamente inserta en la rama izquierda
  5. Si llegamos a una hoja, le haremos un hijo y pondremos el dato ahí

 

 

Eliminar Elementos

Ok, ok, no te alarmes, pero esta puede que sea la operación más difícil de todas (pero ni tanto) 

Pero es que hay varias «formas»de hacerlo dependiendo del número de hijos que tengas, así que vamos con el algoritmo:

Algoritmo:

Como podemos dividir esto en 3 casos, hoy a explicarlo como 3 casos diferentes pero recuerda que todos están unidos:

Caso 1: Si eres un nodo hoja has que tu padre apunte a NULL y borralo, tan simple.

Caso 2: Si tienes un hijo entonces has que tu padre apunte a tu hijo y borralo, tan simple.

Caso 3: Si tienes 2 hijos (aquí esta lo feo) … Así que habrá que hacer dos caminos 3A y 3B desde aquí, pero antes explicaré que vamos a hacer:

..Espera, creo que me he perdido en esa última parte ¿Como que 3A y 3B?

Lo que pasa es que no hay «una forma correcta» de eliminar un nodo con dos hijos ya que a fuerzas hay que cambiar la estructura del árbol para que no perdamos información.

Así que ahora hay que pensar: ¿Qué vamos a poner en donde esta el nodo que vamos a eliminar? ¡Pues muy fácil!, mira este árbol binario, quizá con dibujos sea más fácil:

bst

Aquí un BTS con sus elementos ordenados

Ahora, ¿recuerdas que podemos hacer barras verticales de manera que solo toquen a un nodo?..y eso hace que sea más obvio que esta ordenado:

bts

Perdonen calidad de GIF

Bueno digamos que quiero eliminar el 23, ¿Qué hago?

Pues nuestro objetivo es eliminarlo pero haciendo cuanto menos desastre mejor, así que habrá que elegir en un valor que este muy próximo a 23, mira, aquí esta una lista de cuanto vale cada nodo de forma ordenada:

05,12,21,23,26,53…

Bueno, en realidad solo nos importan los valores próximos a 23:

05,12,21,23,26,53…

Bueno tenemos dos candidatos: O el 21 o el 26, ahora bien: ¿Cuál?

La respuesta es que no tengo ni idea, quizá dependiendo de como este tu árbol te convenga más usar uno u el otro, quizá te de lo mismo, quizá uno sea la raíz de un árbol enorme que no te conviene reajustar, la verdad es que depende, así que te dejo a que tu eligas como quieras (con una función tuya o al azar o siempre poniendo siempre el mismo-el de la derecha o el de la izquierda- o lo que tu quieras) .

…Pongamos otro ejemplo, ahora con la raíz, el 53, si quisiéramos eliminarlo tenemos dos opciones.

BSTs.png

¡Es por eso que esto es tan difícil, porque no hay un camino «correcto» pero bueno, explicado este texto enorme continuamos…Ya elegimos uno pero ¿Ahora qué?

Camino 3A(Queremos que en donde estaba nuestro nodo este algo más grande):

  1. Si quieres eso tendremos que buscar del nodo en el que estamos, de su subarbol derecho el que tenga el valor mínimo (o dicho de otra forma el que este más a la izquierda)
  2. Una vez que lo encuentres lo colocas donde estaba el nodo que querías eliminar y ahora eliminas recursivamente el nodo que acabas de encontrar

Camino 3B(Queremos que en donde estaba nuestro nodo este algo más pequeño):

  1. Si quieres eso tendremos que buscar del nodo en el que estamos, de su subarbol izquierdo  el que tenga el valor máximo (o dicho de otra forma el que este más a la derecha)
  2. Una vez que lo encuentres lo colocas donde estaba el nodo que querías eliminar y ahora eliminas recursivamente el nodo que acabas de encontrar

 

 

 

 

 

AVL: La versión Pro

Un Árbol AVL es un BTS muy especial, en el que además que todas las cosas que ya conocemos le agregamos algo mas… Es que se auto balancea.

Decimos que un BTS es un AVL si que la diferencia entre la profundidad de dos nodos cuales quiera no puede ser mas de uno.

AVL

 

 

Rotaciones

 

Hay muchas versiones de las rotaciones, muchos nombre, así que haré mi mejor esfuerzo para mostrarles todas las versiones que hay de las mismas:

La Super Pro

Con estas rotaciones podemos sacar todas las que necesitamos:

SuperRotaciones.png

Las Rotaciones Pro

 

Ahora veamos las Comunes y como las podemos representar usando las que creamos arriba:

Right-Right Rotation (Rotación Derecha)

También la llaman simplemente Right Rotation y es literalmente igual a la que tenemos allá arriba, ¿Puedes verlo? (X y sus hijos son T1 arriba)

 

RightRotation.png

La Clásica Rotación Derecha

Left-Left Rotation (Rotación Izquierda)

También la llaman simplemente Left Rotation y es literalmente igual a la que tenemos allá arriba, ¿Puedes verlo? (Z y sus hijos son T3 arriba)

 

LeftRotation.png

La Clásica Rotación Izquierda

 

 

Right-Left Rotation (Rotación Derecha-Izquierda)

Logramos esto de manera completa así:

RightLeftRotation.png

La Compleja Derecha Izquierda

 

Pero también  lo podemos expresar como:

  1. Primero has una rotación a la Derecha en Hijo derecho de la Raíz
  2. Después has una rotación a la Izquierda en la Raíz

Veámoslo en acción:

 

RightLeftRotationPart1.png

Paso 1: Rotación Derecha en Z

RightLeftRotationPart2.png

Paso 2: Rotación Izquierda en X

Left-Right Rotation (Rotación Izquierda-Derecha)

Logramos esto de manera completa así:

LeftRightRotation.png

La Compleja Izquierda-Derecha

 

Pero también  lo podemos expresar como:

  1. Primero has una rotación a la Izquierda en Hijo Izquierdo de la mañana
  2. Después has una rotación a la Derecha en la Raíz

Veámoslo en acción:

LeftRightRotationPart1.png

Paso 1: Rotación Izquierda en X

LeftRightRotationPart2.png

Paso 2: Rotación Derecha en Z

 

 

 

 

btn1 btn
btn

Árboles I: La Amenaza Fantasma

Oscar Rosas Deja un comentario

…Sabia que algún dia iba a ocupar los grafos. ¡Lo sabía!

g53Los arboles son casi casi crear un grafo en una computadora, así que antes que nada tengo algo que decirte:

Esta lección no la empezaré desde cero, pues voy a suponer que ya sabes que son los grafos, al menos lo básico, así que ve y revisa esta lección primero:

MD: ¿Qué son los Grafos?

Ok, con esto fuera del camino es hora de que empecemos:

Árboles

 

arbolEstas son esencialmente diferentes a las listas y todas sus parientes. Esta estructura no es lineal (Osea que puede haber nodos que apunten a más de un elemento).

Estos son básicamente estructuras para guardar información en una jerarquía, son utilizadas en las bases de datos o para hacer un árbol de carpetas dentro de una computadora.

Al principio se parecen, volveremos a crear un nodo como antes:

Nodos

Vamos a meter cada información que queramos guardar en la pila en un nodo, esto es un nodo:

El nodo tiene dos partes:

  1. Dato: Representa el dato a almacenar. Puede ser de cualquier tipo.
  2. Enlaces:Los arboles son como listas, pero tienen nodos, con s, son varios.

arbol

¿Qué es un árbol?

Así una árbol no es más que esto, un montón de nodos unidos. (Hasta se ve sencillo si lo ves así). En Matemáticas Un árbol es un grafo que:

  • Es dirigido (Osea en enlace en el nodo tiene un «origen y una dirección»).
  • Es conexo (Eso quiere decir que no existen nodos «perdidos» o inaccesibles desde la raíz, es decir que en un árbol puedo llegar  a cualquier nodo desde la raíz).
  • Todos los vértices tienen grado de entrada 1 excepto  un vértice (Eso quiere decir que en «español» que cualquier nodo tiene un solo padre, y que solo es posible llegar a ese nodo a través de ese padre; PD: Ese que no tiene grado de entrada se llama raíz).
  • No puedes tener ciclos: Ósea regresar a un nodo si ya habías pasado por ahí

Así que veámoslo gráficamente:

  • Raíz: Es el nodo al que no es apuntado por nada, es el origen del árbol…digo, por algo se llama raíz.
  • Hoja: Es la punta del árbol, no apuntan a nada, no tienen hijos.
raiz-hoja

Raiz- Hoja

padreshijos

Padres e Hijos

Nivel: Es el numero de «saltos» que tengo que hacer para llegar a el nodo indicado.

nivel-arbol

Nivel de un árbol

Podemos finalmente hablar de un último concepto:

Orden: Orden es el número MAXIMO de hijos que puede tener un nodo.

Árboles Binarios

g53.pngLos árboles binarios son mis favoritos, son muy my poderosos, pero ¿Porque me deberían de interesar?

El tema de localizar elemento es muy interesante porque son lo que se utiliza en cosas como las bases de datos, pues con su estructura son capaces de encontrar lo que nosotros le pidamos demasiado rápido.

¿No me crees?

Imagínate un montón de nombres, por ejemplo en una guía telefónica o una base de datos, si fuera un árbol binario (BTS) por ejemplo podría encontrar cualquier elemento de una base tan grande como una de 32,000 nombres en menos de 15 comparaciones. Si, 15 pasos y puedo encontrar a más de 32,000 personas, con 30 comparaciones puedo encontrar hasta 1,073,741,824 nombres. ¡Asombroso! …Pero ¿Cómo lo hacen?

¡Ya lo veremos!

Pero bueno, sigamos, sus características son sencillas:

  • Tienes Orden 2 ó máximo 2 hijos, como ustedes quieran verlo.
  • Se distingue entre hijo derecho o izquierdo

 

 

Tipos de Árboles

 

Full Binary Tree

Todos los nodos o son hojas o tienen 2 hijos. Esa es la única condición.
output_Y95Fjl

Complete Binary Tree

Si ignoras el último nivel es un Perfect Tree. Si hay UN solo hijo en el ultimo nivel tiene que irse llenando de IZQUIERDA A DERECHA
Complete

Perfect Tree

Es un árbol en el que todos sus nodos o tienen dos hijos o sin hojas y que esta completo INCLUYENDO el último nivel, son preciosos.
perfect

Conceptos:

  • Un Árbol es degenerado si solo tiene un hijo.

Así que bueno, con esto terminamos por hoy, si, se que es mucho, imagínate a mi inocente cuando pensé que podía meter todo lo de Árboles en una lección. Inocente yo.

btn1 btn
btn

Listas Enlazadas

Oscar Rosas Deja un comentario

 

Lista Enlazadas Simples

Ok, empecemos por esta que es la más sencilla, aquí la definición: «Es un grupo de elementos en forma de secuencia»

Y antes de que me lo digas, si se que parece que estoy diciendo array de manera fancy y si, son casi iguales.

La lista enlazada nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber «a priori» los elementos que puede contener.

¿Cómo creamos una lista como concepto?

Antes que programar ni nada así, vamos a hablar de ideas, imagina que tienes una información que quieres guardar:

Como por ejemplo un número o una letra:

 

Ahora vamos por la clave, los nodos.

Nodos

Vamos a meter cada información que queramos guardar en la lista en un nodo, esto es un nodo:

listas-4

Partes de un Nodo

El nodo tiene dos partes:

  1. Dato: Representa el dato a almacenar.Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.
  2. Enlace: Es un puntero al siguiente elemento de la lista; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.

Lista

Ahora podemos dar hasta una mejor definición de lista: Un montón de nodos.

 

Diagrama

Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un indice sino mediante un puntero. La asignación de memoria es hecha durante la ejecución.

En una lista los elementos son contiguos en lo que concierne al enlazado. En cambio, mientras que en un array los elementos están contiguos en la memoria, en una lista los elementos están dispersos. El enlace entre los elementos se hace mediante un puntero. En realidad, en la memoria la representación es aleatoria en función del espacio asignado.

El puntero siguiente del último elemento tiene que apuntar hacia NULL (el fin de la lista). 

Partes de la Lista

Claro que no pudieron parar ahí así que les pusieron nombres raros a sus partes:

Cabeza

Es el nodo principal y es el único que necesitamos para acceder a la lista y empezar a trabajar, pues simplemente vamos accediendo de enlace a enlace hasta llegar a donde queramos.

listas-7.png

Y a todo lo que no es cabeza le llamamos cola:

listas-8.png

Y así podemos irnos al infinito porque las colas son listas, que tienen una cabeza y así:

listas-9.png

Ventajas

Una vez que ya aprendimos que son las listas, nos preguntamos ¿porque usarlas?

  • Los nodos no tienen porque estar contiguos en memoria, gracias a esto evitar problemas al trabajar con gran cantidad de datos.
  • Pueden tener longitud variable
  • Podemos agregar o quitar elementos en tiempo de ejecucción.

Pero como en la vida también tienen cosas negativas:

  • No tienen un indice, por lo que no podemos entrar a cualquier nodo así como así
  • Necesitan más espacio en memoria, pues guardo el dato y el enlace.

 

 

Zona Dos: Código Real

Ok, ok, todo muy bonito hasta aquí, pero ahora es hora de ponernos a trabajar.

codigo

 

 

 

 

btn1 btn
btn

Colas

Oscar Rosas Deja un comentario
peach

Tenia que ponerlo

Ok, antes de que hagan un chiste lo haré yo, una cola es el nombre más ridículo, perfecto y divertido para una estructura de datos.

Pero bueno, vamos a ponernos serios, las colas son estructuras de datos que almacenan datos de un mismo tipo, pero lo hacen de una manera muy especial.

Tienen un nombre que muchas veces ocupan en los libros de computación, las llaman estructuras FIFO (First In First Out) o en español: «Lo primero que entra es la primero que sale».

Una cola es de verdad un buen nombre porque la estructura funciona igual que en la vida real, pues siguen sus dos principios básicos:

  • Al llegar a una cola tu siempre vas al final
  • Siempre se atiende al primero y así sucesivamente

Así que para hacer nuestra cola, haremos algo parecido a una lista, es más, haremos algo muy parecido y más simple.

(Si no sabes que es una lista no te preocupes, no es necesario, pero te puedo adelantar que son como colas con esteroides, capaces de hacer lo mismo que te enseñare ahora y más, así que quizá te guste echarles un vistazo después, solo digo: Lección de Listas Enlazadas).

Colas.png

¿Cómo creamos una Cola como concepto?

Antes que programar ni nada así, vamos a hablar de ideas, imagina que tienes una información que quieres guardar:

Como por ejemplo un número o una letra:

Ahora vamos por la clave, los nodos.

Nodos

Vamos a meter cada información que queramos guardar en la cola en un nodo, esto es un nodo:

El nodo tiene dos partes:

listas-4

Partes del Nodo

  1. Dato: Representa el dato a almacenar.Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.
  2. Enlace: Es un puntero al siguiente elemento de la cola; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.

Así una cola no es más que esto, un montón de nodos unidos.

pilas-dibujos

Diagrama de una Cola

Y si, no son mas que una versión «de prueba» de una lista enlazada, estas estructuras las puedes revisar aquí.

 

Funciones Básicas de una Cola

ENQUEUE: Encolar

Es básicamente introducir algo en la cola, ósea añadir un elemento al final de la estructura

colas

 

UNQUEUE: Procesar una Cola

Esta operación se puede dividir en dos operaciones independientes:

procesarcola

Zona Dos: Código Real

Ok, ok, todo muy bonito hasta aquí, pero ahora es hora de ponernos a trabajar.

Esta parte sera algo, algo MUY largo, así que te recomiendo que veas el código completo y original que tengo en Github. Da click en el botón:

Codigo.png

 

 

https://gist.github.com/SoyOscarRH/4cf3cc3da54c675b188e7474833f14b5

Y ya esta, como te das cuenta estas estructuras sirven un propósito muy específico, así que espero que ya haya gustado esta lección.

Ahora si, estas listo para ver las listas enlazadas, esto se va a poner bueno.

 

 

btn1 btn
btn

Pilas

Oscar Rosas Deja un comentario

pilasLas pilas, son todo un clásico porque no son la forma mas tradicional de agrupar datos, pero una vez que las comprendes veras que son muy muy útiles.

Tienen un nombre que muchas veces ocupan en los libros de computación, las llaman estructuras LIFO (Last In First Out) o en español: «Lo último que entra es la primero que sale».

Una pila es de verdad un buen nombre porque la estructura funciona igual que en la vida real, pues siguen sus dos principios básicos:

  • Al llegar a una pila tu siempre vas al final
  • Siempre se atiende al último y así sucesivamente

Así que para hacer nuestra pila, haremos algo parecido a una lista, es más, haremos algo muy parecido y más simple.

(Si no sabes que es una lista no te preocupes, no es necesario, pero te puedo adelantar que son como pilas con esteroides, capaces de hacer lo mismo que te enseñare ahora y más, así que quizá te guste echarles un vistazo después, solo digo: Lección de Listas Enlazadas).

¿Cómo que se procesa el último?

– Si, se que parece algo muy estúpido, ¿para que haría eso?

– Pues no te preocupes, te explicaré con varios ejemplos donde son útiles las pilas:

Ejemplo #1: Bolsas de Dinero

Imagínate que eres rico trabajando de programador (que divertido ¿verdad?), entonces tienes un montón de dinero que tienes que guardar, así que lo ordenas en un pila.

Entonces como los ordenaste en una pila cuando te llega tu nuevo pago del mes lo metes en la pila. Y luego cuando quieres sacar algo de tus pequeños ahorros para comprarte a última Mac, entonces sacas LA ÚLTIMA BOLSA.

pila.gif

Una pila…y mucho dinero

Ejemplo #2: Simplificar una expresión

expresion

Como puedes ver hay muchas situaciones donde una pila puede ser una herramienta muy útil para organizar información, pero bueno, es hora de ponernos a trabajar ¿Cómo las creamos?

¿Cómo creamos una Pila como concepto?

 

Antes que programar ni nada así, vamos a hablar de ideas, imagina que tienes una información que quieres guardar:

Como por ejemplo un número o una letra:

Ahora vamos por la clave, los nodos.

Nodos

Vamos a meter cada información que queramos guardar en la pila en un nodo, esto es un nodo:

El nodo tiene dos partes:

  1. Dato: Representa el dato a almacenar. Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.
  2. Enlace: Es un puntero al siguiente elemento de la pila; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.
listas-4

Partes de un Nodo

Así una pila no es más que esto, un montón de nodos unidos.

pila

Y si, no son mas que una versión «de prueba» de una lista enlazada, estas estructuras las puedes revisar aquí.

 

Funciones Básicas de una Pila

Bueno, listo estas funciones podemos ahora si ver las dos que controlan una lista:

PUSH: Apilar en la Pila

Es básicamente introducir algo en la pila, ósea podemos verlo como añadir algo al principio de la lista:

apilar

POP: Procesar una Pila

Vamos a trabajar con un elemento, procesarlo y eliminarlo, y lo vamos a hacer en el mismo sentido que en el que apilamos (en listas esto sería equivalente a eliminar el primer elemento). Esta operación se puede dividir en dos operaciones independientes:

desapilar

PEEK: Consulta la Cabeza

Nos regresa, sin eliminar nada la cabeza de nuestra pila, esto s puede lograr usando un POP, y después un PUSH .

Implementación con Array

Hay otra manera, si entendiste la de arriba, esta es mucho más sencilla, vamos a usar arrays y punteros, verás que cool es:

Y es que las pilas en inglés se llaman Stack, así que vamos a usar un «Stack pointer» para convertir nuestro array en una pila:

Aquí esta la primera función:

stack

Como ven nuestro puntero va posicionándose en un lugar libre y lo va llenando..cuando el puntero apunta fuera de nuestro «stack» decimos que paso un «stack overflow».

stack

La segunda operación es también muy fácil de visualizar, mira:

array

 

 

 

Zona Dos: Código Real

Ok, ok, todo muy bonito hasta aquí, pero ahora es hora de ponernos a trabajar.

Esta parte sera algo, algo MUY largo, así que te recomiendo que veas el código completo y original que tengo en Github. Da click en el botón:

Codigo.png

 

 

 

 

https://gist.github.com/SoyOscarRH/974196a8ca920f1d3ffd362f1f12f529

 

 

btn1 btn
btn

Introducción a Estructuras de Datos

Oscar Rosas Deja un comentario

¿Qué demonios son?

Podemos entenderlas como «la forma en la que tenemos de representar la información dentro de una computadora».

o para mí:

«La forma en la que organizamos la información (int, chats, floats , etc..) en un programa»

Recuerda, la computadora solo reconoce entre 1 y 0, así que es nuestro trabajo darle un significado a esos montones de unos y ceros.binario.png

… Pero para que te quede más claro, te daré una pista:

¡Ya los conoces!

Los Arrays son un tipo de Estructura, son una muy estúpida ahora que lo piensas, son un montón de tipos de datos iguales todos juntos, como un montón de personas en una fila o como un montón de enteros o un montón de caracteres.

fila

¿Porqué los necesito?

Ok, ok, pero si yo estoy muy a gusto con mis arrays ¿para que quiero aprender esto?

Muy fácil:

– ¿Cómo harías para guardar de forma eficiente la información de 100,000,000 clientes (edad, no. de cuenta, nombre)?

– Pues uso un array de 100,000,000 elementos

–¿Y cómo le vas a hacer para guardar a siguiente cliente?¿De verdad crees que vas a encontrar memoria para guardar eso? ¿Amas es lag? ¡Verdad!

La respuesta es sencilla: Usa estructuras, no reinventes la rueda, tu problema ya fue solucionado hace muchísimos años, pero no hay UNA solución, porque veras, hay muchas muchas estructuras posibles, así que vamos a aprenderlas.

btn1 btn
btn

Interfaces

Oscar Rosas Deja un comentario

Recordemos para que servían añadir «abstract»:

«Para evitar que se puedan generar objetos de la clase padre si es que no se quiere se tiene que añadir  Abstract de esta manera lo que se hará es que para esta clase será imposible instanciar objetos».

En Java, una clase sólo tiene una superclase. No existe la herencia múltiple. Para solucionar las situaciones en las que es necesario definir una clase con características definidas en  más de una clase, se emplean interfaces.

Una interfaz es una colección de constantes y métodos abstractos.

No es una clase, sirven como guía, pero tienen varias limitantes:

  • No pueden contener atributos ni constructores y solo se pueden hacer métodos abstractos, que no se inicializan, es más ni siquiera se tiene que poner esa palabra.
  • Es imposible poder crear un objeto de esa clase.

Sintaxis:

public interface NombreDeInterfaz{
    public Constantes;
public MetodoAbstracto(…);
}

Para implementar una interfaz se usa la siguiente sintaxis:

public class ClaseHija implements NombreDeInterfaz{
   //Contenido de Clase
}
public class ClaseHija extends ClasePadre implements Interfaz1, Interfaz{
   //Contenido de Clase
}

¿Para que sirven?

Espera, espera, espera ¿Para que demonios quiero una interfaz?, digo, si no puedo crear objeto de ella ni atributos, ni anda así ¿para que la necesito?  ¿Porque no se llama interfaz, porque no clase basura o clase inútil?

Pues lo primero de todo es que clase inútil no suena nada mal. Me gusta.

Pero ya enserio, sirven a un solo propósito: Y es que cuando tu «extiendes» o «implementas» de una interfaz hay que redefinir todos los métodos incluidos en la interfaz.TODOS.

Por defecto, todas las interfaces son abstractas y todos los métodos de una interfaz abstractos y públicos, por eso no se especifica explícitamente

Las interfaces pueden formar jerarquías heredando de una interfaz determinada (cláusula extends).

Oye..antes de que te vayas, te daré un secreto…No se pueden instanciar Objetos, sin embargo si es posible hacer:

NombreDeInterfaz Instancia = new NombreDeClaseHija();

Este nuevo objeto, es capaz funciona como una instancia de NombreDeClaseHija siempre que esas referencias estén también en la Interfaz, es decir, si hay un método propio de la clase o un atributo, el programa crashea, pero si solo haces referencia a los métodos que existen en la interfaz, todo esta bien.

Así que en resumen podemos darle estos usos a las interfaces:

  • Como un contrato de Software, que te obliga a implementar unos métodos específicos  con un nombre, tipos de datos de entrada y salida ya definidos, así todo el proyecto queda mas consistente.
  • Permite emular una jerarquia múltiple.
  • Permite el Poliformismo como allá arriba.

Diferencias entre Interface y Clase abstracta

interfaces

Interfaz vs Clase Abstracta… Fight!

La principal diferencia entre interface y una clase abstracta abstract es que un interfaz proporciona un mecanismo de encapsulación de los prototipos de  los métodos evitando al desarrollador forzar  una relación de herencia.

La ventaja principal del uso de interfaces es que una clase interface puede ser implementada por cualquier número de clases, permitiendo a cada clase compartir el interfaz de programación sin tener que ser consciente de la implementación que hagan las otras clases que implementen el interface.

Una clase abstracta puede incluir métodos implementados y no implementados o abstractos, constantes y otros atributos.

Una clase solamente puede derivar (extends) de una clase base, pero puede implementar varios interfaces. Los nombres de los interfaces se colocan separados por una coma después de la palabra reservada implements.

El lenguaje Java no fuerza por tanto, una relación jerárquica, simplemente permite que clases no relacionadas puedan tener algunas características de su comportamiento similares.

…

Y ya, lo has logrado

¿No fue divertido?

lisa.jpg

 

 

btn1 btn
btn

Herencia

Oscar Rosas Deja un comentario

Relaciones entre Clases

Antes de entrar de lleno a herencia, vamos a ver las relaciones entre las clases, pues resulta ser que aunque la herencia es la más útil, la más famosa y la que mas te va a importar no es la única.

Esta jerarquía de clasificación es  subjetiva, dependiendo de las intenciones con las que se pretenda trabajar. Es muy difícil establecer una relación perfecta y surgen elementos que no se acomodan en ninguna categoría.

Agregación / Composición

«todo – parte / tiene-un / parte-de»

Esta relación se presenta entre una clase TODO y una clase PARTE que es componente de TODO. La implementación de este tipo de relación se consigue definiendo como atributo un objeto de la otra clase que es parte-de.

Los objetos de la clase TODO son objetos contenedores. Un objeto contenedor es aquel que contiene otros objetos.

Tipos

  • Contenido Físico- Valor

El contenedor contiene el objeto en sí. Cuando creamos un objeto contenedor, se crean también automáticamente los contenidos.

  • Conceptual – Referencia

Se tienen punteros a objetos. No hay un acoplamiento fuerte. Los objetos se crean y se destruyen dinámicamente. La relación de agregación/composición establece jerarquías de clases por grado de composición.

El ejemplo más clásico de esto es el del motor y un auto:

tesla
motor

Asociación

Es una relación entre clases. Implica una dependencia semántica. Son relaciones del tipo “pertenece a” o “está asociado con”. Se da cuando una clase usa a otra clase para realizar algo.

Herencia

viejo

¡Respeta a la Clase Padre!

La herencia es un mecanismo fundamental en la construcción de clases, necesario para reutilizar código. Mediante la herencia podemos crear clases nuevas a partir de otras que ya existen, sin necesidad de reescribir todo el código: mecanismo de reutilización de código.

Mediante la herencia podemos organizar las distintas clases en estructuras jerárquicas.

Algo especializado va a heredar de algo general, como un coche de un vehículo, o un loro de un ave. Esto se hace en programación porque se suelen tener muchas cosas en común pero no todas. 

Entonces lo que se hace es poner todas las características en común de los objetos en una clase “Padre” de la que todos va a heredar.

herencia1

Entonces al decirte a Java que es una clase hija, esta nueva clase ahora es capaz de acceder a todos los atributos, interfaces implementadas y todos los métodos que tiene su padre, siempre que sean públicos o protegidos.

Sintaxis

Para que Java sepa que una clase es hija se declara la clase de la siguiente manera:

public class ClaseHija extends ClasePadre{
   //Contenido de Clase
   ...
}

De este modo ahora ahora la clase hija se refería bajo esta nomblecaruta:

  • Super: Clase Padre
  • This: Clase Propia

Constructor de una Clase Hija

public class ClaseHija extends ClasePadre{                //Constructor
   public NombreClase(Tipo Algo1,Tipo Algo2,Tipo Algo3){
       Super(Algo1, Algo2)                                //Atributos Extendidos
       this.Algo3 = Algo3;                                //Atributos Unicos
   }
}

Recuerda que Super simpre tiene que ir al principio del Constructor.

Clases Abstractas

«¡Timmy! ¿Qué demonios es un objeto Vehículo marino? ¡Eso no existe! ¿Quién permitió que esto fuera posible de hacerse»

Para evitar que se puedan generar objetos de la clase padre si es que no se quiere, se tiene que añadir Abstract de esta manera lo que se hará es que para esta clase será imposible instanciar objetos.

public abstract class NombreDeClase{
   ...
}

Métodos Abstractos

Son necesarios crear algo así, déjame te explico:

NombreDeClasePadre Instancia = new NombreDeClaseHija();

Y que no den ningun error hay que implantar tener en cuenta que:

  • No se puede llamar a un método si no existe en la clase Padre a pesar de ser un objeto de la Clase Hija.
  • Si existe en ambos el mismo método se llama al de la Clase Hija.

Para cumplir esto es necesario crear clase abstractas que existan en el Padre, pero que no hagan nada, simplemente que obligan a las clases hijas a añadirlas.

public abstract NombreDeClase();

Herencia en Varios Niveles

Es posible en Java crear herencias en varios niveles, es decir que ahora la clase nieta es capaz de acceder a todos los atributos y todos los métodos que tiene su padre y su abuelo siempre que sean públicos o protegidos.

herencia2

Sintaxis:

public class ClaseAbuelo{
//Contenido de Clase
}
public class ClasePadre extends ClaseAbuelo{
//Contenido de Clase
}

public class ClaseNieta extends ClasePadre{
//Contenido de Clase
}

La  herencia es al final del día:

HERENCIA = TRANSMISIÓN + REDEFINICIÓN + ADICIÓN

Es decir, la herencia te permite TRANSMITIR todos los métodos y atributos de una clase padre a la mía, REDEFINIR varios métodos de la clase padre si así lo deseo  y AÑADIR más si requiero más.

 

btn1 btn
btn

Polimorfismo

Oscar Rosas Deja un comentario

Es Polimorfismo es la capacidad que tiene un lenguaje de programación, en este caso Java, elegir uno u otro método en función del contexto.

mariposa

La SobreCarga

Es posible en Java crear dos métodos con el mismo nombre pero que reciben un tipo de dato diferentes, es decir con un parámetro diferente, es decir este ejemplo es posible:

//METODO #1
public void MétodoX(int Numero){
  Sentencias;
  ...
}

//METODO #2
public void MétodoX(String Frase){
  Sentencias;
  ...
}

Y el programa será capaz de decidir a cuál método nos referimos simplemente por el tipo de datos que le pasemos como parámetro.

La SobreEscritura

Es posible en Java crear dos métodos con el mismo nombre y que reciben un tipo de datos usando Herencia (ya lo verás después) , entonces dependiendo de si llamas a la un objeto de la clase hija o padre accederás a uno u otro método.

sobrecarga

Adios al viejo método

Es decir, se puede crear en una clase hija otro método con el mismo nombre y parámetros que un método en la clase padre, y entonces se dice que este método se ha sobrescrito.

Polimorfismo en POO

Es posible crear objetos en referencias de los padres, es decir:

NombreDeClasePadre Instancia = new NombreDeClaseHija();

Esto es útil para hacer vectores de objetos y demás, en el caso de que esto sea así se seguirán las siguientes reglas:

  • No se puede llamar a un método si no existe en la clase Padre a pesar de ser un objeto de la Clase Hija.
  • Si existe en ambos el mismo método se llama al de la Clase Hija.
btn1 btn
btn

Métodos y Constructores

Oscar Rosas Deja un comentario

constructores

Métodos

Los métodos son la siguiente parte importante de todo esto, representan las acciones que nuestro objeto puede hacer:

Es el nombre de las funciones en Java. Su sintaxis es:

public Tipo nombreDeMétodo(){
     sentencias;
     ...
     return Atributo
}

Métodos Especiales

Cuando se coloca un atributo en Java en privado para poder acceder a el se hacen métodos o funciones que dan permisos de Leer y Escribir (o llamadas GET y SET).

Métodos GET

Este tipo de funciones lo que devuelve es el atributo deseado, para que lo puedan ver desde fuera de la clase pero no puedan modificarlo.

public Tipo getAtributo(){
    return Atributo;
}

Ejemplo:

//Ejemplo 1
public String getNombre(){
    return Nombre;
}

//Ejemplo 2 (Usando Constructores)
public Tipo getAtributo(){
    return new Tipo(Atributo);
}

//Ejemplo 3 (Usando Constructores de Copia)
public vertice getA(){
    return new vertice(a);
}

Métodos SET

Este tipo de funciones lo que hace es darle valor a un atributo deseado, para que lo puedan ver desde fuera de la clase pero no puedan modificarlo.

Nota: Al referirnos al this.Atributo lo que estamos haciendo es referirnos al atributo de la clase, y al solo poner Atributo dentro del método nos referimos al atributo que acabamos de crear como parámetro del método.

public void setAtributo(){
     this.Atributo = Atributo;
}

Ejemplo:

//Ejemplo 1
public void getNombre(String Nombre){
   this.Nombre = Nombre;
}

Métodos de Object

Todos los objetos en Java son hijos de la clase Object, por lo que existen unos métodos bastante comunes que nosotros podemos sobre escribir y que nos muy útiles.

Método toString()

Cuando tu colocas el nombre de tu objeto donde venia ir un string se llama de forma automática este método. Generalmente se espera que regrese un string.

Método equals()

Es muy común que se llame para saber si dos objetos con lo «mismo» tu puedes modificarlo según lo que para ti se considere que tu objeto sea «igual» al otro.

Método finalize()

Se llama al colector de basura, nos permite guardar el estado o datos que creemos que son necesarios conservar antes de «borrar» un objeto.

Constructor

constructores

Es un método que evita tener que llenar los valores de cada objeto. Suele ser el primer método que se encuentra en cada clase, justo después de la declaración de atributos.

Aquí te coloco sus características mas comunes:

  • Tiene el mismo nombre que la clase
  • Generalmente es público
  • Su objetivo (su motivo en la vida) es inicializar el estado de los atributos de una clase
  • Se puede sobrecargar

Forma Básica

public NombreClase(Tipo Algo1, Tipo Algo2){
   this.Algo1 = Algo1;
   this.Algo2 = Algo2;
}

Constructores de Copia

Este tipo de constructores se usan cuando se crean objetos de objetos, decir, y valga la redundancia, copia o clona un objeto que ya existe.

Este tipo de constructores permiten crear objetos que serán independientes de sus paramentos una vez creados, pues de otra manera si se modificarán los atributos que usa un constructor para crear un objeto, los atributos del objeto en sí serán cambiados.

Usado cuando se crean objetos que reciben como parámetros de creación otros objetos.

public NombreClase(NombreClase ObjetoACopiar){
Algo1 = ObjetoACopiar.Algo1();
Algo2 = ObjetoACopiar.Algo2();
...
}

Ejemplo:

public Triangulo(Punto 1, Punto 2, Punto 3){
this.1 = new Punto(1);
this.2 = new Punto(2);
this.2 = new Punto(3);
}

Entonces no se llaman ya a los métodos SET and GET sino solo:

clase Nombre = new clase(Algo1,Algo2...)

Tipo NO tiene porque ser sólo int o strings sino que puede recibir objetos de tipos que hemos creado como autos o figuras.

Destructor

Java no tiene en si un destructor, pero si que tiene algo muy parecido, te mostrare:

public void Destruir(){
Algo1 = null;
Algo2 = null;
System.gc();
}

Sobrecarga de Métodos

Finalmente algo muy importante de lo que hablar es de la sobrecarga que permite que existan en una clase varios métodos que se llamen diferente y permite una mayor versatilidad.

Si principal ventaja es que permite reutilizar muchísimo código.

Hay varias características:

  • No importan si unos son public o private
  • Igual tipo de datos devuelto
  • Igual nombre del método
  • Distintos parámetros

Por ejemplo, veamos la clase de Ejemplo:

package LogicaDelSistema;

public class Persona {

    // ====== Atributos =====
    private int edad;
    private String nombre;
    private boolean sexo;

    // === Constructor ======
    public Persona(){
        this(0,"",false);

    }
    // === Constructor SobreCarga ===
    public Persona(int edad, String nombre, boolean sexo){
        this.edad = edad;
        this.nombre = nombre;
        this.sexo = sexo;
    }
    // === Constructor Copia ===
    public void setPersona(Persona PersonaOriginal){
        this.edad = PersonaOriginal.edad;
        this.nombre = PersonaOriginal.nombre;
        this.sexo = PersonaOriginal.sexo;
    }
    // === Constructor SET ===
    public void setPersona(int edad, String nombre, boolean sexo){
        this.edad = edad;
        this.nombre = nombre;
        this.sexo = sexo;
    }

    public String toString(){
        String mensaje;
        if(sexo){mensaje= "Hombre";}
        else{mensaje = "Mujer";}
        return "Edad:"+edad+"\n"+"nombre:"+nombre+"\n"+"sexo:"+mensaje;
    }

    public void Comer(){
        System.out.print("Comiendo ");
    }

    public void Comer(String comida){
        Comer();
        System.out.print(comida);
    }

    public void Comer(String comida, String amigo){
        Comer(comida);
        System.out.print(" con "+amigo);
    }

}

Sobrecarga de Operadores

Naaaaaahh…. Java no la tiene XD.

Pero aun así es un tema muy interesante, así que solo, SOLO con este tema te contaré lo que hace C++.

Así que olvida por un rato que estamos en Java y veamos como lo hace la competencia:

Por ejemplo, veamos la clase de Ejemplo:

tipo nombre_clase::operator + (lista de parámetros);

Podemos ver distinguir entre 2 Operaciones:

Los operadores binarios se declaran con un solo parámetro, ya que el primer parámetro es pasado por el programa como this, es decir, un puntero al mismo objeto.

// Binario
Objeto Objeto::operator + (Objeto &B);
Objeto A, B, C;
C = A + B;               // C = A.operator+(&B);

Los operadores unarios se declaran sin paramétros, ya que el único parámetro es pasado por el programa como this.

// Unario
Objeto Objeto::operator ++ (int Basura);
Objeto A, C;
C = A++;                 // C = A; A = A + 1;
C = A++;                 // C = A.operator++(int Basura);

This vs *This

class Foo {
    public:
        Foo(){
            this->value = 0;
        }

        Foo tenCopia(){
            return *this;
        }

        Foo& copiaComoReferencia(){
            return *this;
        }

        Foo* tenPuntero(){
            return this;
        }

        void aumenta(){
            this->value++;
        }

        void imprime(){
            std::cout<< this->value << "\n";
        }
}

Así podemos ver que:

int main(){
    Foo foo;
    foo.aumenta();
    foo.imprime();

    foo.tenCopia().aumenta();
    foo.imprime();

    foo.copiaComoReferencia().aumenta();
    foo.imprime();

    foo.tenPuntero()->aumenta();
    foo.imprime();

    return 0;
}

Así tenemos este resultado:

1
1
2
3
btn1 btn
btn