Capítulo 7

...
Estructuras De Datos Dinámicas

Hasta aquí hemos trabajado con estructuras y tipos de datos estáticos. Variables, arrays, todos ellos definidos en un momento anterior a la ejecución del algoritmo.

Los arrays (por ejemplo) son una colección de variables del mismo tipo asignadas en posiciones consecutivas de memoria. Pero la cantidad máxima de elementos que pueden contener debe fijarse previamente, al momento de definir el array en la sección type o var.

En este capítulo analizaremos tipos de datos dinámicos que nos permitirán alocar memoria dinamicamente para almacenar información a medida que en nuestro algoritmo lo vayamos necesitando.


Punteros y Alocación Dinámica de Memoria

En cualquier parte de nuestro programa podemos alocar memoria dinamicamente para almacenar datos de cualquier tipo: integer, real, string, registros, etc. Pero claro, para poder acceder a esa sección de memoria necesitaremos conocer su dirección. Así, entra en juego un nuevo tipo de datos: el puntero.

Un puntero es una variable capáz de contener una dirección de memoria. A través del puntero podemos acceder al espacio de memoria que este direcciona para asignar valores u operar con ellos.

Veamos un ejemplo:

testPtr.pas

   1:
   2:// la variable p es de tipo ^integer
   3:// Es decir: p es un puntero a integer
   4:var p: ^integer;
   5:begin
   6:   // aloca memoria para un integer y 
   7:   // asigna la direccion en p
   8:   new(p);
   9:   // asigna el valor 10 al contenido de p
  10:   p^:=10;
  11:
  12:   writeln('El contenido de p es: ',p^);
  13:end.
  14:

En el ejemplo definimos la variable p de tipo "^integer" (léase "sombrero integer"). Esto significa que p es una variable en la cual podemos asignar la dirección de memoria de un integer. O simplemente: p es un puntero a integer.

Para alocar la memoria necesaria para almacenar un número entero (2 bytes) utilizaremos la función de Pascal new. Esta función aloca memoria y le asigna al puntero que recibe como parámetro la dirección de la memoria alocada.

Por último, para asignar un valor en la memoria que acabamos de alocar (en este caso el valor 10) tenemos que hacerlo a través del puntero. p es el puntero y p^ (léase "p sombrero") hace referencia al espacio de memoria direccionado por p por lo tanto la asignación p^:=10 asigna el valor 10 al integer que alocamos dinamicamente.

Resumiendo:

• p - es un puntero, contiene una dirección de memoria.
• p^ - ("p sombrero") es la memoria direccionada por p.

El ejemplo anterior también podríamos haberlo escrito de la siguiente manera.

   1:
   2:type
   3:   // las variables de tipo PInteger
   4:   // seran punteros a integer
   5:   PInteger = ^integer;
   6:
   7:// la variable p es de tipo PInteger
   8:var p:PInteger;
   9:begin
  10:   // aloca memoria y asigna la direccion a p
  11:   new(p);
  12:   p^:=10;
  13:
  14:   writeln('El contenido de p es: ',p^);
  15:end.
  16:

La única diferencia es que en este caso definimos un nuevo tipo de datos (en la sección type):

type
...PInteger = ^integer;

Luego, la variable p de tipo PInteger también queda definida como un puntero a integer.

Por convensión utilizaremos el prefijo P para identificar tipos que definan punteros. PInteger, PString, etc.


Estructuras Dinámicas

Utilizando punteros podemos crear dinamicamente distintos tipos de colecciones de elementos. A cada elemento de la colección lo llamaremos nodo.

Un nodo es un registro (definido en la sección type) que contiene campos para almacenar información más un campo especial para almacenar la dirección de memoria del próximo nodo de la colección.

El gráfico muestra una lista (colección) de nodos. Una sección del nodo almacena información (info) y la otra un puntero (ptr) o referencia al siguiente nodo en la lista. También vemos un puntero p que apunta al primer nodo de la lista.

