Estructura de datos: organización de datos en un conjunto con relaciones bien definidas. Pueden ser anidadas. Estos datos pueden ser:
Numéricos
Decimales
Enteros
Caracter
char
String
Lógico
Booleanos
float
double
int
byte
short
long
Indican verdad o falsedad (true o false)
Intervalo : [-2^31 ... (2^31)-1]
Tamaño en disco: 4 byte
int nombreDato = 11;
Intervalo : [-128 ... 127]
Tamaño en disco: 8 bits
Intervalo : ['\u0000' .. '\uffff'] o [0 .. 65.535]
Tamaño en disco: 2 byte
Conjunto de caracteres, se puede implementar de la siguiente forma (java):
String nombreDato = " cadena ";
Intervalo : [-2^63 ... (2^63)-1]
Tamaño en disco: 8 byte
Intervalo : [-32,768 ... 32,767]
Tamaño en disco: 2 byte
Tamaño en disco: 8 byte
Tamaño en disco: 4 byte
long nombreDato = 12123;
char nombreDato = ' - ';
byte nombreDato = 1;
float nombreDato = 12,5 ;
double nombreDato = 0,13345;
boolean nombreDato;
nombreDato = true;
nombreDato = false;
Vectores o Arreglos unidimensionales
Intervalo : [±1,7·10^(-308) .. ±1,7·10^308]
Intervalo :[±3,4·10^(-38) .. ±3,4·10^38]
short nombreDato = 12;
Matrices o Arreglos bidimensionales
Poliedros o Arreglos multidimensionales
Grafos
Árboles
Colas
Listas enlazadas
Pilas
Arrays o Arreglos
Su tamaño puede variar durante la ejecución del programa. Su acceso es secuencial
Combinan tipos de datos primitivos en estructuras complejas y permiten representar la estructura de la información que el programa debe procesar, además se pueden implementar objetos
Tamaño definido antes de la ejecución del programa, no varían durante la ejecución.
Almacenan datos del mismo tipo o clase, se puede acceder a la información guardada mediante índices, además se puede trabajar arreglo de arreglos y arreglos escalonados
Poseen un solo índice de accesibilidad a la información, el tamaño depende de un solo dato
TipoArreglonombreDelArreglo[]= newTipo de arreglo[n] ; donde n es el tamaño del arreglo, TipoArreglo puede ser int, char, double, clasePersona, etc. (En java)
La estructura básica de este tipo de estructuras son los llamados NODOS, los cuales se componen por dos cosas importantes, la primera: donde se encuentran los datos, y la segunda: la que referencia a un objeto tipo nodo; por lo que podemos decir que es auto-referenciable,
la estructura básica del nodo es la siguiente:
publicclass NODO {
int dato; NODO sgt;
{
Poseen dos índices de accesibilidad a la información, el tamaño depende dos datos (número de filas y número de columnas)
TipoArreglonombreDelArreglo[][]= new Tipo de arreglo[f][c] ; donde f son las filas y c las columnas, TipoArreglo puede ser int, char, double, clasePersona, etc.(En java)
Poseen dos a más índices de accesibilidad a la información, cuando hacemos referencia a multidimensión facilmente podemos hablar de arreglo de arreglos. De la misma forma podemos pensar en un arreglo más próximo al tema de multidimensionalidad como: un arreglo con un índice más con respecto a una matriz; dandonos una idea de "un cubo"
TipoArreglonombreDelArreglo[][][]= new Tipo de arreglo[f][c][m] ; donde f son las filas, c las columnas, m las capas, TipoArreglo puede ser int, char, double, clasePersona, etc. (Sin embargo, un arregllo multidimensional puede aludir a una matriz que tiene por elementos arreglos)
Además de la diferencia de la manipulación del tamaño en la ejecución, existe algo por recalcar, el acceso varia dependiendo el tipo de dato estructurado. Si bien el estático favorece el acceso de una manera directa o aleatoria ( debido al índice ), cosa que no se cuenta en una estructura dinámica debido a que esta es secuencial y carece de índice; hay una desventaja en ciertos métodos tales como insertar y eliminar, cosa que en las dinámicas es mucho más facil que en las estáticas.
Esta estructura de datos se carecteriza por lo siguiente: Su modo de acceso es del tipo FILO ( last in, first out) el último en entrar es el primero en salir; además de ser muy sencillo y posee una buena respuesta a los procesos
Posee dos operaciones básicas tales como : push (apilar) y pop (desapilar); con esto se puede entender que hay acceso siempre al último elemento y , para acceder al resto, debemos empezar por retirar este último (top of stack) y así consecutivamente hasta llegar al deseado
En java se puede emplear la clase Stack para realizar la tarea de una pila
Esta estructura de datos se carecteriza por lo siguiente: Su modo de acceso es del tipo FIFO ( first in, first out) el primero en entrar es el primero en salir; al contrario de una pila, los elementos se insertan por un extremo y salen por el otro.
Posee operaciones básicas como : encolar , agregar un elemento al final de la cola; y desencolar, que quita el primer elemento al principio de la cola. Además de la operación frente, que devuelve el último elemento agregado
Podemos encontrar colas lineales o prioridad, circulares(donde el primer elemento y el último están unidos) y bicolas(los nodos se pueden añadir y quitar por ambos extremos, llamados DEQUE)
Esta estructura de datos es una de las fundamentales y se la puede usar para implementar otras estructuras de datos(como las pilas y las colas). Es una secuencia de datos dispuestos uno detrás de otro (un nodo destrás de otro) y se relacionan a través de un "enlace"
Debido a que se compone de nodos, los cuales son auto-referenciables, esos enlaces también se pueden conocer como "referencias"
Las listas enlazadas se clasifican en : simplemente enlazadas, doblemente enlazadas, circularmente enlazadas y circular doblemente enlazada
SIMPLEMENTE ENLAZADA
DOBLEMENTE ENLAZADA
CIRCULARMENTE ENLAZADA
CIRCULAR DOBLEMENTE ENLAZADA
Esta estructura se caracteriza por la forma que posee al ser representada, ya que hace referencia a la forma jerárquica de un árbol (aunque facilmente se parece a una raíz).En java se usan TreeMap para representar un BST(Binary Search Tree). Debido a esto, a continuación se muestra una terminología usada para estos árboles
Sirve para estructurar
Ambos son TDAs (TIPOS DE DATOS ABSTRACTOS
Los TDA o ADT (en inglés), son un tipo de dato definido por el usuario, cuyas operaciones especifican como un usario (que sería el cliente) puede manipular datos, definiendo así una interfaz entre usuario y dato; por otro lado, un TDA se representa por medio de clases
Raíz: El nodo superior de un árbol. Hijo: Un nodo conectado directamente con otro cuando se aleja de la raíz. Padre: La noción inversa de hijo. Hermanos: Un conjunto de nodos con el mismo padre Descendiente: Un nodo accesible por descenso repetido de padre a hijo. Ancestro: Un nodo accesible por ascenso repetido de hijo a padre. Hoja: Un nodo sin hijos. Nodo interno: Un nodo con al menos un hijo Grado: Número de subárboles de un nodo Brazo: La conexión entre un nodo y otro Camino: Una secuencia de nodos y brazos conectados con un nodo descendiente. Nivel: El nivel de un nodo se define por 1 + (el número de brazos entre el nodo y la raíz) Altura de un nodo: La altura de un nodo es el número de brazos en el camino más largo entre ese nodo y una hoja Altura de un árbol: La altura de un árbol es la altura de su nodo raíz Profundidad: La profundidad de un nodo es el número de brazos desde la raíz del árbol hasta un nodo Bosque: Un bosque es un conjunto de árboles n ≥ 0 disjuntos Rama: Una ruta del nodo raíz a cualquier otro nodo.
Dentro de los árboles encontramos a los famosos árboles binarios: cuya característica principal es que cada nodo posee un hijo izquierdo y uno derecho, no excediendo mas de dos hijos por nodo. Además de los árboles binarios de búsqueda:los cuales son arboles binarios que satisfacen la siguiente condición:
Árbol binario de búsqueda
Sea A un árbol binario de raíz R e hijos izquierdo y derecho (posiblemente nulos) HI y HD , respectivamente.
Decimos que A es un árbol binario de búsqueda (ABB) si y solo si se satisfacen las dos condiciones al mismo tiempo:
"HI es vacío" o ("R es mayor que todo elemento de HI" y "HI es un ABB").
"HD es vacío" o ("R es menor que todo elemento de HD" y "HD es un ABB").
Un grafo
Los árboles tienen muchas utilidades en el ámbito informático tales como : En árboles de busqueda,hash trees, treap(que tiene que ver con redes inalámbricas y asignación en memoria), huffman coding tree ( que tienen que ver con los archivos de formato .jpeg y .mp3), etc
si se analiza el árbol en base a la condicion, se obtiene que es un BST.
Partes básicas
Grafos dirigidos
Grafos ponderados, etiquetados, con costos o pesados
Grafos no dirigidos
Esta estructura se caracteriza por que existe una relación entre los nodos que la componen, mediante "aristas", estos grafos son estudiados en la TEORÍA DE GRAFOS (donde se estudia su implementación mediante un lenguaje de programación). Sus aplicaciones son diversas en las ciencias computacionales y matemáticas debido, justamente, a la teoría de datos. Los grafos son escenciales para las resoluciones de algoritmos complejos.
Dentro de los grafos podemos encontrar diversos tipos; sin embargo, de forma básica son interesantes los siguientes (los demás se estudiarán más a fondo luego de comprender los mencionados) :
Se dice que un arbol se convierte en grafo, si uno de los nodos hijos llegase a tener dos padres
