Estructura de Datos I

Publicado por rogikato / en 20:20 / / 0 comentarios

Contenido

•  Introducción

•  Tipos de Datos Abstractos

• Tipos de Datos
• Tipos de Datos Abstractos

•  Recursividad

•  Análisisi de la Performance de Algoritmos

•  TAD Lista

• Listas Secuenciales
• Listas Encadenadas
• Listas Simplemente Encadenadas
• Implementación (Estática)
• Implementación (Dinámica)
• Listas Doblemente Encadenadas
• Implementación (Dinámica)
• Listas Circulares
• Implementación (Dinámica)
• Pilas y Colas
• Pilas
• Implementación (Estática)
• Implementación (Dinámica)
• Colas
• Implementación (Estática)
• Implementación (Dinámica)
• Listas Generalizadas
• Implementación
• Algoritmos Recursivos

•  Matrices

• Matrices Esparcidas
• Representación por líneas
• Representación utilizando conjunto de listas encadenadas

•  Hashing

• Funciones Hash
• Método de la División
• Implementación
• Hashing Universal
• Colisiones
• Encadenamiento Separado (Separate Chaining)
• Direccionamiento Abierto (Open Addressing)
• Distribución lineal
• Distribución cuadrática
• Distribución doble

•  Ordenamiento

• 47">BubbleSort
• implementación
• Método de inserción directa
• implementación
• Shell (Classificación de Incremento Decreciente)
• Implementación
• HeapSort
• Implementación
• Teorema Master
• MergeSort
• Implementación
• QuickSort
• implementación
• BucketSort

•  Arboles

• Arboles Binarios
• Representación de Árboles Binarios
• Representación Implicita
• Representación Encadenada
• Recorrido de árboles binarios
• Representación de Árboles a través de Árboles Binarios
• Arbol de Búsqueda Binaria
• Inserción en árboles de búsqueda binaria
• Eliminación en árboles de búsqueda binaria
• Árboles AVL
• Algoritmo de Inserción en un árbol AVL
• Implementación de las Rotaciones
• Algoritmo de Inserción
• Algoritmo de Eliminación en árbol AVL
• Árboles-B
• Búsqueda en un árbol-B
• Inserción en un árbol-B
• Eliminación en árbol-B

• 75">Quad-Tree

•  Grafos

• Representación de Grafos
• Matriz de Adyacencia
• Listas de adyacencia
• Multilistas
• Búsqueda en Grafos
• Búsqueda en Profundidade
• Búsqueda en anchura
• Árbol generador mínimo
• Camino de costo Mínimo
• Camino más Corto
• Algoritmo de Dijkstra
• Ordenación Topológica
• Coloración en Grafos

•  Bibliografia

Listas Encadenadas

Publicado por rogikato / en 19:49 / / 0 comentarios

En listas encadenadas, los elementos consecutivos en la lista no significa que los mismos esten consecutivamente representados (el orden es lógico)
En la implementación es necesario almacenar separadamente la información de un elemento de la lista, normalmente el primero.
Existen dos formas representar listas encadenadas, a través de array, denominadas listas estáticas, o por punteros llamadas listas dinámincas.

Las principales ventajas de las listas encadenadas son:
 1. Elimina el problema de los traslados de nodos
 2. En el caso de listas dinámicas no se requiere saber previamente el número de elementos a ser almacenados.
Las principales desventajas son:
 1. No se consigue (de manera directa) accesar a los elementos de la lista en tiempo constante.
 2. Mayor número de operaciones para mantener la integridad de los datos.
Las listas encadenadas puede ser divididas en:

• Únicamente o simplemente encadenadas 
• Doblemente encadenadas 
• Circulares 

En el caso de listas no circulares, las operaciones de inserción y eliminación deben considerar algunos o casos especiales, que son las inserciones y eliminaciones al comienzo y final de las listas.
La inserción del primer elemento en la lista (convirtiéndola en no vacía) y la eliminación del último elemento (convirtiéndoloa en vacía) deben ser considerados como casos especiales para todos los tipos de lista.

Listas Doblemente Encadenada

Publicado por rogikato / en 19:27 / / 0 comentarios

En una lista doblemente encadenada, cada elemento posee las informaciones de quien es su sucesor y su antecesor.
 
Principales ventajas:
 1. Permite caminar en las dos direcciones de la lista.
 2. Inserción y eliminación de elementos son realizados con más facilidad.

Principales problemas:
 • Mayor espacio reservado
 • Manipulación de un puntero extra Implementación (Dinámica)

