Estructuras de Datos y Algoritmos (EDA)

Un curso sobre Tipos Abstractos de Datos

Archive for the ‘cosas de clase’ Category

Vídeos sobre algoritmos de ordenación

without comments

Written by Javier Campos

November 29th, 2016 at 2:29 am

Sobre la implementación de montículos

without comments

La implementación habitual (vista en clase, transparencia 16) de un montículo es estática, es decir, basada en almacenar el árbol en un vector, por niveles, desde la raíz hacia abajo y de izquierda a derecha para cada nivel.

Lógicamente, esa implementación plantea el típico problema (en representaciones estáticas) de saturación cuando la capacidad del vector se completa.

Hay una solución para ese problema. Se basa en tener un vector de punteros a vectores de datos en el que inicialmente sólo se usa el primer puntero a vector, y apunta a un montículo almacenado como el visto en clase (en el vector, por niveles de arriba a abajo y de izquierda a derecha). Cuando ese primer vector de datos se llena, se usa el siguiente puntero a vector para apuntar a un nuevo vector en el que se guardará el siguiente nivel del montículo. Si ese nivel también se llena, se genera espacio para un nuevo nivel (puntero a un nuevo vector), etcétera.

Está explicado en esta página.

dynamic_heap

Written by Javier Campos

November 28th, 2016 at 11:39 am

Posted in cosas de clase

Enrutamiento de direcciones IP

without comments

patriciaUna de las formas de almacenar la información sobre las direcciones IP en los nodos que hacen función de enrutamiento en internet es la estructura de datos Patricia.

Consultando el Patricia en un nodo de enrutamiento, es posible rechazar un dominio como no válido (si no está almacenado en el Patricia) o como válido, y en este caso, bien aceptarlo (si ya se ha alcanzado el dominio buscado) o redirigir la petición HTTP al siguiente nodo.

Éste es el artículo en el que se propuso por vez primera (en 1991) el Patricia para este uso.

En esta página podéis encontrar un simulador y algunas explicaciones.

En este artículo, una comparativa del uso de Patricia frente al uso de tablas hash (las veremos más adelante).

Y en estas transparencias (desde la nº 142 a la nº 150), algunas ideas sobre la implementación de un Patricia.

Written by Javier Campos

November 22nd, 2016 at 12:17 am

Para pasar un rato durante las fiestas del Pilar…

without comments

binky

Haz clic en la imagen de arriba para que empiece…

Directamente desde la Universidad de Stanford. Recomendable además leer el documento sobre “punteros y memoria” de la misma Universidad.

Written by Javier Campos

October 4th, 2016 at 10:00 am

Entender la recursividad, en pocas palabras

without comments

Written by Javier Campos

November 5th, 2015 at 10:54 am

Posted in cosas de clase

Corrección de un detalle de C++ en alguna transparencia

without comments

Atención: se ha corregido un detalle de codificación C++ en las transparencias del apéndice de la lección 8 (implementación de la operación vacía) y en la lección 9 (implementación de la operación vacía de pilas y colas). Se ha añadido además la implementación de alguna operación más (anyadirPrimero en el apéndice de la lección 8 y apilar en la lección 9), para ilustrar la creación de nuevos datos dinámicos.

Written by Javier Campos

October 8th, 2015 at 12:08 pm

Para pasar el rato durante las fiestas del Pilar…

without comments

binky

Haz clic en la imagen de arriba para que empiece…

Directamente desde la Universidad de Stanford. Recomendable además leer el documento sobre “punteros y memoria” de la misma Universidad.

Written by Javier Campos

October 6th, 2015 at 10:22 am

Ejemplos de uso del TAD pila

without comments

Tenéis un par de ejemplos no triviales de utilización del TAD pila en este enlace.

Written by Javier Campos

October 5th, 2015 at 10:03 am

Cronograma de los lenguajes de programación de alto nivel (1954-2015)

without comments

Puede verse y descargarse en esta página web.

Written by Javier Campos

September 29th, 2015 at 11:15 am

Tipos enumerados en C++

without comments

Podéis leer cómo se definen tipos enumerados en C++ en esta página.

Written by Javier Campos

September 29th, 2015 at 10:36 am