ALGORITMOS Y ESTRUCTURAS DE DATOS

CAPTULO 8

ESTRUCTURAS DINMICAS LINEALES

INTRODUCCIN
En captulos anteriores se han desarrollado las estructuras de datos estticas. stas permiten el manejo de un gran volumen de datos bajo un solo identificador, pero estn limitadas a la declaracin inicial en cuanto a su tamao. A partir de este captulo se comenzarn a estudiar las estructuras de datos dinmicas, comenzando por aquellas de organizacin lineal. Estas estructuras de datos permiten manejar en forma dinmica (de all su nombre) al conjunto de datos, por lo que no requieren la definicin del espacio de memoria al momento de programar. El uso dinmico de la memoria permite crear estructuras de datos que se adapten a las necesidades reales de los programas. Como veremos, estas estructuras de datos son muy flexibles, ya sea en cuanto al orden, la estructura interna o las relaciones entre los elementos que las componen. Para su construccin, se requiere el uso de apuntadores: un tipo de dato que permite almacenar la ubicacin de otro dato; una estructura de datos llamada registro: una coleccin de datos que constituyen un nuevo tipo de datos y la implementacin fsica de un tipo abstracto de datos. Estos elementos son necesarios para la implementacin de las estructuras dinmicas. En cuanto a la clasificacin de las estructuras de datos dinmicas, las hay lineales y no lineales. Esta clasificacin hace referencia al orden de acceso a los elementos que la constituyen. En este captulo, se tratarn exclusivamente las lineales pilas, colas y distintos tipos de listas. Comenzaremos por los conceptos de registro, tipo abstracto de datos y puntero, necesarios stos para la implementacin de cualquier estructura dinmica.

- 92 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

8.1 ESTRUCTURAS DINMICAS

Una limitacin que se presenta con las estructuras de datos estticas es la necesidad de conocer la cantidad de datos a procesar al momento de programar, para asignar el espacio de memoria. Esto rara vez sucede y adems, para distintas ejecuciones la cantidad de datos puede variar. Ante esta dificultad, las estructuras dinmicas no requieren la definicin del espacio de memoria, a stas se asigna el espacio durante la ejecucin del programa. Una estructura de datos es dinmica cuando la asignacin del espacio de memoria requerido se realiza durante la ejecucin del programa. Esto permite que la estructura ocupe ms o menos espacio de memoria de acuerdo a la necesidad de datos durante la ejecucin del programa. Existen diferencias claras respecto de los arreglos: - En la declaracin no se indica una cantidad mxima de elementos, puesto que esto vara durante la ejecucin del programa. - El conjunto de elementos que constituye la estructura, no necesita de un espacio contiguo de memoria. - No se utiliza un ndice para referenciar a los elementos, sino un puntero. - Existen limitaciones en cuanto al acceso a los datos: el acceso a los elementos de las estructuras dinmicas lineales es nicamente secuencial. Para la implementacin de estas estructuras es necesario conocer previamente algunos conceptos no vistos hasta el momento: registro (un tipo de datos definido por el programador), tipo abstracto de datos (una herramienta con la que se especifican datos y operaciones vlidas con ellos) y punteros (un tipo de datos especial que se utiliza para almacenar direcciones de memoria). Estos sern los temas a tratar previo a la construccin de estructuras de datos dinmicas.

8.2 LA ESTRUCTURA REGISTRO

Constituye uno de los tipos de datos estructurados ms utilizados. Permite agrupar datos de distintos tipos con cierta conexin lgica bajo una estructura nica. Por ejemplo, los datos correspondientes a un alumno pueden consistir de una matrcula, un nmero de documento, su nombre, su domicilio, su fecha de nacimiento, una direccin de correo electrnico y un promedio de notas. Esto puede involucrar datos de distintos tipos (cadenas de caracteres, nmeros enteros, nmeros reales). Este tipo de datos lo debe definir el programador segn las necesidades del algoritmo (de hecho, el registro es un tipo de datos definido por el programador). Definiremos Registro, como una estructura compuesta de un conjunto de valores con las siguientes caractersticas: - Los valores pueden ser de distintos tipos, es decir, es una estructura heterognea. - Los valores almacenados en un registro se llaman campos y cada uno tiene un identificador (un nombre, similar a una variable). - El espacio de memoria ocupado por un registro es fijo, esto lo convierte en una estructura esttica. En el apartado 3.2 (Partes de un programa) se vio que la primera parte est reservada para la declaracin de tipos de datos no estndares. El registro constituye un tipo de datos no estndar, por lo que deber declararse en este espacio.

8.2.1

DECLARACIN DE REGISTROS
Para la declaracin utilizaremos la palabra reservada tipo en nuestro pseudocdigo. La decla- 93 -

ALGORITMOS Y ESTRUCTURAS DE DATOS racin requiere un identificador (nombre para el tipo) y un cierre con la indicacin fintipo. Entre el encabezado de la declaracin y el cierre se declaran los campos que lo constituyen, cada uno como una declaracin de variables. Tomemos como ejemplo el dado para un tipo llamado alumno, mencionado anteriormente:
tipo alumno real matricula caracter documento[8] caracter nombre[20] caracter domicilio[25] caracter fecha_nac[10] caracter e_mail[25] real promedio fintipo

Una vez que se declar al nuevo tipo de datos, ste se agrega a los ya conocidos tipos simples estndar, por lo que la declaracin de una variable (llammosla alum) de tipo alumno, se har:
variables alumno alu

Podemos ver a esta estructura de la siguiente forma:

alu

Cuando sea necesario hacer referencia a un componente (campo) de la estructura alumno en la variable alu es necesario nombrar a la variable, y para hacer referencia al campo se usa un punto y el nombre del campo. Por ejemplo, para asignar datos de un alumno a la estructura haremos:
alu.matricula 94879 alu.documento 12345678 alu.nombre Juan Gomez alu.domicilio 9 de Julio 1245 alu.fecha_nac 10/12/1940 alu.e_mail [email protected] alu.promedio 8,75

Una vez que los datos se han almacenado, podemos imaginar que esta estructura puede verse as:
alu 94879 12345678 Juan Gomez 9 de Julio 1245 10/12/1940 [email protected] 8,75

Donde toda la estructura se almacena bajo el nombre alu. Cuando se quiere utilizar uno de los componentes se deber hacer referencia al nombre de la variable (alu) y al del campo correspondiente, como cuando se almacenaron los datos. Esta estructura no es un arreglo. Finalmente, la fecha de nacimiento de los alumnos, tambin pueden considerarse como estructuras compuestas por da, mes y ao. En este caso, declararemos primero la estructura fecha y luego la utilizaremos en la declaracin de la estructura alumno:
tipo fecha entero dia entero mes entero ao fintipo tipo alumno real matricula caracter documento[8]

- 94 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

caracter nombre[20] caracter domicilio[25] fecha fecha_nac caracter e_mail[25] real promedio fintipo

Obsrvese que es necesario declararlas en el orden indicado: primero el tipo fecha y luego el tipo alumno ya que la estructura fecha se utiliza en la estructura alumno.

8.3 TIPO ABSTRACTO DE DATOS

Una de las tareas de todo programador es la abstraccin de datos. Esto implica caracterizar objetos del mundo real de tal forma que puedan ser implementados en un programa. En la programacin estructurada, esta abstraccin se logra identificando atributos mensurables que pueden ser representados a travs de datos y atributos funcionales que caracterizan a su comportamiento. Un objeto del mundo real no puede ser representado por datos de tipo simple. Por ejemplo, el tipo alumno del ejemplo anterior requiere una estructura de datos. Pero la estructura declarada no es suficiente, tambin se debe programar las operaciones que un alumno real puede realizar, como ser matricularse, rendir exmenes, calcular su promedio. Es evidente que la estructura de datos y las operaciones programadas forman un conjunto. As, la representacin de un objeto del mundo real en un algoritmo requiere un tipo de datos definido por el programador ms la programacin de las operaciones que el objeto puede realizar. Este conjunto se denomina tipo abstracto de datos. Luego, un tipo abstracto de datos incluye: - La especificacin de la estructura de datos que representa a los elementos del tipo. - La especificacin de las operaciones permitidas sobre el tipo. - El tratamiento de ambos elementos como una unidad. Entonces, definimos tipo abstracto de datos como un conjunto conformado por un tipo de datos definido por el programador ms un conjunto de operaciones definidas sobre ese tipo que le otorgan una funcionalidad. Lo define el programador segn las necesidades del programa. No debe confundirse los conceptos de tipo de datos, tipo abstracto de datos y estructura de datos. Son tres conceptos distintos. Un tipo de datos es un conjunto de datos con caractersticas similares vinculados a un conjunto de operaciones para manipularlos que tienen una representacin interna en la mquina. Un tipo abstracto de datos es un modelo conceptual conformado por un tipo de datos definido por el programador ms un conjunto de operaciones definidas sobre ese tipo a travs de mdulos de cdigo. Una estructura de datos, es la implementacin fsica de un tipo abstracto de datos utilizando una coleccin de datos de tipo simple u otra estructura. Como puede deducirse, un tipo abstracto de datos constituye el resultado de una abstraccin del mundo real que debe implementarse con una estructura de datos. Puede decirse que es un concepto que debe ser implementado en su totalidad: los almacenes de datos y la funcionalidad requerida. Las pilas, colas, listas y los rboles constituyen tipos abstractos de datos que sern tratados a partir de este captulo. La mxima expresin de este concepto se encuentra en la programacin orientada a objetos. En ella los objetos del mundo real se modelan a travs de tipos abstractos de datos constituidos por atribu- 95 -

