Monday, January 09, 2006

Listas ordenadas

Listas ordenadas
Las listas ordenadas son aquellas en las que la posición de cada elemento depende de su contenido. Por ejemplo, podemos tener una lista enlazada que contenga el nombre y apellidos de un alumno y queremos que los elementos -los alumnos- estén en la lista en orden alfabético.
La creación de una lista ordenada es igual que antes:
struct lista *L;
L = NULL;
Cuando haya que insertar un nuevo elemento en la lista ordenada hay que hacerlo en el lugar que le corresponda, y esto depende del orden y de la clave escogidos. Este proceso se realiza en tres pasos:1.- Localizar el lugar correspondiente al elemento a insertar. Se utilizan dos punteros: anterior y actual, que garanticen la correcta posición de cada enlace.2.- Reservar memoria para él (puede hacerse como primer paso). Se usa un puntero auxiliar (nuevo) para reservar memoria.3.- Enlazarlo. Esta es la parte más complicada, porque hay que considerar la diferencia de insertar al principio, no importa si la lista está vacía, o insertar en otra posición. Se utilizan los tres punteros antes definidos para actualizar los enlaces.
A continuación se expone un programa que realiza la inserción de un elemento en una lista ordenada. Suponemos claves de tipo entero ordenadas ascendentemente.

No comments: