DATOS. TIPOS LINEALES TEMA 3: TIPOS ABSTRACTOS DEusers.dsic.upv.es/~erodri/tema3.pdf · 3.2 Definición y especificación de tipos lineales Pilas Colas ... de datos lineales: listas,

ADII 98/99. Tema 3: Tipos Abstractos de Datos. Tipos Lineales.

1

TEMA 3: TIPOS ABSTRACTOS DEDATOS. TIPOS LINEALES

ÍNDICE.

3.1 Tipos Abstractos de Datos (TAD´s)� Especificación e Implementación

� Programación con TADs

� Ejemplo: Números complejos

3.2 Definición y especificación de tipos lineales� Pilas

� Colas

� Listas con punto de interés

3.3 Implementaciones de los tipos lineales� Asignación dinámica de memoria. Punteros

� Implementaciones del tipo Pila

� Implementaciones del tipo Cola

� Implementaciones del tipo Lista con punto de interés


2

OBJETIVOS.

� Reforzar a través de la definición de abstracción de datos lasdiferencias entre especificación (TAD) e implementación de unaabstracción.

� Estudiar los tipos (abstractos) de datos lineales: listas, pilas ycolas. Analizar sus distintas implementaciones (representación delos datos y diseño de los algoritmos de manejo).

� Estudiar los mecanismos de asignación dinámica de memoria y eltipo puntero.

� Estudiar algunas aplicaciones concretas de estas estructuras dedatos.

BIBLIOGRAFÍA .

� Aho, Hopcroft, Ullman. “Estructuras de Datos y Algoritmos.”Addison Wesley Iberoamericana, 1988 (edición en inglés de 1983).Capítulo1, capítulo 2 (apartados 1, 2, 3 y 4).

� Franch X. “Estructura de Dades. Especificació, disseny iimplementació”. Edicions UPC, 1993. Capítulos 3 y 7.


3

3.1 TIPOS ABSTRACTOS DE DATOS (TADS).

��Un grupo de operaciones que actúan sobre un mismo tipo dedatos (conjunto de valores)��Con la restricción de que el comportamiento de estas operacionesdefine al tipo.

“Lo interesante de un tipo de datos NO es tanto los valores que lo constituyeny MUCHO MENOS su representación concreta, como la clase de

manipulaciones a las que se le puede someter o las propiedades quesatisface” (F. Orejas).

Ejemplos de abstracción de datos:

1.- Tipos elementales de un lenguaje de programación. La definición de laabstracción de datos entero sería:

entero

+

-

*

IMP

LEM

EN

TA

CIO

N

2.- Los tipos definidos por el usuario no tienen operadores predefinidos. Sedeben definir como (sub)algoritmos. Definición de la abstracción de datosconjunto:

conjunto

U

-

IMP

LEM

EN

TA

CIO

N

U


4

ESPECIFICACIÓN E IMPLEMENTACIÓN DE TADS

Como ocurre con toda abstracción, tanto de operaciones como dedatos, debemos distinguir dos niveles en su DISEÑO:

1.- Especificación o definición ¿qué es? o ¿qué hace? laabstracción. Esta definición puede ser formal o informal.

Ejemplo: Especificación de una abstracción de operacionesmediante su pre/postcondición expresadas mediante el lenguajelógico de primer orden.

2.- Implementación o ¿Cómo es? o ¿Cómo lo hace? en undeterminado entorno informático.

Ejemplo: Implementación de una abstracción de operacionesmediante las “function” y “procedure” de los lenguajes deprogramación.

La ESPECIFICACIÓN DE UN TIPO DE DATOS debe incluir:

� Nombre del tipo [parámetro1, ... , parámetron]

� Lista de operaciones sobre el tipo: sintaxis o perfil de lasoperaciones. Se dará como cabecera de procedimiento o función

� Semántica de las operaciones sobre el tipo: precondición ypostcondición


5

PROGRAMACIÓN CON TADS

VENTAJAS:

� Independencia de la implementación del tipo.� Programas más portables, legibles, reutilizables.� Mayor seguridad de la información, menos efectos

colaterales.� Mayor facilidad para comprobar la corrección.

TADs y Lenguajes de Programación:

� Los lenguajes de programación posteriores al 1975 soportanel concepto de TAD (Ej. ADA, Modula-2, C++)

� Si el lenguaje no permite el diseño basado en TADs seránecesario suplir esta insuficiencia con una disciplina en suuso: usar sólo las posibilidades del mismo que no violen losprincipios de ocultamiento establecidos en el diseño (Ej.PASCAL, C, FORTRAN, COBOL)


6

EJEMPLO : NÚMEROS COMPLEJOS

Para poder resolver problemas en los que se utilizan númeroscomplejos se define el tad número complejo mediante:

- una representación posible (forma cartesiana)- operaciones de transformación de tipos:

