7/25/2007

Memoria Dinámica en Pascal

La siguiente introducción a estructura dinámicas básicas está básada en los procedimientos estándar de la cátedra de mi facultad: Algoritmos y Estructuras de Datos de la Universidad Tecnológica Nacional de Buenos Aires, escritos por Sergio Fernando Abad.

Memoria Dinámica en Pascal

En teoría los programas PASCAL permiten utilizar 64KB de memoria estática.

Esto generalmente no es suficiente para aplicaciones reales, por eso pascal nos permite acceder a un sector de memoria que puede administrar el programador, tomando y liberando memoria arbitrariamente mientras las capacidades de la computadora en dónde ejecuta el programa lo permitan.

En memoria dinámica hay tres estructuras de datos principales que implementaremos en los ejemplos, a saber:

  • Listas
  • Pilas
  • Colas

Punteros

Hay un tipo de variable que nos permitirá construir las estructuras dinámicas. A esta variable se la conoce como Puntero, y es una variable de tipo estática pero con la particularidad de que su dominio de valores son las direcciones de memoria disponibles para el programador.

Esto significa que la variable tendrá como contenido una dirección de memoria (que puede ser la dirección dónde se encuentra, alguna otra variable, incluso la dirección dónde se encuentra otro puntero).

En PASCAL, declaramos los punteros con el símbolo ^ y una dirección de memoria a la cual lo hacemos apuntar. El tamaño que ocupa un puntero está dado por el tamaño necesario para almacenar una dirección de memoria, en muchas PCs hogareñas este valor suele ser 4 bytes.

    VAR PUNTERO:^INTEGER;
  

En el código anterior hemos declarado un puntero llamado PUNTERO que está apuntando a un tipo de dato entero, es decir que en él podemos almacenar valores de direcciones de memoria dónde se encuentren enteros.

Si bien el puntero está listo para guardar una dirección aún no lo hemos inicializado con ninguna dirección, el siguiente paso es reservar la memoria de un entero en el área de HEAP (dónde se aloca la memoria solicitada dinámicamente) y guardar la dirección de ese lugar en el puntero.

Para realizar esto utilizamos la instrucción NEW(), en caso de que la máquina no obtenga memoria para alocar el pedido, al puntero se le asignara la dirección NIL, cuyo significado es la "nada", es decir el puntero no apunta a ningún sector de la memoria.

Al terminar de utilizar la memoria a la cual accedíamos con el puntero, lo recomendable es siempre liberarla, para que quede disponible para otras aplicaciones que soliciten memoria.

Ahora bien, tiene sentido que uno quiera acceder al valor de lo que uno hasta el momento sólo conoce la dirección que almacena el puntero. Pascal nos permite referirnos al valor que se encuentra en la dirección de memoria de un puntero simplemente utilizando el nombre del puntero seguido inmediatamente por el símbolo ^.

    PUNTERO^ := 25;
    WRITELN( PUNTERO^ );
  

En las dos instrucciones anteriores hemos asignado al entero al cual apunta PUNTERO con 25, y luego hemos mostrado tal valor por pantalla.

Otro ejemplo, que muestra la diferencia entre el valor de un puntero y el valor que se haya en la dirección de memoria que guarda el puntero

    PROGRAM PUNTEROS_01;
    VAR
      PUNTERO:^INTEGER;
      AUXILIAR:^INTEGER;
    BEGIN
      NEW(PUNTERO);
      PUNTERO^:= 154;
      AUXILIAR:= PUNTERO;
      WRITELN( PUNTERO^ );
      WRITELN( AUXILIAR^ );
      DISPOSE(PUNTERO);
    END.
  

En el ejemplo anterior se ve el uso de las dos funcionalidades del puntero, cuando asignamos la dirección de memoria que contiene PUNTERO como valor, no utilizamos el símbolo ^, debido a que justamente estamos guardando la dirección en otro puntero llamado AUXILIAR. En cambio cuando queremos imprimir los valores de los enteros a los cuales apuntan (en este caso ambos apuntan a lo mismo) debemos utilizar el el símbolo ^.

NODOS

Un nodo es una pequeña estructura especialmente creada por el programador, para poder crear otras estructuras tales cómo Listas o Colas en memoria dinámica.

Los nodos guardan en una parte de la estructura la información que justamente requiere guardar nuestra aplicación o programa, en la otra parte tenemos un puntero que guarda la dirección de otro nodo.

Debido a que un nodo posee un puntero que permite almacenar una dirección de otro nodo, podemos valernos de él para enlazar múltiples nodos entre sí y hacer nuestras estructuras más complejas y alocarlas en memoria dinámica.

Ejemplo de definición:

    TYPE
      TipoLista =^ TipoNodo;
      TipoNodo = Record
        Info:TipoInfo;
        Siguiente:TipoLista
      END;
  