ALGORITMOS Y ESTRUCTURAS DE DATOS tos de los objetos reales (elementos de datos) y funciones que los manipulan (cdigo de control), encapsulados en unidades llamadas clases. Durante la ejecucin del programa, los objetos se generan dinmicamente en base a las clases.

8.4 PUNTEROS
Como los elementos de las estructuras dinmicas de datos no necesariamente se almacenan en forma contigua en la memoria, se necesita conocer su ubicacin. Esta ubicacin est dada por una direccin numrica especial en la memoria de la mquina. Las direcciones de memoria no estn constituidas por nmeros enteros ni reales, tienen un tratamiento especial (tema no contemplado en este material). Cada celda de memoria posee su propia direccin de memoria. As, almacenado un dato en la memoria, ste puede ser ubicado a travs de su direccin de memoria. De hecho, una variable es una representacin simblica de la ubicacin de memoria donde se guardan datos. La direccin de memoria a su vez, puede ser almacenada en una variable especial: un puntero. Un puntero es un tipo de variable, en la que se almacena la direccin de memoria de otra variable o el valor especial Null que indica que el puntero no tiene almacenado ninguna direccin vlida de memoria. Por ser una variable, debe ser declarado en el espacio de declaraciones de variables; pero a diferencia de stas, en su declaracin se antepondr una al nombre dado. Todo puntero contiene adems informacin sobre el tipo de datos al cual apunta, por lo tanto, se lo declara de un cierto tipo de datos. El puntero solo podr apuntar a datos del tipo indicado en su declaracin. La siguiente es una declaracin vlida para un puntero que apunta a datos de tipo entero: entero p Que indica la declaracin de un puntero de nombre p que podr apuntar a datos de tipo entero. Sin embargo, el puntero p no puede recibir datos, solo direcciones de memoria. Cmo se logra una direccin vlida de memoria para almacenar datos. Los lenguajes de programacin que soportan la asignacin dinmica de memoria proveen de una accin especfica para ello. En nuestro pseudocdigo, esta operacin se har con la palabra reservada nuevo, una funcin que requiere la indicacin del tipo de datos a almacenar y cuyo resultado es una direccin de memoria libre o el valor Null si no se encuentra: p nuevo(entero) El resultado de esta operacin es la asignacin al puntero p de una direccin de memoria libre en la que podr almacenarse nmeros enteros, o bien el valor Null que indica que no se encontr un espacio libre para datos. Grficamente, esta situacin se representa de la siguiente forma: p El esquema representa a un puntero p apuntando a un espacio de memoria asignado por la funcin nuevo en el que se podr almacenar los datos, estos ltimos deben ser del mismo tipo al indicado en la declaracin del puntero y en la solicitud de memoria (en el ejemplo el tipo es entero). Decimos que este espacio de memoria fue asignado dinmicamente durante la ejecucin del programa, mientras que el puntero ocupa un espacio esttico de memoria. Un puntero que no tiene asignado una direccin de memoria, no puede ser utilizado para almacenar datos.

- 96 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

8.4.1

OPERACIONES CON PUNTEROS

Supongamos las siguientes declaraciones de punteros: entero p, q

Es vlida la operacin de solicitud de memoria para datos de tipo entero y asignar la direccin de memoria devuelta a uno de ellos: p nuevo(entero) a partir de esta operacin, es vlida la siguiente: q p sta indica que tambin el punteo q apuntar al espacio de memoria asignado en la operacin anterior, podemos graficarlo de la siguiente manera: p q Es vlido tener varios punteros sealando al mismo dato. Otra accin vlida es asignar el valor Null a un puntero, sin embargo ser necesario que otro puntero posea almacenada la direccin de memoria asignada dinmicamente, caso contrario el dato almacenado se perder: q Null el resultado de esta operacin lo podemos graficar de la siguiente manera: p q donde p apunta al espacio de memoria asignado dinmicamente, mientras q no posee una direccin vlida de memoria (representada con la en el puntero), es decir, su valor es Null. No debe asignarse a ambos punteros el valor Null, ya que en ese caso se perder el espacio de memoria asignado dinmicamente. Pero NO ser vlida la siguiente accin: p 4 Para almacenar un dato en el espacio de memoria asignado dinmicamente, se deber utilizar el operador de direccionamiento: . Luego, para asignar un valor a la celda de memoria apuntada por p se deber escribir la siguiente accin: p 4 esto dar el siguiente resultado: p Finalmente, el espacio asignado dinmicamente con la funcin nuevo deber ser liberado antes de la finalizacin de la ejecucin del programa. La funcin nuevo, es una interaccin entre el programa que realiza la solicitud de espacio de memoria y el sistema operativo. El espacio de memoria asignado dinmicamente queda indicado en tablas del sistema operativo como espacio de memoria ocupado, por lo que antes de finalizar la ejecucin del programa que realiz la solicitud, ste deber liberarlo, as el sistema operativo lo sealar en sus tablas como espacio libre. Si el programa finaliza y el espacio asignado dinmicamente no se libera, el sistema operativo lo seguir registrando como espacio ocupado aunque ningn programa lo est usando: el resultado es espacio de memoria que no se puede utilizar. Para liberar el espacio de memoria asignado dinmicamente utilizaremos la accin liberar(puntero), una interaccin entre el programa que utiliza la asignacin dinmica y el sistema - 97 -

ALGORITMOS Y ESTRUCTURAS DE DATOS operativo, para que este ltimo actualice sus tablas indicando que el espacio de memoria sealado por el puntero se encuentra ahora disponible. La accin liberar(puntero), asigna al puntero el valor Null y se escribe: liberar(p) Si bien el puntero asume el valor Null despus de liberarse el espacio de memoria asignado dinmicamente, el resultado obtenido no es el mismo que se obtiene asignando este valor al puntero. En el primer caso, se libera el espacio de memoria dinmico y se asigna el valor Null al puntero, en el segundo caso solo se asigna el valor Null al puntero, pero el espacio de memoria asignado dinmicamente no se ha liberado (se pierde su direccin de memoria). Con lo que se ha desarrollado hasta el momento sobre el uso de punteros y asignacin dinmica de memoria, puede observarse que no se obtienen ventajas respecto del uso de variables estticas, ya que adems del espacio asignado dinmicamente para el dato es necesario un espacio para el puntero. Si necesitramos almacenar diez datos, sera necesario declarar diez punteros, ya que cada puntero puede almacenar a lo sumo una direccin de memoria y no se estara haciendo uso eficiente de esta. Como el puntero solo puede apuntar a un dato, se necesita un mecanismo capaz de crearlos dinmicamente junto al espacio para almacenar datos. Esto significa que, al solicitar espacio de memoria para almacenar datos, tambin se debe solicitar espacio para un nuevo puntero. De esta forma siempre habr un puntero libre al cual se podr asignar otra direccin de memoria. De todas formas ser necesario declarar al menos un puntero en forma esttica al cual asignar la direccin de memoria del primer bloque. Esto lo podemos representar de la siguiente forma: p donde la parte en gris junto a los datos representa a un puntero. De esta forma es posible solicitar otro espacio de memoria similar y asignar su direccin a este puntero, representado de la siguiente forma: p El puntero p apunta a un espacio de memoria compuesto por datos y un puntero, este ltimo tambin apunta a otra estructura similar. El ltimo puntero posee el valor Null, aqu representado con la indicando el final de la estructura. Obsrvese que enlazando de esta forma estructuras compuestas por datos y punteros obtenidos dinmicamente, la nica limitacin es el total de espacio de memoria disponible (espacio libre de memoria). El ltimo esquema representa a la estructura lista enlazada simple, una de las estructuras dinmicas lineales que estudiaremos en este captulo.

8.4.2

NODO

Para la construccin de las estructuras dinmicas, durante la ejecucin del programa es necesario solicitar espacios de memoria para datos y punteros, y enlazarlos como en el esquema anterior. Cada componente de la estructura completa es, a su vez, una estructura compuesta por un espacio para datos y uno o ms punteros. A los elementos componentes de las estructuras dinmicas los llamamos nodos. Entonces, definimos nodo a cada elemento de una estructura dinmica que se construye en base a una estructura de registro formada por campos de datos y uno o ms punteros. Estos elementos se generan dinmicamente durante la ejecucin del programa. p
puntero nodo

Para su creacin, ser necesario declarar un nuevo tipo de datos: un registro formado por datos (de cualquiera de los tipos conocidos) y al menos un puntero a otro nodo. Supongamos que se necesita una estructura para almacenar datos de alumnos tal como se ejemplific antes en este captulo en el apartado registros. Al tipo alumno se deber agregar un puntero (de tipo alumno): - 98 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

tipo fecha entero dia entero mes entero ao fintipo tipo alumno real matricula caracter documento[8] caracter nombre[20] caracter domicilio[25] fecha fecha_nac caracter e_mail[25] real promedio alumno sgte fintipo

Para almacenar datos de un alumno, se necesita un espacio de memoria de tipo alumno y para almacenar su direccin ser necesario un puntero (tambin de tipo alumno):
variables alumno alu

En el cuerpo principal del algoritmo, se solicita espacio de memoria para almacenar datos de un alumno. Si la solicitud de espacio de memoria no fall, ahora se puede almacenar datos en el nodo:
Inicio alu nuevo(alumno) si (alu <> Null) entonces leer(alumatricula) leer(aludocumento) leer(alunombre) leer(aludomicilio) leer(alufecha_nac.dia, alufecha_nac.mes, alufecha_nac.ao) leer(alue_mail) leer(alupromedio) alusgte Null finsi

liberar(alu) Fin

// contina el cdigo // esto cuando ya no se necesiten los datos del alumno y antes del fin // fin del algoritmo

Obsrvese la necesidad de utilizar el operador de direccionamiento , como tambin el . entre el nombre del campo fecha_nac y sus componentes da, mes y ao. Ahora poseemos los conocimientos necesarios de las herramientas bsicas para comenzar a estudiar las estructuras dinmicas lineales. En primer lugar, estudiaremos los TAD (tipos abstractos de datos) pila, cola y lista, para luego implementarlos con listas enlazadas simples.

8.4.3

COMPARACIONES ENTRE PUNTEROS

Supongamos las siguientes declaraciones de punteros: entero p, q

Es vlida la operacin de comparacin por igualdad (verifica si ambos punteros apuntan a la misma direccin de memoria) o por desigualdad (verifica si los punteros apuntan a distintas direcciones - 99 -

ALGORITMOS Y ESTRUCTURAS DE DATOS de memoria). Tambin es posible verificar si un puntero posee (o no) el valor Null. No es vlido otro tipo de comparacin (por ejemplo, no es vlido verificar si un puntero posee almacenado una direccin de memoria superior a otro, es decir, no es vlido la comparacin por mayor o menor). Entonces, solo son vlidas las siguientes comparaciones:
si (p = q) entonces // operaciones cuando p y q apuntan al mismo espacio de memoria finsi si (p <> q) entonces // operaciones cuando p y q no apuntan al mismo espacio de memoria finsi si (p = Null) entonces // operaciones cuando p no apunta a un espacio de memoria vlido

finsi

8.5 TAD PILA

La pila es una de las formas ms simples de organizar elementos en el mundo real. Por ejemplo, apilamos platos, libros, camisas. Constituye una superposicin de objetos en la que cada nuevo elemento se ubica sobre todos los anteriores y en todo momento es adems el primero que se puede recuperar. En la vida cotidiana decimos que el ltimo objeto que colocamos en la pila se encuentra en su tope, es el ltimo que se ubic all y el primero que retiramos. En informtica, este concepto se implementa a travs del TAD Pila y su aplicacin es muy amplia. Por ejemplo, en un programa los retornos desde los mdulos se realizan en el orden inverso al efectuado en los llamados, esto se logra apilando las direcciones de memoria de las lneas de cdigo que esperan continuar la ejecucin y desapilndolas cuando finaliza el mdulo (la implementacin de esta pila es tarea de los compiladores). Tambin el Sistema Operativo utiliza pilas durante la ejecucin de los programas. Si bien estos ejemplos no requieren la intervencin del programador, resultan tiles para resaltar su importancia. Definimos Tipo Abstracto de Datos Pila a una coleccin dinmica de elementos homogneos en la que el ltimo en entrar es el primero en salir. Por este motivo se las denomina LIFO, siglas en ingls de ltimo en entrar, primero en salir (Last In, First Out). Una pila es un TAD dinmico homogneo al que slo se tiene acceso al elemento que se encuentra en su tope. Sus operadores bsicos son apilar, desapilar y pila_vaca, aunque para este TAD, tambin se pueden definir otros operadores auxiliares. Las caractersticas del TAD Pila son: - Los elementos son del mismo tipo, esto la convierte en una estructura homognea. - Los elementos se recuperan en el orden inverso al que fueron almacenados. Por eso su forma de acceso se denomina LIFO (Last In, First Out). - La cantidad de elementos que contiene la pila puede variar a lo largo de la ejecucin del programa. Por esta razn, es una estructura dinmica. El TAD Pila puede ser implementado con arreglos o con listas enlazadas simples. En esta ctedra se utilizar la ltima opcin. Debido a esto, cada elemento que constituye la pila ser un nodo construido en base a una estructura de registro formada por datos (segn el caso particular del problema a resolver) y un puntero para enlazarlos.

- 100 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

8.5.1

EL CONCEPTO PILA
Para comprender el concepto se utilizar un ejemplo.

Supongamos que es necesario apilar paquetes de arroz en un almacn. Como estos paquetes tienen formas irregulares, es conveniente colocarlos previamente en cajas y apilar estas ltimas. El procedimiento a seguir lo podemos sintetizar con los siguientes pasos: - Buscar una caja vaca. - Llenar la caja con paquetes de arroz. - Cerrar la caja. - Apilarla. Estos pasos se repiten hasta que no queden paquetes de arroz o no se consiga una caja vaca. Cuando se necesitan paquetes de arroz, los pasos a seguir son: - Bajar la caja que se encuentra en el tope de la pila. - Abrirla y tomar los paquetes de arroz - Descartar la caja. Anlogamente, en la programacin las cajas estn representadas por nodos vacos y los paquetes a introducir en ellas por datos. Luego, los pasos a seguir en el proceso de pilas sern: - Solicitar espacio de memoria para un nodo nuevo. - Cargar datos en el nodo. - Asignar el valor Null al puntero incluido en el nodo. - Apilar el nodo. Estas operaciones slo podrn llevarse a cabo si la primera accin no fall, es decir, si hay espacio libre de memoria para albergar un nodo nuevo. Cuando se necesite procesar los datos que se encuentran en la pila, los pasos sern: - Desapilar el nodo que se encuentra en el tope de la pila. - Procesar sus datos. - Liberar el espacio de memoria, o introducir el nodo en otra estructura. Estas operaciones se podrn realizar mientras haya nodos apilados, cuando ya no los haya, diremos que la pila est vaca. Algortmicamente podemos imaginarnos a este TAD de la siguiente forma:

En el esquema, se observa una pila cuyo tope est sealado por el puntero Tp, y un nodo que no pertenece a ninguna estructura apuntado por p. Este ltimo puede ser apilado.

8.5.2

CREACIN DE PILAS

Los lenguajes de programacin no disponen de un tipo de datos simple para implementar el concepto de Pilas. Esta es la razn por la que es necesario programar el TAD Pila para implementarlo. - 101 -

ALGORITMOS Y ESTRUCTURAS DE DATOS Como lo implementaremos utilizando listas enlazadas, la creacin de Pilas implica la declaracin de un tipo de datos para los nodos y la posterior programacin de las operaciones apilar, desapilar y pila_vacia. Podemos decir entonces que en la pila se estarn almacenando nodos de un tipo declarado para tal fin. En la seccin 8.4.2 vimos un ejemplo de la creacin de nodos. Estos nodos constituyen las estructuras de datos de los elementos del TAD. Junto a las operaciones propias de un TAD, permitirn la construccin de estructuras de datos que respondan al concepto del TAD particular.

8.5.3

OPERADORES DEL TAD PILA

Como se mencion, cada tipo abstracto de datos requiere la definicin de las operaciones permitidas con l, esto se refiere a la necesidad de escribir el cdigo para implementarlas. Para el TAD Pila son tres los operadores bsicos: apilar (colocar un nodo en el tope de la pila), desapilar (sacar el nodo del tope de la pila) y vaca (para verificar si existen nodos apilados).

LA OPERACIN APILAR
La operacin apilar coloca nodos en el tope de una pila. Para ello, es necesario pasarle la direccin de memoria del nodo a apilar y la direccin del tope de pila sobre la que se apilar el nodo mencionado. Tomando el esquema anterior, la operacin apilar ubicar el nodo sealado por el puntero p sobre el actual tope de la pila apuntada por Tp.

Situacin antes de apilar el nodo sealado por p en la pila apuntada por Tp

Como resultado, el nodo apuntado por p se almacena en la pila siendo su nuevo tope (apuntado por Tp) y el puntero p queda en Null:

Resultado despus de apilar el nodo sealado por p en la pila apuntada por Tp

Ahora la pila se compone de cuatro nodos, y el puntero p puede utilizarse para otra operacin, ya que se encuentra libre. Apilar, puede ser implementado como una funcin o como un procedimiento. Recordemos que las variables que sern modificadas dentro del mdulo deben ser pasadas por referencia. Como son dos los valores a modificar por la operacin (el puntero al nodo y el puntero al tope de la pila), conviene implementarlo como procedimiento pasando los punteros por referencia. La sintaxis de su encabezado ser: - 102 -

ALGORITMOS Y ESTRUCTURAS DE DATOS procedimiento apilar(tipoPila ref nodo, tipoPila ref tope) Por lo que el llamado a apilar el nodo apuntado por p deber realizarse de la siguiente forma: apilar(p, Tp) Si lo implementamos como funcin, su encabezado ser: tipoPila funcion apilar(tipoPila ref nodo, tipoPila tope) Y el llamado a apilar se har de la siguiente forma: Tp apilar(p, Tp) Volviendo al ejemplo de alumnos presentado anteriormente, supngase que es necesario apilar los nodos para su posterior procesamiento. El algoritmo requiere un puntero para el tope de la pila: llamemos a este punteo TpAlu. Asumiendo que se ha declarado el tipo alumno como se vio anteriormente, el cdigo para apilar un nodo con datos de un alumno en la pila apuntada por TpAlu ser:
variables alumno alu, TpAlu Inicio alu nuevo(alumno) si (alu <> Null) entonces leer(alumatricula) leer(aludocumento) leer(alunombre) leer(aludomicilio) leer(alufecha_nac.dia, alufecha_nac.mes, alufecha_nac.ao) leer(alue_mail) leer(alupromedio) apilar(alu, TpAlu) finsi

Fin

// contina el cdigo // fin del algoritmo

Antes del final de la ejecucin de este algoritmo, es necesario liberar cada uno de los nodos de la pila (no incluido en el ejemplo an).

LA OPERACIN DESAPILAR
La operacin desapilar toma el nodo del tope de la pila, se lo pasa a un puntero auxiliar (en los esquemas es el puntero p) y actualiza el puntero que apunta al tope de la pila (representado por Tp). Como resultado, el nodo que se encuentra en el tope de la pila antes de ejecutarse esta operacin, ya no pertenecer a ella; pero no ser eliminado de la memoria de la mquina, estar sealado por el puntero auxiliar. Para esta operacin, es necesario que el puntero auxiliar previamente se encuentre en Null, ya que tomar la direccin del nodo desapilado. Tomemos el siguiente esquema previo a desapilar:

Estado previo a la ejecucin de desapilar

- 103 -

ALGORITMOS Y ESTRUCTURAS DE DATOS Despus de desapilar, el resultado ser:

Estado posterior a la ejecucin de desapilar

Ahora la pila se compone de dos nodos, y el puntero p seala al nodo desapilado. Obsrvese que el puntero que enlazaba al nodo desapilado con el siguiente nodo de la pila (componente interno del nodo) ya no apunta a este, su valor fue reemplazado por Null. Esto tambin debe realizar la operacin desapilar. Tambin desapilar puede ser implementado como una funcin o como un procedimiento. Nuevamente, como son dos los valores a ser modificados por esta operacin (el puntero al nodo y el puntero al tope de la pila), conviene implementarlo como procedimiento pasando los punteros por referencia. La sintaxis de su encabezado ser: procedimiento desapilar(tipoPila ref nodo, tipoPila ref tope) Por lo que al realizar el llamado para desapilar un nodo ser: desapilar(p, Tp) Si lo implementamos como funcin, su encabezado ser: tipoPila funcion desapilar(tipoPila ref tope) Y el llamado a desapilar se har de la siguiente forma: p desapilar(Tp) Tomando nuevamente el ejemplo de alumnos, supngase que se debe procesar los datos de uno de ellos. Ahora ser necesario desapilar el nodo que se encuentra en el tope de la pila. Con las declaraciones ya vistas, la operacin ser:
Inicio

// cdigo de creacin de la pila, presentado anteriormente si (not vacia(TpAlu)) entonces desapilar(alu, TpAlu) procesar(alu) // aqu se debe hacer algo con el nodo desapilado finsi
Fin // el cdigo contina // fin del algoritmo

Antes del final de la ejecucin de este algoritmo, es necesario liberar cada uno de los nodos de la pila (no incluido en el ejemplo an). Obsrvese que la operacin desapilar est condicionada a que la pila no se encuentre vaca, este control lo realizamos con la operacin vacia que se tratar a continuacin. Con respecto al nodo desapilado, hay una observacin que se debe realizar: despus de - 104 -

ALGORITMOS Y ESTRUCTURAS DE DATOS procesar sus datos, o bien se lo libera o bien se lo coloca en otra estructura basada en el mismo tipo.

LA VERIFICACIN DE PILA VACA

Obsrvese que es imposible desapilar nodos cuando la pila se encuentra vaca, por lo tanto, antes de ejecutar el procedimiento desapilar es necesario verificar si hay nodos apilados. Esto lo realiza la funcin vacia. Vacia, es una funcin que requiere como parmetro de entrada la indicacin del tope de la pila que se desea verificar, y devuelve verdadero o falso segn se encuentre o no vaca. Luego, la sintaxis de su encabezado es: logico funcion vacia(tipoPila Tp) Volviendo al ejemplo de la pila de alumnos: Antes de finalizar la ejecucin del algoritmo que la cre, es necesario destruirla. Destruirla significa liberar todos los nodos que la componen (uno a uno). Esto lo hacemos con un bucle hasta que no queden nodos en la pila:
variables alumno alu, TpAlu Inicio // cdigo de creacin de la pila, presentado anteriormente // aqu representa al proceso de los datos mientras (not vacia(TpAlu)) entonces desapilar(alu, TpAlu) liberar(alu) finmientras

Fin

// el cdigo continua // fin del algoritmo

El cdigo contenido en el bucle mientras, desapila y libera todos los nodos que componen la pila hasta que no haya ms nodos en ella.

8.6 TAD COLA

La cola es otra forma de organizar elementos en el mundo real. Por ejemplo: para poder acceder a los servicios de un cajero, primero se debe esperar a que ste atienda a todas las personas que llegaron previamente, es necesario esperar para ser atendido. La cola est constituida por un conjunto de objetos en la que cada nuevo elemento se ubica al final de los anteriores (constituyndose en el ltimo) y en todo momento solo el primero puede ser atendido. De esta manera, los objetos que constituyen la cola se atienden en el mismo orden en que fueron llegando. Es particularmente til en informtica, y su ejemplo ms visible es la impresin de documentos. Cuando se envan varios documentos a imprimir, se crea una cola de espera para ser atendidos segn el orden de envo. Tambin los procesos durante su ejecucin deben respetar colas. Definimos Tipo Abstracto de Datos Cola a una coleccin dinmica de elementos homogneos en la que el primero en entrar es el primero en ser atendido. Por este motivo se las denomina FIFO, siglas en ingls de primero en entrar, primero en salir (First In, First Out). Una cola es un TAD dinmico homogneo al que slo se tiene acceso a un elemento: el que se encuentra al principio de ella. Sus operadores bsicos son encolar, desencolar y cola_vaca, aunque (al igual que en Pilas), para este TAD tambin se pueden definir otros operadores auxiliares. - 105 -

ALGORITMOS Y ESTRUCTURAS DE DATOS Las caractersticas del TAD Cola son: - Los elementos son del mismo tipo, esto la convierte en una estructura homognea. - Los elementos solo se pueden recuperan en el orden en que fueron almacenados. Por eso su forma de acceso se denomina FIFO (First In, First Out). - La cantidad de elementos que contiene la cola puede variar a lo largo de la ejecucin del programa. Por esta razn, es una estructura dinmica. El TAD Cola puede ser implementado con arreglos o con listas enlazadas simples. Al igual que para el TAD Pilas se utilizar la ltima opcin.

8.6.1

EL CONCEPTO DE COLA
Para comprender el concepto se utilizar un ejemplo.

Supongamos que estamos en un supermercado haciendo compras. Para pagarlas, debemos esperar en la cola a ser atendidos. Bsicamente los pasos son: - Ubicarnos al final de una cola de espera correspondiente a una caja. - Esperar hasta que se desocupe el cajero. - Acceder a la caja a pagar los productos. - Retirarnos. Llevando este ejemplo a la informtica, los productos comprados seran los datos a procesar, el canasto que los contiene sera el nodo, la cola de espera de personas con productos estara representada por otros nodos conteniendo datos y el paso por caja para pagar sera el proceso a efectuar. Los pasos a seguir en el proceso de encolar nodos sern: - Solicitar espacio de memoria para un nodo nuevo. - Cargar datos en el nodo. - Asignar el valor Null al puntero incluido en el nodo. - Encolar al nodo. Al igual que en pilas, estas operaciones slo podrn llevarse a cabo si la primera accin no fall, es decir, si hay espacio libre de memoria para albergar un nodo nuevo. Cuando se necesite procesar los datos que se encuentran en la cola, los pasos sern: - Desencolar el nodo que se encuentra en la salida de la cola (prximo a ser atendido). - Procesar sus datos. - Liberar el espacio de memoria, o introducir el nodo en otra estructura. Algortmicamente podemos imaginarnos a este TAD de la siguiente forma:

Tres nodos en una cola de espera

Donde el puntero E (entrada, final o ltimo nodo de la cola) seala al ltimo nodo ingresado en la cola, y el puntero S (salida, inicio o primer nodo de la cola) el prximo a ser atendido. Como puede observarse, el TAD Cola requiere dos punteros para su implementacin, y al igual que en el caso de las pilas, para los nuevos nodos ser necesario un puntero auxiliar.

8.6.2

CREACIN DE COLAS

Los lenguajes de programacin tampoco disponen de un tipo de datos simple para implementar Colas. Por esta razn es necesario programar el TAD Cola e implementarlo sobre estructuras conocidas. - 106 -

ALGORITMOS Y ESTRUCTURAS DE DATOS Como lo implementaremos utilizando listas enlazadas, la creacin de Colas implica la declaracin de un tipo de datos para los nodos y la posterior programacin de las operaciones encolar, desencolar y cola_vacia. Como ejemplo, consideremos la cola de una caja en un supermercado. Para representarla podramos crear una estructura de datos para los nodos compuesta por la cantidad y la descripcin de los artculos comprados y el importe total a obtener en el proceso (por el cual se espera). La estructura de los nodos sera:
tipo carrito entero cantidad caracter descripcion[100] real importe carrito sgte fintipo

Esto implica que tambin en las colas se almacenan nodos de un tipo declarado para tal fin. Esto se realiza con punteros que debern ser declarados en el espacio de declaracin de variables. A continuacin se presentan las operaciones propias del TAD Cola que permitirn la construccin de estructuras de datos que respondan al concepto cola.

8.6.3

OPERADORES DEL TAD COLA

Las operaciones bsicas permitidas sobre el TAD Cola son tres: encolar (colocar un nuevo nodo al final de la cola), desencolar (sacar el nodo del inicio de la cola) y vaca (para verificar si existen nodos en la cola).

LA OPERACIN ENCOLAR
La operacin encolar ubica nuevos nodos al final de la cola de espera. Para ello, es necesario pasarle la direccin de memoria del nodo a encolar (puntero al nuevo nodo) y las direcciones de entrada y salida de la cola (punteros de entrada y de salida). Tomando el esquema anterior con tres nodos en la cola de espera, la operacin encolar consiste en ubicar un nuevo nodo (aqu sealado por el puntero p) al final de la cola (apuntada por E).

Estado previo a encolar el nodo sealado por p al final de la cola sealada por E

Como resultado, el nodo apuntado por p se almacena al final de la cola (apuntado por E) y el puntero p queda en Null:

Estado de la cola despus de encolar el nodo

Despus de ejecutarse la operacin encolar, la cola se compone de cuatro nodos, y el puntero p puede utilizarse para otra operacin, ya que se encuentra libre. Una vez ms, esta operacin se puede implementar como funcin o como procedimiento. Implementada como procedimiento, la sintaxis de su encabezado ser: procedimiento encolar(tipoCola ref nodo, tipoCola ref entrada, tipoCola ref salida) - 107 -

ALGORITMOS Y ESTRUCTURAS DE DATOS Por lo que el llamado a encolar el nodo apuntado por p a la entrada de la cola apuntada por E deber realizarse de la siguiente forma: encolar(p, E, S) Si lo implementamos como funcin, su encabezado ser: tipoCola funcion encolar(tipoCola ref nodo, tipoCola ref entrada, tipoCola salida) Y en este caso el llamado a encolar se har de la siguiente forma: E encolar(p, E, S) Siguiendo con el ejemplo de la cola de espera de la caja del supermercado, para encolar los carritos necesitaremos al menos tres punteros: uno para representar carritos nuevos (nodos nuevos): crr y dos para la propia cola: Entrada y Salida. El cdigo para encolar un nodo con datos de los artculos contenidos en un carrito ser:
variables carrito crr, Entrada, Salida Inicio

// lneas de cdigo previas a la creacin de un nodo

crr nuevo(carrito) si (crr <> Null) entonces leer(crrcantidad) leer(crrdescripcion) crrimporte 0

// el importe se obtiene cuando se atiende al carrito

encolar(crr, Entrada, Salida) finsi // contina el cdigo Fin // fin del algoritmo

LA OPERACIN DESENCOLAR
La operacin desencolar consiste en tomar el nodo que se encuentra a la salida de la cola (en el ejemplo sealado por el puntero de salida S), asignar su direccin a un puntero auxiliar que debe estar en Null (en el ejemplo es p) y eliminar el enlace entre este nodo y la cola. Internamente, ser necesario trabajar con los punteros de entrada y salida de la cola, todos parmetros necesarios en esta operacin. Tomando el esquema de tres nodos presentado anteriormente, el nico nodo que puede salir de la cola es el que se encuentra sealado por S:

Estado previo a desencolar el nodo sealado por S (inicio de la cola)

Como resultado de desencolar, el nodo que se encontraba apuntado por S estar sealado por el puntero auxiliar p:

Estado de la cola despus de desencolar el nodo

- 108 -

ALGORITMOS Y ESTRUCTURAS DE DATOS Despus de ejecutar la operacin desencolar, la cola se compone solo de dos nodos, y el puntero p seala al nodo desencolado. Una vez ms, esta operacin se puede implementar como funcin o como procedimiento. Implementada como procedimiento, la sintaxis de su encabezado ser: procedimiento desencolar(tipoCola ref nodo, tipoCola ref entrada, tipoCola ref salida) Por lo que el llamado a desencolar el nodo de la salida se deber realizar de la siguiente forma: desencolar(p, E, S) Si lo implementamos como funcin, su encabezado ser: tipoCola funcion desencolar(tipoCola ref entrada, tipoCola ref salida) Y en este caso el llamado a desencolar se har de la siguiente forma: p desencolar(E, S) Para desencolar un nodo de la cola de espera del ejemplo (la cola de la caja del supermercado) una opcin es:
variables carrito crr, Entrada, Salida Inicio

// cdigo de creacin de la cola, presentado anteriormente

si (not vacia(Salida)) entonces desencolar(crr, Salida, Entrada) procesar(crr)

finsi

// aqu se debe hacer algo con el nodo desencolar (podra ser liberarlo) // el cdigo continua // fin del algoritmo

Fin

En este ejemplo, procesar(crr) podra ser asignarle un importe a los artculos comprados (almacenados en el nodo) y acumular ese importe al total que la cajera deber rendir al final de su turno. Una vez que se realiz el proceso de los datos, el nodo podr ser liberado o bien se lo deber ubicar en otra estructura.

LA VERIFICACIN DE COLA VACA

Evidentemente es imposible desencolar nodos cuando la cola est vaca; por lo tanto, antes de ejecutar el procedimiento desencolar es necesario verificar si hay nodos en ella. Esto lo realiza la funcin vacia. Vacia, es una funcin que requiere como parmetro de entrada el puntero de salida de la cola que se desea verificar, y devuelve verdadero o falso segn esta se encuentre o no vaca. Luego, la sintaxis de su encabezado es: logico funcion vacia(tipoCola salida) Volviendo al ejemplo de la cola de carritos del supermercado: Antes de finalizar la ejecucin del algoritmo que la cre, es necesario procesar todos sus nodos y destruirla. Destruirla significa liberar todos sus nodos (uno a uno) hasta que quede vacia: - 109 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

variables carrito crr, Entrada, Salida Inicio // cdigo de creacin de la pila, presentado anteriormente // otras lneas de cdigo previas a la destruccin de la cola mientras (not vacia(Salida)) entonces desencolar(crr, Salida, Entrada) procesar(crr) liberar(crr) finmientras // el cdigo continua Fin // fin del algoritmo

El cdigo contenido en el bucle mientras, desencola, procesa y libera todos los nodos que componen la cola hasta que no haya ms nodos en ella antes de finalizar la ejecucin del programa.

8.7 TAD LISTA

La lista es otro TAD lineal. Se deriva del concepto de listas del mundo real, como por ejemplo una lista de alumnos. Se constituye de un conjunto de objetos vinculados de tal forma que cada uno posee un predecesor (excepto el primero) y un sucesor (excepto el ltimo). Considerando las operaciones que se pueden realizar sobre este TAD, resulta ser el ms verstil de los TAD lineales. Definimos Tipo Abstracto de Datos Lista a una coleccin dinmica de elementos homogneos con un orden lgico en ella, tal que cada elemento tiene un nico predecesor (excepto el primero) y un nico sucesor (excepto el ltimo). En informtica, este TAD se implementa a travs de la estructura dinmica lista enlazada, que se tratar ms adelante en este captulo. Las caractersticas del TAD Lista son: - Los elementos son del mismo tipo, esto la convierte en una estructura homognea. - Los elementos se recuperan a partir de uno que constituye el inicio de la lista. - La cantidad de elementos que contiene la lista puede variar a lo largo de la ejecucin del programa. Por esta razn, es una estructura dinmica. - Es de acceso secuencial, es decir, para acceder a un elemento es necesario acceder a todos los elementos previos. Las operaciones tpicas del TAD Lista son insertar un nuevo nodo, recorrer la lista para procesar sus datos, buscar un nodo que cumpla con un criterio dado, borrar un nodo de la lista y borrar la lista completamente; pero tambin se pueden definir otras operaciones adicionales de acuerdo a las necesidades del caso donde se la utiliza. Como el TAD Lista se implementa con listas enlazadas, sus operaciones sern desarrolladas conjuntamente con la estructura lista enlazada simple.

8.8 LISTAS ENLAZADAS

Las listas enlazadas son estructuras de datos dinmicas que se constituyen con nodos. Recordemos que un nodo es una estructura generada dinmicamente en base a un tipo registro definido por el programador que se constituye con dos o ms campos: un puntero de enlace y uno o ms campos de - 110 -

ALGORITMOS Y ESTRUCTURAS DE DATOS datos. La estructura del registro se crea para representar a un objeto del mundo real de acuerdo a la abstraccin que de ste se realice. Definimos entonces: Una Lista Enlazada es una estructura de datos dinmica lineal formada por un conjunto de elementos homogneos denominados nodos, donde estos no necesariamente ocupan posiciones contiguas en memoria, pero mantienen un orden lgico entre ellos. Cada elemento de la estructura posee un nico predecesor (excepto el primero) y un nico sucesor (excepto el ltimo). Decimos que el orden de los elementos que constituyen la lista (los nodos) es lgico puesto que est sealado por punteros que los enlazan. Al no ocupar necesariamente ubicaciones contiguas en memoria (es decir, sus componentes pueden aparecer fsicamente dispersos en la memoria), se necesita el uso de punteros para mantener la estructura. Posee las mismas caractersticas del TAD Lista, del cual deriva. Existen distintas implementaciones para esta estructura, la ms utilizada es la lista enlazada simple. Otras implementaciones son la lista doblemente enlazada, la lista circular y la lista circular doblemente enlazada. Como se ver ms adelante, los TAD Pilas y Colas se pueden implementar utilizando listas enlazadas simples, con restricciones en cuanto a las operaciones permitidas (solo se permiten las operaciones propias de cada TAD).

8.8.1

LISTAS ENLAZADAS SIMPLES

Las listas enlazadas simples constituyen un caso particular de listas enlazadas, donde cada nodo posee un nico puntero de enlace: un puntero al nodo sucesor. Definimos lista enlazada simple a una coleccin de nodos con un orden lgico dado por la posicin dentro de la estructura, tal que a cada uno de ellos se accede mediante el puntero de enlace del nodo anterior. Este concepto la hace una estructura de acceso secuencial unidireccional (solo se puede recorrer en un sentido, el indicado por los punteros de enlace). Como cada nodo posee un puntero al nodo siguiente, podemos graficar a esta estructura de la siguiente manera:

Una lista de datos con cuatro nodos

Donde el puntero L siempre debe estar indicando al primer nodo, y el sentido de recorrido est dado por los punteros. El ltimo nodo de la estructura almacena el valor Null en su puntero de enlace al nodo siguiente puesto que no lo posee, este valor Null indica adems el final de la lista. Para ejecutar las distintas operaciones sobre esta estructura, ser necesario utilizar punteros auxiliares.

8.8.2

IMPLEMENTACIN DEL TAD LISTA

Para la implementacin del TAD Lista utilizaremos listas enlazadas simples.

Como todo TAD, el TAD Lista requiere la especificacin de tipo de datos que represente a los elementos de datos que constituirn la lista. Esto nos lleva nuevamente a la creacin de un tipo de datos registro definido por el programador.

8.8.2.1 ESPECIFICACIN DE LOS DATOS

Tomemos como ejemplo simplemente una lista de nmeros (los algoritmos no difieren si se trata de otro objeto, como puede ser una lista de alumnos). Para crear una lista, es necesario crear una estructura de datos para los nodos: - 111 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

tipo numeros entero numero numeros sgte fintipo

Creadas las estructuras de datos para representar a los nmeros, a continuacin se crean las variables necesarias para la construccin y mantenimiento de la estructura de la lista de nmeros:
variables numeros num, aux, ant, L

Donde num ser utilizado como un puntero auxiliar para sealar nodos en la lista y L ser el puntero a su nodo inicial. Tanto aux como ant sern utilizados como auxiliares en los procesos. A continuacin se debern implementar los mdulos correspondientes a las operaciones propias del TAD Lista: insertar un nuevo nodo, recorrer la lista para procesar sus datos, buscar un nodo que cumpla con un criterio dado, borrar un nodo de la lista y borrar la lista completa.

8.8.2.2 DESARROLLO DE OPERADORES

Cabe aclarar una vez ms que los operadores que se desarrollarn a continuacin, no son los nicos que se pueden definir sobre el TAD Lista, como tampoco es nica su implementacin. En cada caso se desarrollar un solo algoritmo. Recuerde que todos los operadores se pueden implementar como procedimiento o como funcin segn resulte ms conveniente. Comenzaremos con el proceso de recorrido (acceder sucesivamente a todos los nodos de la lista para procesar sus datos).

LA OPERACIN RECORRER
Es la operacin ms simple sobre listas. Consiste en utilizar un puntero auxiliar que comienza apuntando al nodo cabecera de la lista y desde all, acceder secuencialmente a todos los dems para procesar los datos. Lo desarrollaremos como un procedimiento (tambin puede ser implementado como una funcin). El encabezado del procedimiento es:
procedimiento recorrer(tipoLista inicio)

El procedimiento recorrer necesita como parmetro la direccin del nodo cabecera (segn el algoritmo particular, pudiera requerir otros parmetros). Si se implementa como funcin, el valor de retorno depender de cada situacin particular.
tipoDato funcion recorrer(tipoLista inicio)

Para el ejemplo planteado e implementndola como procedimiento tenemos:

variables numeros num, L Inicio

recorrer(L)

Fin

// acciones previas a la insercin de nuevo nodo // llamado al procedimiento de recorrido // contina el cdigo // fin del algoritmo principal

procedimiento recorrer (numeros rc) inicio mientras (rc <> Null) procesar (rc) rc rcsgte // ac se procesa el nodo (o se llama a un procedimiento) // y se avanza al siguiente nodo

- 112 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

finmientras finprocedimiento

El procedimiento recorrer necesita como parmetro la direccin del nodo cabecera. Desde l, se procesa los datos del nodo y se avanza al siguiente hasta acceder a todos los que componen la lista.

LA OPERACIN BUSCAR
El nico mtodo de bsqueda sobre listas la bsqueda lineal. No se puede realizar bsqueda binario puesto que para aplicar este mtodo se necesita un medio de almacenamiento con direccionamiento directo a sus elementos. Con arreglos se tiene acceso a cualquier celda a travs del ndice. Sobre listas no se puede hallar el nodo central sin recorrer toda la estructura. Buscar podr ser implementado en una funcin o en un procedimiento segn convenga.
variables numeros num, L entero n Inicio

leer (n) buscar(n, L)

Fin

// // // //

acciones previas a la insercin de nuevo nodo se lee el dato a buscar llamado al procedimiento de bsqueda contina el cdigo

// fin del algoritmo principal

procedimiento buscar (entero dato, numeros rc) inicio mientras (rc <> Null) si (rcnumero = dato) procesar (rc) rc Null sino rc rcsgte finsi finmientras finprocedimiento entonces // ac se procesa el nodo o se llama a un procedimiento // se proces el nodo buscado, se puede salir del bucle // no es el nodo buscado, se avanza al siguiente

Como parmetros, buscar necesita el dato a buscar y la direccin de inicio de la lista.

LA OPERACIN INSERTAR
Insertar se implementar asumiendo que previamente se ha creado el nodo y almacenado datos en l. La operacin insertar tan solo har que este pase a pertenecer a la estructura. La sintaxis de su encabezado si se la implementa como un procedimiento ser:
procedimiento insertar(tipoLista ref nodo, tipoLista ref inicio)

Por lo que en el ejemplo, el llamado a insertar el nodo apuntado por num deber realizarse de la siguiente forma: insertar(num, L) Si lo implementamos como funcin, su encabezado ser:
tipoLista funcion insertar(tipoLista ref nodo, tipoLista inicio)

Y el llamado a insertar utilizando las variables del ejemplo de nmeros se har de la siguiente forma: - 113 -

ALGORITMOS Y ESTRUCTURAS DE DATOS L insertar(num, L) Para implementar la operacin, asumamos que la lista de nmeros debe estar ordenada ascendentemente por nmero. El mtodo de ordenamiento que se aplica sobre listas enlazadas es el ordenamiento por insercin directa. Esto significa que la lista ha de construirse ordenadamente (no ordenarla posteriormente), por lo que antes de insertar un nuevo nodo se deber realizar una bsqueda para hallar su ubicacin. Para esto es necesaria una funcin de bsqueda auxiliar que devuelva la direccin del nodo detrs del cual se deber insertar el nuevo (su anterior): buscarAnterior. Esto es necesario puesto que el puntero sgte de este nodo deber apuntar al nuevo. Veamos la siguiente situacin:

Nuevo nodo a insertar en la lista

Para poder insertar el nodo conteniendo el 12, es necesario posicionar un punteo sobre el nodo que posee el 10 (ser el anterior del nuevo nodo), ya que su puntero siguiente deber sealar al nuevo nodo (usaremos el puntero local auxiliar ant). Para la insercin, se deber reemplazar el valor Null del puntero siguiente del nuevo nodo por la direccin del nodo que almacena el 15 y en el siguiente del anterior la direccin del nuevo nodo. Esto lo podemos ver en el siguiente grfico, representado por punteros graficados en lneas punteadas.

Punteros a modificar para insertar el nuevo nodo en la lista

Luego, el procedimiento inserta necesita la direccin del nodo detrs del que se deber insertar el nuevo. Esta direccin se obtiene con la funcin buscarAterior. Asumiendo que se declararon los punteros como se vio en el pargrafo anterior,
Inicio

num nuevo(numeros) si (num <> Null) entonces leer(numnumero) numsgte Null insertar(num, L) finsi

// acciones previas a la insercin de nuevo nodo

Fin //

// contina el cdigo // fin del algoritmo principal En el procedimiento, L estar representado por ini y num por nv.

- 114 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

procedimiento insertar(numeros ref nv, numeros ref ini) numeros ant inicio ant buscarAnterior(nvnumero, ini) si (ant <> Null) entonces nvsgte antsgte antsgte nv sino nvsgte ini ini nv finsi nv Null finprocedimiento numeros funcion buscarAnterior (entero dato, numeros rc) numeros ant inicio ant Null mientras (rc <> Null) si (rcnumero > dato) entonces rc Null // encontr la ubicacin, se puede salir del bucle sino ant rc // se guarda la direccin del nodo actual rc rcsgte // y se verifica el siguiente finsi finmientras retornar(ant) finfuncion // se retorna la direccin del nodo anterior // // // // // el sgte del nuevo apunta al nodo del 12 el sgte del anterior apunta al nuevo nodo no hay anterior, se inserta nueva cabecera el sgte del nuevo apunta a la cabecera el nuevo nodo es la nueva cabecera de la lista

// hacemos que el puntero de nuevos nodos sea Null

La funcin buscarAnterior recibe como parmetros el nmero contenido en el nodo a insertar y la direccin del nodo cabecera. Realiza un recorrido sobre la lista con el puntero rc buscando la ubicacin donde se debe insertar el nuevo nodo, cuando la encuentra retorna la direccin del nodo anterior (almacenada en el puntero ant). Obsrvese las diferencias entre esta bsqueda y la presentada anteriormente: en esta, interesa la direccin del nodo anterior, en la que se present anteriormente interesaba hallar el nodo que contiene los datos a procesar. Despus de ejecutar el procedimiento insertar, el resultado es el siguiente:

Resultado de insertar el nuevo nodo en la lista

LA OPERACIN BORRAR NODO

Antes de eliminar un nodo de la lista es necesario redireccionar los punteros que la mantienen unida de forma tal que los dems nodos puedan ser recorridos. Si no se redireccionan correctamente estos punteros se pierde parte de la lista (situacin no deseada). - 115 -

ALGORITMOS Y ESTRUCTURAS DE DATOS Tomemos como ejemplo la siguiente lista ordenada de datos y digamos que se necesita buscar y sacar de ella el nodo que contiene el 15:

Lista que tomaremos como ejemplo

Para sacar este nodo de la lista tambin ser necesario trabajar con su anterior, puesto que se deber redireccionar el puntero siguiente de este nodo al siguiente del que se borrar. Una vez que se hizo esto, el nodo a borrar queda fuera de la lista y el espacio de memoria que ocupa puede ser liberado (o se lo puede insertar en otra estructura). De hecho, borrar un nodo de la lista implica previamente sacarlo de ella. Luego, nuevamente necesitamos un proceso auxiliar buscarAnterior, pero hay diferencias respecto de la funcin que se present anteriormente: en este caso se debe buscar el dato por igualdad y retornar dos direcciones: la direccin de su nodo anterior (o Null si es el nodo a borrar es el primero de la lista) y la direccin del nodo a borrar (o Null si no se encuentra). Obsrvese que son tres las situaciones que se pueden presentar: 1- el nodo buscado no se encuentra en la lista (nada para borrar), 2- el nodo buscado para borrar es el primero: se debe actualizar el puntero de inicio a la lista (no existe un anterior), 3- se est por borrar cualquier otro nodo (se debe actualizar el puntero siguiente del nodo anterior al que se borrar). Como hay dos valores de retorno, la bsqueda para borrar el nodo se implementar como un procedimiento al cual se pasan parmetros por referencia (los punteros ant que seala al nodo anterior y bor puntero que seala el nodo a borrar), adems del dato a buscar en la lista. Al iniciar el proceso de bsqueda del nodo a borrar y su anterior, el puntero que sealar al nodo a borrar (puntero bor) se debe posicionar apuntando al primer nodo y el que sealar al anterior (puntero ant) en Null:

Estado inicial del proceso de bsqueda

Despus de la bsqueda, la situacin es la siguiente: el puntero bor seala el nodo a borrar, y el puntero ant al anterior.

Punteros sealando los nodos que intervienen en el borrado

Se observa en el grfico un lazo desde el nodo apuntado por ant al siguiente del nodo que se ha de borrar. Este lazo se logra con la operacin antsgte borsgte
variables numeros num, L entero n

- 116 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

Inicio

leer (n) borrarNodo(n, L)

Fin

// // // // //

acciones previas al llamado a borrar se lee el dato a buscar en el nodo llamado al procedimiento de borrar el nodo con el dato n contina el cdigo fin del algoritmo principal

procedimiento borrarNodo(entero num, numeros ref ini) numeros ant, bor inicio bor ini buscarAnterior(num, bor, ant) si (bor <> Null) entonces si (ant = Null) entonces // el nodo a borrar no tiene anterior: es el primero ini inisgte // se borra primer nodo, hay una nueva cabecera borsgte Null // el nodo a borrar no pertenece ms a la lista sino // el nodo a borrar est entre otros nodos. antsgte borsgte // el sgte del anterior, pasa a ser el sgte del nodo a borrar borsgte Null // el nodo a borrar no pertenece ms a la lista finsi sino // no se encontr el nodo buscado (bor = Null) Escribir (El dato (nodo) buscado no est en la lista) finsi liberar(bor) finprocedimiento procedimiento buscarBorrar (entero dato, numeros ref rc, numeros ref ant) logico encontrado // variable lgica que se utilizar para salir del bucle inicio ant Null encontrado falso mientras ((rc <> Null) and (not encontrado)) si (rcnumero = dato) entonces encontrado verdadero // encontr el nodo, se puede salir del bucle sino ant rc // se guarda la direccin del nodo actual rc rcsgte // y se avanza al siguiente finsi finmientras // se sale del procedimiento: si el dato est, entonces rc indica su direccin // si no se encontr, rc y ant son Null finprocedimiento // liberamos el espacio de memoria del nodo // punteros locales

El nuevo lazo entre el nodo que contiene al 10 y el nodo que contiene al 20, es necesario para no perder parte de la estructura.

- 117 -

ALGORITMOS Y ESTRUCTURAS DE DATOS

LA OPERACIN BORRAR LA LISTA

Esta es una operacin que se debe ejecutar antes de finalizar la ejecucin del algoritmo. Consiste en eliminar toda la lista, es decir, todos sus nodos. Despus de ejecutar esta operacin, el puntero de inicio a la lista (puntero L) estar en Null, por lo que no podr realizarse ninguna operacin con l, excepto crearla nuevamente. El algoritmo ms simple para esta operacin es utilizar un puntero auxiliar que seale al primer nodo de la lista, hacer que el puntero al inicio seale el siguiente y poner el valor Null en el siguiente del sealado por el auxiliar:

Puntero auxiliar sealando el nodo a borrar

A continuacin se libera el espacio de memoria del nodo apuntado por el auxiliar. Estas operaciones se repetirn hasta que no haya nodos. Se implementar con una funcin a la que se pasa la direccin del primer nodo y se retorna el valor Null para almacenar en el puntero al inicio de la lista (puntero L), sealando que la lista est vaca.
variables numeros num, L Inicio

L borrarLista(L)

Fin

// // // //

acciones previas a la insercin de nuevo nodo llamado a la funcin para borrar la lista contina el cdigo fin del algoritmo principal

numeros funcion borrarLista (numeros ini) numeros aux, bor inicio mientras (ini <> Null) aux ini // ini inisgte // auxsgte Null // liberar (aux) // finmientras retornar(Null) finfuncion el puntero auxiliar seala el primer nodo el puntero de inicio pasa al siguiente nodo se desenlaza el primer nodo de la lista se libera el espacio de memoria ocupado por el nodo // punteros auxiliar

Existen otras operaciones sobre listas, como ser combinar dos listas, localizar ltimo nodo, etc.

8.8.3

IMPLEMENTACIN DEL TAD PILA

La implementacin de la pila utilizando listas enlazadas simples, requerir definir un formato para los nodos, es decir, definir un tipo registro compuesto por los datos a procesar y un puntero. Luego ser necesario declarar al menos dos punteros: uno para la manipulacin de nodos no apilados (que no forman parte de la pila) y el otro para indicar, en todo momento, el tope de la pila. Como ya se sabe, para la implementacin de las estructuras que responden a un Tipo Abstracto - 118 -

ALGORITMOS Y ESTRUCTURAS DE DATOS de Datos, se necesita crear una estructura para los nodos. Este tema ya fue tratado con anterioridad, cuando se desarroll el TAD Pilas. Solo resta la implementacin de las operaciones apilar, desapilar y vaca presentadas en su momento.

8.8.3.1 DESARROLLO DE OPERADORES

Como se vio anteriormente, son tres los operadores bsicos para la implementacin de Pilas:

LA OPERACIN APILAR
Como la implementacin de pilas se hace a travs de listas enlazadas simples, la operacin apilar consiste en un caso especial de insercin: el nuevo nodo siempre se inserta al inicio de la lista. De acuerdo a lo desarrollado anteriormente, apilar se implementar en un procedimiento cuyo encabezado es: procedimiento apilar(tipoPila ref nodo, tipoPila ref tope) En su desarrollo, simplemente se deber hacer que el puntero siguiente del nuevo nodo (el puntero al nodo nuevo es nv) seale al tope de la pila, que este nuevo nodo pase a ser el tope y finalmente asignar el valor Null al puntero del nuevo nodo:
procedimiento apilar(tipoPila ref nv, tipoPila ref tope) inicio nvsgte tope tope nv nv Null finprocedimiento // el nuevo nodo apunta al actual tope de la pila // el nuevo nodo pasa a ser el tope de la pila // el nuevo nodo ya no est sealado por el puntero auxiliar

LA OPERACIN DESAPILAR
La operacin desapilar consiste en sacar nicamente el nodo que se encuentra en la cabecera de la lista y sin liberar el espacio de memoria que este ocupa. De acuerdo a lo desarrollado anteriormente, se implementar el procedimiento desapilar, cuyo encabezado es: procedimiento desapilar(tipoPila ref nodo, tipoPila ref tope) Para su desarrollo, simplemente se deber hacer que el puntero auxiliar (en el desarrollo llamado ds) seale al tope de la pila, el tope apuntar al siguiente y finalmente asignar el valor Null al puntero siguiente del nodo desapilado (sealado por el puntero auxiliar ds):
procedimiento desapilar(tipoPila ref ds, tipoPila ref tope) inicio ds tope tope topesgte dssgte Null finprocedimiento // el puntero auxiliar seala al tope de la pila // el tope de la pila pasa a ser el siguiente nodo // el nodo desapilado no tiene siguiente

Observe que no es necesario verificar dentro del procedimiento si existen nodos apilados antes de desapilar, puesto que, como se vio anteriormente en el desarrollo del TAD Cola, esto se realiza antes del llamado a la funcin.

LA VERIFICACIN DE PILA VACIA

La operacin vacia consiste en verificar el tope de la pila (puntero a la cabecera de la lista). Si - 119 -

ALGORITMOS Y ESTRUCTURAS DE DATOS este puntero es Null (pila vaca) se devuelve verdadero; si apunta a un nodo (pila no vaca), se devuelve falso. Su encabezado es: logico funcion vacia(tipoPila Tp) Para el desarrollo de esta funcin se necesita una variable auxiliar de tipo lgica. Como esta funcin no modifica valores, el parmetro no se pasa por referencia:

logico funcion vacia(tipoPila Tp) logico vac // variable auxiliar que indicar si est o no vaca
inicio si (Tp = Null) entonces vac Verdadero // la pila est vaca: se devolver verdadero sino vac Falso // la pila no est vaca: se devolver falso finsi retornar(vac) finfuncion

8.8.4

IMPLEMENTACIN DEL TAD COLA

La implementacin de colas utilizando listas enlazadas simples tambin requiere definir un formato para los nodos, es decir, definir un tipo registro compuesto por los datos a procesar ms un puntero. Considerando que este tema ya fue desarrollado con anterioridad, simplemente se desarrollarn los algoritmos que implementan las operaciones encolar, desencolar y vaca. Recordemos que una cola necesita dos punteros: uno de entrada (ltimo nodo encolado) y uno a la salida (primer nodo de la cola). Los llamaremos E y S respectivamente.

8.8.4.1 DESARROLLO DE OPERADORES

Son tres los operadores bsicos para el procesamiento de colas:

LA OPERACIN ENCOLAR
La operacin encolar consiste en ubicar nuevos nodos al final de la cola de espera. Para ello, es necesario pasarle la direccin de memoria del nodo a encolar (puntero al nuevo nodo) y las direcciones de entrada y salida de la cola (punteros de entrada y de salida). Implementada como procedimiento, su encabezado es: procedimiento encolar(tipoCola ref nodo, tipoCola ref entrada, tipoCola ref salida) En el desarrollo del procedimiento encolar se deber hacer que el puntero siguiente del ltimo nodo de la cola apunte al nuevo nodo, que ste sea sealado como ltimo nodo y que el puntero al nuevo nodo sea Null. Como caso especial, cuando la cola est vaca tanto el puntero de entrada como el de salida deben sealar al nodo a encolar (por este motivo es necesario que el procedimiento reciba ambos punteros por referencia):

- 120 -

ALGORITMOS Y ESTRUCTURAS DE DATOS procedimiento encolar(tipoCola ref nv, tipoCola ref E, tipoCola ref S)
inicio si (E = Null) entonces S nv sino Esgte nv finsi E nv nv Null finprocedimiento // la cola est vaca, se inserta el primer nodo // el puntero de salida seala al nico nodo encolado // el nuevo nodo se ubica detrs del ltimo nodo de la cola // el nuevo nodo encolado pasa a ser el ltimo de la cola // el nodo pertenece a la cola, ya no est sealado por el // puntero auxiliar

LA OPERACIN DESENCOLAR
La operacin desencolar posee similitudes con desapilar: consiste en sacar nicamente el nodo que se encuentra en la cabecera de la lista sin liberar el espacio de memoria que este ocupa. Sin embargo, existe un caso especial no presente en Pilas: cuando la cola posee un nico nodo ste a su vez es tambin el ltimo; al desencolarlo, tambin se debe poner el valor Null en el puntero de entrada, no solamente en el puntero de salida. Por esta razn, se necesita pasar ambos punteros por referencia. De acuerdo a lo desarrollado anteriormente, desencolar se implementar como un procedimiento, cuyo encabezado es: procedimiento desencolar(tipoCola ref nodo, tipoCola ref entrada, tipoCola ref salida) Para su desarrollo, se deber hacer que el puntero auxiliar (en el desarrollo llamado ds) seale al primer nodo de la cola, el puntero de entrada seale al siguiente y asignar el valor Null al puntero siguiente del nodo desencolado (sealado por el puntero auxiliar ds). En el caso especial en que la cola posee un nico nodo, al desencolarlo tambin se asignar el valor Null al puntero de entrada (por esta razn es necesario pasar tanto el puntero de entrada como el de salida por referencia). procedimiento desencolar(tipoCola ref ds, tipoCola ref E, tipoCola ref S)
inicio ds S S Ssgte dssgte Null si (S = Null) entonces E Null finsi finprocedimiento // // // // // el puntero auxiliar apunta a la salida de la cola la nueva salida de la cola es el nodo siguiente el nodo desencolado no tiene siguiente se verifica si la cola qued vaca cola qued vaca: tambin el puntero de entrada es Null

LA VERIFICACIN DE COLA VACIA

Consiste en verificar si el puntero de salida seala un nodo o es Null. Si este puntero es Null significa que la cola est vaca y se devuelve verdadero; si apunta a un nodo (cola no vaca), se devuelve falso. Su encabezado es: logico funcion vacia(tipoCola salida) El desarrollo de esta funcin es muy similar al desarrollo de la verificacin de Pila vaca: - 121 -

ALGORITMOS Y ESTRUCTURAS DE DATOS logico funcion vacia(tipoCola S) logico vc // variable auxiliar que indicar si est o no vaca
inicio si (S = Null) entonces vc Verdadero sino vc Falso finsi retornar(vc) finfuncion

// la cola est vaca, se devolver verdadero // la cola no est vaca, se devolver falso

8.8.5

LISTAS CIRCULARES

Las listas enlazadas simples no permiten acceder directamente a cualquier nodo a partir de una posicin dada, siempre es necesario iniciar la bsqueda desde el primer nodo. En lugar de almacenar un puntero con el valor Null en el ltimo nodo, se hace que ste apunte al primero.

Lista circular

Presentan las siguientes ventajas respectos de listas enlazadas simples: - Cada nodo es accesible desde cualquier otro nodo. - No es necesario mantener un puntero sealando siempre a un nodo particular, debido a esto - No existe un primer nodo bien definido, ya que el puntero puede sealar cualquier nodo. - Se puede recorrer la estructura sin uso de punteros auxiliares. - La insercin ordenada no presenta casos especiales. Presenta el siguiente inconveniente: - Si no se cuida en el recorrido, se pueden producir bucles infinitos.

8.8.6

LISTAS DOBLEMENTE ENLAZADAS

Para todos los casos presentados anteriormente, solo es posible recorrer las estructuras en un sentido. Existen casos donde es conveniente recorrer la estructura en ambos sentidos. Para poder recorrerlas en ambos sentidos se necesita un puntero al nodo anterior. Estas listas son llamadas listas doblemente enlazadas. En la definicin del tipo de datos para estas listas, adems de los datos propios del caso, se debe incluir dos punteros: uno para sealar el nodo siguiente (al igual que en listas enlazadas simples) y uno para sealar al anterior. Los extremos almacenan el valor Null sealando que no existe un siguiente al ltimo nodo ni un anterior al primer nodo.

Lista doblemente enlazada

Presentan las siguientes ventajas respectos de listas enlazadas simples: - Cada nodo es accesible desde cualquier otro nodo. - 122 -

ALGORITMOS Y ESTRUCTURAS DE DATOS - No es necesario mantener un puntero sealando siempre a un nodo particular. - Se puede recorrer la estructura en ambos sentidos. Presenta el siguiente inconveniente: - Los algoritmos de insercin y borrado son ms largos. - Ocupan ms espacio de memoria (por el puntero adicional).

- 123 -