- creaC, crea un complejo a partir de dos reales- prealC, obtiene la parte real de un complejo- pimgC, obtiene la parte imaginaria de un complejo

- operaciones aritméticas entre complejos:- sumaC, restaC, multC, divsnC y módC

Especificación del Tad Número complejo

TIPO complejo

SINTAXISfunción creaC(pr,pi:real):complejo;función prealC(c:complejo):real;función pimagC(c:complejo):real;función sumaC(c1,c2:complejo):complejo;función restaC(c1,c2:complejo):complejo;función multC(c1,c2:complejo):complejo;función divsnC(c1,c2:complejo):complejo;función módC(c:complejo):real;

SEMÁNTICA


7

{ pr=PR � pi=PI }c:=creaC(pr,pi)

{ c=(PR + PIi) }

{ c = (A + Bi) }r :=prealC(c)

{ r = A }

{ c = (A + Bi) }r :=pimagC(c)

{ r = B }

{ c1 = (A + Bi) � c2 = (C + Di) }c3:=sumaC(c1,c2)

{ c3 =(A+C) + (B+D)i }

{ c1 = (A + Bi) � c2 = (C + Di) }c3:=restaC(c1,c2)

{ c3 =(A-C) + (B-D)i }

{ c1 = (A + Bi) � c2 = (C + Di) }c3:=multC(c1,c2)

{ c3 =(AC-BD) + (AD+BC)i }

{ c1 = (A + Bi) � c2 = (C + Di) � c2 � (0 + 0i) }c3:=divsnC(c1,c2)

{ c3 =[(AC+BD)/(C²+D²)] + [(BC-AD) /(C²+D²)] i }

{ c = (A + Bi) }r :=módC(c)

{ r = raíz(A²+B²) � 0�r }


8

Implementación del Tad Número complejo

Como se sigue la representación cartesiana de los númeroscomplejos, se representarán mediante una tupla con doscomponentes:

Tipo: complejo = tupla preal: real; pimag: real;

ftupla

Operaciones:{ pr=PR � pi=PI }función creaC(pr,pi:real): complejo;

var c:complejo fvarc.preal:=pr; c.pimag:=pi;devuelve(c)

ffunción{ creaC(pr,pi)=(PR + PIi) }

{ c = (A + Bi) }función prealC(c:complejo):real;

devuelve(c.preal)ffunción{ prealC(c)= A }

{ c = (A + Bi) }función pimagC(c:complejo):real;

devuelve(c.pimag)ffunción{ pimagC(c) = B }

{ c1 = (A + Bi) � c2 = (C + Di) }


9

función sumaC(c1,c2:complejo):complejo;var c3:complejo fvar

c3.preal:=c1.preal + c2.preal;c3.pimag:=c1.pimag + c2.pimag;devuelve(c)

ffunción{ sumaC(c1,c2) =(A+C) + (B+D)i }

{ c1 = (A + Bi) � c2 = (C + Di) }función restaC(c1,c2:complejo):complejo;var c3:complejo fvar

c3.preal:=c1.preal - c2.preal;c3.pimag:=c1.pimag - c2.pimag;devuelve(c)

ffunción{ restaC(c1,c2) =(A+C) - (B+D)i }

{ c1 = (A + Bi) � c2 = (C + Di) }función multC(c1,c2:complejo):complejo;var c3:complejo fvar

c3.preal:=c1.preal*c2.preal - c1.pimag*c2.pimag;c3.pimag:=c1.preal*c2.pimag + c2.preal*c1.pimag;devuelve(c)

ffunción{ multC(c1,c2) =(AC-BD) + (AD+BC)i }


10

{ c1 = (A + Bi) � c2 = (C + Di) � c2 � (0 + 0i) }función divsnC(c1,c2:complejo):complejo;var c3:complejo; aux:real fvar

aux:=c2.preal*c2.preal + c2.pimag*c2.pimag;c3.preal:=(c1.preal*c2.preal + c1.pimag*c2.pimag)/aux;c3.pimag:=(c2.preal*c1.pimag - c1.preal*c2.pimag)/aux;devuelve(c3)

ffunción{divsnC(c1,c2)=[(AC+BD)/(C²+D²)]+[(BC-AD) /(C²+D²)]i}

{ c = (A + Bi) }función módC(c:complejo):real;

devuelve(raíz(c.preal*c.preal+c.pimag*c.pimag)){ módC(c) = raíz(A²+B²) � 0�r }

Una vez definido el tad número complejo, se tiene:

- Es posible utilizar el tipo complejo para efectuar nuevasdefiniciones, de forma similar a como se haría con losrestantes tipos numéricos.

- Las únicas operaciones permitidas sobre datos de tipocomplejo son las definidas en el tad del mismo.

- Los algoritmos que utilicen el tad complejo no dependende la representación interna de dicho tipo, ni de laimplementación que se haya efectuado de las operaciones.


11

