El primero fue de Sockets en Tcl, este será el segundo artículo que escribí hace como 6 años, este es sobre estructuras de datos en C++, Java y Python, me hubiera gustado terminarlo :D.
------
Estructuras de Datos en C++, Java y Python
-----------------------------------------------------------Este articulo esta dirigido a aquellas personas que tienen un conocimiento sobre lenguajes de programacion y que desean aprender un poco mas sobre ellos y sobre como mejorar sus programas mediante el uso de estructuras de datos mas complejas. En este articulo explicare en detalle algunas estructuras de datos ( las mas comunes ) y su implementacion en lenguajes de programacion como C++ y Java; sobre los algoritmos de manipulacion sobre dichas estructuras y sobre como optimizar su uso.
En este articulo supongo que el lector tiene conocimiento en dichos lenguajes y debido a esto no hare mucho incapie en sintaxis ni explicaciones pertinentes al lenguaje, solo a las estructuras.
Contenido:
---------------- Introduccion.
-- Estructuras Fundamentales.
--- Array.
--- Lista.
- Pilas.
-- Representacion.
-- Algoritmos de Manipulacion.
--- Push.
--- Pop.
--- Top.
--- Empty.
-- Implementacion en C++.
-- Implementacion en Java ( propia ).
-- Explicacion de la clase Stack de Java.
-- Implementacion en Python.
- Colas.
-- Representacion.
-- Algoritmos de Manipulacion.
--- Insert.
--- Delete.
--- Find.
--- Sort.
--- Empty.
-- Implementacion en C++.
-- Implementacion en Java.
-- Implementacion en Python.
- Listas Enlazadas.
-- Representacion.
-- Algoritmos de Insercion, Busqueda y Eliminacion.
-- Implementacion en C++.
-- Implementacion en Java ( propia ).
-- Explicacion de la clase LinkedList de Java.
-- Implementacion en Python.
-- Recomendaciones.
- Listas Doblemente Enlazadas.
-- Representacion.
-- Algoritmos de Manipulacion.
-- Implementacion en C++.
-- Implementacion en Java ( propia ).
-- Implementacion en Python.
-- Recomendaciones.
- Listas Circulares.
-- Representacion.
-- Algoritmos de Manipulacion.
-- Implementacion en C++.
-- Implementacion en Java ( propia ).
-- Implementacion en Python.
-- Recomendaciones.
- Arboles
--
- Grafos
- Tablas Hash
-------------------------------------------------------------------------------
- Introduccion:
---------------------Las estructuras de datos se basan en la teoria de conjuntos. Son agrupaciones de datos con caracteristicas comunes para su facil manejo. Existen dos tipos de estructuras de datos conocidas como "Estructuras Fundamentales" que son: Array y Lista, Son las mas faciles de manipular debido a que no existen sobre ellas ningun tipo de restriccion, por tanto los procesos de "Consultas y Modificaciones" son mucho mas faciles; muchas de las estructuras mas complejas
como pilas o colas son implementadas en base a estas dos, son como arrays con restricciones de acceso o modificacion.
La desventaja de la estructura Array es que es estatica, su tamaño debe ser fijado en tiempo de compilacion para la reserva de la memoria, mientras que las Listas permiten hacer reserva de mas memoria en tiempo de ejecucion de un programa, por tanto son dinamicas y pueden crecer con forme pasa el tiempo de ejecucion mientras que el array permanecera estatico durante dicho tiempo. En ambas estructuras no existe forma de saber si un dato se encuentra almacenado a menos que se haga un recorrido por toda la estructura y esto en cualquier caso tomara "Theta ( n )" ( se lee teta de n ) donde "n" es el tamaño de la estructura ( la cantidad de datos ) por tanto si "n" es muy grande esta busqueda seria demasiado costosa en tiempo. Por otro lado, Buscar
un elemento en la lista siempre sera "Theta ( n )", mientras que en un Array puede ser "Theta(1)" debido a que tiene un comportamiento parecido a una Tabla Hash, lo que permite hacer un accesado directo al dato buscado si tenemos la "llave" ( key ), en el caso de los Arrays dicha "llave" es el indice en el cual se encuentra el elemento. Para que quede mas claro muestro un ejemplo:
Tenemos dos estructuras:
Array [ n ]; // n es la cantidad de elementos.Lista.p = 0; // La estructura Lista tiene dos campos: p -> int, Lista.next = Lista // next -> puntero al siguiente elemento de la lista ( lista enlazada ).Inicializamos las estructuras.
for i <- 0 to n // para i desde 0 hasta n. Array [ i ] <- ( i + 1 ); Lista.p <- ( i + 1 ); Lista <- Lista.next; Lista.p <- infinito;Lista.next <- null;Si queremos saber si 9 esta en la lista tocaria:
for i <- 0 to n if Array [ i ] == 9 print "Esta en la pocision: " i; else print "No esta";i <- 0; while Lista.next != null if Lista.p == 9 print "Esta en la pocision: " i; else Lista <- Lista.next; i++;Como se ve, en ambas toca hacer una busqueda en toda la estructura hasta encontrar el elemento buscado. Ahora miremos otras operaciones:
Si queremos insertar un elemento:
Array [ k ] <- elemento // k es la pocision donde lo vamos a insertar.ptrLista.p <- elemento // ptrLista es un puntero a la ultima pocisionptrLista.next <- null // de la lista.Esta operacion es rapida y no toma mucho tiempo si tenemos en ambos casos una variable externa que nos indique en donde vamos en la estructura ( en Array es "k" y en Lista es "ptrLista" ), en caso contrario tocaria hacer de nuevo una busqueda por toda la estructura para encontrar el final e insertar ahi el nuevo elemento.
*********************************************************************************
Tip: Es bueno tener dicha variable externa en caso de realizar varias operaciones de este tipo sobre la estructura para ahorrar en tiempo de ejecucion.
*********************************************************************************
Ahora veamos que pasa cuando buscamos un elemento en una determinada pocision:
print Array [ k ]; // k es la pocision del elemento.i <- 0;while Lista.next != null if i == k print Lista.p; else Lista <- Lista.next; i++;Como vemos, en el Array hay un acceso directo por tanto el tiempo es Theta(1) mientras que en Lista hay que hacer una busqueda por toda la estructura, haciendo que su tiempo en el peor de los casos sea "Theta(n)".
Una vez visto la introduccion a estas estructuras basicas, entremos en materia. La estructura Lista sera explicada mas adelante.
-------------------------------------------------------------------------------
- Pilas ( Stack ):
----------------------Esta es una de las estructuras mas simples que existen, es generalmente implementada basandose en Array o Lista a las cuales se le aplican las restricciones necesarias para que se comporte como lo hace una pila ( LIFO, Last In, First Out ). La estructura de una pila responde al comportamiento de una pila de platos, donde se coloca uno, luego otro y asi sucecivamente hasta llegar a un numero "N" de platos apilados, luego cuando se desea obtener un plato en la pocision "X" ( 0 < style="font-style: italic;">Ultimo en llegar, Primero en Salir y es asi pues para obtener el ultimo plato primero deben retirarse los N-1 platos que estan encima de el ultimo.
Ejemplo:
N = 3, TotalPlatos = 1. Pos = 1 = XN = 3, TotalPlatos = 2. Pos = 1 = X Pos = 2 = XN = 3, TotalPlatos = 3. Pos = 1 = X Pos = 2 = X Pos = 3 = XComo se ve en el ejemplo, el ultimo en llegar queda ubicado en el tope de la pila y el primero va quedando "
cepultado". Ahora si desdeamos obtener el
tendriamos que retirar primero el para luego obtener el , asi: "X = 2", retiramos los "X - 1 = 2 - 1 = 1" platos antes que hay encima de él, o el , hariamos: "X = 3" y "3 - 1 = 2" platos que se
deben retirar primero.
******************************************************************************
Tip: en la computadora las pilas no se llenan hacia arriba como una pila de platos, se llenan es hacia abajo, por eso en la pila de datos de un programa, los parametros a funciones se pasan de forma inversa a la que son enviados asi, si tenemos:
function algo ( par1, par2 ), en la pila veriamos: // Sentido inverso al que nosotros lo enviamos.y al retirar el elemento del tope tendriamos: // El ultimo elemento era Esto por que supone que el orden importa y el elemento que se pasa de primero se va a utilizar de primero, asi que lo pone de ultimo en la pila para poder acceder de inmediato a ese elemento.
******************************************************************************
En este tipo de estructuras existen dos operaciones que son insertar conocida como PUSH y eliminar llamada POP, tambien es comun encontrar una tercera funcion para ver el ultimo elemento de la pila sin eliminarlo llamada TOP. En muchas implementaciones como en la de Stack de Java encontramos otras funciones como EMPTY y FULL para saber si la pila esta llena o vacia, ahora vamos a estudiar estos algoritmos en detalle.
-- Algoritmos de Manipulacion.
---------------------------------------- - Push ------- Push ( x ) Tope () = Tope () + 1 // Incrementa el tope de la pila. Pila ( Tope () ) = x // Almacena el nuevo elemento en el tope de la pila. - Pop ------ Pop ( ) Tope () = Tope () - 1 // Decrementa el tope en 1. Return Pila ( Tope () + 1 ) // Devuelve el elemento que se retiro para mostrarlo.En el algoritmo Pop se ve que solo se decrementa el contador del tope, esto es por que no hace falta eliminarlo realmente debido a que cuando se vaya a insertar un nuevo elemento, solo hace falta tener el tope, incrementarle 1 y ahi se sobre-escribe el dato. Asi como funciona el "rm" de las computadoras que no elimina realmente, solo etiqueta con "libre" y luego cuando va a guardar sobre-escribe.
Obviamente se puede mejorar estos algoritmos para evitar overflow y underflow pero esta es como la implementacion basica; la complejidad de estos dos es O(1) debido a que son operaciones que toman tiempo constante.
*********************************************************************************
Tip: En estas estructuras de datos hay dos tipos de vulnerabilidades que son:
underflow: cuando se desea retirar un elemento y la pila esta vacia. Este error es tipicamente tratado.
overflow: cuando se desea insertar un elemento y la pila esta llena. Este error no se trata con frecuencia es un topico importante en la validacion de seguridad de un programa. Genera un bug que puede ser explotado.
********************************************************************************
-------
Por desgracia este artículo lo dejé hasta ahí, espero sirva de algo para alguien jajaja. Gracias :P
Leer ++;
Leer --;
[Ciberpunk]