En la definición anterior en la primer instrucción declaramos un tipo de puntero llamado TipoLista que apunta a un registro TipoNodo, el cual aún no está definido hasta la siguiente línea, de hecho al momento de definir el tipo TipoNodo indicamos que la variable Siguiente es un puntero a un tipo de dato TipoLista. Esta forma de definición recursiva es totalmente legal y nos permite construir los nodos.

Listas

Llamamos Lista a una variable de tipo puntero que apunta a un nodo.

Ese nodo puede apuntar a otro nodo y este último a un próximo, por lo tanto podemos hablar de ciertas operaciones posibles en una Lista, como por ejemplo: insertar nodo al final, insertar al principio, insertar en el medio, buscar nodo, sacar del final, sacar del principio, etc.

Crear Lista

Ejemplo de procedimiento que crea una Lista:

PROCEDURE CrearLista (VAR Lista:TipoLista); BEGIN Lista := NIL END;

El código anterior recibe un puntero y lo inicializa en NIL.

Insertar primer Nodo

Ejemplo de procedimiento que inserta el primer nodo de una Lista:

    PROCEDURE InsertaPrimero (VAR Lista:TipoLista; Valor:TipoInfo);
    VAR
      Ptr:TipoLista;
    BEGIN
     New(Ptr);
     Ptr^.Info := Valor;
     Ptr^.Siguiente := NIL;
     Lista := Ptr;
    END;
  

El código anterior recibe la Lista en la cual vamos a insertar un primer nodo, y el valor de la información que contendrá este nodo. Dentro del procedimiento tenemos una variable local a él, que la reservamos con la instrucción New(Ptr), luego le asignamos el valor recibido como parámetro e indicamos que este primer nodo apunta a NIL, por último debemos apuntar la lista a este nodo recien creado.

Insertar adelante

Ejemplo de procedimiento inserta un nodo para que sea el primero de la lista:

    PROCEDURE InsertaAdelante (VAR Lista:TipoLista; Valor:TipoInfo);
    VAR
      Ptr:TipoLista;
    BEGIN
      New(Ptr);
      Ptr^.Info := Valor;
      Ptr^.Siguiente := Lista;
      Lista := Ptr;
    END;
  

Nuestro objetivo es insertar un nodo que sea el primero de la lista, para esto recibimos como parámetro la Lista en la cual queremos insertar el nodo y el valor que guardará como información el nodo. Creamos el nodo, guardamos la información recibida, y le decimos al nuevo nodo que apunte a dónde está apuntando actualmente la Lista, resguardada esta dirección podemos decirle a Lista que apunte al nuevo nodo, de esta manera el nodo queda insertado al principio de todo.

Insertar con Orden

Ejemplo de procedimiento que dada una Lista y un valor inserta un nodo dónde corresponda según el valor que se pase por paramétro:

    PROCEDURE InsertaEnOrden (VAR Lista:TipoLista ; Valor:TipoInfo);
    VAR
      Ptr, PtrAux : TipoLista;
    BEGIN
      New(Ptr);
      Ptr^.Info := Valor;
      Ptr^.Siguiente := NIL;
      PtrAux := Lista;
      WHILE ( PtrAux^.Siguiente <> NIL )  AND ( Valor > PtrAux^.Siguiente^.Info ) do
        PtrAux := PtrAux^.Siguiente;
      Ptr^.Siguiente := PtrAux^.Siguiente;
      PtrAux^.Siguiente := Ptr;
    END;
  

Este código es algo más complejo. Para empezar como siempre que se trate de una inserción debemos recibir el valor y la lista en dónde insertar. Luego creamos dos variables locales, Ptr y PtrAux, la primera es el nuevo nodo a insertar y la segunda será un auxiliar para recorrer la lista y encontrar la posición adecuada al nodo. Debido a que esta última variable sólo nos vale para encontrar la posición no hace falta que le reservemos memoria ya que le asignaremos direcciones de memoria ya reservada, en cambio para Ptr sí que debemos hacerlo porque justamente representa nuestro nuevo nodo. Por lo tanto guardamos el valor pasado por parámetro en este, y luego lo hacemos apuntar a NIL.

Para la búsqueda del lugar adecuado, asignamos a nuestro auxiliar al principio de la lista, y luego lo hacemos avanzar evaluando siempre que no estamos parados en el último nodo y que el Valor que queremos insertar es mayor que el Info del nodo siguiente al cual estamos apuntando. La manera de avanzar es bien sencilla y es obligar a PtrAux que apunte al nodo siguiente.

Al momento del salir del While indefectiblemente PrtAux estará apuntando al último nodo o bien a un nodo cuyo valor es el mayor de todos los valores menores al nuevo Valor. Es decir que estamos insertando al nuevo nodo ordenadamente de manera ascendente según el valor que trae y los valores de los nodos ya existentes en la lista.

