TEMA 2:MEMORIA DINÁMICA

yPUNTEROS

Departamento de InformáticaUniversidad de Valladolid

Campus de Segovia______________________

Prof. José Vicente Álvarez Bravo

MEMORIA DINÁMICA yPUNTEROS

•Introducción•Conceptos básicos•Definición y declaración de punteros•Creación y destrucción de variablesdinámicas.•Operaciones básicas con datosreferenciados•Operaciones básicas con punteros•El valor nil•Aplicaciones no recursivas de lospunteros

INTRODUCCIÓN

• Las estructuras de datos hasta ahora vistasse almacenan estáticamente en la memoriafísica del ordenador.

– El espacio de memoria se reserva con anticipación yno cambia durante la ejecución del programa*.

– Esto permite una comprobación de tipos en tiempode compilación.

• Inconvenientes de la configuraciónestática:

– Su rigidez, ya que estas estructuras no puedencrecer o menguar durante la ejecución delprograma.

* Esto no implica que la cantidad de memoria de ejecución de un programa seaconstante, ya que dependerá del numero de subprogramas recursivos invocadospor el programa.

INTRODUCCIÓN

• La definición y manipulación de estosobjetos se realiza en Pascal mediante lospunteros (variables cuyo contenido sonposiciones de memoria).

• Ventaja frente a las estructuras estática:– La flexibilidad que poseen las estructuras

dinámicas en cuanto a las formas que puedenadoptar: árboles, listas, redes, etc...

• Inconvenientes:– Alliasing: Doble direccionamiento sobre una

misma variable lo que implica efectos laterales.

– Gestión de la memoria: Su uso requiere unaespecial atención de la memoria disponible asícomo de la que ya no queramos utilizar.

CONCEPTOS BÁSICOS

• Un puntero es una variable que contienela dirección de memoria donde seencuentra almacenado un dato.

• Una variable referenciada o datoapuntado es el dato cuya posición enmemoria está contenida en un determinadopuntero (variable dinámica).

DATO

1365 20560123 4567

1365 2056

Dirección de memoria Memoria

puntero

Variablereferenciada

REPRESENTACIÓN GRÁFICA

DATO

VariablereferenciadaPuntero

DEFINICIÓN YDECLARACIÓN DE

PUNTEROS

• Para poder usar una variable puntero esnecesario:

– Definir el tipo de dato (o estructura) al que seapunta. (esta declaración se realiza dentro dela sección TYPE).

– Declarar las variables punteros que seannecesarias (esta declaración se realiza dentrode la sección VAR).

– En Pascal un puntero sólo puede señalara objetos de un mismo tipo, elestablecido en la declaración.

DIAGRAMA SINTÁCTICO

TIPO^

Ejemplo I:

TYPEtapunchar=^char;

VARapcar:=tapunchar;

Ejemplo II:

TYPEtApNodo=^tNodo;tNodo=record

info:.......Sig:tApNodo

end;VAR

ApNodo:=tApNodo;

ALGUNAS OBSERVACIONESAL RESPECTO

• Una variable de tipo puntero ocupa unacantidad de memoria fija, independientedel tipo de dato al que apunta.

• Un dato referenciado, como el del ejemplo,no posee existencia inicial, o lo que es lomismo no existe inicialmente espacioreservado en memoria para el.

LA NECESIDAD DE UTILIZARPUNTEROS

• Para poder emplear variables dinámicas esnecesario emplear un tipo de dato quepermita referenciar nuevas posiciones dememoria que no han sido declaradas apriori y que se van a crear y destruir entiempo de ejecución.

• Estas variables son los punteros que enPascal es un tipo de dato simple.

CREACIÓN Y DESTRUCCIÓNDE VARIABLES DINÁMICAS

• Las variables dinámicas son por definiciónaquellas que se crean cuando se necesitan yse destruyen cuando ya han cumplido consu cometido.

• En pascal la creación y destrucción devariables dinámicas se realiza mediante lossiguientes procedimientos:

– New(puntero)

– Dispose(puntero)

CREACIÓN DE UNAVARIABLE DINÁMICA

• New(puntero)

– Reserva la memoria necesaria para un dato deltipo apropiado.

– Coloca la dirección de memoria de esta nuevavariable en el puntero.

• Gráficamente esto se representa:

???????

DESTRUCCIÓN DE UNAVARIABLE DINÁMICA

• Dispose(puntero)

– Libera la memoria asociada a la variablereferida (dejándola libre para otros fines).

– Deja indefinido el valor del puntero.

• Gráficamente esto se representa:

?????????

OPERACIONES BÁSICAS CONVARIABLES

REFERENCIADAS

• El contenido de la variable referenciadapor el puntero se denota:

puntero^

• Las operaciones permitidas para esta nuevavariables son:

– Asignación– Lectura– Escritura– Todas las operaciones legales que se puedan

realizar con dicho tipo.

EJEMPLO I...........TYPE

tApcar=^char;VAR

Apcar:tApcar;

BEGIN.........New(Apcar);Readln(Apcar^); {Por ejemplo ‘B’}Apcar^:=Pred(Apcar^);Writeln(Apcar^);..........END.

‘A’