Ejemplo: utilización del tad complejo

En teoría de circuitos es habitual utilizar matrices de númeroscomplejos para representar circuitos eléctricos en los queaparecen elementos inductivos o capacitivos.

En el estudio de dichos circuitos se utilizan operacionesalgebraicas como el producto matricial, entre otras, así:

dadas A,B�Cnxn ;se desea calcular M�Cnxn, tal que M=A*B

TipoMatrizC : Vector[1..N,1..N] de complejo;

{a=A � b=B }procedimiento prodMC( a,b: MatrizC; var m: MatrizC);var i,j,k: entero fvar

Para i:=1 hasta N hacerPara j:=1 hasta N hacer

m[i,j]:=creaC(0,0); /* se asigna el neutro*/Para k:=1 hasta N hacer

m[i,j]:=sumaC(m[i,j], multC(a[i,k],b[k,j]));fpara

fparafpara

fprocedimiento{ m= A*B }


12

3.2 DEFINICIÓN Y ESPECIFICACIÓN DE TIPOS LINEALES

PILAS

Una abstracción de datos Pila es una estructura LIFO (del inglésLast-In First-Out, o "el último que entra es el primero que sale"):

��

Los elementos se insertan de uno en uno y se recuperan también deuno en uno, en orden inverso a como se han introducido.

Se caracteriza por las siguientes operaciones:

creap(p): crea una pila vacíaapilar(p,v): añade el elemento v en la pila pdesapilar(p): saca un elemento de la pilatopep(p): consultar el tope de la pilavaciap?(p): decidir si la pila está vacia

Ejemplos: utilización de pilas en el diseño de algoritmos

� Gestión de las direcciones de retorno que hace el sistema en lasllamadas a procedimientos en un programa.

� Evaluación de expresiones.� Transformación de algunas clases de funciones recursivas eniterativas.


13

Especificación de PILA o TAD PILA

TIPO pila [elemento]SINTAXISprocedimiento creap(sal p:pila);procedimiento apilar(ent/sal p:pila; v:elemento);procedimiento desapilar(ent/sal p:pila);función topep(p:pila) devuelve elemento;función vaciap?(p:pila) devuelve lógico;

SEMÁNTICA

{}creap(p){p=}

{p=P1 P2.. Pn � v=V }apilar(p,v){p=P1 P2.. Pn V}

{p=P1 P2.. Pn ��p<>}desapilar(p){p=P1 P2.. Pn-1}

{p=P1 P2.. Pn ��p<>}e:=topep(p){ p=P1 P2.. Pn ��e= Pn}

{ p=P1 P2.. Pn }b:=vaciap?(p){ p=P1 P2.. Pn ��b=(p=)}


14

COLAS

Una Cola es una estructura FIFO (First-In First-Out o “el primeroque entra es el primero que sale”).

Las inserciones se realizan por un extremo y las extracciones por elotro; el elemento que se puede consultar en todo momento es el queprimero se insertó.

Se caracteriza por las siguientes operaciones:

creaq: crea una cola vacíaencolar(q,e): inserta un elemento en la coladesencolar(q): elimina el primer elemento de la colaprimero(q): obtiene el primer elemento de la colavaciaq?(q): devuelve CIERTO si la cola está vacía y FALSO encaso contrario

Ejemplo de aplicación:La asignación de CPU a procesos de usuarios que realiza el sistemaoperativo con una política round-robin sin prioridades:los procesosque solicitan el procesador se encolan de forma que cuando acabael que se está ejecutándose actualmente pasa a ejecutarse el quelleva mas tiempo esperando.


15

Especificación de COLA o TAD COLA

TIPO cola [elemento]

SINTAXISprocedimiento creaq (e/s q:cola);procedimiento encolar (e/s q:cola; e:elmento);procedimiento desencolar (e/s q:cola);función primero (q:cola) devuelve elemento;función vaciaq? (q:cola) devuelve lógico;

SEMÁNTICA{}creaq(q){q=}

{q=Q1 Q2 .. Qn � e=E}encolar(q,e){q=Q1 Q2 .. Qn E}

{q=Q1 Q2 .. Qn ��q<>}desencolar(q){q=Q2 .. Qn }

{q=Q1 Q2 .. Qn ��q<>}e:=primero (q){ q=Q1 Q2 .. Qn ��e = Q1 }

