Estructura de datos: Estructuras de datos.

http://img.scoop.it/9PkWDNq54W6bvNGjVdy1qzl72eJkfbmt4t8yenImKBVvK0kTmF0xjctABnaLJIm9

Contenido:

1. Arboles A.V.L.
1.1 Rotaciones
1.1.1 Rotación a la derecha.
1.1.2 Rotación a la izquierda.
1.1.3 Doble rotación a la derecha.
1.1.4 Doble rotación a la izquierda.
1.2 Creación de un árbol A.V.L.
1.3 Ejemplo de creación y balanceo de un árbol A.V.L.

2. Archivos.
2.1 Archivos de texto.
2.2 Archivos binarios.
2.3 Manejo de archivos.
2.3.1 Manejo de archivos.

3.Arboles B.

3.1 Generalidades de los arboles B.
3.2 operaciones principales de los arboles B.
3.2.1 inserción.
3.2.1 eliminación.

4. Arboles B+
4.1 Operaciones básicas.
4.1.1 búsqueda.
4.1.2 inserción.
4.1.3 eliminación.

5. Grafos
5.1 Características de los grafos
5.1.1 Adyacencia
5.1.2 Incidencia
5.1.3 Camino Simple
5.1.4 Arco cíclico
5.1.5 Grado de un vértice
5.2 Tipos de grafos
5.2.1 Grafo simple
5.2.2 Grafo completo
5.2.3 Grafo regular
5.2.4 Multigrafo
5.2.5 Grafo dirigido
5.2.6 Grafo Euleriano
5.2.7 Grafo Hamiltoniano
5.3 Almacenamiento de grafos
5.3.1 Lista de adyacencia
5.3.2 Matriz de adyacencia
5.4 Digrafo fuertemente conectado

6. Algoritmo de Warshall.

7. Algoritmo de Prim.

8. Algoritmo de Dijkstra.

9. Algoritmo de Floyd.

10. Algoritmo de Kruskal.

1. Arboles A.V.L.

Son arboles binarios balanceados por altura, esto implica que la altura de una rama menos la altura de la otra no sea mayor a 1 o menor a -1.

-1 > 0 > 1

Factor de balance en A: 0-0=0

Factor de balance en B: 1-1=0

Factor de balance en C: 0-0=0

Estructura de un árbol A.V.L.

struct nodo

{

Int info;

Int fb;

struct nodo*izq;

struct nodo*der;

};

1.1 Rotaciones

1.1.1 Rotación a la derecha:
Se hace una rotación a la derecha cuando la rama izquierda del árbol este des-balanceada y que el nodo que indica p tiene un factor de balance >1 y el nodo que indica q tienen factor de balance = 1, el inorden tiene que ser igual antes y después de hacer la rotación.

1.1.2 Rotación a la izquierda:
Se hace una rotación a la izquierda cuando la rama derecha del árbol este des-balanceada que el nodo que indica p tiene un factor de balance <-1 y el nodo que indica q tienen factor de balance =-1, el inorden tiene que ser el mismo antes y después de la rotación.

1.1.3 doble rotación a la derecha:
Se hace una doble rotación a la derecha cuando el nodo que indica p tiene un factor de balance >1 y el nodo que indica q tienen factor de balance = -1, el inorden tiene que ser el mismo antes y después de la rotación.

1.1.4 doble rotación a la izquierda:
Se hace una doble rotación a la izquierda cuando el nodo que indica p tiene un factor de balance <-1 y el nodo que indica q tienen factor de balance =1, el inorden tiene que ser el mismo antes y después de la rotación.

1.2 Creación de un árbol A.V.L:
Para la creación de un árbol A.V.L el primer elemento dado es la raíz, se van ingresando los siguientes elementos teniendo en cuenta que si es menor que la raíz se coloca al lado izquierdo y si es mayor se coloca al lado derecho. Los siguientes elemento a ingresar se comparan con los nodos hojas, se verifica el elemento que este mas cerca y se hace el mismo procedimiento que con la raíz, si el árbol queda des-balanceado se hace la o las rotaciones correspondientes.

1.3 Ejemplo
Dados los elementos crear el árbol A.V.L, balancearlo y decir cuantos saltos hay hasta el numero 20.