Apcar

Apcar^

EJEMPLO II...........TYPE

tApnum=^integer;VAR

Apnum1, Apnum2:tApnum;BEGIN.........New(Apnum1); New(Apnum2);Apnum1^:=2; Apnum2^:=4;Apnum2^:=Apnum1^+Apnum2^;Apnum1^:=Apnum2^ DIV 2;..........END.

3

Apnum1

6

Apnum2

EJEMPLO III

...........TYPE

tVector10=array[1..10] of real;tApnumero=^integer;tApvector=^tvector10;

VARApnum1, Apnum2: tApnum;Apvect: tApvector10;i: integer;

BEGIN.........

New(Apnum1); New(Apnum2); New(apvect);Apnum1^:=45; Apnum2^:=30;Apvect^[1]=2;for i:=2 to 10 do

Apvect^[i]:=Apvect^[i-1] * 2;..........END.

EJEMPLO III

• Dejando el estado de la memoria de lasiguiente forma:

3

Apnum1

6

Apnum2

2,0

Apvect

4,0 1024,0

OPERACIONES BÁSICAS CONPUNTEROS

• Las únicas operaciones válidas son:

– La comparación (se comparan las direcciones,no los contenidos de los datos apuntados).

Apnum1=Apnum2

– La asignación (se asignan las direcciones entresí, no los contenidos de los datos apuntados).

Apnum1:=Apnum2

LA COMPARACIÓN

• Apnum1=Apnum2

• La comparación anterior daría comoresultado el valor ‘false’ ya que cada unoapunta a una dirección de memoriadiferente.

3

Apnum1

3

Apnum2

LA ASIGNACIÓN

• Apnum1:=Apnum2

3

Apnum1

5

Apnum2

3

Apnum1

5

Apnum2

LA ASIGNACIÓN

• Los cambios efectuados sobre Apnum1afectan a la variable Apnum2 (sonindistintas) (Alliasing).

• El espacio de memoria reservadoinicialmente por el puntero Apnum1 siguesituado en memoria. Una adecuada gestiónde la memoria hubiera exigido laliberación de ese espacio antes de efectuarla asignación.

3

Apnum1

5

Apnum2

CONSISTENCIA ENTRE TIPOS

• Operaciones válidas

– Apnum1:=Apnum1– Apnum1=Apnum2– Apvector1:=Apvector2

• Operaciones no válidas:

– Apnum1:=Apchar;– Apnum1=Apvector;

EL VALOR NIL

• Un modo alternativo de asignar un valor aun puntero es indicar que no apunta aningún dato. Esto se lleva a cabo mediantela constante predefinida “nil”

• “nil” es independiente del tipo del datoapuntado por lo que puede ser utilizado porcualquier puntero.

– Apcar:=nil;– Apcar=nil;

• Representación gráfica:

APLICACIONES NORECURSIVAS CON

PUNTEROS

• Asignación de objetos no simples en unsolo paso

• Definición de funciones cuyo resultado noes simple

ASIGNACIÓN DE OBJETOSNO SIMPLES

• Esta aplicación es de utilidad cuando semanejan variables o estructuras de datos degran tamaño (por el elevado coste quesupone el realizar la copia de todas suscomponentes).

– Asignación de variables de gran tamaño

– Ordenación de vectores con elementos de grantamaño.

EJEMPLO IASIGNACIÓN DE VARIABLES DE GRAN

TAMAÑO

TYPEtFicha=record

nombre:string;direccion:string;..............

End; {tFicha}

VARpers1,pers2:tFicha;

BEGIN....................Pers1:=pers2; {operación muy costosa en

espacio y tiempo}....................

SOLUCIÓN AL EJEMPLO I

TYPEtApficha=^tFicha;tFicha=record

nombre:string;direccion:string;..............

End; {tFicha}

VARp1,p2:tApficha;

BEGIN....................p1:=p2; {asignación instantánea}....................

EJEMPLO IIORDENACIÓN DE VECTORES CONELEMENTOS DE GRAN TAMAÑO

TYPEtApFicha=^tFicha;tFicha=record

nombre:string;direccion:string;..............

End; {tFicha}{tListaAlumnos=Array[1..100] of tFicha;}tlistaApAlum=array[1..100] of tApFicha;.............

• Las operaciones de ordenación y búsquedase realizan sobre el array de punteros.

FUNCIONES DE RESULTADONO SIMPLE

• Como en el caso anterior se cambia elobjeto por el puntero que lo apunta.

• Ejemplo: Definir un subprograma que apartir de un punto del plano, un ángulo yuna distancia calcule la posición de unnuevo punto.

FUNCIONES DE RESULTADONO SIMPLE, EJEMPLO

........TYPE

tPunto=recordx,y:real;

end; {tPunto}tApPunto=^tPunto;

VARangulo,distancia:real;origen:tPunto;pDestino:tApPunto;

..........FUNCTION Destino(orig:tPunto;ang,dist:real):tApPuntoVAR

pPun:tApPunto;Begin

New(pPun);pPun^.x:=orig.x+dist*cos(ang);pPun^.y:=orig.y+dist*sen(ang):destino:=pPun;

End; {Destino}