Analizaremos algunas de las diferentes estructuras dinámicas que podemos conformar a partir de enlazar nodos.

Cada estructura dinámica se compone de una colección de nodos relacionados entre si y de un conjunto de operaciones.


Lista Enlazada

Este es el caso más simple. Se trata de un conjunto de nodos donde cada nodo contiene la un puntero al próximo nodo de la lista.

Analizaremos una lista de enteros (integer).

El gráfico muestra que existe un puntero p que apunta al primer nodo de la lista. Cada nodo contiene un valor entero y una referencia al nodo siguiente. El último nodo tiene un valor nulo representado por una crúz. En Pascal el valor nulo se representa con NIL.

Las operaciones básicas que podemos aplicar sobre una lista son las siguientes:

• agregar - Agregar un nodo al final de la lista.
  
• insetarOrdenado - Agregar un nodo en la posición que corresponda para mantener la lista ordenada.
  
• buscar - Buscar el nodo que contenga un valor determinado.
• buscarEInsertarOrdenado - Idem. anterior pero si no existe ningún nodo con el valor que buscamos entonces crearlo e insertarlo ordenado.
  
• eliminar - Eliminar el nodo que contenga cierto valor.
  
• liberar - Eliminar toda la lista y liberar la memoria alocada.
  

Analizaremos la unidad (unit) untListas.pas en la que definiremos los tipos Nodo, PNodo y los prototipos e implementaciones de los procedimientos y funciones necesarios para trabajar con las listas.

untListas.pas

   1:
   2:unit untListas;
   3:
   4:interface
   5:
   6:type
   7:   // el tipo PNodo representa un puntero a Nodo
   8:   PNodo = ^Nodo;
   9:   Nodo = record
  10:      // campo para almacenar el valor entero
  11:      info:integer;
  12:      // referencia al siguiente nodo de la lista
  13:      sig:PNodo;
  14:   end;
  15:
  16:   // agrega un nodo con el valor especificado 
  17:   // al final de la lista, si la lista esta 
  18:   // vacia (lst=NIL) le asigna el primer nodo
  19:   procedure agregar(var lst:PNodo; valor:integer);
  20:
  21:   // inserta un nodo con el valor especificado
  22:   // manteniendo el orden ascendente de la lista
  23:   // retorna un puntero al nodo que inserto
  24:   function insertarOrdenado(var lst:PNodo
  25:                           ; valor:integer):PNodo;
  26:
  27:   // busca el valor especificado. Si existe entonces
  28:   // retorna un puntero al nodo que lo contiene y
  29:   // asigna true al parametro encontrado. Si no
  30:   // entonces inserta (ordenado) un nodo con el
  31:   // valor, asigna false al parametro encontrado
  32:   // y retorna un puntero al nodo insertado
  33:   function buscarEInsertarOrdenado(
  34:                     var lst:PNodo
  35:                   ; valor:integer
  36:                   ; var encontrado:boolean):PNodo;
  37:
  38:   // busca un valor en la lista. Si lo encuentra
  39:   // retorna un puntero al nodo que lo contiene,
  40:   // si no lo encuentra retorna NIL
  41:   function buscar(lst:PNodo; valor:integer):PNodo;
  42:
  43:   // elimina y libera el nodo que contenga 
  44:   // el valor especificado
  45:   procedure eliminar(var lst:PNodo; valor:integer);
  46:
  47:   // recorre la lista liberando todos los nodos
  48:   procedure liberar(var lst:PNodo);
  49:
  50:implementation
  51:// :
  52:// la seccion implementation se desarrolla
  53:// mas abajo...
  54:// :
  55:

Definimos el tipo Nodo con dos campos: info (para almacenar un valor entero) y sig para almacenar la dirección del próximo nodo de la lista.

A continuación analizaremos cada uno de los procedimientos y funciones descriptos en la sección interface de untListas.


procedure agregar(var lst:PNodo; valor:integer)

