representación y manipulación de estructuras lineales ... · de estructuras lineales dinámicas;...

Representación y manipulación de estructuras lineales dinámicas;

tablas de dispersión

Reservación dinámica de arreglos

✓ Iniciamos con un arreglo de un tamaño moderado C

✓ Llenamos desde la primera celda disponible

✓ Cuando más de S % de las celdas han sido ocupadas, se duplica el tamaño

✓ Si la tasa de ocupación baja debajo de I %, se elimina la mitad de las celdas

✓ En realidad uno reserva un arreglo nuevo de otro tamaño y copía los contenidos

...

...

...

O(1)}O(S · n)

O(I · n)

Listas (dinámicas por diseño)

Creamos el primer elemento

Enlazamos otro elemento enfrente

También podemos enlazar atrás

También podemos eliminar

Implementación de listas

! A base de punteros

! Hay que mantener un puntero al primer elemento

! Cada elemento contiene, en adición a su dato, un puntero a su seguidor

! Al añadir un elemento, se modifica el puntero del elemento después del cual se está insertando para que apunte al elemento nuevo

! Si hay elementos después del elemento insertado, primero hay que ajustar su puntero a enlazarse con su seguidor

Pseudocógicos

<estructura> elemento { elemento* siguiente = NULL; int dato;}

void main() { elemento* primero = NULL; primero = inserta(3, primero); primero = inserta(7, primero); primero = elimina(3, primero); return;}

Pseudocógicos

elemento* inserta(int valor, elemento* inicio) { pos = inicio; while (pos.siguiente != NULL) { // busca el final pos = pos.siguiente; // avanza elemento por elemento } a = new elemento; pos.siguiente = a; // ponlo al final a.dato = valor; // asigna el valor return (inicio != NULL ? inicio : a);} elemento* elimina(int valor, elemento* inicio) {

if (inicio.dato == valor) { pos = inicio.siguiente; delete inicio; // estuvo en el primer elemento return pos; } pos = inicio; while (TRUE) { if (pos.siguiente == NULL) { return inicio; // no estuvo el valor } else if (pos.siguiente.dato == valor) { a = pos.siguiente.siguiente; delete pos.siguiente; pos.siguiente = a; break; } pos = pos.siguiente; } return inicio;}

?

Otras opciones en enlazado

! En ambas direcciones (enlazado doble)! Conviene mantener un puntero al último elemento

también

! Involucra más mantenimiento de punteros, pero ofrece accesos más rápidos al procesar la lista

! Ramificando para obtener estructuras no lineales

! Estos incluyen árboles, grafos y montículos

Añadir un elemento entre elementos existentes

… …Puntero al seguidor

Cuando añadimos al final, actualizamos un solo puntero

Eliminar un elemento entre elementos existentes

… …

Si eliminamos el primer elemento, simplemente actualizamos el puntero desde

nuestro programa al inicio de la lista

Colas

= listas donde siempre se añade al final y elimina del inicio

Muy importantes en simulación de sistemas, optimización, telecomunicaciones, etcétera.

Pilas

= listas donde siempre se añade al inicio y elimina del inicio

(inicio = arriba)

Igual de importantes en simulación de sistemas, optimización, electrónica, etcétera.

Tablas de dispersión

! Llenado de arreglos dinámicos en otro orden, en combinación con listas enlazadas

! El arreglo contiene punteros a los elementos

! Los datos se puede ubicar en la memoria en lugares bien separados, que facilita la reservación de memoria

! Se requiere la definición de una función de dispersión (inglés: hash function)

! La función de dispersión calcula el índice en el cual el elemento se ubicará a base de su dato

! Si hay más que un elemento asignado al mismo índice, se forma (o extiende si ya está) una lista enlazada en ello

Tablas de dispersión

La calidad de la función determina cómo crecen las listas y qué tan

uniformemente se llena el arreglo

(Inglés: hash tables) Tablas de dispersión

Una opción que evita vacíos en el arreglo es “corrida” de índices - si el índice que da la función

está ocupado, el elemento corre al siguiente disponible.