Insertar Nodo

Recapitulando tenemos una serie de procedimientos que nos permiten insertar de diferente manera nodos en una Lista, ahora nos valeremos de todos ellos para crear un procedimiento Insertar Nodo genérico que según el valor dado inserte el nodo en la posición más conveniente:

    PROCEDURE InsertaNodo (VAR Lista:TipoLista; Valor:TipoInfo);
    BEGIN
     IF Lista = NIL THEN
       InsertarPrimero(Lista,Valor);
     ELSE
       IF Valor < Lista^.Info THEN
         InsertarAdelante(Lista,Valor);
       ELSE
         InsertaEnOrden(Lista,Valor);
    END;
  

El procedimiento InsertaNodo no utiliza variables locales, simplemente evalua a que procedimiento llamar para insertar el nuevo valor en la Lista pasada por parametro. Si la lista está vacía utiliza el procedimiento de insertar el primer nodo, si la lista ya contiene nodos entonces evalua sí el nodo debe ser ir adelante de todo o debemos meterlo por el medio. ¿Se te ocurre alguna manera de generalizar InsertaEnOrden para que pueda tratar con todas las situaciones? Me gustaría ver tu solución en los comentarios.

Suprimir Nodo

Mostramos ahora un procedimiento que suprime nodos de una Lista:

    PROCEDURE SuprimeNodo (VAR Lista:TipoLista ;  Valor:TipoInfo );
    VAR
      PtrAct , PtrAnt : TipoLista;
    BEGIN
      PtrAct := Lista;
      PtrAnt := NIL;
      WHILE ( PtrAct <> NIL ) AND ( Valor > PtrAct^.Info ) DO
      BEGIN
        PtrAnt := PtrAct;
        PtrAct := PtrAct^.Siguiente;
      END;
      IF ( PtrAct <> NIL ) AND ( Valor = PtrAct^.Info ) THEN
      BEGIN
 If PtrAnt <> NIL THEN
   PtrAnt^.Siguiente := PtrAct^.Siguiente
 ELSE
   Lista := PtrAct^.Siguiente;
 DISPOSE (PtrAct);
      END
    END;
  

Al procedimiento SuprimeNodo le pasamos la Lista de la cual queremos quitar un nodo y el Valor del nodo que queremos suprimir.

Como variables locales al procedimiento tenemos dos punteros auxiliares para realizar la operación de borrado. La idea es recorrer la lista con ellos, uno apuntando una posición más que el otro, cuando PtrAct se apunte a un nodo cuyo valor es menor que el del parámetro Valor detenemos la recorrida, si esto nunca sucede detendremos la recorrida al momento que PtrAct alcance el fin de la lista.

Al finalizar el WHILE debemos preguntarnos si el nodo al cual apunta PtrAct es realmente el nodo con el valor buscado, si realmente es así todavía tenemos que evaluar si PtrAnt se encuentra apuntando a NIL (el nodo a eliminar es el primero), o está apuntando a un valor distinto de NIL lo cual nos dice que éste nodo es el que debemos colgar de la dirección a la cual dejará de apuntar el nodo próximo a elminar (PtrAct).

Por último, si bien hemos quitado el nodo de la Lista, aún no hemos liberado la memoria que este ocupa, para esto utilizamos la instrucción antes mencionada, Dispose.

Pilas

La Pila es una Lista a la que sólo se le permite insetar y quitar nodos por el principio.

Con tal concepto y con los procedimientos escritos para la Lista no es díficil tomar un subconjunto de estos y crear la Pila y procedimientos para manipularla.

Crear Pila

  
    PROCEDURE CrearPila ( VAR Pila : TipoPila );
    BEGIN
      Pila := NIL;
    END
  

Nuevamente recibimos por referencia el nombre de la pila y la inicializamos en nil

Insertar PUSH

Este procedimiento es común encontrarlo escrito en su traducción en inglés Push:

    PROCEDURE Insertar ( VAR Pila:TipoPila ; Valor:TipoInfo);
    VAR
      Ptr:TipoPila;
    BEGIN
      New(Ptr);
      Ptr^.Info := Valor;
      Ptr^.Siguiente := Pila;
      Pila := Ptr;
    END;
  

En el código anterior, recibimos la Pila y un Valor, localmente con el puntero Ptr alocamos la memoria dinámica y asignamos el valor al nuevo nodo, a este lo hacemos apuntar al primer nodo al que apunta la Pila, y por último a la Pila la hacemos apuntar al nuevo puntero. De esta manera acabamos de insertar el nuevo nodo al principio de la pila.

Sacar POP

