Estructura de Datos I

Contenido
  Introducción
  Tipos de Datos Abstractos
  • Tipos de Datos
  • Tipos de Datos Abstractos
  Recursividad
  Análisisi de la Performance de Algoritmos
  TAD Lista
  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

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.
Listas Encadenadas
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:

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

En una lista doblemente encadenada, cada elemento posee las informaciones de quien es su sucesor y su antecesor.
  Listas Doblemente Encadenada
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): Listas Doblemente Encadenada
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.
  Descarga

Código:
 

Listas Circulares

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.
  Listas Circulares
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
Descarga
Código


Listas Circulares doblemente enlazada
Descarga
Código

Listas Secuenciales

En una lista secuencial, el sucesor de un elemento ocupa la posición física subsecuente de este elemento. Una de las formas más comunes de implementar una lista secuencial es utilizando ARRAY. En un array asociamos a cada elemento un índice (lo denominamos elemento a(i)). De esta forma, estamos almacenando el elemento a(i) e a(i+1) en las posiciones consecutivas i e i+1
Listas Secuenciales
Las principales ventajas de utilizar un array son:
  1. Rápido acesso a los elementos.
  2. Facilidad en modificar información.
Los elementos del array pueden ser accesados en tiempo constante, por ejemplo en C el elemento que está en la posición i de un array a pode ser recuperado utilizando a[i]. Las principales desventajas son:
  1. Definición previa del tamaño de un array.
  2. Dificultad para insertar (y eliminar) un elemento entre dos otros ya existentes.
En la definición de un array necesitamos especificar el número máximo de elementos que serán almacenados.

Suponga que querramos inserir un nuevo elemento x en una posición i ya ocupada de un vector
Para realizar esta tarea tendremos que mover los elementos a(i+1), a(i+2)...a(k)  para las posiciones i+1, i+2, i+3...,i+k+1 respectivamente. Note que en el peor de los casos (insertar en la primera posición) esta operación lleva un tiempo de O(n).

Listas Secuenciales

Tabla Hash en c++

"Hashing" es una técnica que busca realizar las operaciones de inserción, eliminación y búsqueda en tiempo constante. Esa característica es muy importante cuando se traba con almacenamiento secundario en disco, donde el acceso a una determinada dirección es bastante lenta. Algunas aplicaciones que son beneficiadas por el uso de tablas hash son diccionarios y tablas de palabras reservadas de un compilador.
En vez de organizar la tabla según el valor relativo de cada llave en relación a las demás, la tabla hash toma encuenta solamente su valor absoluto, interpretado como un valor numérico.


tabla hash en c++

Si consiguiésemos asociar a cada elemento a ser almacenado un número como en el ejemplo anterior, podremos realizar las operaciones de inserción, eliminación y búsqueda en tiempo constante.
La función que asocia a cada elemento de un conjunto U un número que sirva de índice en una tabla (array) es llamada de función hash.
Una función hash debe satisfacer las siguientes condiciones:
  1.  Ser simple de calcular
  2. Asegurar que elementos distintos posean índices distintos.
  3. Generar una distribución equilibrada para los elementos dentro del array.
Funciones Hash

Crear una función hash satisfaciendo las condiciones anteriores no siempre es una tarea fácil. Existen mucho modelos de creación para funciones hash. A continuación se presentan apenas dos formas de creación de funciones hash. en "Cormen,T.H. Leiserson C.E., Rivest R.L. Introduction to Algorithms" pueden ser encontraod varios ejemplos afines hash.

Una buena función hash es aquella en que toda entrada (slot) del array posee la misma probabilida de ser alcanzado por la función.

Método da División
El método de la división consiste en los siguiente: suponga que los elementos x que deben ser almacenados sean números enteros, una función hash que puede ser utilizada para distribuir tales números en un array (tabla hash) es:
h(x)=x% (tamaño de la tabla)
Implementación
La siguiente función describe la implementación de la función hash descrita anteriormente para el caso de strings.

int Hash(char *a, int stringsize)
{
        int hashval, j;
        hashval = (int) a[0];
       for (j = 1; j < stringsize; j++)
       hashval += (int) a[j];
       return(hashval % tablesize); /* suponiendo que tablesize es global */
 }

Método del Doblado
En este método, las llaves son interpretadas como una secuencia de dígitos escritos en un pedazo de papel. Ello consiste en "doblar" ese papel, de manera que los dígitos se superpongan sin llevar en consideración el "se lleva uno" como se muestra en la siguiente figura.

metodo del boblado hash


El proceso es repetido hasta que los dígitos formen un número menor al del tamaño de la tabla hash.
Es importante resaltar que el metodo de doblar tambien puede ser usado con números binarios. En este caso, en vez de la suma, se debe realizar una operación de "OR exclusivo", pues operaciones de "AND" y de "OR" tienden a producir direcciones-base concentrados al final o al inicio de la tabla.



Colisiones

Por más que se intente encontrar una función hash eficiente, en aplicaciones prácticas es difícil conseguir evitar el problema de colisiones de llaves. Así, se vuelve necesario estudiar alternativas para este problema.
Existen varias formas de resolver el problema de colisiones, dentro de ellas destacamos:
Existen varias formas de resolver el problema de colisiones, dentro de ellas destacamos:
Encadenamiento Separado o Externo (Separate Chaining)
En el encadenamiento separado colocamos los elementos que poseen llaves iguales en una listas encadenada.

coliciones con listas

Utilizando esta estrategia, no es difícil percibir que en el peor de los casos el tiempo para insertar un nuevo elemento en la tabla es de O(1). La búsqueda por un elemento, toma el tiempo proporcional al tamaño de la lista almacenada en cada slot.

Encadenamiento Interno
Encadenamiento interno es un método para resolver problemas de colisiones mediante el empleo de listas encadenadas que comparten el mismo espacio de memoria al de la tabla de distribución.

El encadenamiento interno prevee la división de la tabla T en dos zonas, una de dirección-base, de tamaño p, y otra reservada para colisiones, de tamaño s. Naturalmente, p+s = m, donde m corresponde al tamaño de la tabla hash.


encadenamiento interno
Un problema de esta técnica es que ella puede provocar colisiones secundaria, eso quiere decir, que puede provocar colisiones provenientes de la coincidencia de direcciones para llaves que no son sinónimas. Este fue el caso ocurrido en al figura anterior cuando se intentó insertar el número 02. En la dirección base de este número ya se encontraba el número 14, el cual no es sinónimo de 02.
Otra dificultad de esta técnica se encuentra en la función de eliminación de un elemento. Es necesario tomar cuidado en este procedimiento para que la llamada de búsqueda y eliminación futuras no retornen falsos resultados. ¿Por qué? Cuando estudiamos la técnica de direccionamiento abierto, veremos una solución para este problema.

Implementación

A continuación se tiene la implementación de una estructura hash y las funciones de inserción, búsqueda y eliminación en la tabla.


Ver código

Árbol Patricia en c++

Practical Algorithm to Retrieval Information Coded in Alphanumeric.
Es un trie en el cual se han eliminado todas las ramas (terminales o no) que degeneran en listas.



la estructura del arbol esta dado por:

struct nodo_arbl
{
char dato;
int vistas;
ro *dir[32];
};

un nodo contiene con 32 punteros pa las diferentes letras mas un contador de visitas, y su dato..
el contadro de visitas se usa para cuando queramos imprir las palabras ..
para ver cuantas veces fue visitado ese nodo, si lo no lo visito mas de 1 ves es evidencia de que es un nodo padre ..
para el cual es ahi donde se aplica la recursividad de en orden ....

descargar:

Descarga

Listas simplemente encadenada

En una lista simplemente encadenada, cada elemento posee apenas información de quien es su sucesor.
Es necesario también almacenar la información del primer elemento de la lista.
Principales problemas:
_Imposibilidad de regresar al elemento anterior.
_Necesidad de guardar información del elemento anterior a fin de realizar algunas operaciones.


Implementación (Estática)


Para simplificar se considerará que los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada.
El esquema gráfico abajo muestra el proceso de inserción de un nuevo elemento en una lista encadenada estática. El nuevo elemento será insertado entre el elemento actual y el elemento anterior.

Listas simplemente encadenada estática
Especificación:
1. LE *Inicia_Lista(int N)         // Crea una nueva lista con N elementos
2. void Inserta_Elemento(LE *L, int A)    //Inserta un nuevo elemento A en la posicion correcta de la lista L
3. int Elimina_Elemento(LE *L, int A)      //Elimina el elemento A de la lista L. Si el elemento no existe o la lista está vacía, retorna -1.
4. void Imprime_Lista (LE *L)
5. LE *Vacia_Lista(LE *L)
Descarga

Código:



Implementación (Dinámica)

Por simplicidad los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada.
El esquema gráfico abajo muestra el proceso de inserción de un nuevo elemento en una lista encadenada dinámica. el nuevo elemento será insertado entre el elemento actual y el elemento anterior.




Las operaciones ilustradas pueden ser descritas como:
nuevo->prox = actual;
anterior->prox = nuevo;

Especificación:


  1. LE *Inicia_Lista()                                 //Crea una nueva lista
  2. void Inserta_Elemento(LE *L, int A)    //Inserta un nuevo elemento A en la posición correcta de la lista L
  3. int Elimina_Elemento(LE *L, int A)       //Elimina el elemento A de la lista L. Si el elemento no existe o la lista está vacía retorna -1.
  4. void Imprime_Lista (LE *L)
  5. LE *Vacia_Lista(LE *L)

Descarga

Código:

Bienbenidos

Este es un foro de programacion esta orientado a estudiantes de preparatoria en la universidad y publico en general interezado.

Ps aki os dejare alguno ejempliyos que son pedidos con frecuencia para tareas y trabajos...cualquier pedido solo haganmelo llegar..bueno el lenguaje q domina es el c++ y java..si quieren los programas igual me piden ..yo les dejo aki .....xfa comenten..