IPT7punteros

7.1. Objetivos
Las estructuras estáticas no pueden cambiar su tamaño durante la ejecución del programa
??Cambiar la disposición de los elementos dentro de la estructura estática es costoso.
Ejemplo: las posiciones de los elementos dentro de un array (no podemos redimensionar el array).
??En tiempo de diseño no sabemos exactamente cuánta memoria necesitamos ni cómo se va a organizar
??Solución: definir y organizar esa memoria en tiempo de ejecución ==> utilización de estructuras de memoria dinámica
??La gestión de memoria dinámica se realiza a través de los punteros
Memoria dinámica: memoria en la que se puede reservar espacio en tiempo de ejecución
??Estructuras de memoria dinámica: colección de elementos (denominados nodos de la estructura) que están enlazados entre sí.
??Variables Dinámicas: Posiciones de memoria reservadas en tiempo de ejecución
??Def.: Es una variable que sirve para indicar cual es
la posición de memoria de otra variable.
??Semántica:
Declara un tipo de datos (Identificador) que es un puntero a otro tipo de datos (Tipo)

7.2. Punteros
7.2.1. Operaciones con punteros
New: procedimiento por el que se reserva un espacio de memoria dinámica
??Sintáxis: new (Variable_puntero);
??Semántica: reserva un espacio de memoria y la variable puntero que se pasa como parámetro se deja apuntando a dicho espacio
Dispose: procedimiento por el que se libera memoria dinámica
??Sintáxis dispose (Variable_puntero);
??Semántica: Libera el espacio de memoria apuntado por la variable puntero que se pasa como parámetro
Acceso a los datos: operador ^ (circunflejo) (también llamado operador de desreferencia)
A partir del operador ^ la referencia se trata según el tipo de datos al que hace referencia el puntero
No siempre es obligatorio reservar memoria para utilizar un puntero
??Obtención de la dirección de memoria de una variable: operador @ (referencia)
NIL (Puntero nulo) es una constante de tipo puntero
??Un puntero NIL, indica que no apunta a ninguna posición de memoria
??Cuidado con las posiciones que se dejan de apuntar, podemos perder memoria si no las liberamos antes
Sólo permite las operaciones de asignación (:=) y comparación con los operadores relacionales (= y <>)
??Los operandos han de ser punteros a variables del mismo tipo o NIL
Procedimientos y Funciones
??Pueden ser parámetros, por valor y por
referencia, de los subprogramas.
??Se pueden devolver como resultado de una
función.
??Aunque f sea una función que devuelva un
puntero a un registro, no se permite:
f(parámetros reales)^.nombre; X
varPuntero := f(parámetros reales); V

7.2.2. Observaciones
??Declarar una variable de tipo puntero no siempre es suficiente para poder utilizarla
??Para crear información dinámicamente se debe llamar al procedimiento new
??Después de llamar a new, el valor al que apunta el puntero es indefinido. Para definirlo es necesario asignarle un valor.

??Variable_puntero ? Variable_puntero^
??Es muy conveniente liberar el espacio de memoria mediante dispose cuando no se vaya a utilizar más un puntero
7.3 Listas Enlazadas
Una lista está formada por una colección de elementos llamados

nodos tales que cada uno de ellos almacena dos valores:
??El elemento de la lista: todos son del mismo tipo de dato (también llamado campo de información)
??Un puntero que indica la posición del nodo que contiene el siguiente elemento de la lista
??El enlace se realiza a través del puntero asociado a cada nodo.
??Es necesario tener la referencia del nodo que contiene el primer elemento de la lista.
??La lista enlazada es una estructura recursiva.
7.3.1. Listas enlazadas simples
??Estructura dinámica más sencilla: solo tiene un enlace.
??Un nodo se representa mediante un registro con dos campos: uno para los datos y el otro es un puntero a otro nodo.
TYPE
tDato =String[25] {tipo de los elementos de la
lista}
tLista=^tNodoLista;
tNodoLista=RECORD
nombre:tDato;
sig:tLista {Estructura Recursiva}
END;
VAR
paux, aux, primer, anterior,lista:tLista;
Crear una lista vacía:
lista := NIL;
??Comprobar si una lista está vacía:
IF (lista = NIL) THEN
{lista vacía}
ELSE
{hay uno o más elementos} (Ejemplos 10a, 10b)
??Fin de una lista:
IF (lista.sig = NIL) THEN
{último elemento de la lista}
7.3.2. Listas doblemente enlazadas
Mantiene enlaces en ambas direcciones
??Necesita dos punteros:
??Ant: apunta al nodo anterior
??Sig: apunta al nodo siguiente
??Desventaja: Operaciones como inserción y borrado son más complejas (necesita más punteros auxiliares)
Ventaja: acciones como ordenar una lista u obtener una lista inversa son fáciles de realizar.
7.4 Otras estructuras dinámicas
Pilas: Es una lista particularizada al caso en el cual sólo se insertan y eliminan elementos por uno de los extremos: Lista LIFO (LastInFirstOut)
??Colas: Es una lista particularizada al caso en el cual se insertan los elementos por un extremo y se eliminan por el otro: Lista FIFO (FirstInFirstOut)
7.5 Observaciones estructuras dinámicas
??El concepto de lista puede implementarse de forma estática (array parcialmente lleno)
??La lista dinámica tiene desventajas frente al array: complejidad de acceso O(n) frente a O(1)
??Hay que tener especial cuidado de no perder el puntero que apunta a la cabeza de la lista, perderíamos toda la lista si no la tenemos apuntada por un auxiliar.
??Cuando borramos elementos de una lista no nos debemos olvidar de liberar el nodo que borramos (no basta con puentearlo)