El objetivo de este procedimiento es agregar un nuevo nodo al final de la lista. Para esto debemos recorrer la lista hasta llegar al último nodo (identificado por tener NIL en su campo sig) y asignarle en el campo sig la dirección del nuevo.

Podemos distinguir un caso especial: ¿que pasa si la lista aún no existe (no tiene ningún elemento)? En este caso el valor del parámetro lst será NIL y entonces debemos asignar a lst la dirección del nuevo nodo. Por tal motivo recibimos el parámetro lst con var (por referencia).

Veamos el algoritmo:

Leyendo paso a paso el algoritmo vemos que se crea un nuevo nodo al principio. Como la consigna es agregar este nodo al final de la lista podemos asegurar que este nodo será el último. Por eso tendrá NIL en el campo sig. Luego preguntamos si el parámetro lst es NIL. Si esto es así estamos en el caso en que la lista está vacia. Aún no tiene elementos. Por lo tanto el nodo que recién creamos además de ser el último será el primero y (entonces) debe ser apuntado por el parámetro lst (este parámetro se recibe por referencia).

En el caso en que lst es distinto de NIL necesitamos recorrer la lista para llegar al último nodo. Para esto utilizamos una variable aux en la que asignamos el valor del primer nodo (lst) y luego dentro de un while le asignamos su próximo valor. Así, cuando su próximo valor sea NIL cortamos el ciclo iterativo y en aux tendremos un puntero al último nodo de forma tal que haciendo aux^.sig:=nuevo estaremos enlazando el nuevo nodo al final de la lista.

untListas.pas (implementación: procedure agregar)

   1:
   2:procedure agregar(var lst:PNodo; valor:integer);
   3:var nuevo, aux:PNodo;
   4:begin
   5:   // creo el nodo a insertar
   6:   new(nuevo);
   7:   nuevo^.info:=valor;
   8:   nuevo^.sig:=NIL; // va al final... sig=>NIL
   9:
  10:   // la lista no tiene elementos aun
  11:   if( lst=NIL ) then begin
  12:      // el nuevo nodo en realidad sera el primero
  13:      lst:=nuevo;
  14:   end else begin
  15:      // recorro la lista hasta llegar al final
  16:      aux:=lst;
  17:      while( aux^.sig<>NIL ) do begin
  18:         aux:=aux^.sig;
  19:      end;
  20:
  21:      // sale porque el siguiente de aux es NIL
  22:      // (aux es el ultimo) entonces enlazo el
  23:      // nuevo nodo como siguiente de aux
  24:      aux^.sig:=nuevo;
  25:   end;
  26:end;
  27:

function insertarOrdenado(var lst:PNodo; valor:integer):PNodo

Esta función debe insertar un nuevo nodo en la lista pero ordenado en forma ascendente. Retorna un puntero al nodo que insertó.

Debemos analizar los diferentes casos:

• que la lista no contenga elementos aún, entonces el nuevo nodo será el primer elemento.
• que el valor a insertar sea anterior al primer elemento de la lista
• que el valor a insertar deba ser insertado en el medio de la lista
• que el valor a insertar sea el último elemento de la lista
  

En este caso comenzaremos analizando el código Pascal y luego desarrollaremos el diagrama.