7, 4, 9, 20, 15.

2. Archivos.

Un archivo es una estructura de datos que almacenar datos de manera ordenada, como una colección de información es decir una conjunto de registros, existen dos tipos de archivos de texto y binarios.

2.1 Archivos de texto:
es una secuencia de caracteres organizados en lineas de texto, se puede almacenar textos planos, bases de datos entre otras, estos solo pueden tener textos.

2.2 Archivos binarios:
es un conjunto de bytes que tienen comunicación entre si, estos archivo pueden ser textos con formatos, imágenes, vídeos, entre otros.

2.3 Manejo de archivos:

Antes de empezar con la creación se debe crear un archivo .txt en algún lugar de la memoria del computador, para trabajar archivos se utiliza unos estructura especial dentro de ella esta la función FILE se utiliza para crear el archivo, la funciones "fstdio.h" trae todas las funciones de los archivos predefinidas por defecto, por la general las instrucciones inician col la letra f.

2.3.1 Funciones básica:

se crea un apuntador de tipo FILE* , una vez creado el archivo se procede abrir el archivo utilizando la función fopen que crea los ficheros en el disco, dentro de el se asigna una instrucción que llama a nuestro apuntador. Se pueden realizar operación cono de lectura, escritura, edición, etc. el archivo se cierra con la función fclose.

el siguiente cuadro muestra las funciones de un archivo:

nombre	Función
fopen()	Abre un archivo
fclose()	Cierra un archivo
fgets()	Lee una cadena de un archivo
fputs()	Escribe una cadena de un archivo
fseek()	Busca un byte especifico de un archivo
fprintf()	Escribe una salida con formato en el archivo
fscanf()	Lee una entrada con un formato en el archivo
feof()	Devuelve cierto si se llega al final del archivo
ferror()	Devuelve cierto si se produce un error
rewind()	Coloca el cursor de posición en el archivo al principio del mismo
remove()	Borra un archivo
fflush()	Vacía un archivo
fread()	Lee un bloque de una “stream” de datos (binario)
fwrite()	Escribe un bloque de datos a un archivo como “stream” (binario)

FILE * fopen (const char *filename, const char *opentype); //apertura de un archivo.

int fclose (FILE *stream); //cierre de archivos.

opentype es una lista de parámetros para la función fopen que dice el tipo de fichero que esta llamando.

parámetro	descripción
r	Abrir un archivo para lectura, el fichero debe existir.
w	Abrir un archivo para escritura, se crea si no existe o se sobrescribe si existe
a	Abrir un archivo para escritura al final del contenido, si no existe se crea.
rt	Abrir un archivo para lectura y escritura, el fichero debe existir.
wt	Crear un archivo para lectura y escritura, se crea si no existe o se sobrescribe si existe.
r+b o rb+	Abre un archivo en modo binario para actualización (lectura y escritura).
rb	Abre un archivo en modo binario para lectura.

este es un prototipo de un archivo para lectura, es necesario verificar si el archivo se abrio correctamente con lña condicion " if(fp==NULL) ".

#include <fstdio.h>

#include <stdlib.h>

int main(int argc, char** argv)

{

FILE *fp;

fp = fopen ( "fichero.in", "r" );

if (fp==NULL)

{

fputs ("File error",stderr); exit (1);

}

fclose ( fp );

return 0;

}

3.Arboles B.

Son estructuras de datos utilizados para búsqueda de información, son arboles no binarios y con condiciones de balanceados, estos arboles son muy utilizados en las bases de datos.

3.1 generalidades de los arboles B.

Utilizan un método de búsqueda externo.
Cada nodo o pagina en un árbol B de orden D debe tener 2d calves como máximo y d claves como mínimo.
cada pagina de un árbol B tiene 2d+1 hijos como máximo y d+1 hijos como mínimo, excepto la raíz que debe tener 1 clave y por consiguiente 2 hijos.
Las paginas hijas van todas en el mismo nivel.
los arboles B crecen de abajo hacia arriba.

3.2 operaciones básicas de arboles B

3.2.1 inserción:

