REGISTROS Y PILAS

REGISTRO

Es interesante poder manejar una especie de arrays heterogéneos en los que sus elementos puedan ser de tipos diferentes. Llamaremos registro a una estructura de datos, formada por yuxtaposición de elementos que contienen información relativa a un mismo ente. A los elementos que componen el registro los llamamos campos, cada uno de los cuales es de un determinado tipo, simple o estructurado. Los campos dentro del registro aparecen en un orden determinado y se identifican por un nombre. Para definir el registro es necesario especificar el nombre y tipo de cada campo. Por ejemplo consideremos un registro, referido a Empleado, que está constituido por tres campos: Nombre (cadena), Edad(entero) y Porcentaje de impuestos (real).

Nombre Edad Porcentaje de impuestos

Las operaciones básicas que se ejecutan con los registros son: asignación del registro completo a una variable de tipo registro, (definida con sus mismos campos) y selección de un campo, que se realiza especificando el nombre del campo. Puesto

que esta estructura, esta especialmente ligada a las transferencias con los periféricos de almacenamiento, volveremos sobre ella cuando nos refiramos a los archivos.

LISTAS ENLAZADAS

Estas listas están formadas por un conjunto de nodos, en los que cada elemento contiene un puntero con la posición o dirección del siguiente elemento de la lista, es decir su enlace. Se dice entonces, que los elementos de una lista están enlazados por medio de los campos enlaces. Cada nodo está constituido por dos partes: información o campos de datos (uno o varios) y un puntero (con la dirección del nodo siguiente). Al campo o campos de datos del nodo lo designaremos como INFORMACIÓN del nodo y al puntero por SIGUIENTE del nodo. Con esta organización de los datos, es evidente que no es necesario que los elementos de la lista estén almacenados en posiciones físicas adyacentes para estar relacionados entre sí, ya que el puntero indica unívocamente la posición del dato siguiente en la lista.

Una forma alternativa de ver las listas enlazadas, es considerarlas como una estructura que contienen un dato dado como la cabeza, y el resto como la cola. La notación usual es la siguiente:(A | B), donde la lista tiene el elemento A en la cabeza y el elemento B como cola. Recursivamente, (A| (B |(C D ) ) ) es la lista con el elemento A en la cabeza, mientras que la cola está forma por una lista con el elemento B en la cabeza y una lista que contiene los elementos C y D en la cola,

etc. Nótese que para tener definida una lista enlazada, además de la estructura de cada uno de sus nodos, necesitamos una variable externa a la propia lista, con un puntero que marque la posición de la cabeza (inicio, primero) de la lista. Esta variable es quien normalmente da nombre a la lista, pues nos dice donde localizarla, sea cual sea su tamaño. Para detectar el último elemento de la lista se emplea un puntero nulo, que por convenio, se suele representar de diversas formas: por un enlace con la palabra reservada nil (NULO), por una barra inclinada (/) o por un signo especial, tomado de la toma de tierra en electricidad. Una lista enlazada sin ningún elemento se llama lista vacía y las distinguiremos asignando a su puntero de cabecera el valor nil.

LISTA

La implementación de una lista enlazada, depende del lenguaje de programación, ya que no todos soportan el puntero como tipo de datos; afortunadamente los más modernos como C, Pascal, etc., si lo hacen, por lo que en lo que sigue vamos a asumir el uso de punteros para su manejo. La alternativa, al uso de punteros, es recurrir a vectores paralelos en los que se almacenan los datos correspondientes a INFORMACION y SIGUIENTE, con una variable que apunte al índice que contiene la cabeza de la lista, de forma que nos podemos imaginar el siguiente esquema de equivalencia, entre ambas estructuras físicas:

Una vez definida la estructura de sus nodos, cosa que dejamos aparte, pues dependerá de cada lenguaje de programación, crear una lista consiste en llenar un primer nodo con la información correspondiente a un elemento y cuyo campo de enlace sea NULO. Además hay que definir la variable con el puntero externo que debe contener la dirección de este nodo inicial. Fijarse que ello supone que el lenguaje de programación que utilicemos debe tener una función que nos de la posición de memoria en la que se ha almacenado este nodo. A partir de este nodo inicial la lista empieza a modificarse, creciendo y disminuyendo, insertando y borrando nodos.

Recorrido

...