PDF de programación - Tablas de Símbolos - Programación de Sistemas de Telecomunicación - Informática II

Tablas de Símbolos

Programación de Sistemas de Telecomunicación

Informática II

Departamento de Sistemas Telemáticos y Computación

(GSyC)

Universidad Rey Juan Carlos

Noviembre 2017

GSyC - 2017

Tablas de Símbolos

1

c2017 Grupo de Sistemas y Comunicaciones.
Algunos derechos reservados.
Este trabajo se distribuye bajo la licencia
Creative Commons Attribution Share-Alike
disponible en http://creativecommons.org/licenses/by-sa/2.1/es

GSyC - 2017

Tablas de Símbolos

2

Contenidos

1 Tablas de Símbolos

2

3

Implementación de TS mediante un array no ordenado

Implementación de TS mediante una lista enlazada no ordenada

4 Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

5

6

7

8

Iteración sobre todos los elementos de una colección

Implementación de TS mediante un Array ordenado

Implementación de TS mediante una lista enlazada ordenada

Implementación de TS mediante un árbol de búsqueda binaria (ABB)

9 Ejemplo de ejecución: Get en un ABB

10 Ejemplo de ejecución: Put en un ABB vacío

11 Ejemplo de ejecución: Put en un ABB

12 Borrado de un nodo en un ABB

GSyC - 2017

Tablas de Símbolos

3

Tablas de Símbolos

Contenidos

1 Tablas de Símbolos

2

3

Implementación de TS mediante un array no ordenado

Implementación de TS mediante una lista enlazada no ordenada

4 Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

5

6

7

8

Iteración sobre todos los elementos de una colección

Implementación de TS mediante un Array ordenado

Implementación de TS mediante una lista enlazada ordenada

Implementación de TS mediante un árbol de búsqueda binaria (ABB)

9 Ejemplo de ejecución: Get en un ABB

10 Ejemplo de ejecución: Put en un ABB vacío

11 Ejemplo de ejecución: Put en un ABB

12 Borrado de un nodo en un ABB

GSyC - 2017

Tablas de Símbolos

4

Tablas de símbolos

Tablas de Símbolos

La tabla de símbolos es una estructura de datos también
conocida por los siguientes nombres: mapa, array asociativo.

La tabla de símbolos es una estructura de datos que almacena
elementos compuestos por parejas (Clave, Valor)
Clave y Valor pueden ser tipos de datos cualesquiera
Tiene tres operaciones básicas:

Put: Dado un nuevo elemento (Clave, Valor) como
parámetro, se añade éste a la tabla. Si ya existía un elemento
con la misma Clave, se substituye su Valor asociado por el
especificado en la llamada a Put
Get: Dada una Clave como parámetro, devuelve el Valor
asociado a la misma en la tabla en caso de que exista un
elemento (Clave, Valor)
Delete: Dada un Clave como parámetro, se borra de la tabla,
si existe, el elemento (Clave, Valor)

GSyC - 2017

Tablas de Símbolos

5

Usos de las tablas de símbolos (I)

Tablas de Símbolos

Lista de usuarios en Mini-Chat:
(Clave => EP, Valor => Nickname)
Lista de últimos mensajes vistos en Peer-Chat:
(Clave => EP, Valor => Número de secuencia)
Listado de teléfonos:
(Clave => Nombre, Valor => No de teléfono)
Diccionario:
(Clave => Palabra, Valor => Definición)
DNS:
(Clave => Nombre de máquina, Valor => Dirección IP)

GSyC - 2017

Tablas de Símbolos

6

Usos de las tablas de símbolos (II)

Tablas de Símbolos

DNS inverso:
(Clave => Dirección IP, Valor => Nombre de máquina)
Valoración burslátil:
(Clave => Valor bursátil, Valor => Cotización)
Intercambio de ficheros P2P:
(Clave => Fichero, Valor => Máquina)
Índice inverso de un libro:
(Clave => Vocablo, Value => Lista de números de página)
Catálogo de buscador Web:
(Clave => Palabra, Value => Sitios web )

GSyC - 2017

Tablas de Símbolos

7

Especificación de la tabla de símbolos

Tablas de Símbolos

with Ada.Strings.Unbounded;
package Maps is

type Map is limited private;

procedure Get (M

: Map;
: in
ASU.Unbounded_String;
: out ASU.Unbounded_String;

Key
Value
Success : out Boolean);

procedure Put (M

: in out Map;
: ASU.Unbounded_String;

Key
Value : ASU.Unbounded_String);

procedure Delete (M

: in out Map;
: in

Key
Success : out Boolean);

Asu.Unbounded_String;

function Map_Length (M : Map) return Natural;

--
-- Cursor Interface for iterating over Map elements
--

...
private

...

end Maps;

GSyC - 2017

Tablas de Símbolos

8

Implementaciones de tablas de símbolos

Tablas de Símbolos

Mediante un Array no ordenado

Mediante una Lista enlazada no ordenada

Mediante un Array ordenado con búsqueda binaria

Mediante una Lista enlazada ordenada
Mediante un Árbol de búsqueda binaria (ABB)

GSyC - 2017

Tablas de Símbolos

9

Implementación de TS mediante un array no ordenado

Contenidos

1 Tablas de Símbolos

2

3

Implementación de TS mediante un array no ordenado

Implementación de TS mediante una lista enlazada no ordenada

4 Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

5

6

7

8

Iteración sobre todos los elementos de una colección

Implementación de TS mediante un Array ordenado

