PDF de programación - Tema 1 - Introducción a los TADs - Estructuras de datos

TEMA 1
Introducción a los
TADs

ESTRUCTURAS DE DATOS

1

Objetivos
 Preliminares, eficiencia y corrección

◦ Análisis de complejidad algorítmica en notación O()

 Abstracción de datos

 Presentar los Tipos Abstractos de Datos (TAD’s)

 Presentar la especificación algebraica de TAD’s



2

Contenidos
 1.1 Preliminares

◦ Normas de estilo
◦ Conceptos aprendidos
◦ Paradigmas y lenguajes de programación
◦ Eficiencia y corrección

 1.2 Abstracción de datos y TAD’s

◦ Diseño basado en abstracciones: abstracción procedimental y de datos
◦ Definición de TAD’s y realización de TAD’s en Pascal
◦ Especificación algebraica de TAD’s



3

1.1 Preliminares
 ¿Qué debemos saber?

◦ El lenguaje Pascal
◦ Entorno EclipseGavab

◦ https://github.com/codeurjc/eclipse-gavab

◦ https://bintray.com/sidelab-urjc/EclipseGavab

◦ Soltura con la sintaxis e instrucciones de control

◦ Especialmente Arrays, Registros y Punteros

 Ciclo de Vida del Software

◦ Análisis: Qué se hace
◦ Diseño: Cómo se hace
◦ Codificación: Se hace
◦ Pruebas: Se prueba y se corrige
◦ (Mantenimiento: Se corrige y amplía)

4

1.1 Preliminares
 Conceptos aprendidos

Problema

Algoritmo

Fase de resolución

Atajo tentador

Programa

Fase de implementación

5

1.1 Preliminares: normas de estilo
 Eliminar varias instrucciones en una misma línea

 Tabular adecuadamente el anidamiento que generen algunas
sentencias:
◦ Evitar:


IF precio>MAXIMO THEN writeln(‘Precio abusivo’);


 Salvo contadores, identificadores mnemotécnicos que describan
cometido o lo que representan (subprogramas y variables).

 Palabras reservadas en mayúsculas

◦ WHILE, FOR, RECORD,...

6

1.1 Preliminares: normas de estilo
Identificadores: descriptivos y minúsculas

◦ Identificadores con varias palabras, unidas por '_', o con el primer

carácter de la palabra sufija en mayúscula, o ambos
◦ Ej.: nombre_archivo, nombreArchivo, nombre_Archivo, …

◦ Constantes en mayúsculas
◦ Ej.: IVA, PI, NUMERO_E, ...

◦ Procedimientos: Empezando por letra mayúscula.
◦ Ej.: BusquedaBinaria, Apilar, PilaVacia, ...

◦ Tipos: Empezando por “Tipo” o “T”

◦ Ej.: TipoPila, TPila, ...

7

1.1 Preliminares: normas de estilo
 Módulos y Ficheros:

◦ Nombres de programas y módulos (unidades) deben coincidir con los

nombres de los ficheros que los contienen.

◦ Empezando por mayúsculas y resto minúsculas
◦ Escribir una cabecera de identificación como la que se muestra a

continuación:

{*********************************************************************

* *

* Módulo: Nombre *

* Fichero: ( ) Programa ( ) Espec. TAD ( ) Impl. TAD ( ) Otros *

* Autor(es): Nombre(s) *

* Fecha: Fecha de actualización *

* *

* Descripción: *

* Breve descripción del módulo (párrafo corto) *

* *

*********************************************************************}

8

1.1 Preliminares: normas de estilo
 Uso extendido de subprogramas para tareas bien
identificadas

 Adecuado uso de sentencias de repetición (especialmente
bucles FOR y WHILE)
◦ Esquema de búsqueda vs recorrido

 Evitar variables globales en subprogramas

 Uso adecuado de funciones

◦ Devuelven un único valor



9

1.1 Preliminares: conceptos aprendidos
 Arrays en Pascal:

◦ Un tipo de dato array se define en la sección de declaración de tipos

TYPE

TYPE

TipoCoordenada = ARRAY [1..3] OF real;

TipoVector = ARRAY [1..3] OF real;

TipoMatriz = ARRAY [1..3, 1..7] OF char;

TipoViviendas = ARRAY [1..3, 1..3, ’A’..’E’]OF boolean;



VAR

origen: TipoCoordenada;

desplazamiento: TipoCoordenada TipoVector;



10

1.1 Preliminares: conceptos aprendidos
 Arrays en Pascal (cont.):

◦ Los arrays son estructuras de acceso directo, ya que permiten

almacenar y recuperar directamente los datos, especificando su
posición dentro de la estructura.

◦ Los arrays son estructuras de datos homogéneas: sus elementos son

todos del mismo tipo.

◦ El tamaño de un array se establece de forma fija, en un programa,

cuando se define una variable de este tipo.

◦ Cuidado con paso de arrays como parámetros de tipo anónimo a

subprogramas.


11

1.1 Preliminares: conceptos aprendidos
 Registros en Pascal:

◦ Tipo de datos estructurado que permite almacenar datos

heterogéneos (de distintos tipos)

TYPE

TNombreReg = RECORD

idCampo1 : idTipo1;

idCampo2 : idTipo2;

...

idCampon : idTipon

END; {Fin de TNombreReg}

12

1.1 Preliminares: conceptos aprendidos
Registros en Pascal (cont.):