Para insertar un nuevo elemento a un árbol B debemos tener en cuenta la clave a ingresar y donde lo vamos a ingresar. Se ingresa siempre en las paginas hijas, si la pagina tiene campo se busca el lugar donde va a quedar esta nueva clave y simplemente se ingresa, si la pagina esta llena se ingresa la clave y se sube el que esta mas hacia el centro de la pagina como raíz y se divide la pagina hija en dos.

3.2.2 Eliminación:

Esta operación es mas complicada que la inserción, trata de quitar una clave del árbol sin violar los principios del mismo, en la pagina raíz no debe haber menos de d claves ni mas de 2d claves, si se encuentra en la hoja simplemente se elimina, pero si no debe bajarse el adyacente de la pagina antecedente y sustituir esta clave con la que se encuentra mas a la derecha del sub-árbol izquierdo o la que esta mas a la izquierda del sub-árbol derecho.

4. Arboles B+.

Es una estructura de datos de tipo árbol, en el se encuentran reunidos datos ordenados de manera ordenada y donde el árbol quede balanceado, se pueden hacer operación en el como los que se pueden hacer en los demás arboles como lo es la búsqueda, la inserción y el borrado de claves. En un árbol B+ se puede tomar cualquier camino desde la raíz hasta una calve y debe tener la misma longitud, este tipo de arboles ocupa mas espacios ya que hay duplicidad de las claves.

4.1 operaciones básicas:

Estas operaciones son la búsqueda, la inserción y la eliminación.

4.1.1 Búsqueda:

Se comienza desde la raíz hasta llegar al hoja que se pida.

4.1.2 Inserción:

La inserción en un árbol B+ es parecida a la inserción el los arboles B, cuando se inserta una clave en una pagina y esta esta llena, se divide en dos a la izquierda y la derecha que deban tener d y d+1 claves. Una copia de la clave del medio sube a la pagina antecesora.

4.1.3 Borrado:

El borrado en un árbol B+es mas simple que en el árbol B por que las claves siempre están en las hojas del árbol, existen dos casos para la eliminación

- Al eliminar una clave m la pagina queda >=d termina la operación, las claves de la pagina raíz o de las demás no se modifican ya que son copias.

- Si m > d debe realizarse una distribución de claves como de paginas hojas, el árbol puede disminuir su altura.

5. Grafos

Un grafo es una estructura de datos que permite representar varias relaciones entre objetos, un grafo contiene vértices y arcos. Los grafos tiene una gran cantidad de aplicaciones, como los son el manejo de redes, construcción de circuitos electrónicos, en estrategias de ventas, cartografía, economía, entre otras.

5.1 Características de los grafos

5.1.1. Adyacencia:

Dos vértices tienen adyacencia si están unidos por un arco.

5.1.2. Incidencia.

Un arco es incidente en un vértice si una de de la puntas llega a ese vértice.

5.1.3. Camino simple.

Se tiene camino simple en un grafo si partiendo de cualquier vértice podemos recorrer todos los vértices sin repetir arcos.

5.1.4. Arco cíclico.

Un arco cíclico es cuando partiendo desde un vértice se llega al mismo vértice.

5.1.5. Grado de un vértice.

Es el numero de arcos que inciden en un vértice.

5.2 Tipos de grafos:

5.2.1. Grafos simples:

un grafo es simple si en su estructura no tiene arcos cíclicos y solo hay un solo arco entre dos vértices.

5.2.2 Grafo Completo.

Un grafo es completo su su grado es de n-1, donde n es la cantidad de vértices que comprenden toa la estructura del grafo.

5.2.3 Grafo regular.

Un grafo es regular si todos sus vértices tienen el mismo grado.

5.2.4 Multigrafo.

Es un grafo donde dos de sus vértices esta unidos por mas de un arco.

5.2.5 Grafo dirigido

Es cuando los arcos de un grafo tienen dirección (Dígrafo).

5.2.6 Grafo Euleriano

Es un grafo donde se parte de cualquier vértice podemos recorrer todos los arcos llegando de nuevo al vértice origen, se puede pasar por los vértices cuantas veces sea necesario pero los arcos solo se recorren una vez.

5.2.7 Grafo Hamiltoniano