Implementación de TS mediante una lista enlazada ordenada

Implementación de TS mediante un árbol de búsqueda binaria (ABB)

9 Ejemplo de ejecución: Get en un ABB

10 Ejemplo de ejecución: Put en un ABB vacío

11 Ejemplo de ejecución: Put en un ABB

12 Borrado de un nodo en un ABB

GSyC - 2017

Tablas de Símbolos

10

Implementación de TS mediante un array no ordenado

Implementación de TS mediante un array no ordenado

Put, Get y Delete requieren una búsqueda lineal en el Array:
en el peor caso hay que recorrer todos los elementos

El Array tiene un tamaño máximo fijado de antemano

GSyC - 2017

Tablas de Símbolos

11

Implementación de TS mediante una lista enlazada no ordenada

Contenidos

1 Tablas de Símbolos

2

3

Implementación de TS mediante un array no ordenado

Implementación de TS mediante una lista enlazada no ordenada

4 Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

5

6

7

8

Iteración sobre todos los elementos de una colección

Implementación de TS mediante un Array ordenado

Implementación de TS mediante una lista enlazada ordenada

Implementación de TS mediante un árbol de búsqueda binaria (ABB)

9 Ejemplo de ejecución: Get en un ABB

10 Ejemplo de ejecución: Put en un ABB vacío

11 Ejemplo de ejecución: Put en un ABB

12 Borrado de un nodo en un ABB

GSyC - 2017

Tablas de Símbolos

12

Implementación de TS mediante una lista enlazada no ordenada

Tipos de datos

package Maps is

package ASU renames Ada.Strings.Unbounded;

type Map is limited private;

procedure Get (M

: Map;
: in
ASU.Unbounded_String;
: out ASU.Unbounded_String;

Key
Value
Success : out Boolean);

private

type Cell;
type Cell_A is access Cell;
type Cell is record

: ASU.Unbounded_String := ASU.Null_Unbounded_String;
Key
Value : ASU.Unbounded_String := ASU.Null_Unbounded_String;
Next : Cell_A;

end record;
type Map is record

P_First : Cell_A;
Length : Natural := 0;

end record;

end Maps;

GSyC - 2017

Tablas de Símbolos

13

Implementación de TS mediante una lista enlazada no ordenada

Comparación con la implementación mediante un Array no
ordenado

La lista enlazada puede crecer / contraerse
La búsqueda de un elemento (Get) no mejora respecto a la
implementación con un Array no ordenado: hay que buscar
linealmente la Clave
La inserción de un elemento (Put) tampoco mejora, pues
requiere buscar la Clave, ya que si existe hay que substituir el
valor almacenado por el nuevo
El borrado de un elemento (Delete) tampoco mejora, pues,
de nuevo, hay que buscar la Clave

GSyC - 2017

Tablas de Símbolos

14

Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

Contenidos

1 Tablas de Símbolos

2

3

Implementación de TS mediante un array no ordenado

Implementación de TS mediante una lista enlazada no ordenada

4 Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

5

6

7

8

Iteración sobre todos los elementos de una colección

Implementación de TS mediante un Array ordenado

Implementación de TS mediante una lista enlazada ordenada

Implementación de TS mediante un árbol de búsqueda binaria (ABB)

9 Ejemplo de ejecución: Get en un ABB

10 Ejemplo de ejecución: Put en un ABB vacío

11 Ejemplo de ejecución: Put en un ABB

12 Borrado de un nodo en un ABB

GSyC - 2017

Tablas de Símbolos

15

Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

GSyC - 2017

Tablas de Símbolos

16

Maps.Put (A_Map, ASU.To_Unbounded_String("facebook.com"), ASU.To_Unbounded_String("69.63.189.16")); 1 Maps.Get (A_Map, ASU.To_Unbounded_String(“www.urjc.es"), Value, Success); 2 Maps.Put (A_Map, ASU.To_Unbounded_String(“google.com"), ASU.To_Unbounded_String(“66.249.92.104")); 3 Maps.Put (A_Map, ASU.To_Unbounded_String(“www.urjc.es"), ASU.To_Unbounded_String(“212.128.240.25")); 4 Maps.Put (A_Map, ASU.To_Unbounded_String(“facebook.com"), ASU.To_Unbounded_String(“69.63.189.11")); 5 Maps.Delete (A_Map, ASU.To_Unbounded_String(“google.com"),Success); 6 Maps.Delete (A_Map, ASU.To_Unbounded_String(“www.urjc.es"),Success); 7 Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

GSyC - 2017

Tablas de Símbolos

17

A_Map.P_First
 0 A_Map.Length Key
 Value Next
 Cell
 Maps.Put (A_Map, ASU.To_Unbounded_String("facebook.com"), ASU.To_Unbounded_String("69.63.189.16")); 1 Ejemplo de ejecución (TS mediante lista enlazada no ordenada)

GSyC - 2017

Tablas de Símbolos

18

M.P_First
 0 M.Length procedure Put (M : in out Map; Key : ASU.Unbounded_String; Value : ASU.Unbounded_String) is P_Aux : Cell_A; Success : Boolean; begin P_Aux := M.P_First; Success := False; while not Success and P_Aux /= null loop if P_Aux.Key = Key then P_Aux.Value := Value; Success := True; end if; P_Aux := P_Aux.Next; end loop; if not Success then M.P_First:=new Cell'(Key, Value, M.P_First); M.Length := M.Length + 1; end if; end Put; P_Aux
 Key
 Value Next
 Cell
 Maps.Put (A_Ma