{ q=Q1 Q2 .. Qn }b:=vaciaq?(q){ q=Q1 Q2 .. Qn ��b=(q=�}


16

3.2.3 LISTAS CON PUNTO DE INTERÉS

Una lista es una secuencia de elementos de un tipo dado, ordenadoslinealmente según la posición que ocupan en la misma.

Una lista con punto de interés es una lista que tiene una posiciónespecial, o distinguida, sobre la que se aplican las distintasoperaciones.

La posición distinguida, o punto de interés, se puede cambiar, con loque es posible operar sobre los distintos elementos de la lista.

La lista con punto de interés se caracteriza por tres tipos deoperaciones:

Operaciones para manipular el contenido:

creal(l): crea una nueva lista vacía.inserta(l,e): inserta el elemento e en la lista l en la posicióninmediatamente anterior a la distinguida.suprime(l): elimina el elemento que está en la posición distinguidade la lista l.recupera(l): devuelve el elemento que está en la posicióndistinguida de la lista l.

Operaciones para cambiar el punto de interés:

principio(l): sitúa el punto de interés de la lista l al principiofin(l): sitúa el punto de interés de la lista l al finalsiguiente(l): cambia el punto de interés de la lista l de la posiciónque ocupa a la siguiente.

Operaciones para consultar el estado de la lista:


17

esvacial(l): devuelve CIERTO si la lista l está vacía y FALSO encaso contrario.esfin(l): devuelve CIERTO si el punto de interés de la lista l esposterior al último elemento y FALSO en caso contrario.

Especificación del Tad Lista con punto deinterés

TIPO lista[elemento]

SINTAXIS

procedimiento creal (sal l:lista);procedimiento inserta (ent/sal l:lista; e:elemento);procedimiento suprime (ent/sal l:lista);función recupera (l:lista) devuelve elemento;procedimiento principio (ent/sal l:lista);procedimiento fin (ent/sal l:lista);procedimiento siguiente (l:lista);función esvacial (l:lista) devuelve lógico;función esfinl (l:lista) devuelve lógico;

SEMÁNTICANotación utilizada:- l = L1L2..Ln ��0�n, donde n=0 equivale a l=,- pos, 1�pos�n+1,es la posición del punto de interés.

{}creal(l)


18

{l =�� pos=1}

{l =L 1L2..Ln � pos=i � 1�pos�n+1�� e=E }inserta(l,e){l=L’ 1L’ 2...L

’n+1�(L’ 1=L1...L’ i-1=Li-1)�L’ i=E�(L’ i+1=Li...L’n+1=Ln)�pos=i+1}

{l =L 1L2...Ln � pos=i � 1�pos�n }suprime(l){l=L’ 1 L’ 2...L

’n-1 �(L’ 1=L1...L’ i-1= Li-1)�(L’ i=Li+1...L’n-1= Ln)� pos=i }

{l = L 1L2...Ln � 1�pos�n }e:=recupera(l){l = L 1L2...Ln � e=Lpos}

{l=L 1 L2...Ln � 0�n}principio(l){l=L 1L2...Ln � pos=1}

{l=L 1L2...Ln � 0�n}fin(l){l=L 1L2...Ln � pos=n+1}

{l=L 1L2...Ln ��1�pos�n � pos=i}siguiente(l){ l=L 1L2...Ln ��pos=i+1}

{l=L 1L2...Ln � 0�n}b:=esvacial(l){b=(n=0)}

{l=L 1L2...Ln � 0�n}b:=esfin(l){b=(pos=n+1)}

Ejemplos de utilización del TAD lista conpunto de interés


19

1.- Tratamiento de todos los elementos de una lista l:

{ l=L 1L2...Ln � 0�n }procedimiento recorrer(ent l:lista)

var e:elemento fvar;

primero(l);

mientras no esfin(l) hacer

e:=recupera(l); tratar(e);

siguiente(l);

fmientras;

fprocedimiento{ l=L 1L2...Ln � �i:1�i�n:tratar(Li) }

Ejercicios propuestos:

-Dada la lista l, crear la lista l’ con el mismo contenido que l

-Dada la lista l, borrar todos sus elementos

-Dadas las listas l y l’, obtener l’’ concatenación de l y l’


20

2.-¿Existe en l un elemento que cumple la propiedad P?

{ l=L 1L2...Ln � 0�n }función búsqueda(l:lista): lógico

var enc: lógico; e:elemento fvar

enc:=falso; primero(l);

mientras (no esfinl(l)) y (no enc) hacer

e:=recupera(l);

si P(e) entonces enc:=cierto

sino siguiente(l) fsi

fmientras;

devuelve(enc)

ffunción

{ búsqueda(l) l=L1L2...Ln � �i:1�i�n:P(Li) }

Ejercicios propuestos:

-Obtener la posición del primer elemento de l que cumple P

-Obtener la posición del último elemento de l que cumple P

-¿Todos los elementos de l, cumplen la propiedad P?


21

3.3 IMPLEMENTACIÓN DE TIPOS LINEALES .

1.- Representación vectorial: Los elementos de la estructurase almacenan en un vector de forma que elementosconsecutivos en la pila ocupan posiciones consecutivas en elvector (array ).

2.- Representación enlazada: Se rompe la propiedad derepresentación secuencial y se introduce el concepto deenlace: todo elemento de la estructura identificaexplícitamente la posición que ocupa su sucesor en la misma.La estructura se puede almacenar en un vector o gestionarladinámicamente utilizando punteros.


22

ASIGNACIÓN DINÁMICA DE MEMORIA . PUNTEROS

EL TIPO PUNTERO EN PASCAL

Se caracteriza por su bajo nivel de abstracción debido a queesta muy próximo a la organización de la información en lamemoria central de un ordenador.

Es un tipo de datos elemental cuyo dominio está compuesto pordirecciones de memoria con tipo. El tipo de estas variables sellama Tipo Puntero a un tipo de datos dado T.

No existe un tipo puntero único como ocurre en los otros tiposde datos básicos, sino tipos punteros a tipos de datos.


23

Definición de una variable de tipo puntero-a:VAR nombre_de_variable : �T;

var ......

I : T ;PtoI : �T;

p p+1 p+2 p+n-1

La variable I es de tipo T y la variable PtoI es de tipo puntero aun valor de tipo T que ocupa n posiciones de memoria a partirde la posición p.

Ejemplo: Var I : integer;PtoI, ptoJ : ˆ integer;

VALOR NULO DE LOS TIPOS PUNTERO-A (polimorfismo)

Para todos los conjuntos de valores de los tipos puntero-a, existeun valor que representa la dirección de memoria nula: NIL.

Ejemplo: Var p1: ̂ T1;p2: ̂ T2; /*Donde T1 � T2*/

p1 := Nil;p2 := Nil;

Los tipos de p1 y p2 son puntero a T1 y puntero a T2. Son dostipos diferentes a los que se le asigna un valor nulo diferente paracada tipo pero con la misma representación (NIL).


24

VARIABLES DINÁMICAS

En el lenguaje Pascal existen dos clases de variables según elmomento en el que se asigna memoria para poder guardar unvalor:- Una variable es estática si la asignación de memoria se

realiza durante el análisis estático (compilación)- Una variable es dinámica si la asignación de memoria se

realiza durante la ejecución del programa.

Para la asignación de memoria a una variable dinámica elprograma en ejecución dispone de dos zonas de memoria:

� La Pila: se utiliza para asignar memoria a los parámetros ylas variables locales de funciones y procedimientos.

� El Heap: se utiliza para asignar memoria al resto devariables dinámicas.

ASIGNACIÓN Y LIBERACIÓN DE MEMORIA

Las variables dinámicas sólo utilizan memoria durante laejecución de un programa, por lo que se hace necesario unmecanismo que permita el proceso de asignación y liberaciónde memoria.

Para la pila de ejecución este proceso es automático en ellenguaje Pascal.

Para la gestión del Heap, Pascal proporciona una primitivas quepermiten que el proceso de asignación y liberación de memorialo determine el propio programador.


25

Primitivas para la obtención y liberación de memoria:

A la obtención de memoria para una variable dinámica sedenomina CREACIÓN DE UNA VARIABLE DINÁMICA:

Primitiva: NEW(pto)Var pto : ˆ T;

new(pto);

new(pto) reserva la memoria suficiente en el heap para guardarla representación binaria de un valor de tipo T. En la variablepto se almacena la dirección a la celda de memoria a partir dela cual se puede almacenar un valor de tipo T.

pto

Heap

.....

p p+1 p+2 p+n-1

- La variable pto contiene la dirección p- Son necesarias n celdas para guardar la representación binaria de un valor de tipo T.


26

A la liberación de la memoria utilizada por una variabledinámica se denomina BORRADO DE UNA VARIABLEDINÁMICA.

Primitiva: DISPOSE(pto)pto

Heap

.....

p p+1 p+2 p+n-1

El procedimiento dispose libera el uso de la memoria del heaputilizada para guardar un valor de tipo T.

dispose(pto)pto

Heap ¿?

.....

p

La memoria liberada por dispose queda disponible para nuevasdemandas de memoria.La variable puntero que apunta a una variable dinámica que hasido borrada pasa a contener un valor indefinido.


27

ACCESO A LOS VALORES DE UN VARIABLE DINÁMICA

A una variable dinámica se accede a través de la dirección apartir de la cual esta guardado su valor, es decir, utilizando unpuntero que la apunta. El operador de acceso a una variabledinámica es: �

Var pto : �T;

beginnew(pto);pto�:= <valor>;

Donde <valor> es un dato de tipo T.

Ejemplo:Program ejemplo (input,output);

Var p: �integer;I:integer;

beginI:=5;New(p);p�:=I;writeln(p �);p�:= p �+1;writeln(p �);

end.

Este programa produce los valores 5 y 6 en su salida estándar.


28

EJEMPLOS DE USO

Var

pto1, pto2, pto3: �integer;

begin

new(pto1);new(pto2);{ pto1 � pto2 }

pto1�:= 1;pto2�:= 2;{pto1� = 1 � pto2� = 2 � pto1 � pto2 }

pto3 := pto1;{pto1�=1�pto2�=2�pto3�=1�pto1�pto2�pto1�pto3 � pto2� pto3}

pto1�:= pto2�;{pto1�=2�pto2�=2�pto3�=2�pto1�pto2�pto1�pto3 � pto2� pto3}

dispose(pto3);{pto2�=2�pto1=indefinido� pto3=indefinido}

end.


29

IMPLEMENTACIÓN DE UNA PILA .

Representación vectorial

P1 P2 ... Pn �

tope

� Apilar un elemento:P1 P2 ... Pn V

� tope

� Desapilar un elemento:P1 P2 ... Pn-1 Pn

� tope

tipo pila = tupladatos: vector [1..MaxP] de elemento;tope: Natural;

ftupla

� Si p es de tipo pila, la información está en p.datos[1..p.tope]

{}procedimiento creap (sal p:pila)

p.tope := 0

fprocedimiento{p=}


30

{p = P1 P2.. Pn � v = V }procedimiento apilar (ent/sal p: Pila; v: elemento)

si p.tope<MaxP entonces

p.tope := p.tope + 1; p.datos[p.tope]:=v

sino error(‘La pila está llena’)

fprocedimiento{p = P1 P2.. Pn V}

{p = P1 P2.. Pn��p <> }procedimiento desapilar (ent/sal p: Pila)

p.tope := p.tope - 1

fprocedimiento{p = P1 P2.. Pn-1}

{p = P1 P2.. Pn ��p <> }función topep (p: Pila) devuelve elemento

devuelve p.datos[p.tope]

ffunción{ p = P1 P2.. Pn ��topep(p) = Pn}

{ p = P1 P2.. Pn }función vaciap? (p:Pila) devuelve Lógico

devuelve (p.tope = 0)

ffunción{ p = P1 P2.. Pn ��vaciap?(p) = (p = )}

� El coste temporal de las operaciones es óptimo, �(1)� El coste espacial es �(MaxP) independientemente del número deelementos que la formen.


31

Representación enlazada usando variabledinámica

tipo pila = �Nodo

Nodo = tupladato: elemento;sig: pila;

ftupla;

{}procedimiento creap (sal p: pila)

p := nil

fprocedimiento{p=}

{p = P1 P2.. Pn � v = V }procedimiento apilar (ent/sal p: pila;v: elemento)

var nuevo: pila fvar;

new(nuevo); nuevo^.dato := v; nuevo^.sig := p; p := nuevo;

fprocedimiento{p = P1 P2.. Pn V}

{p = P1 P2.. Pn��p <> }procedimiento desapilar (ent/sal p:pila)

var borra:pila;

borra := p; p := p^.sig; dispose(borra);

fprocedimiento{p = P1 P2.. Pn-1}


32

{p = P1 P2.. Pn ��p <> }función topep (p:pila) devuelve elemento

devuelve p^.dato;

ffunción{ p = P1 P2.. Pn ��topep(p) = Pn}

{ p = P1 P2.. Pn }función vaciap? (p:pila) devuelve Lógico

devuelve (p=nil)

ffunción{ p = P1 P2.. Pn ��vaciap?(p) = (p = )}

Estudio comparativo de las implementaciones

• La complejidad temporal de todas las operaciones en ambasrepresentaciones es independiente de la talla del problema.

• En cuanto a complejidad espacial, la implementaciónvectorial presenta el inconveniente de la estimación del tamañomáximo y la reserva de espacio que en muchos casos no seutilizará. La representación enlazada requiere un espacio dememoria adicional para los enlaces.


33

IMPLEMENTACIÓN DE COLAS

Representación vectorial

Los elementos de la cola se distribuyen secuencialmente en unvector; además necesitamos para su representación:

1.- un marcador (“libre”) de la posición donde insertar el siguienteelemento (marcador al primer elemento libre de la cola).

a b c � � libre MaxC

¿qué pasa si desencolamos?

Si el 1er elemento de una cola fuera siempre el que ocupa la 1ªposición del vector, cada operación de borrado, “desencolar”,supondría el desplazamiento del resto de elementos de la cola unaposición hacia la izquierda;

a b c � � libre MaxC

desencolar(q)

b c � � libre MaxC

desplazar(q);

b c� �libre MaxC

¡extremadamente ineficiente!


34

2.- Necesitamos también un marcador de primer elemento de lacola, que llamaremos “prim”

a b c � � � prim libre MaxC

Como consecuencia de tener sólo los marcadores “libre” y “prim”para manejar el vector-cola, es posible que cualquiera de estos dosmarcadores (o ambos) llegen al final del vector (MaxC)

¡SIN QUE LA COLA ESTÉ TOTALMENTE LLENA!

Para poder reutilizar todas las posiciones del vector sin tener quedesplazar elementos, y así llegar a su final con todas sus posicionesocupadas:

Consideraremos el vector como una estructura circular , sinprincipio ni fin, donde después del último elemento va el primero

.....

....

MaxC

1

2

prim

libre

COLA c

COLA_VACIA: prim= libreCOLA_LLENA: prim = libre


35

3. Aún con la estructura circular propuesta NO hay suficienteinformación para decidir si una cola está vacía o no, ya que lacondición de cola vacía es la misma que la de cola llena. Por tanto,además de la estructura circular con dos marcadores, el vector-colanecesita de un tercer marcador: el indicador de cola vacía o llena.Hemos implementado este indicador como un contador deelementos de la cola.

Representación vectorial circulartipo

cola = tupladatos = vector [1..MaxC] of elemento;prim, libre: Nat;long: Nat;

ftupla

Si q es de tipo cola, la información está en

q.datos[q.prim..q.libre-1]

.....

....

MaxC

1

2

c.prim

c.libre

COLA c

COLA_VACIA: (c.prim = c.libre) � (c.long = 0)COLA_LLENA: (c.prim = c.libre) � (c.long �MaxC)


36

{}procedimiento creaq (e/s q:cola)

q.pri:= 1; q.libre:= 1; q.long:=0;

fprocedimiento{q = }

{ q=Q1 Q2 .. Qn � e=E }procedimiento encolar (e/s q:cola; e:elemento)

si q.long<MaxC entonces

q.elementos[q.libre]:=e;

q.libre:=siguiente(q.libre);

q.long:=q.long+1

sino error (‘Cola llena’)

fprocedimiento{q=Q1 Q2 .. Qn E}}