Por simplicidad los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada. (Fig 4.2)La operación de inserción de un nuevo elemento en la posición anterior al elemento actual puede ser descrito como sigue (suponiendo que actual no es el primer elemento de la lista):
nuevo->proximo = actual; 
nuevo->anterior = actual->anterior; 
actual->anterior->proximo = nuevo; 
actual->anterior = nuevo; 
 Note que en este caso no es necesario un elemento posterior. Especificación: Igual a la del ejemplo estático para listas simplemente encadenadas
Observación: En el ejemplo abajo todavía estamos utilizando un puntero auxiliar llamdo "ant", como ejercicio, realice una nueva implementación de la función inserta_elemento sin utilizar este puntero auxiliar.
 

Código:
  #include<iostream.h> #include<conio.h> #include<stdlib.h> typedef struct lista LE; typedef struct nodo_lista NO; struct nodo_lista{ int elem; NO *prox; // guarda la pos. del próx. elem. en la lista NO *ante; // guarda la pos.del elem. ant. en la lista */ }; struct lista { NO *head ; // guarda la dir. de primer elem. de lista }; LE *Inicia_Lista(void) { LE *temp; if ((temp = (LE *) malloc(sizeof(LE))) != NULL) { temp->head = NULL; return(temp); } else exit(0); } void Inserta_Elemento(LE *L, int A){ NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { aux->elem = A; if (L->head == NULL)//lista ESTA VACIA { aux->prox = NULL; aux->ante = NULL; L->head = aux; } else{ atu = L->head; ant = NULL; while ((atu != NULL) && (atu->elem <= A)) { ant = atu; atu = atu->prox; } if (ant == NULL) // insert en primera pos. de lista { aux->prox = L->head; aux->ante = NULL; L->head->ante = aux; L->head = aux; } else { aux->prox = ant->prox; aux->ante = ant; if (ant->prox != NULL) ant->prox->ante = aux; ant->prox = aux; } } } else exit(0); return; } int Eliminar_Elemento(LE *L, int A){ NO *ant,*act; if ((ant = (NO *) malloc(sizeof(NO))) != NULL) {if(L->head==NULL) return -1; else { act=L->head; if(act->elem==A) {if(act->prox==NULL) L->head=NULL; else{ L->head=act->prox; act->prox->ante=NULL; }return 1; } while(act!=NULL) { if(act->elem==A) { if(act->prox==NULL) {ant->prox=NULL; act->prox=NULL; act->ante=NULL; } else{ ant->prox=act->prox; act->prox->ante=ant; act->prox=NULL; act->ante=NULL; } return 1; } else { ant=act; act=act->prox; } } return -1; } } } void Imprime_Lista(LE *L){ NO *aux,*atu; int tam=0; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; while (atu != NULL) { tam++; cout<<atu->elem<<" "; atu = atu->prox; } cout<<" de tama\xa4o "<<tam; } } main() { int aux_l; LE *l; int x; char opc; l = (LE *) Inicia_Lista(); while (1) { cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) "; cin>>opc; if (opc == 'i') { cout<<"\n Ingrese el nuevo elemento entero "; cin>>x; Inserta_Elemento(l,x); } if (opc == 'e') { cout<<"\n Ingrese el numero entero a buscar "; cin>>x; aux_l = Eliminar_Elemento(l,x); if (aux_l == -1) cout<<"Numero no encontrado\n"; } if (opc == 'p') Imprime_Lista(l); if (opc == 's') { //l = (LE *) Vacia_Lista(l); exit(0); } } }

Listas Circulares

Publicado por rogikato / en 4:29 / / 0 comentarios

Una lista circular puede ser simple o doblemente encadenada. Lo que caracteriza a las listas circulares es el hecho que el sucesor del último elemento es el primer elemento de la lista. En el caso de una lista doblemente encadenada, el predecesor del primer elemento es el último elemento de la lista.
 
La principal ventaja de las listas circulares es que no necesitamos considerar casos especiales de inserción y eliminación de elemento (primero y último).

 Implementación (Dinámica)

Listas Circulares simplemente enlazada