◦ Las funciones no pueden devolver un registro.
◦ Para acceder a un campo se usa el operador punto (.):



NombreVariableRegistro.NombreCampo

◦ También se puede acceder a los campos de un registro “abriendo” el

registro con la sentencia WITH
◦ Absolutamente no recomendado

13

1.1 Preliminares: conceptos aprendidos
 Punteros en Pascal:

◦ La gestión de memoria dinámica se realiza a través de los

denominados punteros a memoria

◦ Una variable puntero sirve para indicar cuál es la posición de

memoria (potencialmente de otra variable)

◦ Posee mecanismos para reservar y liberar posiciones de memoria en

tiempo de ejecución
◦ Generando variables dinámicas

◦ A través del puntero se puede acceder al valor del dato que apunta



14

1.1 Preliminares: conceptos aprendidos
 Punteros en Pascal:

pEnt

PROGRAM prueba1;

TYPE

tPEntero = ^integer;

VAR

pEnt: tPEntero;

ent: integer;

BEGIN

ent := 5;

writeln(ent);

pEnt := @ent;

pEnt^ := 4;

writeln(ent);

END.

?

pEnt

?

pEnt

pEnt

ent

?

ent

5

ent

5

ent

4

15

1.1 Preliminares: conceptos aprendidos
 Punteros en Pascal:

pEnt

PROGRAM prueba1;

TYPE

tPEntero = ^integer;

VAR

pEnt: tPEntero;

ent: integer;

BEGIN

pEnt := @ent;

ent := 5;

writeln(ent);

pEnt^ := 4;

writeln(ent);

END.

?

pEnt

pEnt

pEnt

ent

?

ent

?

ent

5

ent

4

16

1.1 Preliminares: conceptos aprendidos
 Punteros en Pascal:

pEnt

PROGRAM prueba1;

TYPE

tPEntero = ^integer;

VAR

pEnt: tPEntero;

ent: integer;

BEGIN

ent := 5;

writeln(ent);

pEnt^ := 4;

pEnt := @ent;

writeln(ent);

END.

?

pEnt

?

ent

?

ent

5

Se produce un error! pEnt

apunta a una posición

indefinida de memoria y no
reservada, por lo tanto, a
través de él no se puede

modificar el valor

17

1.1 Preliminares: conceptos aprendidos
 Punteros en Pascal:

◦ Para utilizar una variable puntero no siempre hay que reservar

memoria con él
◦ Por ejemplo para recorrer una lista ya creada

◦ Solo en ocasiones donde generamos datos en tiempo de ejecución

utilizamos el procedimiento new

◦ Si no necesitamos un área de memoria reservada anteriormente la

debemos liberar con el método dispose

◦ Para apuntar a “nada” utilizamos la constante NIL

18

1.1 Preliminares: conceptos aprendidos
 Punteros en Pascal:

TYPE

tLista = ^tNodoLista;

tNodoLista = RECORD

informacion: Integer;

sig: tLista {Estructura Recursiva}

END;



VAR

lista: tLista;

19

1.1 Preliminares: Evolución de los LPs
 Los motores que impulsan el desarrollo de los lenguajes de
programación son:
◦ Abstracción
◦ Modularidad
◦ Encapsulación
◦ Jerarquía



20

1.1 Preliminares: Evolución de los LPs
 Abstracción: Proceso mental por el que el ser humano
extrae las características esenciales de algo, e ignora los
detalles superfluos.

 Modularización: Proceso de descomposición de un sistema
en un conjunto de elementos poco acoplados
(independientes) y cohesivos

 Encapsulación: Proceso por el que se ocultan los detalles
de las características de una abstracción

 Jerarquía: Proceso de estructuración por el que se
organizan un conjunto de elementos en diferentes niveles
atendiendo a unos criterios determinados



21

1.1 Preliminares: Evolución de los LPs
 Código máquina

 Lenguaje Ensamblador

 Lenguaje de alto nivel

◦ Programación Estructurada
◦ Programación Modular
◦ Programación con TAD’s (Tipos Abstractos de Datos)
◦ Programación Orientada a Objetos



22

1.1 Preliminares: Evolución de los LPs

23

1.1 Preliminares: Evolución de los LPs

http://www.digibarn.com/collections/posters/tongues/ComputerLanguagesChart.png

24

1.1 Preliminares: Evolución de los LPs

25

1.1 Preliminares: Paradigmas de programación
 Un paradigma de programación se define como una
colección de patrones conceptuales que moldean la forma
de razonar sobre problemas, de formular algoritmos y de
estructurar programas

 Paradigmas:

◦ Programación imperativa
◦ Programación funcional
◦ Programación lógica
◦ Programación orientada a objetos



26

1.1 Preliminares: Programación imperativa
 Basada en comandos que actualizan variables que están en
almacenamiento

 Permite cierto nivel de abstracción: variables, expresiones,
instrucciones

 Para programar:

◦ Declarar las variables necesarias
◦ Diseñar una secuencia (algoritmo) adecuada de instrucciones

(asignaciones)



27

1.1 Preliminares: Programación funcional
 Tiene su base en el concepto de función matemática:

f: dominio --> rango

 Para programar:

◦ Se construyen funciones sencillas
◦ Se construyen funciones más complejas a partir de las sencillas
◦ Se evalúan las funciones sobre los datos de entrada



28

1.1 Preliminares: Programación lógica