{q=Q1 Q2 .. Qn � q � }procedimiento desencolar (e/s q:cola)

q.pri:=siguiente(q.pri);

q.long:=q.long-1;

fprocedimiento{q=Q2 .. Qn }

{q=Q1 Q2 .. Qn � q � }función primero (q:cola) devuelve elemento

devuelve q.datos[q.pri]

fprocedimiento{ q=Q1 Q2 .. Qn � primero(q) = Q1}


37

{ q=Q1 Q2 .. Qn }función vaciaq? (q:cola) devuelve lógico;

devuelve (q.long=0)

ffunción{ q=Q1 Q2 .. Qn � b=(q=�}

Función privada de la implementación de la cola

{1 ��i ��MaxC}función siguiente (i:Nat) devuelve Nat

devuelve (i mod MaxC) + 1

ffunción{(1 ��i ��MaxC ��siguiente(i) = i+1)

�i = MaxC ��siguiente(i) = 1)}

� El coste temporal de las operaciones es �(1) .


38

Representación enlazada usando variable dinámica.Ejercicio.

Implementar el TAD COLA utilizando una representaciónenlazada con variables dinámicas.

tipoenlace= �nodo;

cola= tupla prim,ult:enlace; long:nat;ftupla

nodo= tupla dato:elemento; sig:enlace;ftupla