Código
#include<iostream.h> #include<conio.h> #include<stdlib.h> typedef struct lista LE; typedef struct nodo_lista NO; struct nodo_lista { int elem; NO *prox; /* guarda la posicion del proximo elemento en la lista */ }; struct lista { NO *head ; /* guarda la dirección del primer elemento de la lista */ }; LE *Inicia_Lista(void) { LE *temp; if ((temp = (LE *) malloc(sizeof(LE))) != NULL) { temp->head = NULL; return(temp); } else exit(0); } void Inserta_Elemento(LE *L, int A) { NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { aux->elem = A; if (L->head == NULL) { aux->prox = aux; L->head = aux; } else { /* Inserta en la pos. anterior de head */ aux->prox = L->head->prox; L->head->prox = aux; } } else exit(0); return; } int Eliminar_Elemento(LE *L,int A){ NO *ant,*act; if ((ant = (NO *) malloc(sizeof(NO))) != NULL) { if(L->head == NULL){ return -1; } else { act=L->head; ant=NULL; do {ant=act; act=act->prox; }while(act->elem!=A&&act!=L->head); if(act->elem==A) { ant->prox=act->prox; act->prox=NULL; if(act==L->head) {L->head=ant; if(act==ant) L->head=NULL; } return 1; } else return -1; } } } void Imprime_Lista(LE *L){ NO *aux,*atu; int tam=0; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; do { if(L->head!=NULL) {tam++; cout<<atu->elem<<" "; atu = atu->prox; } }while (atu != L->head); if(tam)cout<<" de tama\xa4o "<<tam; else cout<<"Lista vacia"; } } /* Ejercicios: Implementar las funciones que faltan */ main() { int aux_l; LE *l; int x=0; char opc; l = (LE *) Inicia_Lista(); while (1) { cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) "; cin>>opc; if (opc == 'i') { cout<<"\n Ingrese el nuevo elemento entero "; cin>>x; Inserta_Elemento(l,x); } if (opc == 'e') { cout<<"\n Ingrese el número entero a buscar "; cin>>x; aux_l = Eliminar_Elemento(l,x); if (aux_l == -1) cout<<"Numero no encontrado\n"; } if (opc == 'p') Imprime_Lista(l); if (opc == 's') { //l = (LE *) Vacia_Lista(l); exit(0); } } }

Listas Circulares doblemente enlazada

Código
#include<iostream.h> #include<conio.h> #include<stdlib.h> typedef struct lista LE; typedef struct nodo_lista NO; struct nodo_lista { int elem; NO *prox,*ante; /* guarda la posicion del proximo elemento en la lista */ }; struct lista { NO *head ; /* guarda la dirección del primer elemento de la lista */ }; LE *Inicia_Lista(void) { LE *temp; if ((temp = (LE *) malloc(sizeof(LE))) != NULL) { temp->head = NULL; return(temp); } else exit(0); } void Inserta_Elemento(LE *L, int A) { NO *aux,*ant,*atu; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { aux->elem = A; if (L->head == NULL) { aux->prox = aux; aux->ante=aux; L->head = aux; } else { /* Inserta en la pos. anterior de head */ aux->prox = L->head->prox; L->head->prox = aux; aux->ante=L->head; L->head->prox->ante = aux; } } else exit(0); return; } int Eliminar_Elemento(LE *L,int A){ NO *ant,*act; if ((ant = (NO *) malloc(sizeof(NO))) != NULL) { if(L->head == NULL){ return -1; } else { act=L->head; ant=NULL; do {ant=act; act=act->prox; }while(act->elem!=A&&act!=L->head); if(act->elem==A) { ant->prox=act->prox; act->prox->ante=ant; act->prox=NULL; act->ante=NULL; if(act==L->head) {L->head=ant; if(ant==act) L->head=NULL; } return 1; } else return -1; } } } void Imprime_Lista(LE *L){ NO *aux,*atu; int tam=0; if ((aux = (NO *) malloc(sizeof(NO))) != NULL) { atu = L->head; do { if(L->head!=NULL) {tam++; cout<<atu->elem<<" "; atu = atu->prox; } }while (atu != L->head); if(tam)cout<<" de tama\xa4o "<<tam; else cout<<"Lista vacia"; } } /* Ejercicios: Implementar las funciones que faltan */ main() { int aux_l; LE *l; int x=0; char opc; l = (LE *) Inicia_Lista(); while (1) { cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) "; cin>>opc; if (opc == 'i') { cout<<"\n Ingrese el nuevo elemento entero "; cin>>x; Inserta_Elemento(l,x); } if (opc == 'e') { cout<<"\n Ingrese el número entero a buscar "; cin>>x; aux_l = Eliminar_Elemento(l,x); if (aux_l == -1) cout<<"Numero no encontrado\n"; } if (opc == 'p') Imprime_Lista(l); if (opc == 's') { //l = (LE *) Vacia_Lista(l); exit(0); } } }