Nuevamente a este procedimiento se lo suele llamar Pop en muchos programas:

    PROCEDURE Pop ( VAR Pila:TipoPila ; VAR Valor:TipoInfo);
    VAR
      Ptr:TipoPila;
    BEGIN
      Ptr := Pila;
      Pila := Ptr^.Siguiente;
      Valor := Ptr^.Info;
      DISPOSE(Ptr);
    END;
  

Aquí agarramos con un puntero local al procedimiento al primer nodo de la pila y luego hacemos a apuntar a ésta última al siguiente nodo. Antes de liberar la memoria del nodo "sacado", asignamos su valor al parametro por referencia Valor, luego sí estamos en condiciones de liberarlo con DISPOSE.

Colas

Una Cola es otro tipo de lista que restringe las operaciones, la idea es insertar siempre al principio (tal como se inserta en una pila) y luego retirar del final.

Cuando retiramos un nodo de una Cola sabemos qué este es el nodo más antiguo (que entró hace más tiempo) de todos de los que están presente en la Cola al momento de retirar.

Para poder realizar estas operaciones debemos tener presente que hará falta tener dos punteros, uno apuntando al principio de la cola, y otro auxiliar apuntando al final de ésta.

Crear Cola

Aquí las cosas difieren un poco ya que aparecen los dos punteros de los que hablabamos para mantener la dirección del principio y del fin de la Cola.

    PROCEDURE CrearCola (VAR Cprin , Cfin : TipoCola );
    BEGIN
      Cprin := NIL;
      Cfin := NIL;
    END;
  

Insertar Nodo

Recordemos que esta operación está restringida a insertar al principio:

    PROCEDURE Insertar (VAR Cprin,Cfin:TipoCola; Valor:TipoInfo);
    VAR
      Ptr:TipoCola;
    BEGIN
      New(Ptr);
      Ptr^.Info := Valor;
      Ptr^.Siguiente := NIL;
      IF (Cprin = NIL) THEN
        Cprin := Ptr
      ELSE
        Cfin^.Siguiente := Ptr;
      Cfin := Ptr;
    END;
  

Recibimos el principio y el final de la cola y el valor para insertar el nuevo nodo. Alocamos la memoria del nuevo nodo, asignamos su valor y lo hacemos apuntar a NIL (recordemos que va a entrar al principio). Ahora evaluamos si la Cola está vacia, si esto sucede le asignamos este nuevo nodo a Cprin, en caso contrario lo el que debe apuntar a ese lugar es el nodo al cual actualmente apunta Cfin, en cualquier caso Cfin tiene que apuntar al nuevo nodo creado.

Sacar Nodo

Recordemos que ahora queremos sacar nodos desde el final:

    PROCEDURE Suprimir (VAR Cprin, Cfin:TipoCola ; Var:TipoInfo);
    VAR
     Ptr:TipoCola;
    BEGIN
      Ptr:=Cprin;
      Valor := Cprin^.Info;
      Cprin := Cprin^.Siguiente;
      If (Cprin = NIL) THEN
        CFin := NIL;
      DISPOSE(Ptr)
    END;
  

Antes de soltar al último nodo resguardamos su dirección en Ptr, posteriomente avanzamos en uno a Cprin y luego nos fijamos si la cola quedó vacia, en tal caso Cfin debe tomar la dirección NIL.

Cómo siempre liberamos la memoria que estaba ocupando el nodo quitado de la cola.

7 comentarios:

Writkas dijo...

Muchas gracias tu página me a servido de mucho.

Nacho Rigoni dijo...

Muy buena página!! Muy interesante y muy util!!

Aprovecho para preguntarte:

¿Cómo insertás secciones de código coloreadas? Porque quisiera hacerlo, pero no se cómo..

PD: yo tmb tengo un blog de programación..

Saludos!!!

Nacho.

Rodrigo dijo...

Muchas gracias, estoy estudiando y el tema de punteros está muy concreta y resumidamente explicado. Me sirvió de mucho. Saludos!

Anónimo dijo...

Muy pero muy bueno el resumen.
Me sirvio muchisimo para el parcial que tengo que rendir en unas horas.

Anónimo dijo...

ESTA EXPLICADO DE MANERA ABSTRACTA, COMPLEJA. ES COMO SI YO QUISIERA EXPLICARLES EL COMPORTAMIENTO DE UNA SUPERNOVA A PARTIR DEL USO DE LA SIMBOLOGÍA PURAMENTE EMPÍRICA. CREO QUE ASÍ COMO HACEN UN BLOG SOBRE EL COMPORTAMIENTO DE LAS LISTAS, COLAS, ETC, A PARTIR DEL USO DE PUNTEROS, PODRÍAN TENER UN APARTADO PARA LOS QUE NO ENTENDEMOS NADA DE PUNTEROS.

Anónimo dijo...

oye podrias explicar como mostrar el resultado de la cola

Anónimo dijo...

Muchas gracias. He estado más de una hora copiando en mi cuaderno lo de lista.