Nota: En este caso el marcador señala al último elemento de lacola y NO al primer elemento libre (como en laimplementación con vector circular).


39

IMPLEMENTACIÓN DE LISTAS CON PUNTO DEINTERÉS

Representación secuencial: Vector en el que los elementosde la lista se almacenan en posiciones contiguas

const MaxL = --;tipo

posición= Natural;

lista= tupla datos: vector [1..MaxL] de elemento; ult, pos: posición;ftupla

datos L1 L2 L3 ... Ln ......1 2 3 � MaxL

ult

No se utiliza apenas, por ser una representación ineficiente,puesto que:

- la operación de inserción supone el desplazamiento (unaposición a la derecha) de todos los elementos posteriores

- la operación de borrado supone el desplazamiento (unaposición a la izquierda) de todos los elementos posteriores


40

Representación enlazada

� Para evitar los desplazamientos de los valores se utiliza unarepresentación enlazada, en la que los elementos no estánalmacenados en el mismo orden que ocupan en la lista.

� Esta representación enlazada requiere guardar junto con cadaelemento la dirección del siguiente elemento de la lista.

� La disposición de los elementos en el vector es irrelevante ydepende sólo de la historia de la estructura y de laimplementación de los algoritmos

Dos posibles implementaciones: Vectores o Variables dinámicas

