PDF de programación - Tema 3. Tipos de datos básicos - Estructuras de Datos y Algoritmos

Estructuras de Datos 

y Algoritmos

Tema 3. Tipos de datos básicos

Prof. Dr. P. Javier Herrera

Contenido

1.
2.
3.
4.
5.
6.

Pasos en la implementación de un TAD
Lenguaje abstracto de programación imperativa
Implementación de conjuntos finitos mediante vectores
Implementación de los conjuntos finitos con elementos en 1..N
Implementación de los multiconjuntos finitos con elementos en 1..N
Estructuras lineales enlazadas

Tema 3. Tipos de datos básicos

2

1. Pasos en la implementación de un TAD

•

•

Las implementaciones que vamos a realizar seguirán el paradigma de 
programación imperativo, por lo que para las implementaciones y 
algoritmos usaremos un lenguaje abstracto de programación imperativa.

Implementar un TAD consiste en:
– Representar sus valores por medio de valores de tipos de datos más 

concretos del lenguaje de programación (tipo representante).
• Esta representación se oculta al usuario del TAD.
• Existe mas de una representación posible.

– Simular sus operaciones por medio de funciones o procedimientos 

que actúan sobre dichos tipos más concretos.

Tema 3. Tipos de datos básicos

3

1. Pasos en la implementación de un TAD

•

Existen dos tipos de representaciones:
– Estáticas: el tamaño de la estructura no cambia durante la ejecución.

• Desaprovechamiento de la memoria.
• Desbordamiento.

– Dinámicas:

• Utilizan memoria dinámica.
• Proporcionan estructuras mas versátiles ↔  No tienen un tamaño 

fijo durante la ejecución.

• Su programación es más compleja.

• Una parte esencial de la programación de cualquier algoritmo es el 

estudio de su coste en tiempo y en memoria. En general, nos referiremos 
al coste en tiempo en el caso peor.

Tema 3. Tipos de datos básicos

4

2. Lenguaje abstracto de programación 
imperativa
•

Para la implementación de TADs usaremos un lenguaje abstracto de 
programación imperativa al estilo PASCAL. 

•

Instrucciones que usaremos :
– Nada:

nada

{ instrucción que no hace nada }

– Asignación: 

x := E
{x1, x2, …, xn} := {E1, E2, …, En}

{ la variable x tiene que ser del mismo tipo que E}
{ asignación múltiple }

– Secuencia:

P1 ; P2

Tema 3. Tipos de datos básicos

5

2. Lenguaje abstracto de programación 
imperativa

– Distinción de casos:

casos

B1  P1
B2  P2
...
Bn  Pn

fcasos

– Condicional:

si B entonces P1 fsi
si B entonces P1 si no P2 fsi

– Bucle:

mientras B hacer P fmientras

Tema 3. Tipos de datos básicos

6

2. Lenguaje abstracto de programación 
imperativa

– Bucle con contador:

para i = inicial hasta final paso p hacer P fpara

Cuando p = 1 omitimos la mención del paso en el bucle.

– Entrada: 

– Salida: 

– Error:

leer (c)

{ lee un carácter del dispositivo de entrada }

imprimir (mensaje)

{ imprime un mensaje (cadena de
caracteres) en el dispositivo de salida }

error (mensaje)

{ aborta la ejecución del programa e imprime

un mensaje de error }

– Comentarios: se escriben entre llaves en el lugar del programa que convenga.

Tema 3. Tipos de datos básicos

7

2. Lenguaje abstracto de programación 
imperativa
•

Tenemos los siguientes tipos y construcciones de tipos básicos:
– Tipo booleano bool con valores cierto, falso, y las operaciones booleanas 

habituales: ¬ , ∧, ∨. En algunas ocasiones se utiliza la versión de estas dos 
últimas operaciones con cortocircuito: ∧c ,∨c .

– Tipos numéricos nat (naturales), ent (enteros) y real (reales).
– Tipo de caracteres car.
– Tipos enumerados {valor1, …, valork}, con k ≥ 1.
– Rangos i..j donde i y j son números naturales.
– Vectores

• Declaración: V[i..j] de tipo
• Asignar todas las posiciones del vector: V[i..j] := [valor]

– Registros 

• Declaración: reg campo1 : tipo1, …, campon : tipon freg
• Acceso y modificación: R.campo1

Tema 3. Tipos de datos básicos

8

2. Lenguaje abstracto de programación 
imperativa

– Punteros

tipos

enlace = puntero a nodo
nodo = reg

valor : elemento
sig : enlace

freg

estructura = enlace

ftipos

• Definición: puntero a nombre-tipo
• Acceso: siendo p de tipo puntero, p↑.
• Reservar memoria: reservar (p)
• Liberar memoria: liberar (p)

Tema 3. Tipos de datos básicos

9

2. Lenguaje abstracto de programación 
imperativa

– Funciones: una función se declara con varios parámetros de entrada (o ninguno 
cuando la función es constante) y al menos un parámetro de salida, cada uno de 
ellos con su tipo correspondiente.

fun nombre-fun(e1 : tipo1, …, en : tipon) dev s : tipo'
var x1 : tipo"1, …, xk : tipo"k

P
ffun

Cuando las funciones tienen más de un parámetro de salida, estos se declaran de 

la forma: { s1 : tipo1, …, sm : tipom }, con m > 1

En el cuerpo P se pueden usar variables auxiliares locales declaradas tras la cabecera. 
En general, no hacemos explícitas las declaraciones de variables auxiliares de tipos 
básicos, tales como, por ejemplo, las variables usadas como contadores en bucles con 
contador. Pero hay que tener en cuenta que todas las variables que no son parámetros 
de entrada o salida son variables auxiliares locales, y nunca hay variables globales.

