Estructura de Datos

Datos abstractos. Estructura. Vector. Conjunto. Registro. Entero. Real. Carácter. Booleano. Array. Fichero. Subrango. Enumerados. Pila. Cola. Lista. Gestión dinámica de la memoria. Punteros. Multilista. Árboles binarios. Recorrido. Búsqueda

  • Enviado por: Antonio Vidal
  • Idioma: castellano
  • País: España España
  • 38 páginas

publicidad
cursos destacados
Apps de iPhone y Android con HTML5 para principiantes
Apps de iPhone y Android con HTML5 para principiantes
A todos se nos ocurren ideas de apps y luego, al poco tiempo vemos que otra persona las desarrolla. Que no te pase de...
Ver más información

Aprende jQuery sin sufrimiento
Aprende jQuery sin sufrimiento
En este curso aprenderás a utilizar jQuery desde su instalación hasta que puedas hacer una galería...
Ver más información


TEMA 1: Introducción a las estructuras y tipos de datos

  • .- Introducción

  • .- Abstracción de datos

  • .- Concepto de Tipo Abstracto de Datos (TAD)

  • 1.1.- Introducción

    La informática es la ciencia para el tratamiento automático de la información. Para llevar a cabo este proceso automático hay que tener en cuenta dos puntos:

  • cómo se va a representar la información en el ordenador.

  • cómo se va a manipular esta información según la representación escogida.

  • La única información que entiende un ordenador es una secuencia de 1's y 0's. Por tanto las estructuras de datos que utilicemos serán trasladadas a ristras de ceros y unos para implementarlas en el ordenador

    1001001101 estructura de datos

    ¿entero?

    ¿real?

    ¿caracter?

    y estas estructuras llevarán implícitas unas operaciones características de cada una de ellas con las que podrán agruparse o modificarse.

    TIPOS de DATOS

    Un tipo de Datos consta de dos partes:

  • una estructura con que implementarse en un ordenador.

  • unas operaciones implícitas a la estructura con la que manipularla.

  • Encontramos tres tipos de estructuras: Básicas, Predefinidas, y Definidas por el usuario.

    • Básicas (Entero, Real, Caracter, Booleano).

    • Predefinidas (Array, Registros, Conjuntos).

    • Definidos por el Usuario (Pila, Cola, Lista, Árbol, Grafos).

    Por tanto un tipo de datos consiste en una estructura dotada de operaciones.

    1.2.- Abstracción de datos

    La acción de abstracción de datos consiste en trasladar la información del mundo real de forma ajustada a datos manejables por el ordenador. Para ello debe seleccionarse solamente la información significativa para la abstracción y desechar el resto.

    El proceso de abstracción se compone de 4 etapas:

    • 1ªetapa: Abstracción. En esta etapa se analizan las propiedades del tipo real y se seleccionan datos significativos para su posterior implementación.

    • 2ªetapa: Representación. Se busca la mejor forma de implementar estas propiedades en el ordenador.

    • 3ªetapa: Manipulación. Consiste en establecer reglas para un correcto manejo del tipo de datos en el ordenador.

    • 4ªetapa: Axiomatización. Representación matemática formal.

    Ejemplos:

    Los números naturales

    Abstracción: Cardinalidad de un conjunto para representarlo.

    Representación => Manipulación

    I I I I I I I I I I + I I = I I I I I I

    Numeración romana

    VII, X, C LVI + XLIV = C

    Sistema de numeración árabe

    1327 = 1*103 + 3*102 + 2*10 + 7

    56 + 44 = 100

    Una buena estructuración de los datos se traduce en una estructura más simple de los algoritmos.

    Tipo de dato = Estructura + Operaciones de Manipulación

    En resumen, proceso de abstracción consiste en:

    • Abstracción: Definir y extraer las propiedades características de la información del mundo real.

    • Representación + Manipulación: Seleccionar el tipo idóneo para representar la información a manipular. Esta selección también debe realizarse a favor de simplificar la implementación de sus operaciones.

    • Axiomatización: Teoremas que permitan probar que el proceso global ha sido correcto.

    1.3.- Tipo Abstracto de Datos (TAD)

    Tenemos dos clases de TAD's:

    • Tipos predefinidos: definidos por el lenguaje.

    • Tipos definidos por el usuario: los define el programador.

    Unit PILAS

    • definir estructura de datos para implementar una PILA.

    • definir los algoritmos para la implementación de las operaciones de la PILA.

    De esta forma de consigue un encapsulamiento.

    Cuando definimos una UNIDAD en Pascal (MODULO en Modula-2) como la descrita, concentramos en ella la estructura de un tipo abstracto de datos y las operaciones de manipulación de esta en forma de procedimientos y funciones. Con ello tendremos localizado todo lo referente a una estructura de datos en la UNIT. A esto se le llama encapsulamiento y tiene la ventaja de que en caso de querer localizar una operación en concreto nos será más eficiente si todo está ordenado.

    TAD: Se puede pensar en un tipo abstracto de datos como en un modelo matemático con una serie de operaciones definidas sobre ese modelo. Los TAD son generalizaciones de un tipo de datos primitivo (enteros, reales, ...). Un TAD encapsula cierto tipo de datos en el sentido de que es posible localizar la definición del tipo y todas sus operaciones en una misma porción del programa. Esto facilita posibles modificaciones posteriores ya que el resto del código no dependerá de la implementación del TAD. Con esto se consigue tratar el TAD como un tipo de datos primitivo. Hay que tener en cuenta que ciertas operaciones pueden implicar más de un TAD y deberá hacerse referencia a estas operaciones en los dos TAD's.

    TIPO de DATOS: El tipo de datos de una variable es aquellos valores que ésta puede tomar. Los tipos de datos básicos son en Pascal, entero, real, booleano y caracter. Las reglas para construir tipos compuestos (predefinidas y definidas por el usuario) a partir de estos básicos varían en función del lenguaje de implementación. Para implementar un algoritmo en un lenguaje de programación determinado, debe de hallarse un mecanismo de representar los TAD en función de los tipos de datos y los operadores manejados por ese lenguaje.

    ESTRUCTURA de DATOS: Para representar el modelo matemático básico de un TAD se emplean estructuras de datos. Estas son conjuntos de variables, pueden ser de distintos tipos, conectadas entre sí de diversas formas.

    Ejemplo de TAD

    • Supongamos el TAD números naturales,

    • operaciones constructoras:

    operación cero: ! natural

    operación sucesor: natural ! natural

    operación suma: natural x natural ! natural [producto cartesiano]

    • propiedades: " m, n " N

    suma (0, n) = n

    suma (succ (n), m) = succ (suma (n, m))

    3 + 2 =

    suma (succ (succ (succ (0))), succ (succ (0))) =

    = succ (suma (succ (succ (0)), succ (succ (0)))) =

    = succ (succ (suma (succ (0),succ (succ (0))))) =

    = succ (succ (succ (suma (0, succ (succ (0)))))) =

    = succ (succ (succ (succ (succ (0))))) = 5

    • Tipo Abstracto de Datos PILA,

    Operaciones Apilar, Desapilar, PilaVacía, CrearPila, Tope.

    TEMA 2: Tipos y Estructuras Básicas

  • .- Introducción.

  • .- Tipos escalares

  • 1.- Tipos normalizados

  • 2.- Tipos definidos por el usuario

  • - Tipos estructurados

  • 1.- Tipo VECTOR

  • 2.- Tipo CONJUNTO

  • 3.- Tipo REGISTRO

  • 2.1.- Introducción

    Distinguimos los tipos de datos en escalares, estructurados, y punteros. De estos 3 sólo profundizaremos en los dos primeros, los punteros los dejamos para más adelante.

    Normalizados (Entero, Real, Caracter, Booleano)

    ESCALARES Subrango

    (=, <, >, ", ", ") Definidos por el usuario

    Enumerados

    Array (Tabla)

    Conjunto

    ESTRUCTURADOS

    Registro

    Fichero

    CARDINAL: El cardinal de un tipo (o tipo de datos) es el número de valores posibles en ese tipo.

    2.2.- Tipos Escalares

    Un tipo de datos es ESCALAR si existe una relación de orden entre todos los elementos de ese tipo. En los tipos escalares se pueden utilizar los operadores relacionales (=, <, >, ", ", "). Todos los tipos de datos escalares, excepto el tipo Real, son ordinales. Esto es, que a cada elemento de estos tipos se le puede asociar un precedente, un sucesor, y un ordinal (la posición que ocupa entre los valores de su tipo).

    2.2.1.- Tipos normalizados

    • Tipo entero

  • Conjunto de valores asociados pertenecientes al subconjunto de los enteros infinitos (ya que en un ordenador su representación no es infinita). El rango de representación variará dependiendo del ordenador y/o el lenguaje de programación.

  • {(- maxentero + 1), maxentero}

  • El tipo entero es escalar y ordinal.

  • Los operadores utilizados con el tipo entero se clasifican en 3 grupos:

    • Aritméticos: +, -, *, DIV, MOD

    • Relacionales: <, ", =, ", ", >

    • Ordinales: pred, succ, ord

  • Implementación en el ordenador. Normalmente con n bits de los cuales uno es para el signo. Max_entero = 2n-1 -1. En TurboPascal se usan 5 representaciones: byte, shortint, integer, longint y word.

    • Tipo real

  • Conjunto de valores asociados pertenecientes al subconjunto de R. Al igual que los enteros su rango se ve limitado por el lenguaje y el ordenador usados, además en los números reales también se ve afectado por la precisión en la representación. La precisión hace referencia al menor nº real distinguible de cero.

  • {[- maxreal .. - minreal] , [minreal .. maxreal]}

  • Es un tipo escalar y el único de su clase no ordinal (el resto de escalares lo son).

  • En el tipo reales sólo encontramos operadores del tipo aritméticos y relacionales:

    • Aritméticos: +, -, *, /, sqrt, sqr, ln, sen, cos, tg, ...

    • Relacionales: <, ", =, ", ", >

  • Implementación. Los reales suelen representarse en forma mantisa/exponente. En TurboPascal hay 5 representaciones posibles: Real, simple, double, extended y comp.

  • Relaciones entre entero y real

    • Conversión de entero a real: Operar un entero con un real da como resultado un real. El conjunto de los enteros es subconjunto del de los reales.

    • Conversión de real a entero:

    • Truncamientos (trunc): Se eliminan las cifras a la derecha de la coma.

    • Redondeo (round): Se eliminan las cifras decimales sumándole una unidad al número restante si la primera cifra decimal en mayor que 5 y restándole una unidad si la cifra decimal es menor que 5.

    • round (a) = trunc (a + 0.5)

    • Tipo caracter

  • Conjunto de valores asociados formado por un conjunto de caracteres imprimibles que comprende:

    • Caracteres del alfabeto latino.

    • Dígitos arábigos.

    • Caracteres especiales y de control.

    Para formalizar este conjunto de valores se imponen dos condiciones:

    • Es un subconjunto de un alfabeto ordenado y coherente. Puede incluir letras, dígitos y otros caracteres, por eso es un subconjunto de un alfabeto.

    • Existe un caracter (b) que no es imprimible.

    Normalmente se admite la tabla ASCII como estándar.

  • Gracias al ASCII es considerado un tipo escalar y ordinal.

  • Operadores. Carece de operadores aritméticos:

    • Relacionales: <, ", =, ", ", >

    • Ordinales: pred, succ, ord.

  • Implementación. Un caracter suele representarse por la representación binaria del caracter en la tabla ASCII (la posición que ocupa en esta tabla).

  • Relaciones entre caracter y entero

    • Conversión de caracter a entero (ord): La función ordinal de un caracter devuelve el valor entero de la posición que ocupa en la tabla ASCII.

    • Conversión de entero a caracter (chr): La función caracter (char) de un valor entero devuelve el caracter correspondiente de la tabla ASCII.

    Ejemplos:

    ord (chr (i)) = i, si " chr(i)

    chr (ord (i)) = i

    • Tipos booleano

  • Conjunto de valores asociados con cierto y falso como dos únicos valores posibles.

  • { cierto, falso }

  • El tipo booleano es un tipo escalar y ordinal. Se asume que falso < cierto.

  • Operadores. Carece de operadores aritméticos, pero añade un tipo de operadores exclusivo del tipo booleano.

    • Booleanos: AND, OR, NOT.

    • Relacionales: <, ", =, ", ", >

    • Ordinales: pred, succ, ord.

  • Implementación. Para su representación se basa en los enteros 0 y 1, para los valores falso y cierto respectivamente.

  • 2.2.2.- Tipos definidos por el usuario

    Son subconjuntos de tipos ordinales, por tanto, también son ORDINALES. Dentro de esta clase encontramos los tipos enumerados y los subrangos; tipos normalizados.

    Ejemplo: Menú de selección de un cajero automático.

    Tenemos 6 opciones posibles a elegir. Podríamos usar un tipo entero, pero seguidamente se verá que es más adecuado y ajustado definirse un tipo enumerado o un subrango.

    opcion = 1..6; {definición por subrango}

    opcion = (1,2,3,4,5,6); {definición por enumerado} Dos posibles declaraciones de tipo

    a:opcion; {declaración de la variable}

    ... ... ...

    write('Escoge una opción');

    readln(a);

    ... ... ...

    • Tipo enumerado

    Se define un tipo enumerado mediante identificadores (los valores que queremos que formen el tipo).

    <nombre_tipo>=(<id_1>, <id_2>, ..., <id_n>);

    Ejemplos:

    diasemana=(lunes,martes,miercoles,jueves,viernes,sabado,domingo)

    colores=(verde,rojo,azul,amarillo)

    palos=(oros,copas,espadas,bastos)

    La implementación de un tipo enumerado se basa en el tipo ENTERO. El orden de la declaración es significativo para establecer las relaciones ordinales entre valores.

    miercoles > lunes; viernes < jueves

    ordinal(lunes)=0; ordinal(martes)=1

    OJO: Se trabaja con identificadores por tanto no se pueden leer del teclado ni escribir en la pantalla; es usual utilizar sentencias CASO.

    p:palos;

    CASO QUE p SEA

    oros:escribir('oros');

    copas:escribir('copas');

    espadas:escribir('espadas');

    bastos:escribir('bastos')

    OTRO CASO

    escribir('error')

    • Tipo Subrango

    Se define como subconjunto de otro tipo ORDINAL ya definido indicando un valor mínimo y un valor máximo. Formarán el tipo todos los valores comprendidos entre mínimo y máximo, incluídos éstos.

    <nombre> = Vmin ... Vmax

    Por ejemplo:

    opciones=1..6;

    alfabeto='A'..'Z';

    laborables=lunes..viernes;

    Los tipos subrango heredan las operaciones correspondientes al tipo sobre el que se definen (Ojo, si éste es enumerado!!).

    Peligro de desbordamiento

    x, y, z:opcionesM;

    ... ... ...

    x ! x+y;

    Probar esto para los casos en que x=1 y=4, y x=3 y=6 .

    Enumerados y subrango

    Son de utilidad como tipo índice. Los podemos usar como TI en los bucles PARA.

    PARA i ! 1 HASTA n HACER i"[1..n]

    PARA i ! 'A' HASTA 'L' HACER

    PARA i ! lunes HASTA miercoles HACER

    Los enumerados y subrangos pueden usarse para definir los elementos en los Tipo TABLA (ARRAYS):

    TABLA [1..n, 1..m] DE ...

    TABLA [Vmin .. Vmax] DE ...

    TIPO BASE: Llamaremos así a los tipos cuyos valores permitan construir una estructura de datos.

    2.3.- Tipos Estructurados

    Esta clase permite definir objetos que agrupan distintos valores. Estos valores pueden ser de tipo base u otro tipo estructurado. El lenguaje suele aportar las herramientas para manejar estos tipos, pero es el programador el que hará la definición concreta.

    Nos encontramos en el grupo de Tipos Estructurados a los vectores o tabla, cadenas, conjunto y registro. En los tres primeros los valores son de tipo base y en los registros podemos encontrarnos un tipo base u otro tipo estructurado en su interior.

    2.3.1.- Tipo Vector

    Caracterizamos el tipo estructurado vector por ser un conjunto finito y ordenado de elementos homogéneos. Nos referimos a sus elementos de la forma V[i]=x, donde V es el identificador del vector, i es de tipo índice e indica la posición i del elemento x dentro del vector V, y x es un conjunto de valores del mismo tipo base.

    Definición del Tipo Abstracto de Datos VECTOR

  • Operaciones:

    • Crear: ! vector

    • Extraer: vector x tipo_indice x ! tipo_base

    • Almacenar: vector x tipo_indice x tipo_base ! vector

    • Cuando se crea un vector el resultado es un nuevo vector cuyos elementos no están definidos.

    • La acción de extraer un elemento de un vector supone obtener un elemento de tipo base dados dicho vector y un índice i que indica la posición del elemento.

    • Para almacenar un elemento en una posición i determinada del vector tomaremos el valor del elemento tipo base a almacenar y obtendremos un nuevo valor del vector diferente del anterior.

  • Axiomas:

    • Extraer (Crear, i) = error

    si i=j x

    • Extraer (Almacenar (A, i, x), j) =

    sino Extraer (A, j)

    si i=j Almacenar (A, i, y)

    • Almacenar (Almacenar (A, i, x), j , y) =

    sino Almacenar (Almacenar (A, j, y), i, x)

  • Notación habitual:

  • TIPO

    • Crear (declaración del tipo vector) " vector=TABLA [Ti] DE Tb

    VARIABLES

    v:vector

    • Extraer (V, i) " V[i]

    • Almacenar (V, i, x) " V[i] ! x

    Un caso especial de tipo vector: CADENA

    Se representa como un vector de caracteres.

    <tipo>=TABLA [1..n] de CARÁCTER

    ó

    <tipo>=CADENA[n]

    La cadena admite todas las operaciones del vector y, además, y 4 exclusivas de las cadenas:

    • Subcadena: Cadena x TI x 1..n ! CADENA

    Dada la cadena C, un índice i y una longitud L (entre 1 y n), devolverá la subcadena englobada entre i é (i + L) de la cadena dada.

    • Posición: Cadena x Cadena ! 0..n

    Dadas las cadenas C1 y C2, devuelve la posición i a partir de la cual la cadena C2 está contenida en C1.

    • Longitud: Cadena ! 0..n

    Dada una cadena, devuelve su longitud.

    • Concatenar: CADENA x CADENA ! CADENA

    Dadas C1 y C2, el resultado es la cadena C=C1+C2 (C1 concatenado con C2).

    NOTA:

    El tipo CADENA admite la asignación simultánea de todos los valores.

    VARIABLES

    x:cadena;

    INICIO

    x ! `Hola buenos días'

    FIN.

    2.3.2.- Tipo CONJUNTO

    El tipo Conjunto es un estructurado con un número finito de elementos homegéneos sin ninguna relación de orden entre ellos.

    Definición del Tipo Abstracto de Datos CONJUNTO

  • Operaciones:

    • Crear: ! Conjunto

    El resultado es un conjunto, cuyos elementos no están definidos.

    • Insertar: Conjunto x TB ! Conjunto

    Dado un conjunto y un valor de TB, se obtiene un nuevo conjunto formado al añadir ese valor al conjunto original.

    • Pertenencia: Conjunto x TB ! Booleano

    Dado un conjunto y un valor de TB, indica si dicho valor pertenece o no al conjunto.

    • Unión: Conjunto x Conjunto ! Conjunto

    Dados dos conjuntos, obtiene el “conjunto unión”.

    • Intersección: Conjunto x Conjunto ! Conjunto

    Dados dos conjuntos se obtiene el “conjunto intersección”.

    • Diferencia: Conjunto x Conjunto ! Conjunto

    Dados dos conjuntos obtiene la diferencia entre ambos.

    • Inclusión: Conjunto x Conjunto ! Booleano

    Dados dos conjuntos, devuelve verdad si el segundo está contenido en el primero.

    • Igualdad: Conjunto x Conjunto ! Booleano

  • Axiomas:

  • " S, S1, S2 " Tipo CONJUNTO

    " x, y " Tipo Base

    • Pertenencia (x, Crear) = falso

    Verdad si x=y

    • Pertenencia (x, Insertar (S, y)) =

    Pertenencia (x, S) si x"y

    • Unión (S, Crear) = S

    • Unión (S1, Insertar (S2, x)) = Unión (Insertar (S1, x),S2)

    • Diferencia (Crear, S) = Crear

    Diferencia (S1, S2) si x" S2

    • Diferencia (Insertar (S1, x), S2) =

    Insertar (Diferencia (S1, S2), x) si x " S2

    • Intersección (S1, S2) = Diferencia (S1, Diferencia (S1, S2))

    • Inclusión (S, Crear) = cierto

    Inclusión (S1, S2) si x"S1

    • Inclusión (S1, Insertar (S2, x)) =

    Falso si x"S1

    • Igualdad (S1, S2) = Inclusión (S1, S2) Y Inclusión (S2, S1)

    ¿ Cómo implementaremos los conjuntos?

    TIPO

    Crear <nombre> = CONJUNTO de <Tipo_Base>

    VARIABLES

    c: <nombre>

    Insertar: Dado un valor de tipo base, x, se genera [x] al insertarlo en el conjunto vacío creado. Para insertar el valor en un conjunto no vacío, s: s ! s + [x].

    Pertenencia: Tenemos un valor de tipo base, x, y un tipo conjunto, C. Para comprobar la pertenencia lo haremos mediante la siguiente expresión: x EN C.

    Unión: D ! A+B; siendo D el “conjunto unión” y A,B los conjuntos a unir. Todos de tipo conjunto.

    Diferencia: D ! A-B

    Intersección: D ! A*B

    Igualdad: A=B

    Inclusión: A"B; cierto si A es un subconjunto de B.

    Restricciones al TB

    El tipo base utilizado como elemento de un conjunto debe ser FINITO y ORDINAL. Quedan excluidos, por tanto, Reales y Enteros. Normalmente, definiremos el conjunto en función de un tipo enumerado o subrango.

    colores=(rojo, azul, blanco)

    colorines=CONJUNTO de colores

    conjsubrango=CONJUNTO de Vmin..Vmax

    • Conjunto Vacío: []

    • Construcción de conjuntos:

    • por extensión: C ! [x1, x2, x3]

    • elemento a elemento:

    C ! [];

    MIENTRAS NO condición HACER

    ... ... ...

    x ! ... {valor de TB}

    C ! C + [x]

    FINMIENTRAS

    ... ... ...

    • El único modo de manejar valores de un conjunto es mediante el test de pertenencia.

    Por ejemplo:

    INICIO {subrangos}

    C: CONJUNTO de Vmin .. Vmax; { ó sobre (rojo, negro, blanco)}

    i ! Vmin;

    enc ! falso;

    MIENTRAS (NO enc) Y (i"Vmax) HACER

    enc ! i EN C;

    SI (NO enc) i! i+1 FINSI

    FINMIENTRAS

    FIN.

    INICIO {enumerados}

    i ! rojo;

    enc ! falso;

    MIENTRAS (NO enc) Y (i"blanco) HACER

    enc ! i EN C

    SI (NO enc) i ! succ (i) FINSI

    FINMIENTRAS

    FIN.

    2.3.3.- Tipo REGISTRO

    Un registro es un conjunto de pares (x, id) donde id indica un identificador de campo y x el valor almacenado en dicho campo.

    Definición del REGISTRO como TAD

  • Operaciones:

    • Crear: ! Registro

    Devuelve un registro, cuyos campos no están definidos.

    • Extraer: Registro x idi ! TBi

    Dado un registro y un identificador de un campo i, devuelve el valor de TB almacenado en dicho campo.

    • Almacenari: Registro x idi x Tbi ! Registro

    Dado un registro, un identificador de campo y un valor de TB, devuelve un registro en el que el valor del campo indicado ha sido sustituido por el valor nuevo.

  • Axiomas:

  • "r " Tipo Registro

    "x, y " Tipo Base

    • Extraer (Crear, id) = error

    x si idi=idj

    • Extraerj (Almacenari (r, idi, x), idj) =

    Extraer (r, idj) si idi"idj

    • Almacenarj (Almacenari (r, idi, x), idj, y) =

    Almacenarj (r, idj, y) si idi=idj

    =

    Almacenari (Almacenarj (r, idj, y), idi, x) si idi"idj

    • Instrucción CON (" WITH en Pascal)

    Registro en memoria = dir.base y a continuación los valores de los campos, r.idi.

    • Implementación de las operaciones:

    TIPO

    Crear <nombre>=REGISTRO de

    <campo1>:TB1;

    <campo2>:TB2;

    <campo3>:TB3;

    ... ... ... ... ... ... ... ...

    <campok>:TBk

    FINREGISTRO;

    VARIABLES

    r:<nombre>

    Extraer (r, idi) " r.idi

    Almacenar (r, idi, x) " r.idi ! x

    • Ejemplo:

    TIPO

    Fecha=REGISTRO de

    día, mes, año: ENTERO

    FINREGISTRO;

    VARIABLES

    r:fecha


    INICIO {sin CON}

    r.día ! ... ;

    r.mes ! ... ;

    r.año ! ... ;

    SI (r.anyo>1980) ENTONCES

    r.día ! ...

    FIN.


    INICIO {con CON}

    CON r HACER

    día ! ... ;

    mes ! ... ;

    año ! ... ;

    SI (año>1980) ENTONCES

    día ! ...

    FINCON

    FIN.

    Registros en parte variable

    Parte fija

    Registro = Discriminante

    Parte Variable

    Ejemplo:

    TIPO

    Paciente=(hombre, mujer, niño);

    Hospital=REGISTRO de

    Edad:ENTERO;

    Nombre:CADENA;

    NSS:CADENA;

    Domicilio:CADENA;

    CASO p:paciente QUE

    Mujer:

    Ginecólogo:CADENA;

    Num_partos:ENTERO;

    Hombre:

    Andrologo:CADENA;

    Niño:

    Pediatra:CADENA;

    Vacunas:VECTOR

    FINCASO

    FINREGISTRO;

    VARIABLES

    Ocupación:TABLA [1..n] de Hospital;

    INICIO

    Leer (v[i].edad);

    Leer (v[i].nombre);

    Leer (v[i].NSS);

    Leer (v[i].domicilio);

    CASO v[i].p QUE

    Mujer:v[i].ginecólogo ! `...'

    ... ... ... ... ... ... ... ... ... ... ...

    FINCASO

    ... ... ... ... ... ... ... ... ... ... ... ...

    FIN.

    EN GENERAL,

    <tipobase_discriminante>= _______ (normalmente enumerado ó BOOLEANO);

    <tipo_registro>=REGISTRO DE

    id1:TB1;

    id2:TB2;

    ... ... ... ...

    idn:TBn;

    CASO (discriminante:<tipobase_discriminante>) QUE

    Valor1:

    id11:TB11;

    id12:TB12;

    ... ... ... ... ...

    id1k:TB1k;

    ... ... ... ... ... ...

    Valorq:

    idq1:TBq1;

    idq2:TBq2;

    ... ... ... ... ...

    idqp:TBqp

    FINCASO

    FINREGISTRO;

    Precauciones

    • Definir siempre primero el discriminante.

    • Asociado al uso de la instrucción CASO en el algoritmo que lo maneje.

    • Vector_Conjunto

    {¿Cuándo hay que usarlos?}

    • Registro

    TEMA 3: Estructura de Datos PILA. Punteros

  • El tipo PILA

  • Definición y ejemplos

  • Definición del TAD Pila

  • Implementación Estática del tipo PILA: Uso de Vectores

  • Gestión Dinámica de la memoria

  • Punteros

  • Implementación Dinámica del tipo PILA: Uso de Punteros

  • 3.1.- El tipo PILA

    La pila es una estructura de datos en la que solamente podemos acceder a su último elemento introducido (LIFO). A este último elemento lo llamamos TOPE de la Pila. A esta posición accederemos cuando queremos añadir o eliminar elementos en la pila.

    3.1.1.- Definición y ejemplos

    Una PILA es una estructura de datos ORDENADA y HOMOGÉNEA, en la que sólo podemos acceder a una posición llamada TOPE. Los elementos de una pila se añaden o eliminan siguiendo una política LIFO (Last IN, First OUT).

    La PILA es una estructura DINÁMICA, es decir, su tamaño varía según llevamos a cabo operaciones sobre ella. No tiene limitación (¡¡Teórica!!) de tamaño.

    Importancia de las pilas en Informática

    Program MAIN Procedure A1( ); Procedure A2 ( ); Procedure A3 ( );

    BEGIN BEGIN BEGIN BEGIN

    ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

    ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

    ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

    r-1: A1 ... ... ... s-1: A2 ... ... ... t-1: A3 ... ... ... ... ... ... ... ...

    s: ... ... ... ... ... ... s: ... ... ... ... ... ... t: ... ... ... ... ... ... ... ... ... ... ...

    ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... END.

    ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

    END. END. END.

    3.1.2.- Definición del TAD Pila

    TAD: PILA

    Operaciones

  • Crear: ! Pila {Crea una pila vacía}

  • Añadir: Pila x TipoBase ! Pila {Dada una pila p y un valor e de tipo base, devuelve la pila formada al añadir a p el nuevo elemento (en la posición siguiente a la del TOPE).

  • Borrar: Pila ! Pila {Dada una pila, devuelve el valor del elemento que ocupa el TOPE de la pila}

  • Tope: Pila ! TipoBase {Dada una pila, devuelve el valor del elemento que ocupa el TOPE de la pila}

  • PilaVacía: Pila ! Booleano {Dada una pila, devuelve cierto si está vacía y falso en el caso contrario.

  • Axiomas: "p " PILA, "e " TipoBase

  • PilaVacía (Crear) = cierto

  • PilaVacía (Añadir (p, e)) = falso

  • Borrar (Crear) =error

  • Borrar (Añadir (p, e)) = p

  • Tope (Crear) =error

  • Tope (Añadir (p, e)) = e

  • 3.1.3.- Implementación Estática del tipo PILA: Uso de vectores

    • Similitudes entre pila y vector.

    • Ordenados

    • Homogéneos

    • Diferencias entre pila y vector

    • En un vector hay accesos a todos los elementos y en una pila sólo es posible el acceso al tope.

    • Un vector es una estructura de tamaño fijo (para definirlo hay que indicar su número de elementos); una pila no tiene restricciones TEÓRICAS sobre su tamaño.

    • Como solución a la primera diferencia basta con restringir el acceso a sólo una posición en el vector.

    PILA:

  • Necesitamos un vector y una variable que funcione como tope.

  • Definiremos un registro con un vector en un campo, sobre el que simularemos la pila, y en el otro campo un tope.

    • En cuanto a la limitación de tamaño de un vector no podemos hacer nada. Tan sólo controlar que no se nos llene la pila y se produzca un desbordamiento.

    • Definición de la estructura

    CONSTANTES

    MaxElem = ... ; {nº máximo de elementos en la pila}

    TIPOS

    TipoPila = REGISTRO DE

    Elementos: TABLA [1..MaxElem] de TipoBase;

    Tope: 0 .. MaxElem

    FINREGISTRO;

    VARIABLES

    P: TipoPila;

    ALGORITMO Crear (SAL p:TipoPila);

    INICIO

    p.tope ! 0

    FIN.

    ALGORITMO PilaVacía (ENT p:TipoPila): BOOLEANO;

    INICIO

    PilaVacía ! (p.tope=0)

    FIN.

    ALGORITMO Tope (ENT p:TipoPila; SAL e:TipoBase; error:Booleano);

    INICIO

    SI PilaVacía (p) ENTONCES

    Error ! cierto

    SINO

    Error ! falso;

    E ! p.elementos [p.tope]

    FINSI

    FIN.

    ALGORITMO Borrar (E/S p:TipoPila; SAL error:Booleano);

    INICIO

    SI PilaVacía (p) ENTONCES

    Error ! cierto

    SINO

    Error ! falso;

    p.tope ! p.tope -1

    FINSI

    FIN.

    ALGORITMO Añadir (E/S p:TipoPila; ENT e:TipoBase);

    INICIO

    p.tope ! p.tope +1;

    p.elementos [p.tope] ! e

    FINSI

    {algoritmo añadir con control de pila llena}

    ALGORITMO Añadir (E/S p:TipoPila; ENT e:TipoBase; SAL error:Booleano);

    INICIO

    SI (p.tope=MaxElem) ENTONCES

    Error ! cierto

    SINO

    Error ! falso;

    p.tope ! p.tope +1;

    p.elementos [p.tope] ! e

    FINSI

    FIN.

    ALGORITMO PilaLlena (ENT p:TipoPila): BOOLEANO;

    INICIO

    PilaLlena ! (p.tope=MaxElem)

    FIN.

    3.2.- Gestión dinámica de la memoria

    Estructura estática

    En tiempo de COMPILACIÓN hay un tamaño fijo. En tiempo de EJECUCIÓN no hay operaciones sobre la estructura que permitan variar su tamaño. (Ej: Vector, Registro).

    • Por contra, la pila es DINÁMICA: las operaciones sobre la pila (Añadir, Borrar) afectan a su tamaño.

    3.2.1.- Los Punteros

    Los punteros son un tipo simple (como ENTERO, REAL, CARÁCTER ó BOOLEANO) que permite gestionar de forma dinámica la ocupación en la memoria.

    TIPO

    Puntero_Entero = Puntero a entero;

    Otro_Puntero = Puntero a Elemento;

    Elemento = REGISTRO de

    a, b: entero;

    c: cadena[10]

    FINREGISTRO;

    VARIABLES

    p, q: Puntero_Entero;

    r: Otro_Puntero;

    {p apunta a la primera posición de memoria en la que se almacena un valor de tipo entero}

    Cuando trabajamos con punteros al compilar

    • El compilador reserva espacio para variables de tipo puntero.

    • Como se sabe a qué apunta es posible tenerlo en cuenta en ejecución a la hora de realizar operaciones con ellos.

    Operaciones con PUNTEROS

    • Asignación:

    ¡Ojo! Sólo valores válidos:

    • o bien NIL, p ! NIL

    • o bien el valor de otro puntero

    ... ... ... ... ...

    variables

    p, q: puntero;

    inicio

    p ! q

    fin.

    {suponemos que el valor y el tipo de los dos punteros sean compatibles}

    • NEW(q):

    Es una llamada que resuelve el GESTOR de MEMORIA. Se necesita crear una variable de forma dinámica. El Gestor de Memoria “reserva” el espacio necesario para almacenarla. Devuelve sobre q la posición de memoria a partir de la cual me han reservado el espacio.

    • DISPOSE(q):

    Es una llamada que resuelve el gestor de memoria. Se libera memoria. El gestor de memoria “libera” el espacio de memoria suficiente para almacenar la variable que está siendo apuntada por q, a partir de la posición de memoria indicada por q. El valor de q, queda indefinido.

    3.2.2.- Implementación de la PILA mediante PUNTEROS

    El único acceso del que dispondremos en la PILA, será el puntero a la posición de memoria en la que se almacene el TOPE.

    TPila = Puntero a Elemento;

    Elemento = REGISTRO de

    info: tipobase;

    sig: TPila

    FINREGISTRO;

    ALGORITMO CrearPila (SAL p: TPila);

    INICIO

    p ! NIL

    FIN; {fin crearpila}

    ALGORITMO PilaVacía (ENT p: TPila): Booleano;

    INICIO

    PilaVacía ! (p=NIL)

    FIN; {fin pilavacia}

    ALGORITMO Añadir (E/S p: TPila; ENT i: tipobase);

    VARIABLES

    q: TPila;

    INICIO

    NEW(q);

    q^.info ! i;

    q^.sig ! p;

    p ! q

    FIN; {fin añadir}

    ALGORITMO Borrar (E/S p: TPila; SAL e: booleano);

    VARIABLES

    q: TPila;

    INICIO

    SI PilaVacía (p) ENTONCES

    e ! cierto

    SINO

    e ! falso;

    q ! p;

    p ! p^.sig;

    DISPOSE (q)

    FINSI

    FIN; {fin borrar}

    ALGORITMO Tope (ENT p: TPila; SAL i: tipobase; error: booleano);

    INICIO

    error ! CIERTO;

    SI NO(PilaVacia (p)) ENTONCES

    error ! FALSO;

    i ! p^.info

    FINSI

    FIN; {fin tope}

    Comparación de ambas implementaciones

    • Memoria estática (vectores)

    Pegas:

    • se trabaja con una estructura de tamaño fijo.

    • problemas de PILA LLENA.

    • problemas de desaprovechamiento de memoria.

    • Memoria dinámica (punteros)

    Pegas:

    • en general, el tamaño de cada elemento de la pila es mayor (hay que guardar además del valor de tipo base, el puntero al siguiente, ...).

    TEMA 4: Estructuras COLA y LISTA

    4.1.- El Tipo COLA

  • Definición y ejemplos

  • Definición como TAD

  • Ejemplos de implementación

  • 4.1.3.1.- Implementación del Tipo Cola con Vectores

    4.1.3.2.- Implementación del Tipo Cola mediante Punteros

    4.2.- El Tipo LISTA

  • Definición. El TAD Lista

  • Implementación Dinámica del Tipo Lista

  • TAD's relacionados con el TAD Lista

  • 4.1.- El Tipo COLA

    4.1.1.- Definición y ejemplos

    Una Cola es un conjunto ordenado de elementos homegéneos (tipo base) en el cual, los elementos se eliminan por un punto determinado llamado cabeza, y se insertan por un punto llamado final. Esta estructura sigue la política FIFO (First IN, First OUT).

    Es una estructura dinámica puesto que su tamaño varía al realizar operaciones sobre ella.

    Operaciones:

  • CrearCola: ! Cola

  • ColaVacía: Cola ! Booleano {Indica si una cola está o no vacía}

  • Cabeza: Cola ! TipoBase {Devuelve el valor del elemento situado en lo cabeza de la cola}

  • Encolar:

  • Desencolar:

  • Axiomas: "q " Cola, "i " TipoBase

  • ColaVacía (CrearCola (q)) = CIERTO

  • ColaVacía (Encolar (q,i)) =FALSO

  • Desencolar (CrearCola (q)) = error

  • SI ColaVacía (q) ENTONCES

  • Desencolar (Encolar (q, i)) = CrearCola (q)

  • SINO Encolar (Desencolar (q), i) FINSI;

  • Cabeza (CrearCola (q)) = error

  • SI ColaVacía (q) ENTONCES

  • Cabeza (Encolar (q, i)) = i

  • SINO Cabeza (q) FINSI;

    4.1.3.- Ejemplos de implementación

    • con Vectores

    • con Punteros

    4.1.3.1.- Implementación del Tipo Cola con Vectores

    CONSTANTE

    MAX= ... {Número máximo del elementos}

    TIPOS

    Tcola= REGISTRO DE

    datos: TABLA [1 .. MAX] de TipoBase;

    cabeza, final: 0 .. MAX

    FINREGISTRO;

    Ideas Básicas:

    • Condición ColaVacía es (q.cabeza = q.final)

    • La operación CABEZA tendría una pinta similar a:

    SI NO(ColaVacía (q)) ENTONCES

    i ! q.datos [q.cabeza +1]

    FINSI;

    • La operación Desencolar:

    SI NO(ColaVacía (q)) ENTONCES

    q.cabeza ! q.cabeza +1

    FINSI;

    • La operación Encolar:

    SI NO(ColaLlena (q)) ENTONCES

    q.final ! q.final + 1;

    q.datos [q.final] ! i

    FINSI;

    • Para optimizar la ocupación del vector sobre el que implemente la Cola ! Vector Circular.

    CONSTANTES

    N= ... ;{nº máximo de elementos}

    MAX= N-1;

    TIPOS

    Tcola= REGISTRO DE

    datos= TABLA [0 .. MAX] de TipoBase;

    cabeza, final= 0 .. MAX

    FINREGISTRO;

    q.cabeza ! (q.cabeza + 1) ! (q.cabeza + 1) MOD N

    0, 1, 2, ..., n-1, 0 ,1, ..., n+1, 0 , 1 ...

    ALGORITMO CrearCola (SAL q: Tcola);

    INICIO

    q.cabeza ! 0;

    q.final ! 0

    FIN;

    ALGORITMO ColaVacía (ENT q: Tcola): Booleano;

    INICIO

    ColaVacía ! (q.cabeza = q.final)

    FIN;

    ALGORITMO Cabeza (ENT q: Tcola; SAL i: tipobase; error: booleano);

    INICIO

    error ! CIERTO;

    SI NO( ColaVacía (q)) ENTONCES

    error ! FALSO;

    i ! q.datos [(q.cabeza +1) MOD N]

    FINSI

    FIN;

    ALGORITMO Desencolar (E/S q: Tcola; SAL error : booleano);

    INICIO

    error ! CIERTO;

    SI NO( ColaVacía (q)) ENTONCES

    error ! FALSO;

    q.cabeza ! (q.cabeza + 1) MOD N

    FINSI

    FIN;

    ALGORITMO Encolar (E/S q: Tcola; ENT i: tipobase; SAL error: booleano);

    INICIO

    error ! cierto;

    SI NO(ColaLlena (q)) ENTONCES

    error ! FALSO;

    q.final ! (q.final +1) MOD N;

    q.datos [q.final] ! i

    FINSI

    FIN;

    ALGORITMO ColaLlena (ENT q: Tcola):booleano;

    INICIO

    ColaLlena ! (q.cabeza = ((q.final +1) MOD N))

    FIN;

    4.1.3.2.- Implementación del Tipo Cola mediante Punteros



    TipoPuntero = Puntero a ElemCola;

    ElemCola = REGISTRO DE

    info: <TB>;

    sig: TipoPuntero

    FINREGISTRO;

    Tcola = REGISTRO DE

    cabeza, final: TipoPuntero;

    {longitud: ENTERO}

    FINREGISTRO;


    ALGORITMO CrearCola (SAL q:TCola);

    INICIO

    q.cabeza ! NIL;

    q.final ! NIL;

    {q.longitud ! 0}

    FIN; {fin crearcola}

    ALGORITMO ColaVacía (ENT q: Tcola):Booleano;

    INICIO

    ColaVacía ! (q.cabeza=NIL Y q.final=NIL);

    {ColaVacía ! (q.longitud=0)}

    FIN; {fin colavacia}

    ALGORITMO Cabeza (ENT q: Tcola; SAL i: <TB>; error: Booleano);

    INICIO

    error ! CIERTO;

    SI NO ColaVacía (q) ENTONCES

    error ! FALSO;

    i ! q.cabeza^.info

    FINSI

    FIN; {fin cabeza}

    Desencolar

    ALGORITMO Desencolar (E/S q: Tcola; SAL error: Booleano);

    VARIABLES

    aux: TipoPuntero;

    INICIO

    error ! CIERTO;

    SI NO ColaVacía (q) ENTONCES

    error ! falso;

    aux ! q.cabeza;

    q.cabeza ! q.cabeza^.sig;

    SI (q.cabeza=NIL) ENTONCES {sólo había 1 elemento}

    q.final ! NIL

    FINSI;

    DISPOSE (aux);

    {q.longitud ! q.longitud -1}

    FINSI

    FIN; {fin desencolar}

    Encolar

    ALGORITMO Encolar (E/S q: Tcola; ENT i: <TB>);

    VARIABLES

    aux: TipoPuntero;

    INICIO

    new (aux);

    aux^.info ! i;

    aux^.sig ! NIL;

    SI ColaVacía (q) ENTONCES

    q.cabeza !aux

    SINO

    q.final^.sig ! aux

    FINSI

    q.final ! aux;

    {q.longitud ! q.longitud +1}

    FIN; {fin encolar}

    4.2.- El Tipo LISTA

    4.2.1.- Definición. El TAD Lista

    Estructura ordenada y homogénea en la que cualquier elemento es accesible y en la que es posible añadir o eliminar elementos en cualquier posición. La lista es una estructura de datos dinámica.

    PILA COLA LISTA

    1 punto 2 puntos ninguna restricción

    Definiciones básicas para estas 3 estructuras.

    PILA " TOPE

    COLA " {CABEZA, FINAL}

  • listas simplemente enlazadas (cada elemento tiene acceso al siguiente).

  • listas doblemente enlazadas (cada elemento tiene acceso al siguiente y al anterior).

  • listas circulares (cada elemento tiene acceso al siguiente y el último al primero).

  • Otras posibles definiciones:

    PILA " {tope, longitud}

    COLA " {cabeza, final, longitud}

    LISTA " {primero, longitud}

    " {primero, último}

    " {primero, último, longitud}

    Una lista es una tripla (P, R, v) donde:

    • P es un conjunto de posiciones que almacenan los valores dentro de la estructura.

    • R es la relación de orden entre las posiciones.

    • v es la función que relaciona una posición don el valor almacenado en ella.

    TAD: LISTA

    Operaciones:

    • Contructivas

  • CrearLista: ! Lista

  • Almacenar: Lista x Tipobase ! Lista {puede ser al principio, al final o en cualquier posición de la lista}

    • Modificadoras

  • Insertar: Lista x Tipobase x Posición ! Lista {antes de la posición o después de la posición}

  • Borrar: Lista x Posición ! Lista

  • Modificar: Lista x Posición x Tipobase ! Lista

    • De acceso

  • Dato: Lista x Posición ! Tipobase

  • Longitud: Lista ! Entero

  • Siguiente: Lista x Posición ! Posición

  • ListaVacía: Lista ! Booleano

  • Primero: Lista ! Posición

  • Último: Lista ! Posición

  • Anterior: Lista x Posición ! Posición

  • Buscar: Lista x Tipobase ! Posición

  • ¿Qué tomaremos como tipo Posición?

    • Natural

    • O cualquier otro tipo que sirva para referenciar elementos; por ejemplo un PUNTERO.

    CONJUNTO

    COLA

    PILA

    Contructivas

    Crear

    Crear

    Crear

    Insertar

    Encolar

    Añadir

    Modificadoras

    Unión

    Desencolar

    Borrar

    Diferencia

    Intersección

    De Acceso

    Pertenencia

    ColaVacía

    PilaVacía

    Inclusión

    Cabeza

    Tope

    Igualdad

    CONVENIOS (para los axiomas)

    • CrearLista, crea una lista nueva.

    • Almacenar, siempre añade el nuevo valor al final.

    • Insertar, inserta el nuevo valor antes del elemento indicado por posición.

    • Buscar, devuelve la posición del primer elemento cuyo valor coincida con el dado.

    4.2.2.- Implementación dinámica del tipo LISTA

    TIPO

    POSICIÓN= PUNTERO a Elemento;

    Elemento= REGISTRO DE

    info: tipobase;

    sig: POSICIÓN

    FINREGISTRO;

    TLISTA= POSICIÓN;

    {implementación alternativa}

    TLISTA= REGISTRO DE

    primero, último: POSICIÓN;

    longitud: Entero

    FINREGISTRO;

    ALGORITMO CrearLista (SAL l: Tlista);

    INICIO

    l.primero ! NIL;

    l.último ! NIL;

    l.longitud ! 0

    FIN; {fin crearlista}

    ALGORITMO Dato (ENT l: Tlista; p: posición; SAL i: tipobase);

    INICIO

    i ! p^.info

    FIN; {fin dato}

    {sin asumir NO error}

    ALGORITMO Dato (ENT l:Tlista; p: posición; SAL i: tipobase; error: booleano);

    VARIABLES

    aux: posición;

    INICIO

    aux ! l.primero;

    MIENTRAS (aux " p) Y (aux^.sig " NIL) HACER

    aux ! aux^.sig

    FINMIENTRAS;

    SI (aux = p) ENTONCES

    i ! p^.info

    SINO error

    FINSI

    FIN; {fin dato}

    ALGORITMO Longitud (ENT l: Tlista): Entero;

    INICIO

    longitud ! l.longitud

    FIN; {fin longitud}

    ALGORITMO Siguiente (ENT l: Tlista; p: posición): Posición;

    INICIO

    siguiente ! p^.sig

    FIN; {fin siguiente}

    ALGORITMO ListaVacía (ENT l: Tlista): Booleano;

    INICIO

    ListaVacía ! (Longitud (l) = 0)

    FIN; {fin listavacia}

    ALGORITMO Primero (ENT l: Tlista): Posición;

    INICIO

    Primero ! l.primero

    FIN; {fin primero}

    ALGORITMO Último (ENT l:Tlista): Posición;

    INICIO

    Último ! l.último

    FIN; {fin ultimo}

    ALGORITMO Anterior (ENT l:Tlista; p: posición): Posición;

    VARIABLES

    aux: posición;

    INICIO

    SI (p=primero(l)) ENTONCES

    aux ! NIL

    SINO

    aux ! primero(l);

    MIENTRAS (siguiente(l.aux) " p) HACER

    aux ! siguiente (l.aux)

    FINMIENTRAS

    FINSI;

    Anterior ! aux

    FIN; {fin anterior}

    ALGORITMO Buscar (ENT l:Tlista; i: tipobase): Posición;

    VARIABLES

    aux: posición;

    x: tipobase;

    INICIO

    aux ! primero (l);

    dato (l, aux, x);

    MIENTRAS (x " i) HACER

    aux ! siguiente (l, aux);

    dato (l, aux, x)

    FINMIENTRAS;

    Buscar ! aux

    FIN; {fin buscar}

    ALGORITMO Almacenar (E/S l:Tlista; ENT i:tipobase);

    VARIABLES

    aux: posición;

    INICIO

    new (aux);

    aux^.inf ! i;

    SI ListaVacía (l) ENTONCES

    l.primero ! aux

    SINO

    l.último^.sig ! aux

    FINSI;

    aux^.sig ! NIL;

    l.último ! aux;

    l.longitud ! l.longitud + 1

    FIN; {fin almacenar}

    ALGORITMO Insertar (E/S l: Tlista; ENT p: posición; i: tipobase);

    VARIABLES

    aux1, aux2: posición;

    INICIO

    new (aux1);

    aux1^.inf ! i;

    SI ListaVacía (l) ENTONCES

    l.primero ! aux1;

    l.último ! aux1; Almacenar (l, i)

    aux1^.sig ! NIL

    SINO

    SI (p=primero(l)) ENTONCES

    aux1^.sig ! primero (l);

    l.primero ! aux1;

    SINO

    aux2 ! Anterior (l, p);

    aux2^.sig ! aux1;

    aux1^.sig ! p

    FINSI

    FINSI

    { SI (p=primero(l)) ENTONCES

    l.primero ! aux1

    SINO

    aux2 ! Anterior (l, p);

    aux2^.sig ! aux1

    FINSI

    aux1^.sig ! p }

    l.longitud ! l.longitud + 1

    FIN; {fin insertar}

    ALGORITMO Borrar (E/S l:Tlista; ENT p:posición);

    VARIABLES

    aux: posición;

    INICIO

    SI (p=primero(l)) ENTONCES

    l.primero ! siguiente (l, p);

    SI (primero(l) = NIL) ENTONCES

    l.último ! NIL

    FINSI

    SINO

    aux ! Anterior (l, p);

    aux^.sig ! siguiente (l, p);

    SI (p=último(l)) ENTONCES

    l.último ! aux

    FINSI

    FINSI

    Dispose(p);

    l.longitud ! l.longitud - 1

    FIN; {fin borrar}

    ALGORITMO Modificar (E/S l:Tlista; ENT p: posición; i: tipobase);

    INICIO

    p^.inf ! i

    FIN; {fin modificar}

    4.2.3.- TAD's relacionados con el TAD Lista

  • TAD Lista Ordenada

  • Definición: Estructura lineal, homegénea y ordenada en la que podemos acceder a todos los elementos aunque teniendo en cuenta que estos siempre permanecerán ordenados según algún criterio.

    Operaciones: Las mismas que en el TAD lista con las siguientes excepciones,

    • Las opreaciones Almacenar e Insertar son substituidas por una llamada InsertarOrdenado (cada elemento se añade en su sitio).

    • No hay operación Modificar.

    • Ejemplo de implementación de InsertarOrdenado con el tipo base ENTERO:

    ALGORITMO InsertarOrdenado (E/S l: Tlista; ENT i: entero);

    VARIABLES

    aux1, aux2, aux: posición;

    INICIO

    new (aux1);

    aux1^.info ! i;

    SI ListaVacía (l) ENTONCES

    l.primero ! aux1;

    l.último !aux1;

    aux1^.sig ! NIL

    SINO

    SI (i<Dato(l, primero(l)) ENTONCES

    aux1^.sig ! primero (l);

    l.primero ! aux1;

    SINO

    aux2 ! primero (l);

    MIENTRAS (i>Dato(l, aux2) Y (aux " último(l)) HACER

    aux ! aux2;

    aux2 ! siguiente (l, aux2)

    FINMIENTRAS

    SI (Dato(l, aux2) " i) ENTONCES

    aux1^.sig ! aux2;

    aux^.sig ! aux1

    SINO

    aux1^.sig ! NIL;

    l.último^.sig ! aux1;

    l.último ! aux1

    FINSI

    FINSI

    FINSI

    l.longitud ! l.longitud + 1

    FIN; {fin insertarordenado}

  • TAD Lista de Listas

  • Definición: Una lista en la que el tipo base (sus elementos) es una lista.

    Operaciones: Las operaciones de este tipo serán las de la lista Tlista2 más las operaciones de la lista Tlista.

    En una lista de listas el elemento es una lista.

    • Almacenar en una Tlista2 supone:

    • Crear Tlista.

    • Almacenar elementos en Tlista.

    • Almacenar Tlista en Tlista2.

    • Borrar en Tlista2 supone:

    • Borrar todos los elementos en Tlista.

    • Borrar el elemento en Tlista2.

    • Modificar puede suponer:

    • Modificar toda una lista entero de tipo Tlista (elemento de Tlista2).

    • Modificar un elemento de una Tlista.

  • TAD Multilista

  • Definición: Lista Ordenada en la que existe más de un elemento siguiente y cada uno de ellos tiene un criterio de ordenación.

    Ejemplo:

    Elemento= REGISTRO DE

    titulo, asig CADENA;

    codigo: Entero

    FINREGISTRO;

    Posición= Puntero a ElementoMultiLista;

    ElementoMultiLista= REGISTRO DE

    info: Elemento;

    sigtit, sigasig, sigcod: Posición

    FINREGISTRO;

    MultiLista= REGISTRO DE

    primtit, primasig, primcod: Posición

    FINREGISTRO;

    TEMA 5: Introducción a las estructuras de datos NO Lineales. Árboles Binarios

    5.1.- Introducción

    5.2.- Árboles Binarios. Recorrido

    5.3.- Árboles Binarios de búsqueda

    5.1.- Introducción

    • Árbol: Cada elemento tiene un anterior y varios siguiente.

    • Grafo: Cada elemento tiene varios anteriores y varios siguientes.

    Usos de Árboles: Organización de la información.

    Además, esquemas algorítmicos

    • divide y vencerás

    • programación voraz

    • back tracking

    TERMINOLOGÍA BÁSICA

    • Nodo Padre de otro nodo A es el que apunta al nodo A.

    • Nodo Hijo de otro nodo A es el nodo que está siendo apuntado por el nodo A (cada nodo sólo tiene un padre y puede tener varios hijos).

    • Nodo Raíz es el primer nodo. No tiene nodo padre.

    • Nodo hoja hace referencia a cualquiera de los últimos nodos, es decir, un nodo que no tiene hijos.

    • Nodo interior es el que no es ni raíz ni hoja.

    • Camino es la secuencia de nodos en la que dos nodos consecutivos son padre e hijo. Un camino enlaza dos nodos.

    • Rama camino que va desde el nodo raíz a un nodo hoja.

    • Altura es el máximo número de nodos de cada una de las ramas.

    • Grado de un nodo es el número de hijos que tiene.

    • Grado de un árbol es el número máximo de hijos que puede tener un nodo.

    • Nivel de un nodo es el número de nodos del camino que va del nodo raíz a ese nodo.

    5.2.- Árbol Binario. Recorrido

    Un árbol binario es un árbol de grado 2. Pude ser un árbol vacío o estar formado por un nodo y 2 subárboles: izquierdo y derecho; también árboles binarios.

    Árbol Binario Equilibrado:

    Todos los nodos cumplen la siguiente propiedad,

    (altura (subarbolizquierdo) - altura (subarbolderecho)) " 1

    Árbol Binario Completo:

    Todos los nodos tienen dos hijos y todos los hijos están en el mismo nivel.

    nº de nodos en el nivel k = 2k-1

    nº de nodos total si la altura es h = 2n-1

    5.2.1.- TAD: Árbol Binario

    Operaciones:

  • CrearÁrbol: ! ÁrbolBinario {da como resultado un árbol binario vacío}

  • ConstruirÁrbol: ÁrbolBinario x nodos x ÁrbolBinario ! ÁrbolBinario

  • Ejemplo:

    <vacio> + 3 + <vacio> !

    (<vacio> + 3 + <vacio>) + 2 + <vacio> !

    A partir de dos árboles y un nodo de TipoBase se obtiene un nuevo árbol binario en el que cada uno de los árboles originales pasan a ser los subárboles izquierdo y derecho y el valor de tipobase se almacena en el NodoRaíz.

  • ÁrbolVacío: ÁrbolVacío ! Booleano

  • HijoDerecho: ÁrbolBinario ! ÁrbolBinario

  • HijoIzquierdo: ÁrbolBinario ! ÁrbolBinario

  • DatoRaíz: ÁrbolBinario ! TipoBase

  • Axiomas: " a1, a2 " ÁrbolBinario, "n " TB

  • ÁrbolVacío ( CrearÁrbol) = cierto

  • ÁrbolVacío (ConstruirÁrbol (a1, n, a2)) = falso

  • HijoIzquierdo (CrearÁrbol) = error

  • HijoIzquierdo (ConstruirÁrbol (a1, n, a2)) = a1

  • HijoDerecho (CrearÁrbol) = error

  • HijoDerecho (ConstruirÁrbol (a1, n, a2)) = a2

  • DatoRaíz (CrearÁrbol) = error

  • DatoRaíz (ConstruirÁrbol (a1, n, a2)) = n

  • 5.2.2.- Implementación

    La implementación de árboles se hará exclusivamente con punteros.

    TArbol = Puntero a Nodo;

    Nodo = REGISTRO DE

    info: TipoBase;

    izq, der: TArbol

    FINREGISTRO;

    Para trabajar con un árbol tenemos que conocer el puntero al NodoRaíz del árbol.

    ALGORITMO CrearArbol (SAL a: TArbol);

    INICIO

    a ! NIL

    FIN;

    ALGORITMO ArbolVacio (ENT a: TArbol): Booleano;

    INICIO

    ArbolVacio ! (a=NIL)

    FIN;

    ALGORITMO ConstruirArbol (ENT hi, hd: TArbol; x: TB; SAL a: TArbol);

    INICIO

    New(a);

    a^.info ! x;

    a^.izq ! hi;

    a^.der ! hd

    FIN;

    ALGORITMO HijoIzquierdo (ENT a: TArbol; SAL hi: TArbol; error: Booleano);

    INICIO

    error ! cierto;

    SI NO(ArbolVacio (a)) ENTONCES

    error ! falso;

    hi ! a^.izq

    FINSI

    FIN;

    ALGORITMO HijoDerecho (ENT a: TArbol; SAL hd: TArbol; error: Booleano);

    INICIO

    error ! cierto;

    SI NO(ArbolVacio (a)) ENTONCES

    error ! falso;

    hd ! a^.der

    FINSI

    FIN;

    ALGORITMO DatoRaiz (ENT a: TArbol; SAL x: TipoBase; error: Booleano);

    INICIO

    error ! cierto;

    SI NO(ArbolVacio(a)) ENTONCES

    error ! falso;

    x ! a^.info

    FINSI

    FIN;

    {implementaciones complementarias sin control de error}

    ALGORITMO ConstruirArbol (ENT hi, hd: TArbol; x:TipoBase); TArbol;

    VARIABLES

    nuevo: TArbol;

    INICIO

    new (nuevo);

    nuevo^.info ! x;

    nuevo^.izq ! hi;

    nuevo^.der ! hd;

    ConstruirArbol ! nuevo

    FIN;

    ALGORITMO HijoIzquierdo (ENT a: TArbol): TArbol;

    INICIO

    HijoIzquierdo ! a^.izq

    FIN;

    ALGORITMO HijoDerecho (ENT a: TArbol): TArbol;

    INICIO

    HijoIzquierdo ! a^.der

    FIN;

    ALGORITMO DatoRaíz (ENT a: TArbol): TipoBase;

    INICIO

    DatoRaíz ! a^.info

    FIN;

    5.2.3.- Recorrido de un Árbol Binario

    Realizar un recorrido de un árbol equivale a realizar la operación que permite acceder una única vez a al información de cada uno de los nodos del árbol.

    • PREORDEN: Se accede a la información del NodoRaíz después a la de los nodos del subárbol izquierdo y dinalmente a la de los nodos del subárbol derecho.

    • INORDEN: Se accede a la información del los nodos del subárbol izquierdo, después a la información del NodoRaíz, y finalmente a la información del subárbol derecho.

    • POSTORDEN: Se accede a la información de los nodos del subárbol izquierdo, después a la información del los nodos del subárbol derecho y por último a la información del NodoRaíz.

    ALGORITMO PreOrden (ENT a: TArbol {...});

    VARIABLES

    {...}

    INICIO

    SI NO(ArbolVacio (a)) ENTONCES

    ...

    Procesar (DatoRaiz (a));

    PreOrden (HijoIzquierdo (a));

    PreOrden (HijoDerecho (a))

    ...

    { SINO

    }

    FINSI

    FIN;

    ALGORITMO InOrden (ENT a: TArbol {...});

    VARIABLES

    {...}

    INICIO

    SI NO(ArbolVacio (a)) ENTONCES

    ...

    InOrden (HijoIzquierdo (a));

    Procesar (DatoRaiz (a));

    InOrden (HijoDerecho (a))

    ...

    { SINO

    }

    FINSI

    FIN;

    ALGORITMO PostOrden (ENT a: TArbol {...});

    VARIABLES

    {...}

    INICIO

    SI NO(ArbolVacio (a)) ENTONCES

    ...

    PostOrden (HijoIzquierdo (a));

    PostOrden (HijoDerecho (a))

    Procesar (DatoRaiz (a));

    ...

    { SINO

    }

    FINSI

    FIN;

    ALGORITMO Imprimir_Pre (ENT a: TArbol);

    INICIO

    SI NO(ArbolVacio (a)) ENTONCES

    Escribir (DatoRaiz (a));

    Imprimir_Pre (HijoIzquierdo (a));

    Imprimir_Pre (HijoDerecho (a))

    FINSI

    FIN;

    ALGORITMO Imprimir_In (ENT a: TArbol);

    INICIO

    SI NO(ArbolVacio (a)) ENTONCES

    Imprimir_In (HijoIzquierdo (a));

    Escribir (DatoRaiz (a));

    Imprimir_In (HijoDerecho (a))

    FINSI

    FIN;

    ALGORITMO Imprimir_Post (ENT a: TArbol);

    INICIO

    SI NO(ArbolVacio (a)) ENTONCES

    Imprimir_Post (HijoIzquierdo (a));

    Imprimir_Post (HijoDerecho (a))

    Escribir (DatoRaiz (a));

    FINSI

    FIN;

    5.3.- Árboles Binarios de búsqueda

    Definición:

    Árbol Binario en el que el valor de todos los elementos del subárbol izquierdo es menor o igual que el valor del elemento del nodoraíz que a su vez es menor que el valor de todos los elementos del subárbol derecho.

    Operaciones:

  • CrearArbol: ! TArbol

  • ArbolVacio: TArbol ! Booleano

  • BuscarNodo: TArbol x TipoBase ! TArbol

  • InsertarNodo: TArbol x TipoBase ! TArbol

  • EliminarNodo: TArbol x TipoBase ! TArbol

  • E4

    E3

    E2

    E1

    E1

    E2

    E3

    E4

    E5

    E4

    E3

    E2

    E1

    E1

    E2

    E3

    Tope=E3

    Tope=E4

    Tope=E4

    Tope=E5

    Borrar

    Borrar

    Añadir

    r

    r

    s

    r

    s

    t

    r

    s

    E4

    r

    E3

    E2

    E1

    tope

    E1

    E2

    E3

    E1

    E2

    E3

    E4

    E1

    E2

    E3

    encolar

    desencolar

    cabeza

    cabeza

    cabeza

    fin

    fin

    fin

    valor4

    valor3

    valor2

    valor1

    long=4

    final

    cabeza

    cabeza

    fin

    v1

    v2

    v3

    fin

    cabeza

    v1

    aux

    aux

    LISTA "

    TOPE

    CABEZA

    FIN

    punto de acceso imprescindible

    lista simplemente enlazada " primero

    lista doblemente enlazada " cualquier elemento

    lista circular " cualquier elemento

    primero

    último

    longitud

    3

    7

    10

    15

    8

    i=8

    3

    2

    3