Las listas son unas estructuras de datos formadas por variables dinámicas, es decir, formada por una serie de objetos que se van reando durante la ejecución del programa.

A la hora de declarar una lista, esta no tiene necesariamente que estar ordenada.

Usaremos una variable dirección para guardar el primer elemento y acceder al resto de la lista. Este es un elemento imprescindible. Normalmente lo llamaremos top o cabecera.

Ejercicio 6, pág. 175

* Supongamos que tenemos la siguiente estructura de información.

tipo

nodo=registro

(inf:entero;

seg:apuntador)

fintipo

var

q,r,s:Apuntador;

T:nodo;

finvar

A partir del estado inicial de la figura aplicar cada una de las siguientes operaciones y dibujar la configuración resultante:

q r s

1 2 3 4 5

a) q «-- seg(q) (ó q:=q^.sig) :

q r s

1 2 3 4 5

b) q:=t

Primero deberemos observar si el tipo de las dos variables es compatible. La asignación es incorrecta ya que q es un apuntador, mientras que T es de tipo nodo.

c) q^.siguiente:=q^.sig^.sig

Las variables son del mismo tipo, la asignación es correcta.

q r s

1 2 3 4 5 nil

e) q:=r^.sig

r s q

1 2 3 4 5 nil

Como ejemplo, no es correcta la asignación q:=s^.sig^.sig, ya que este valor no está declarado.

g) s^.sig:=s (1)

T:=q; (2)

q^:=s^; (3)

s^:=T; (4)

(1) `s' se apuntará a él mismo:

q r s

1 2 3 4 5

(2) Supongamos T como un nodo cualquiera:

q r s

1 2 3 4 5

(T) 2

(3) El nodo q^ será igual que el nodo s^.

q r s

1 5 3 4 5

(4)

q r s

1 5 3 4 2

(T) 2

Instrucciones para el manejo de la memoria en las listas dinámicas

Para crear un espacio en memoria:

New(p): Devuelve un espacio en memoria cuya dirección es p. Esta instrucción dará errores si no disponemos de espacio en memoria.

Para dejar un espacio de memoria libre:

Dispose(p): Con esta orden realizaremos un borrado lógico , es decir, eliminamos las direcciones que dan acceso a ese nodo.

Algoritmo para crear una lista lineal

La idea es la de crear nodos de manera que cada uno apunte al siguiente. Para ello deberemos tener un nodo que será el primero de la lista y que en este caso llamaremos top.

type

nodo = record

(info:integer;

sig:^nodo);

end

var

q, p, top:^nodo

Inicio

new(top);

top^.info:=`dato'; {donde dato será un entero}

top^.sig:=nil; {dado que, por ahora, top es el último elemento, top^.sig debe

apuntar a NIL}

q:=top;

while existan elementos* do

inicio

new(p);

p^.info:=`dato';

p^.sig:=NIL; {ya que es el último nodo de la lista}

q^.sig:=p;

q:=p;

fin

* Iremos recorriendo todos los elementos que queramos insertar en la lista, como datos entrados por el usuario, datos de un fichero, etc.