Tema 3. Tipos de datos básicos

10

2. Lenguaje abstracto de programación 
imperativa

– Procedimientos: pueden tener parámetros de entrada/salida, cuyo valor se puede 
modificar a lo largo de la ejecución, y parámetros de entrada que no cambian y que 
se declaran precediéndolos con el símbolo e.

proc nombre-proc(e e1 : tipo1, …, e en : tipon, es1 : tipo'1, …, esm : tipo‘m)
var x1 : tipo"1, …, xk : tipo“k

P
fproc

En algunas ocasiones usamos la notación de precondición y poscondición para dar 
información sobre la entrada y la salida de un algoritmo. 
o La precondición es una expresión booleana que expresa las condiciones sobre los 

parámetros de entrada de un algoritmo que garantizan que la aplicación del 
algoritmo tiene sentido, además de los tipos. 

o La poscondición es una expresión booleana que relaciona los parámetros de salida 

con los de entrada, indicando de esta forma qué cálculo o proceso realiza el 
algoritmo sobre los datos de entrada.

Tema 3. Tipos de datos básicos

11

3. Implementación de conjuntos finitos 
mediante vectores

tipos

conjunto = reg

contenido[1..N] de elemento
último : 0..N

freg

ftipos

• Nótese que un conjunto es vacío si y sólo si el índice último vale cero, y que se 

ignora la información que pueda haber en el vector entre las posiciones último + 1
y N.

Tema 3. Tipos de datos básicos

12

3. Implementación de conjuntos finitos 
mediante vectores
•

Implementación de las operaciones cjto-vacío, unit y es-cjto-vacío?:

 1O
fun cjto-vacío() dev x : conjunto { }

x. último := 0

ffun

 1O
fun unit(e : elemento) dev x : conjunto { }

x. último := 1
x.contenido[1] := e

ffun

fun es-cjto-vacío?(x : conjunto) dev b : bool { }

 1O

b := (x. último = 0)

ffun

Tema 3. Tipos de datos básicos

13

3. Implementación de conjuntos finitos 
mediante vectores
•

Implementación de la operación está?.

fun está?(e : elemento, x : conjunto) dev b : bool { }

último

b := falso
i := 1

mientras i ≤ x. último ∧ ￢b hacer


xO .



b := (x.contenido[i] = e)
i := i + 1

fmientras

ffun

•

El coste es lineal con respecto al tamaño de la parte ocupada del vector.

Tema 3. Tipos de datos básicos

14

Implementación (a): vector con posibles repeticiones

•

Implementación de la operación añadir en un vector con posibles repeticiones. 
Aquí basta con añadir el elemento en la primera posición libre del vector. 

 1O
proc añadir-a(e e : elemento, x : conjunto) { }

si x. último = N entonces error(Espacio insuficiente)
si no

x. último := x. último + 1 ;
x.contenido[x. último] := e

fsi
fproc

Tema 3. Tipos de datos básicos

15

Implementación (b): vector sin repeticiones

•

Implementación de la operación añadir en un vector sin repeticiones. En este caso se 
añade el elemento en la primera posición libre, pero sólo si el elemento no está ya en el 
vector. 


proc añadir-b(e e : elemento, x : conjunto) { }

último


xO .

si ￢está?(e, x) entonces

si x.último = N entonces error(Espacio insuficiente)
si no

x.último := x.último + 1 ;
x.contenido[x.último] := e

fsi

fsi
fproc

•

El coste es lineal debido a la búsqueda. 

Tema 3. Tipos de datos básicos

16

Implementación (c): vector ordenado sin repeticiones

•

•

Implementación de la operación añadir en un vector de elementos sin 
repeticiones y ordenados. Suponemos que el tipo de los elementos sobre 
el que se construyen los conjuntos admite una relación de orden total. 

En este caso, si no está el elemento, se añade en la posición adecuada, 
para lo cual utilizamos la función búsqueda-binaria y un procedimiento 
auxiliar desplazar-der que desplaza elementos hacia la derecha del vector. 

Tema 3. Tipos de datos básicos

17

Implementación (c): vector ordenado sin repeticiones


proc añadir-c(e e : elemento, x : conjunto) { }
{b, n} := búsqueda-binaria(x.contenido, e, 1, x.último)
si ￢b entonces

último


xO .

si x.último = N entonces error(Espacio insuficiente)
si no

desplazar-der(x.contenido, n, x.último)
x.contenido[n] := e
x.último := x.último + 1

fsi

fsi
fproc

•

El coste total es lineal con respecto a x.último (logarítmico por la búsqueda y lineal 
por el desplazamiento)

Tema 3. Tipos de datos básicos

18

Implementación (c): vector ordenado sin repeticiones

{ 1 ≤ c ≤ f +1 < N + 1 }
proc desplazar-der(V[1..N] de elemento, e c, f : nat ) { }

1 c

para i = f + 1 hasta c + 1 paso −1 hacer

V[i] := V[i − 1]

fpara

fproc


fO

{ 1 < c ≤ f +1 ≤ N +1 }
1 c
proc desplazar-izq(V[1..N] de elemento, e c, f : nat ) { }


fO

para i = c hasta f hacer

V[i − 1] := V[i]

fpara

fproc

Tema 3. Tipos de datos básicos

19

Implementación (a): vector con posibles repeticiones

•

Implementación de la operación quitar en un vector con posibles repeticiones. En este 
caso hay que recorrer el vector siempre hasta el final para asegurarse de quitar