(a) Utilizando vectoresPara definir listas enlazadas se utiliza un vector de nodos con lainformación del nodo más la posición que ocupa dentro delvector su elemento sucesor.

const Máximo= ---;tipo

posición=Natural ;Nodo= tupla

e:elemento; pos: posición; ftupla

MEMORIA= vector [1.. Máximo] de NODO;

Lista=tupla pri, ult, pos:posición

ftupla;


41

Convención: el último elemento tendrá el 0 como indicador desu sucesor

Obsérvese cómo en esta estructura se puede representar más deuna lista, e incluso otras estructuras.

Ejemplo: lista de enteros = 20,23,25,30,35

1 30 42 20 5 pri3 25 14 35 0 ult5 23 3...

... ...

Máximo

Ejercicio: Implementar las operaciones del tipo Lista con punto deinterés utilizando una representación vectorial enlazada. Para ello,supóngase que se dispone de dos funciones predefinidas,

obten_posnodo(var m:memoria) devuelve posición

libera_nodo(p:posición; var m: memoria)


42

(b) Utilizando variables dinámicas

� Una lista queda representada por una secuencia de nodosenlazados y tres punteros: pri, ult y ant.

� Para mejorar las operaciones de borrado e inserción y facilitar eltratamiento de la lista vacía, el primer nodo de la lista es‘ficticio’, y tiene posición 0.

