Estructura
de datos
En programación, una estructura de datos
es una forma de organizar un conjunto de datos elementales con el objetivo de
facilitar su manipulación.
Las
estructuras de datos determinan la conexión lógica entre los datos y afectan el
procesamiento físico de los datos.
Las
estructuras de datos son muy importantes en los sistemas de computadora. Los
tipos de datos más frecuentes utilizados en los diferentes lenguajes de
programación son:
Enteros.
Reales.
Carácter
(char).
Las operaciones básicas son:
- Alta, adicionar un nuevo valor a la estructura.
- Baja, borrar un valor de la estructura.
- Búsqueda, encontrar un determinado valor en la estructura para
realizar una operación con este valor, en forma secuencial o binario
(siempre y cuando los datos estén ordenados).
Otras operaciones que se pueden realizar son:
- Ordenamiento, de los elementos pertenecientes a la estructura.
- Apareo, dadas dos estructuras originar una nueva ordenada y que contenga
a las apareadas.
Cada estructura ofrece ventajas y desventajas en
relación a la simplicidad y eficiencia para la realización de cada operación.
De esta forma, la elección de la estructura de datos apropiada para cada
problema depende de factores como la frecuencia y el orden en que se realiza
cada operación sobre los datos.
Las
estructuras de datos dinámicas no tienen las limitaciones o restricciones en el
tamaño de memoria ocupada que son propias de las estructuras estáticas.
Mediante el uso de un tipo de datos específico, denominado puntero, es posible
construir estructuras de datos dinámicas que son soportadas por la mayoría de
los lenguajes, y en aquellos que sí tienen estas características ofrecen
soluciones eficaces y efectivas en la solución de problemas complejos -Pascal
es el lenguaje tipo por excelencia con posibilidad de estructuras de datos
dinámicos. Las estructuras dinámicas por excelencia son las listas -enlazadas,
pilas, colas, árboles- binarios, árbol-b, de búsqueda binaria- y grafos.
Una
característica importante que diferencia a los tipos de datos es la siguiente:
los tipos de datos simples tienen como característica común que cada variable
representa a un elemento; los tipos de datos estructurados tienen como
característica común que un identificador (nombre) puede representar múltiples
datos individuales, pudiendo cada uno de éstos ser referenciado independientemente.
Arreglos
Los arreglos se pueden definir
como objetos en los que podemos guardar más de una variable, es decir, al tener
un único arreglo, este puede guardar múltiples variables de acuerdo a su tamaño
o capacidad, es importante recordar que las variables guardadas deben ser del
mismo tipo. Existen 2 tipos de arreglos, los unidimensionales, y los multidimensionales
(generalmente 2 dimensiones y se les denomina matrices). Los arreglos
unidimensionales son más sencillos y fáciles de comprender, y los
multidimensionales un poco más complejo pero pueden servirnos para muchas aplicaciones.
Cola
Una cola es
simplemente un lugar para almacenar cosas, donde esas cosas se insertan una
detrás de otra y para extraer siempre se lo hace por adelante de la cola donde
se encuentra el primer elemento. Una cola funciona como una fila o cola de
personas, que esperan su turno para ser atendidas, la primera persona atendida
es siempre la primera de la fila y cuando llega una persona y queremos
incorporarla a cola o adicionarla debemos hacerlo por detrás de la ultima
persona en la cola.
Con fines educativos una cola se la
puede representar gráficamente así:
Una cola puede almacenar
lo que nosotros queramos, números, personas, documentos, cualquier cosa. Esta
estructura de datos tiene muchas aplicaciones en la informática al igual que la
pila, por ejemplo cuando mandan a imprimir varios documentos a una impresora,
existe una cola de impresión que sigue la filosofía, se imprimen los primeros
documentos y si quiero imprimir un nuevo documento se adiciona al final de
todos los documentos que están esperando a imprimirse.
Una vez comprendido en
concepto ahora veamos cómo se implementa esto en un lenguaje de programación,
por ahora lo implementaremos en Java. Java en sus librerías ya tiene la forma
de implementar Colas (queue), nosotros ahora haremos como si no existiera, es
decir crearemos nuestra versión, que es lo que generalmente se hace cuando se
aprende colas en la universidad. Pues bien existen dos formas de implementar
para que la cola sea o bien estática (reservamos un espacio fijo en memoria) o
bien dinámica (el tamaño en memoria va creciendo según se requiere), se
implementa con arrays o con listas enlazadas respectivamente. Nosotros
implementaremos haciendo de un array bidimensional es decir de modo estático y
al decir estático estamos diciendo que tendrá un límite para almacenar datos en
la cola.
Para manipular elementos
en el vector de la cola son necesarias variables que me digan en donde empiezan
los elementos y otra en donde terminan, como tal vez estés pensando ¿porque no
solo una? (una que me diga en donde termina asumiendo que siempre se empieza desde
la posición 0 del array), pues se puede implementar con solo una de estas
variables pero presenta muchas desventajas pues si eliminamos un elemento de
nuestra cola, (el primero justamente) tendríamos que recorrer todos los
siguientes elementos una posición adelante y esta manera seria muy lenta de
implementar pues que pasa si son 1000 elementos, eso es mucho tiempo perdido,
entonces es por eso que usamos dos variables que me digan dónde empieza y donde
terminan los elementos de la cola, dos variables enteras que llamaremos inicio
y fin, estas variables funcionan de la siguiente manera:
Pila
La Pila es una estructura de datos donde las inserciones y
recuperaciones/borrados de datos se hacen en uno de los finales, que es
conocido como el top de la pila. Como el último elemento insertado es el
primero en recuperarse/borrarse, los desarrolladores se refieren a estas pilas
como pilas LIFO (last-in, first-out).
Los datos se push (insertan) dentro y se pop
(recuperan/borran) de la parte superior de la pila. La siguiente figura ilustra
una pila con tres String cada uno
insertado en la parte superior de la pila:
Como muestra la figura anterior, las pilas se construyen en
memoria. Por cada dato insertado, el itém superior anterior y todos los datos
inferiores se mueven hacia abajo. Cuando llega el momento de sacar un ítem de
la pila, se recupera y se borra de la pila el ítem superior (que en la figura
anterior se revela como "third").
Cola Circular
Una cola circular o anillo es una estructura de
datos en la que los elementos están de forma circular y cada elemento tiene un
sucesor y un predecesor. Los elementos pueden consultarse, añadirse y
eliminarse únicamente desde la cabeza del anillo que es una posición
distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de
manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor,
respectivamente, de la cabeza actual. Las colas lineales tienen un grave
problema, como las extracciones sólo pueden realizarse por un extremo, puede
llegar un momento en que el apuntador A sea igual al máximo número de elementos
en la cola, siendo que al frente de la misma existan lugares vacíos, y al
insertar un nuevo elemento nos mandará un error de overflow (cola llena).Para solucionar el problema de
desperdicio de memoria se implementaron las colas circulares, en las cuales
existe un apuntador desde el último elemento al primero de la cola. La
representación gráfica de esta estructura es la siguiente: Ejemplo:
Listas Enlazadas
Las listas enlazadas son
estructuras de datos semejantes a los array salvo que el acceso a un elemento
no se hace mediante un índice 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 debe apuntar hacia NULL (el fin de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista es recorrida comenzando por el
inicio, el puntero siguiente permite el desplazamiento hacia el próximo
elemento.
El desplazamiento se hace en una sola dirección, del primer al último
elemento.
Si deseas desplazarte en las dos direcciones (hacia delante y hacia
atrás) deberás utilizar las listas doblemente enlazadas.
Listas doblemente enlazadas
Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples.
La asignación de
memoria es hecha al momento de la ejecución.
En cambio, en
relación a la listas enlazada simple el
enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia
el elemento anterior y otro que apunta hacia el elemento siguiente).
El puntero anterior
del primer elemento debe apuntar hacia NULL (el inicio de la lista).
El puntero siguiente
del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un
elemento, la lista puede ser recorrida en ambos sentidos:
· comenzando por el inicio, el puntero siguiente permite el
desplazamiento hacia el próximo elemento.
· comenzando por el final, el puntero anterior permite el
desplazamiento hacia el elemento anterior.
Las operaciones básicas de una lista doblemente enlazada son:
· Insertar:
inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al
principio o final de la lista o bien en orden.
· Eliminar:
elimina un nodo de la lista, puede ser según la posición o por el dato.
· Buscar:
busca un elemento en la lista.
· Localizar:
obtiene la posición del nodo en la lista.
· Imprimir:
imprime los elementos de la lista
Que no es estructura de Datos
Visto
lo anterior podemos decir que no es una estructura de datos cualquier conjunto
de datos no organizados que dificulta su manipulación para un proceso.
Conclusiones.
