Estructuras De Datos

Repaso De Introducción(conceptos básicos): 

1. Variable: una variable es una entidad donde podemos almacenar datos y posteriormente utilizarlos para realizar operaciones, una variable como su nombre lo indica tiene un valor cambiente. Las variables surgieron como alternativa ya que es mas facil manipular los datos mediante estas que ir cambiando los valores directamente en las celdas de memoria como se hacia anteriormente en lenguaje ensamblador.
2. Variable de Referencia: este tipo de variables son aquellas que apuntan a una direccion de un objeto.
3. Variables de clase: este tipo de variables son instanciadas de una clase y al ser instanciadas heredan sus atributos.
4. arreglo: un arreglo es una estructura lineal que nos permite almacenar datos de un mismo tipo.

Conceptos a tener en cuenta o conclusiones:

• cuando un programa inicia su ejecucion tiene derecho a un espacio en memoria para todo lo que necesite para su optimo funcionamiento.
• todas las variables de clase son variables de referencias y se instancian en la parte de memoria llamada head
• las variables primitivas se crean y cargan en stack
• el cuerpo de un arreglo es un objeto
• los objetos se crean en tiempo de ejecucion

Estructuras Dinamicas VS Estructuras estaticas

Estructuras Dinámicas:

 Ventajas:                                                                      

1. mejor aprovechamiento de memoria       
2. se le puede manipular el tamaño aun despues de haber sido creado                         

  Desventajas:

1. mas lento el acceso a los datos
2. consumen mas memoria

Estructuras Estaticas: 

Ventajas: 

1. es una estructura de facil acceso a los datos

Desventajas:

1. Debe tener un tamaño pre-definido
2. no se le puede modificar el tamaño despues de creado

Estructuras lineales VS Estructuras no lineales

Estructuras lineales: son un tipo de estructuras en la cual los datos se ven unidos en una sola secuencia.

Estructuras no lineales:los datos se presentan unidos por varias secuencias, se usan generalmente cuando hay dependencias entre un dato y otros relacionados a través de nodos.

Estructuras Lineales

Listas

conjunto de objetos enlazados entre si a través de direcciones en memoria en donde cada objeto es llamado nodo conformado por un dato y una dirección.

Tipos de Listas: 

1) Listas simplemente enlazadas: este tipo de listas esta conformada por nodos que contienen dos valores, dato y direccion del siguiente elemento, un nodo siempre esta apuntando al que le sigue.

2) Listas doblemente enlazadas: este tipo de listas esta conformada por nodos que contienen tres valores, referencia al nodo anterior, dato y referencia al nodo siguiente, donde cada nodo apunta al siguiente y al anterior a excepcion del inicial.

3) Listas circulares: este tipo de listas es muy parecida a la listas simplemente enlazadas, con la diferencia de que el ultimo nodo tiene una referencia que apunta hacia el primero


Operaciones con Listas: 

Insertar:
1) Inserar al inicio: inserta un nuevo nodo al inicio de la lista
2) insertar al final: inserta un nuevo nodo al final de la lista
3) Insertar despues de: inserta un nuevo nodo despues del nodo actual
4) Insertar antes de: inserta un nuevo nodo antes del nodo actua

Eliminar:

1) Eliminar al inicio: elimina el  nodo al inicio de la lista
2) Eliminar al final: elimina el nodo al final de la lista
3) Eliminar despues de: elimina el nodo despues del nodo actual
4) Eliminar antes de: elimina el nodo antes del nodo actual

Pilas: las pilas son una estructura de datos lineal en el que el modo de acceso a los datos es LIFO(Last - in - First - Out), ultimo en llegar, primo en salir.

-Operaciones: 
Poner: esta operación consiste en colocar un dato en el tope de la pila, es decir, en el lado superior de la estructura para que al momento de sacarse, sea el primero
Quitar: esta operacion consiste en sacar el dato que se encuentra en el tope de la pila
Cima: esta operacion consiste solamente en mostrar el dato que se encuentra en el tope de la pila, sin sacarlo de esta
Vacia: muestra si la pila esta vacia
Llena: muestra si la pila esta llena