untListas.pas (implementación: function insertarOrdenado)

   1:
   2:function insertarOrdenado(var lst:PNodo
   3:                        ; valor:integer):PNodo;
   4:var aux,ant,nuevo: PNodo;
   5:begin
   6:   // creamos el nodo a insertar
   7:   new(nuevo);
   8:   nuevo^.info:=valor;
   9:
  10:   // ahora los casos posibles son:
  11:   //    1 - la lista esta vacia, lst es NIL
  12:   //    2 - el valor a insertar es anterior al 1ro.
  13:   //    3 - el valor a insertar es mayor que todos
  14:   //    4 - el valor a insertar va en el medio
  15:
  16:   // caso 1: la lista esta vacia, el nuevo es el 1ro.
  17:   if( lst = NIL ) then begin
  18:      // nuevo es el unico nodo... no tiene siguiente
  19:      nuevo^.sig:=NIL;
  20:      // asigno la direccion de nuevo a lst
  21:      lst:=nuevo;
  22:      // la funcion debe retorna el puntero 
  23:      // al nodo insertado
  24:      insertarOrdenado:=nuevo;
  25:
  26:      // finaliza la funcion aqui...
  27:      exit;
  28:   end;
  29:
  30:   // caso 2: el valor a insetar es menor que el 1ro.
  31:   if( valor < lst^.info ) then begin
  32:      // el nuevo sera el primero entonces
  33:      // el siguiente del nuevo debe ser lst 
  34:      // recordemos que lst hasta ahora es el 1ro...
  35:      nuevo^.sig:=lst;
  36:
  37:      // modifico lst para que el inicio de la lista
  38:      // ahora sea a partir del nuevo nodo
  39:      lst:=nuevo;
  40:
  41:      // la funcion retorna el putero al nodo
  42:      // insertado
  43:      insertarOrdenado:=nuevo;
  44:
  45:      // finaliza aqui 
  46:      exit;
  47:   end;
  48:
  49:   // si llegamos hasta este punto entonces solo
  50:   // existen dos posibilidades: los casos 3 y 4
  51:
  52:   aux:=lst;
  53:   ant:=NIL;
  54:
  55:   // recorro la lista mientras no encuentre un nodo 
  56:   // cuyo valor sea mayor y no se llegue al final
  57:   while((aux<>NIL) AND (aux^.info<=valor)) do begin
  58:      ant:=aux;
  59:      aux:=aux^.sig;
  60:   end;
  61:
  62:   // si aux es NIL entonces finalizo la lista y 
  63:   // ningun valor resulto mayor que el que tenemos 
  64:   // que insertar entonces agregamos al final
  65:   if( aux = NIL ) then begin
  66:      ant^.sig:=nuevo; // ant apunta al ultimo
  67:      nuevo^.sig:=NIL; // nuevo ahora es el ultimo
  68:   end else begin
  69:      // salio del while porque encontro un 
  70:      // valor mayor entonces insertamos el
  71:      // nodo entre el anterior y el mayor
  72:      ant^.sig:=nuevo;
  73:      nuevo^.sig:=aux;
  74:   end;
  75:
  76:   // la funcion retorna el valor del nuevo nodo
  77:   insertarOrdenado:=nuevo;
  78:end;
  79:

Analicemos los dos primeros casos. Si lst es NIL entonces la lista aún no existe y valor debe ser el elemento del primer nodo de la lista. Por lo tanto nuevo^.sig debe ser NIL y lst debe apuntar al nuevo nodo.

Notemos que luego de esto utilizamos la sentencia exit. Esta sentencia finaliza la llamada a la función por lo tanto el resto del código será ejecutado solo si el programa no cumplió con la condición anterior (lst = NIL).

Luego preguntamos si valor es menor que lst^.info. Si esto se cumple estamos ante el caso en el que el valor a insertar es anterior al primer elemento de la lista. Para enlazarlo correctamente asignamos nuevo^.sig:=lst y luego a lst (primer nodo de la lista) lo hacemos apuntar a nuevo. También utilizamos la sentencia exit para indicar que la función debe finalizar allí.

El resto de la función solo se ejecutará si no se verificó ninguna de las dos condiciones anteriores. Es decir: los dos primeros casos están descartados.

Sabiendo que la lista no es nula y que el valor a insertar no debe insertarse antes que el primero entonces vamos a recorrer la lista mientras todos los elementos sean menores o iguales a valor y (obviamente) mientras no lleguemos al último nodo.

Utilizamos una variable ant para guardar el nodo actual, antes de avanzar al siguiente nodo de la lista. Así, si al avanzar nos encontramos con NIL entonces en ant tendremos el puntero al último.