Es un grafo donde se parte de cualquier vértice podemos recorrer todo los vértices sin repetir ninguno y finalmente llegar al vértice origen, los arcos pueden ser recorridos cuantas veces sea necesario.

5.3 Almacenamiento de grafos

5.3.1 Lista de adyacencia
Se utiliza una lista de adyacencia para guardar los adjuntos a un vértice dado.

5.3.1 Matriz de adyacencia
Se implementa una matriz de adyacencia para observar los caminos que hay de un vértice a otro, se coloca un 1 cuando hay camino de lo contrario un 0.

1 2 3 4 5
1 2 3 4 5	0	0	0	1	0
	0	0	0	0	1
	1	1	0	0	0
	0	1	1	0	0
	0	0	0	1	0

5.4 Digrafo fuertemente conectado

Un digrafo esta fuertemente conectado si desde un vértice se puede llegar a todos los demás. Para saber si esta fuertemente conectado es necesario hallar la sumatoria de matrices

S= M+ M2+M3+... Mnv

Donde nv es el numero de vértices

6. Algoritmo de Warshall.

"El siguiente escrito fue realizado por el estudiante de ingeniería de sistemas de la Universidad INCCA de Colombia Jeisson Gonzalez"

Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo entre un par de vértices, como resultado nos da la mejor ruta para poder llegar al vértice destino en grafos dirigidos Como resultado nos dará una matriz de clausura transitiva.

Ejemplo:

PASOS

1) Hallamos la matriz de adyacencia.

2) Tomamos cada vértice como pivote llenando su respectiva matriz dependiendo si hay camino o no.

3) Como resultado nos da una matriz de adyacencia transitiva con la cual podemos saber si hay un camino de un vértice cualquiera a otro vértice elegido al azar

PIVOTE=cuando se dice tomamos el vértice como pivote quiere decir que podemos formar una conexión directa entre un vértice y un tercero, como si el vértice tomado como pivote no estuviera

· Matriz de adyacencia.

	a	b	c	D
a	0	1	0	0
b	0	0	1	0
c	1	0	0	1
d	0	0	0	0

· Tomamos como pivote a (a)

M1 (a)

	a	b	c	D
a	0	1	0	0
b	0	0	1	0
c	1	1	0	1
d	0	0	0	0

· Tomamos como pivote a (b) sin olvidar que (a) sigue siendo pivote

M2 (b)

	a	b	c	D
a	0	1	1	0
b	0	0	1	0
c	1	1	1	1
d	0	0	0	0

· Tomamos como pivote a (c) sin olvidar que los anteriores vértices siguen siendo pivotes en este caso (a) y (b)

M3 (c)

	a	b	c	D
a	1	1	1	1
b	1	1	1	1
c	1	1	1	1
d	0	0	0	0

· No realizamos la matriz con el pivote (d) ya que no tiene ningún arco de adyacencia por lo tanto la matriz serian ceros ( 0 )

· Matriz de clausura transitiva.

	a	b	c	D
a	1	1	1	1
b	1	1	1	1
c	1	1	1	1
d	0	0	0	0

7. Algoritmo de Prim.

"El siguiente escrito fue realizado por el estudiante de ingeniería de sistemas de la Universidad INCCA de Colombia Rafael Echeveri"

El algoritmo de Prim consiste en recorrer todos los vértices de un grafo en el menor peso posible, esto genera un árbol recubridor de menor peso, para que esto se cumpla el grafo debe ser conexo, estar etiquetado y sus arcos deben de tener un peso. Es decir

Si observamos el arco que hay entre el vértice 0 y 2 tiene un numero en rojo, eso es lo que llamamos “peso” luego también es un grafo conexo y esta etiquetado.

En el algoritmo de Prim podemos comenzar por cualquier vértice luego para recorrerlo hay que tener los vértices adyacentes al que hemos escogido como punto de partida es decir, si empezamos con el vértice “0” este tiene dos vértices adyacentes que son el “2” y el “3”.