� pri, puntero al primer nodo existente,� ult, puntero al último nodo� ant, puntero al nodo anterior a la posición distinguida

tipoptr = �Nodo;

Nodo= tupladato:elemento;sig:ptr ;

ftupla

Lista= tuplapri, ult, ant: ptr ;

ftupla

pri ult

L1 L2 L3


43

{}procedimiento creal (e/s l:lista)var aux:ptr fvar

new(aux); aux�.sig:=NIL;l.pri:= aux; l.ult:= aux; l.ant:= aux

fprocedimiento{l =�� pos=1}

{l =L 1L2..Ln � pos=i � 1�pos�n+1�� e=E }procedimiento inserta (e/s l:lista; e:elemento)var q:ptr fvar

new(q); q�.dato:=e; q�.sig:=l.ant�.sig;l.ant�.sig:=q;si l.ant=l.ult entonces l.ult:=q fsil.ant:=q

fprocedimiento{l=L’ 1L’ 2...L

’n+1�(L’ 1=L1...L’ i-1=Li-1)�L’ i=E�(L’ i+1=Li...L’n+1=Ln)�pos=i+1}

{l =L 1L2...Ln � pos=i � 1�pos�n }procedimiento suprime (e/s l:lista)var q:ptr fvar

si l.ant�.sig = l.ult entonces l.ult:= l.ant fsi;q:=l.ant�.sig;l.ant�.sig:=l.ant�.sig�.sig;dispose(q)

fprocedimiento{l=L’ 1 L’ 2...L

’n-1 �(L’ 1=L1...L’ i-1= Li-1)�(L’ i=Li+1...L’n-1= Ln)� pos=i }

{l = L 1L2...Ln � 1�pos�n }función recupera (l:lista) devuelve elemento devuelve (l.ant�.sig�.dato)ffunción{ recupera(l)=Lpos�� l = L1L2...Ln }


44

{l=L 1 L2...Ln � 0�n}procedimiento principio (e/s l:lista);

l.ant:= l.pri;f procedimiento{l=L 1L2...Ln � pos=1}

{l=L 1L2...Ln � 0�n}procedimiento fin (e/s l:lista);

l.ant:= l.ult;ffprocedimiento{l=L 1L2...Ln � pos=n+1}

{l=L 1L2...Ln ��1�pos�n � pos=i}procedimiento siguiente (e/s l:lista);

l.ant:=l.ant�.sig;f procedimiento{ l=L 1L2...Ln ��pos=i+1}

{l=L 1L2...Ln � 0�n}función esvacial (l:Lista) devuelve Lógico

devuelve (l.pri=l.ult)ffunción{ esvacial(l)=(n=0) � l=L1L2...Ln }

{l=L 1L2...Ln � 0�n}función esfinl (l:Lista) devuelve Lógico

devuelve (l.ant=l.ult)ffunción{ esfin(l)=(pos=n+1) � l=L1L2...Ln }


45

Estudio comparativo de las implementaciones de Listas

COMPLEJIDAD TEMPORALSecuencial Enlazada

creal(l) �(1) �(1)inserta(l, x) ��(Nºelem) �(1)suprime(l) ��(Nºelem) �(1)

e:=recupera(l) �(1) �(1)b:=esvacial(l) �(1) �(1)

fin(l) �(1) �(1)primero(l) �(1) �(1)Siguiente(l) �(1) �(1)b:=esfin(l) �(1) �(1)

COMPLEJIDADESPACIAL

�(MaxL) �(Nºelem)

• La asignación enlazada requiere un espacio de memoriaadicional para los enlaces.

• Es fácil insertar o borrar un elemento en cualquier parte deuna lista cuando se usan enlaces, pues solo hay que cambiar dosde ellos. En el caso secuencial esta operación representa ungran consumo de tiempo.

• La representación enlazada facilita la unión de dos listas o suseparación.

• El esquema de enlaces se presta para obtener estructuras máscomplejas que las simples listas lineales

Documents

DATOS. TIPOS LINEALES TEMA 3: TIPOS ABSTRACTOS DEusers.dsic.upv.es/~erodri/tema3.pdf · 3.2 Definición y especificación de tipos lineales Pilas Colas ... de datos lineales: listas,