Cuando finalizamos el while preguntamos por cual de las dos condiciones finalizó. Si aux es NIL entonces llegó el último nodo y todos los nodos fueron menores o iguales al nodo a insertar. En este caso tenemos que agregar el nuevo nodo al final de la lista. Para esto asignamos a ant^.sig:=nuevo y (dado que nuevo será el último nodo) a nuevo^.sig:=NIL. Recordemos que ant apunta al último nodo, por lo tanto estamos enlazando el nuevo nodo al final de la lista.
Si aux es distinto de NIL entonces encontramos un nodo cuyo valor es mayor al valor que queremos insertar. Tenemos que insertarlo entre aux y el nodo anterior (ant). Esto lo hacemos asignando a ant^.sig:=nuevo y nuevo^.sig:=aux.


Para resolver esta función utilizamos la sentencia exit para descartar los posibles casos a medida que los vamos resolviendo. Esta metodología se llama "programación por descarte". Y es muy útil para este tipo de problemas.

Si no hubiéramos utilizado la sentencia exit tendríamos que utilizar if (ifes) anidados lo cual (para mi gusto) es demasiado engorroso.

Ahora si, veamos el diagrama.

function buscar(lst:PNodo; valor:integer):PNodo

Para buscar un elemento en la lista utilizaremos una función. La función buscar recibe el puntero al primer elemento de la lista (lst) y el valor a buscar. Recorre la lista y si encuentra un nodo cuyo campo info sea igual a valor entonces retorna el puntero a ese nodo. Si no (no se encuentra el valor en la lista) retorna NIL.

Simplemente iteramos mientras el elemento actual sea distinto de valor y mientras no lleguemos al final de la lista. Cuando finaliza el while tenemos el valor de retorno. Si el while finalizó porque aux^.info=valor entonces encontramos el nodo que buscábamos. Si el while finalizó porque aux=NIL entonces el valor que buscamos no se encuentra en la lista.

En cualquier caso, siempre aux será el valor que debemos devolver en la función.

untListas.pas (implementación: function buscar)

   1:
   2:function buscar(lst:PNodo; valor:integer):PNodo;
   3:var aux: PNodo;
   4:begin
   5:   aux:=lst;
   6:   while((aux<>NIL) AND (aux^.info<>valor)) do begin
   7:      aux:=aux^.sig;
   8:   end;
   9:
  10:   buscar:=aux;
  11:end;
  12:

procedure eliminar(var lst:PNodo; valor:integer)

Este procedimiento busca un valor en la lista apuntada por lst. Si lo encuentra lo elimina de la lista. Si el valor no existe en lista entonces no hace nada.

Recorremos la lista mientras no lleguemos al último nodo y mientras no encontremos el valor que estamos buscando. La variable aux apunta al nodo actual en la iteración y la variable ant apunta al nodo anterior.

Cuando corta el ciclo iterativo preguntamos si cortó porque encontramos el elemento que buscábamos, ya que si no lo encontramos no tenemos nada que hacer.

Si aux^.info es igual a valor encontramos el elemento y aux es el nodo que debemos eliminar, pero antes de hacerlo nos tenemos que asegurar de que dejaremos bien enlazada la lista.

Si ant es distinto de NIL significa que aux no es el primer nodo de la lista. Entonces tenemos que asignar a ant^.sig el valor de aux^.sig. Luego liberamos (con la función de Pascal dispose) el nodo aux.

Si ant es NIL entonces el valor que buscamos lo encontramos en el primer nodo. Es decir: tenemos que modificar el valor del parámetro lst para hacerlo apuntar al segundo nodo. Es decir: a aux^.sig. Por este motivo recibimos el parámetro lst por referencia. Luego si, liberamos aux.