-Aplicaciones: las pilas son de gran utilidad, en especial para evaluar expresiones aritmeticas e incluso en algoritmos que manejan los procesos de la cpu.

Colas: las colas son otra estructura de datos lineal, en este caso el modo de acceso a los datos es FIFO(First-in-First-Out) Primero en llegar, primero en salir.
este tipo de estructura tiene 2 extremos, por uno entran los datos y por el otro se sacan

-Operaciones: 
Poner: esta operación consiste en colocar un dato al final de la cola
Quitar: esta operacion consiste en sacar el dato que se encuentra de primero en la cola
Vacia: muestra si la cola esta vacia
Llena: muestra si la cola esta llena

-Aplicaciones: Cola de procesos, cola de impresion, simulacion, etc

Estructuras No Lineales

Recursividad: Hay que aclarar que la recursividad no es una estructura de datos, mas bien es un mecanismo de la programacion que nos sirve para hacer procesos iterativos que se hacen muy complejos.

Arboles: Estructura de datos no lineal para organizar la informacion por niveles.


Utilidades: Datos que siguen una jerarquia(se diferencia entre elementos mayores y menores)

Aplicaciones: Organigramas, Geneaologia, Directorios, Expresiones aritmeticas, Ordenamiento Y Busqueda

Terminologia(Arbol General): Compuesto por nodos que pueden tener una cantidad determinada de descendientes

En donde, 

Raiz: Unico inicio de Recorrido

Hoja: Nodo que no tiene hijos

Rama: Camino que inicia en una raiz y termina en una Hoja

SubArbol: Un nodo con todos sus hijos

Altura: Cantidad de niveles
Peso: Numero de hojas

Implementacion: 

1)Estatica

2)Dinamica

Arbol Binario: Arbol que solo tiene 2 hijos por nodo, distinguiendose asi la parte izquierda y la parte derecha.

Terminologia:

Arbol Completo: Todos los Nodos tienen 2 hijos o 0.

Arbol Lleno: Todos los niveles tienen un max de nodos 2^n-1

Arbol Degenerado: Todos los nodos tienen un hijo excepto la hoja.

Arbol Balanceado: En todos los nodos la diferencia entre la altura del subarbol izquierdo y derecho es menor q 2 y mayor que -2.

Grafos: Estructura de datos no lineal, compuesta por puntos llamados nodos o vertices a traves de un conjunto de lineas llamadas aristas

Utilidades: Relaciones multiples, Estructuras compuestas por puntos como las redes.

Aplicaciones: Redes informaticas, Redes de obras civiles como alcantarillado, vias etc.

Terminologia: 

En donde, 

Vertice o Nodo: contiene el dato.

Arista o Arco: se encarga de unir los nodos.

Adyacencia: 2 nodos se comunican a traves de una arista.

Grafos Dirigidos: Las aristas tienen direccion o sentido

Grafos Ponderados: Las aristas tienen peso o valor

Grafos Conexos: Todos sus vertices tienen una forma de comunicarse entre si

Implementacion:

1)Matriz de Adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.

2)Vector De Listas: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.

Recorrido:

1) Recorrido en Profundidad: Es un algoritmo para el recorrido de grafos que se basa en la utilizacion de una PILA para su implementacion, consiste en escoger un camino y recorrerlo hasta que no se encuentren mas nodos, luego vuelve para empezar por otro camino.

2)Recorrido en Amplitud: Es un algoritmo para el recorrido de grafos que se basa en la utlizacion de una COLA para su implementacion, consiste en escoger un nodo y explorar todos los nodos adyacentes a este hasta recorrer todo el arbol.


Algoritmos Para Hallar El Camino Mas Corto:

1)Dijkstra: este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.

2)Kruskal: Es un algoritmo que busca un subconjunto de aristas que conecten todo el grafo, siendo el valor de estas aristas el minimo posible.

3)Prim: Consiste en encontrar un camino que cubra todos los vertices del grafo con el minimo valor posible de las aristas sin formar ciclos.

4)Warshall:  El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución.