Ingeniero Técnico en Informática de Sistemas

Estructura de Datos

Compartir 0 Me sirvió 0 No me sirvió

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

{ 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

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

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

Tope=E3

Tope=E4

Tope=E5

Borrar

Añadir

tope

encolar

desencolar

cabeza

fin

valor4

valor3

valor2

valor1

long=4

final

cabeza

fin

cabeza

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

i=8

Tal vez te pueda interesar:

Descargar

Enviado por:	Antonio Vidal
Idioma:	castellano
País:	España

Te va a interesar