Entonces para saber a cuál de los dos escoger, entre el vértice “2” o “3” miramos el peso que tiene cada arco. Así el peso del vértice “0” al vértice “2” es de 5, y del vértice “0” al vértice “3” es de 8 entonces simplemente escogemos el de menor peso que es del vértice “0” al vértice “2” y ya tenemos trazado un arco. Así tenemos que hacer el mismo proceso para los demás vértices hasta completar todo el grafo, hay que tener en cuenta que al hacer el árbol recubridor, este no puede quedar cerrado por que quedaría como un ciclo y no queremos eso. Aquí tendremos un ejemplo…

8. Algoritmo de Dijkstra.

Se le atribuye el nombre al científico de computación Holandés Edsger Dijkstra, también llamado al algoritmo de caminos mínimos. Consiste en encontrar el camino más corto entre dos vértices, cada uno de los vértices debe tener una etiquete y los arcos un peso. El grafo no debe estar dirigido ya que si lo esta no sería de este tipo.

Primero tomamos un punto de partida x, este puede ser cualquier vértices y tomamos uno como el punto de llegada, se toman los vértices adyacentes al origen y se evalúa el de menor peso, es decir, el que tenga la etiqueta con el número menor, se toma ese camino y se hace el mismo proceso hasta llegar al vértice que se tomó como final.

Ejemplo

Calcular la longitud entre a y g.

Vértice	1	2	3	5	6
a	[0 , x]
b		[8 – a]		[6 – d]	[10 – e]
c		[5 – a]
d			[3 – c]
e				[2 – d]
f			[7 – c]	[5 – d]
g					[1 - e]

Camino mas corto: a, c, d, e, g.

En el anterior cuadro se puede ver como se aplica el algoritmo de Dijkstra, se inicia en el primer vértice donde se pone el peso acumulado y el vértice de donde procede al ser el primero no tienen peso acumulado ni un vértice de procedencia, en la segunda casilla se toman los vértices adyacente al primero y se compara, el recuadro azul da la etiqueta definitiva que dice que este es el camino más corto entre los dos vértices comparados, se realiza hasta el final y obtenemos el camino más corto.

9. Algoritmo de Floyd.

"El siguiente escrito fue realizado por la estudiante de ingeniería de sistemas de la Universidad INCCA de Colombia Luisa Parez"

Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Floyd es un ejemplo de programación dinámica.

El algoritmo de Floyd es más importante desde el punto de almacenamiento dado que puede ser implementado una vez se halla actualizado la distancia de la matriz.

EJEMPLO:

Primero hacemos una matriz de caminos y una de padres.

MATRIZ DE CAMINOS MATRIZ DE PADRES

Fila A y columna A

Lo siguiente es coger una columna con una fila y sumarla, si la suma de la fila y la columna es menor que el número que está en la posición evaluada se cambia pero si es mayor no se cambia. Si hay un infinito en la posición evaluada también se cambia por el número que haya dado la suma.

Teniendo en cuenta que no se puede sumar un infinito con otro número u otro infinito.

En la matriz de padres se coloca la letra que se está evaluando que es de donde proviene el número que se puso en la matriz de caminos.

Para saber cuál es el camino que tiene menor peso para llegar de la A a la E se mira en la última matriz de padres entonces para llegar a la E tiene que pasar por la C que es la letra que esta subrayada y si vemos es la que menor peso tiene para llegar a esta esto se ve en la matriz de camino. Otro ejemplo es para llegar de la E a la C tiene que pasar por la B que es la letra subrayada y también es el menor peso por el cual se puede ir lo podemos observar en la matriz de caminos

10. Algoritmo de Kruskal.

"El siguiente escrito fue realizado por el estudiante de ingeniería de sistemas de la Universidad INCCA de Colombia Santiago Rodriguez"

El algoritmo de Kruskal es un algoritmo de recubrimiento mínimo conexo ponderado, o sea que va unir todos los nodos formando un árbol, tomando las aristas que tengan un peso que siempre sea el menor.

Este árbol generado por el grafo es un sub-grafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples arboles.

Características:

Algoritmo basado en las aristas

Agrega las aristas, una a la vez, en orden de peso creciente.
objetivo del algoritmo de Kruskal es construir un árbol (sub-grafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en sus arcos.
Resuelve la misma clase de problemas que el Algoritmo de Prim a diferencia que no se escoge un nodo al azar.
Trabaja con grafos ponderados y no dirigido.