untListas.pas (implementación: procedure eliminar)

   1:
   2:procedure eliminar(var lst:PNodo; valor:integer);
   3:var aux, ant: PNodo;
   4:begin
   5:   aux:=lst;
   6:   ant:=NIL;
   7:
   8:   // recorro mientras no llegue al final y
   9:   // mientras no encuentre el valor que busco
  10:   while((aux^.sig<>NIL) AND (aux^.info<>valor))
  11:   do begin
  12:      ant:=aux;
  13:      aux:=aux^.sig;
  14:   end;
  15:
  16:   // si salio porque se encontro el valor buscado
  17:   if( aux^.info=valor ) then begin
  18:      // el valor se encontro por el medio de la lista
  19:      if(ant<>NIL ) then begin
  20:         // el siguiente del anterior debe apuntar
  21:         // al siguiente del que vamos a eliminar
  22:         ant^.sig:=aux^.sig;
  23:      end else begin // el nodo a eliminar es el 1ro.
  24:         // el inicio de la lista debe apuntar al
  25:         // segundo nodo (el siguiente del primero)
  26:         lst:=aux^.sig;
  27:      end;
  28:
  29:      // liberamos el nodo 
  30:      dispose(aux);
  31:   end;
  32:end;
  33:

procedure liberar(var lst:PNodo)

El objetivo de este procedimiento es liberar todos los nodos de la lista enlazada. Simplemente recorremos la lista y liberamos el nodo actual (apuntado por aux).

La única precaución que debemos tener es guardar en alguna variable temporal la dirección del próximo nodo antes de liberar el nodo actual porque una vez liberado no tendremos forma de acceder al siguiente. Para esto usamos la variable auxSig.

El código es el siguiente:

untListas.pas (implementación: procedure liberar)

   1:
   2:procedure liberar(var lst:PNodo);
   3:var auxSig,aux: PNodo;
   4:begin
   5:   // recorremos la lista
   6:   aux:=lst;
   7:   while( aux<>NIL ) do begin
   8:      // guardamos el siguiente
   9:      auxSig:=aux^.sig;
  10:
  11:      // liberamos el actual
  12:      dispose(aux);
  13:
  14:      // avanzamos al siguiente
  15:      aux:=auxSig;
  16:   end;
  17:end;
  18:

Utilizar Listas para Indexar Archivos

Así como estudiamos la implementación del índice de un archivo sobre arrays, si el archivo no está acotado (no sabemos cuantos registros puede llegar a tener) podemos utilizar una lista enlazada para implementar su índice.

Consideraremos el mismo tipo de registro (REmpleado) que utilizamos en el capítulo de archivos y analizaremos un programa que recorre el archivo, lo indexa y luego permite al usuario consultar el archivo por el campo legajo.

   1:
   2:type
   3:   // tipo de registro del archivo
   4:   REmpleado = record
   5:      legajo: integer;
   6:      nombre: string[20];
   7:   end;
   8: 
   9:   // tipo de archivo
  10:   FEmpleado = file of REmpleado;
  11: 
  12:   // puntero a nodo indice
  13:   PNodoIdx = ^NodoIdx;
  14: 
  15:   // nodo indice
  16:   NodoIdx = record
  17:      legajo: integer;
  18:      pos: integer; // no habra mas de 32767 registros
  19:      sig: PNodoIdx;
  20:   end;
  21:

El programa principal abre el archivo y lo indexa llamando al procedimiento indexarEmpleados. Luego simplemente pide legajos al usuario, los busca invocando a la función buscar, (y si la función no retornó un valor negativo) posiciona el puntero en el archivo, lee el registro y muestra los resultados. Por último libera la lista con el procedimiento liberar.

El procedimiento indexarEmpleados recibe el puntero al inicio de la lista y el archivo (abierto). Lo recorre hasta el eof e insertaOrdenado en la lista.

Las modificaciones respecto de las funciónes estudiadas más arriba son de tipo de datos. Para resolver este problema utilizamos punteros de tipo PNodoIdx y los valores a buscar e insertar los consideramos de tipo REmpleado.

Algoritmos y Estructuras de Datos UTN - UBA.