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

• 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 IIIIIIIIII+II=IIIIII 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. 2

• 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)))) = 3

= 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). 4

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:

5

• 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 6

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). =(, , ..., ); 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');

7

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. = 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 ...

8

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:

9

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. =TABLA [1..n] de CARÁCTER ó =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'

10

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

11

• 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 = CONJUNTO de VARIABLES c: 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 12

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} 13

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) =

14

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 =REGISTRO de :TB1; :TB2; :TB3; ... ... ... ... ... ... ... ... :TBk FINREGISTRO; VARIABLES r: 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

15

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;

16

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 ... ... ... ... ... ... ... ... ... ... ... ...

17

FIN. EN GENERAL, = _______ (normalmente enumerado ó BOOLEANO); =REGISTRO DE id1:TB1; id2:TB2; ... ... ... ... idn:TBn; CASO (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?}

18

• 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 19

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; 20

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

21

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

22

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; 23

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); 24

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;

25

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: 26

• 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:

27

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;

28

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

29

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: ; 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} 30

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: ; 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

31

FINSI; DISPOSE (aux); {q.longitud ! q.longitud −1} FINSI FIN; {fin desencolar} Encolar ALGORITMO Encolar (E/S q: Tcola; ENT i: ); 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 32

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 33

• 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 Insertar

Crear Encolar

Crear Añadir

Modificadoras

Unión Diferencia Intersección

Desencolar

Borrar

Pertenencia Inclusión Igualdad CONVENIOS (para los axiomas)

ColaVacía Cabeza

PilaVacía Tope

De Acceso

• 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); 34

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

35

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

36

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

37

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

38

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

39

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
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. 41

• 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 42

• Á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 43

Ejemplo: + 3 + ! ( + 3 + ) + 2 + ! 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;

44

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;

45

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

46

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 {...});

47

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

48

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

49

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 50

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

51

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

52

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 •

53